题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Kupno gruntu

Bajtazar 计划购买一块矩形工业用地，预算要求如下：

1. 土地价格（矩形内所有单位方块价格总和）需在 $[k, 2k]$ 范围内（$k$ 为其财产，可贷款最多 $k$，总预算上限 $2k$）；
2. 土地为 $n \times n$ 网格中的矩形，由完整单位方块组成，坐标满足 $x_1 \leq x \leq x_2$ 且 $y_1 \leq y \leq y_2$（$(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角）。

需找到任意一块符合条件的矩形，若不存在则输出 NIE。

输入格式

1. 第一行：两个整数 $k$ 和 $n$（$1 \leq k \leq 10^9$，$1 \leq n \leq 2000$），分别表示财产金额和网格边长；
2. 接下来 $n$ 行：每行 $n$ 个非负整数，第 $j+1$ 行第 $i$ 个整数表示坐标 $(i,j)$ 的单位方块价格（坐标 $x$ 从左到右 1~n，$y$ 从上到下 1~n）。

输出格式

• 若存在符合条件的矩形：输出一行四个整数 $x_1, y_1, x_2, y_2$，表示矩形的左上角和右下角坐标；
• 若不存在：输出 NIE。

样例 1

输入

4 3
1 1 1  
1 9 1 
1 1 1  

输出

NIE

样例 2

输入

8 4
1 2 1 3  
25 1 2 1  
4 20 3 3  
3 30 12 2  

输出

2 1 4 2