Description

Byteasar 打算购买一块工业用地。

他的财富估计为 $k$ bythalers，这正是 Byteasar 想要花在这块地上的金额。

然而，找到一块价值恰好为 $k$ bythalers 的地并不是一件容易的事。

因此，Byteasar 准备购买一块更昂贵的地。

他考虑贷款。Byteotian 信贷银行会为他提供最多 $k$ bythalers 的贷款。因此，Byteasar 可以在这块地上花费不超过 $2k$ bythalers，并且他希望花费不少于 $k$ bythalers。

Byteasar 想要购买的地块所在的区域是一个边长为 $n$ 米的正方形。当前的地主为每平方米设定了不同的价格。Byteasar 已经与他们每个人交谈过，并准备了一张该区域的价格地图。地图显示了每平方米的价格。显然，这里有 $n^2$ 个这样的正方形。现在是时候找到梦想中的地块了。它必须是矩形的，并且由完整的单位正方形组成。Byteasar 已经开始在地图上寻找地块，但经过许多小时的努力，他仍然无法找到合适的地块。请帮帮他吧！

任务

编写一个程序：

从标准输入读取数字 $k$ 和 $n$，以及该区域的价格地图，确定一个价格在区间 $[k,2k]$ 内的地块，或者说明不存在这样的地块，将结果写入标准输出。

Input Format

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

接下来的 $n$ 行中的每一行包含 $n$ 个非负整数，用空格分隔。

第 $j+1$ 行的第 $i$ 个数字表示坐标为 $(i,j)$ 的单位正方形的价格。

每平方米的价格不超过 $2,000,000,000$ bythalers。

Output Format

如果不存在价格在区间 $[k,2k]$ 内的地块，你的程序应输出一行，内容为单词 NIE（波兰语中的 NO）。

否则，它应该输出一行，包含四个正整数 $x_1,y_1,x_2,y_2$，用空格分隔，表示矩形的坐标。

$(x_1,y_1)$ 表示矩形的左上角，而 $(x_2,y_2)$ 表示右下角。

然后它由这些正方形组成：$\{x,y\mid x_1\le x\le x_2,y_1\le y\le y_2\}$。

这些正方形的价格总和 $c$ 应满足不等式 $k\le c\le 2k$。

如果有多个矩形地块满足此条件，则任意选择一个。

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

2 1 4 2

Hint

给定 $k,n$ 和 $n\times n$ 的矩阵，求一个子矩形满足权值和在 $[k,2k]$ 之间。

$n<2000$，$1\le k\le10^9$，每个价格都是不大于 $2 \times 10^9$ 的非负整数。

感谢 @cn：苏炯念 提供的 spj。

题面翻译由 ChatGPT-4o 提供。