P3474 [POI 2008] KUP-Plot purchase

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]$ 内的地块，或者说明不存在这样的地块，将结果写入标准输出。

标准输入的第一行包含两个整数 $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。

如果不存在价格在区间 $[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$。 如果有多个矩形地块满足此条件，则任意选择一个。

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