题目描述

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

Bajtazar 计划购买一块工业用地。他的财产估值为 $k$ 拜塔拉尔（bajtalar），他也打算将这笔钱用于购买土地。然而，找到一块价格恰好为 $k$ 拜塔拉尔的土地颇为困难。因此，Bajtazar 愿意考虑购买价格更高的土地，并通过贷款获取额外资金。拜托克信贷银行能提供给他的最大贷款金额等于他的财产价值，即 $k$ 拜塔拉尔。换句话说，Bajtazar 希望购买价格在 $k$ 拜塔拉尔到 $2k$ 拜塔拉尔（含）之间的土地。

Bajtazar 打算购买土地的区域是一个边长为 $n$ 米的正方形。土地的当前所有者为每平方米设定了不同的价格。Bajtazar 进行了详细调查，制作了该区域的价格地图。该地图描述了每个一米乘一米的方块的价格。这样的方块总共有 $n^{2}$ 个。现在需要确定理想的土地。这块土地必须是矩形，且只能由完整的单位方块组成。Bajtazar 开始在地图上寻找合适的土地，但尽管努力，他仍未能找到合适的矩形。请帮助 Bajtazar 解决这个问题。

编写一个程序，完成以下功能：

• 从标准输入读取数字 $k$ 和 $n$ 以及土地的价格地图，
• 确定一块价格在 $[k, 2k]$ 范围内的土地，或者判定这样的土地不存在，
• 将结果输出到标准输出。

输入格式

输入数据的第一行包含两个整数 $k$ 和 $n$，用单个空格分隔，$1 \leq k \leq 10^9$，$1 \leq n \leq 2000$。

接下来的 $n$ 行，每行包含 $n$ 个非负整数，用单个空格分隔。第 $j+1$ 行的第 $i$ 个数字表示坐标为 $(i, j)$ 的土地上一个一米乘一米的方块的价格。每个方块的价格不超过 $2\times 10^9$ 拜塔拉尔。

输出格式

如果不存在价格在 $[k, 2k]$ 范围内的土地，程序应输出 NIE。

否则，程序应输出一行，包含四个正整数 $x_{1}, y_{1}, x_{2}, y_{2}$，用单个空格分隔，表示矩形的坐标。坐标对 $(x_{1}, y_{1})$ 表示矩形的左上角，坐标对 $(x_{2}, y_{2})$ 表示矩形的右下角。矩形由以下坐标集合定义：$\{(x, y) \mid x_{1} \leq x \leq x_{2} \land y_{1} \leq y \leq y_{2}\}$。矩形内方块价格总和 $c$ 应满足不等式 $k \leq c \leq 2k$。如果存在多个符合条件的土地，则输出其中任意一个。

4 3
1 1 1
1 9 1
1 1 1

NIE

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

2 1 4 2

在第二个样例中，价格地图和选定的土地如图所示。