首先显然地，如果某个格子的权值超过2k，其一定不在答案之中；如果在[k,2k]中，其自身就可以作为答案。那么现在我们只需要考虑所选权值都小于k的情况。
可以发现一个结论：若存在一个权值都小于k的矩阵其权值和>=k，那么该矩阵一定存在权值和在[k,2k]中的子矩阵。
找到该子矩阵的过程和证明的过程是一样的：若其权值和已经在[k,2k]内，直接选择该矩阵即可；否则考虑从该矩阵中去掉一行（或一列）。如果矩阵剩下的部分权值和：
(1)在[0,k)内，对去掉的该行（或列）继续执行该操作
(2)在[k,2k]内，已找到答案
(3)在(2k,+∞)内，对剩下的矩阵继续执行该操作
由于矩阵中每一个权值都小于k，权值和不可能从>2k直接跳到<k，最终一定能找到合法矩阵。
于是只需要找到一个>=k的矩阵。悬线法即可。即先计算出每个位置向上向左向右最远能拓展到哪，然后根据其上方的点递推计算该悬线向左右拓展的最远位置。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 2010
int n,k,low,high,a[N][N],l[N][N],r[N][N],up[N][N];
int L,R,U,D;
long long s[N][N];
long long sum(int l,int r,int u,int d)
{
return s[d][r]-s[d][l-]-s[u-][r]+s[u-][l-];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1127.in","r",stdin);
freopen("bzoj1127.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
k=read(),n=read();
low=k,high=k<<;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
s[i][j]=s[i-][j]+s[i][j-]-s[i-][j-]+(a[i][j]=read());
if (a[i][j]>=low&&a[i][j]<=high) {cout<<j<<' '<<i<<' '<<j<<' '<<i;return ;}
}
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++)
if (a[i][j]<low) up[i][j]=up[i-][j]+,l[i][j]=l[i][j-]+;
for (int j=n;j>=;j--)
if (a[i][j]<low) r[i][j]=r[i][j+]+;
for (int j=;j<=n;j++)
if (up[i][j]>) l[i][j]=min(l[i][j],l[i-][j]);
for (int j=n;j>=;j--)
if (up[i][j]>) r[i][j]=min(r[i][j],r[i-][j]);
}
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (a[i][j]<low&&sum(j-l[i][j]+,j+r[i][j]-,i-up[i][j]+,i)>=low)
{
L=j-l[i][j]+,R=j+r[i][j]-,U=i-up[i][j]+,D=i;
break;
}
if (!L) cout<<"NIE";
else
{
while (sum(L,R,U,D)>high)
{
if (D>U)
{
if (sum(L,R,U,D-)<low) U=D;
else D--;
}
else R--;
}
cout<<L<<' '<<U<<' '<<R<<' '<<D;
}
return ;
}