#include<stdio.h>
#include<string.h>
#define N 10005
#define M 512
int v[M][M],n,m;
int s[M][M][20];
int p2[20];
int lg2[M];
inline int max(int a, int b){
    if(a>b)
		return a;
    return b;
}
void plant(){
    int i,j,k,t;
    for(i=1,p2[0]=1;i<16;++i)
        p2[i]=p2[i-1]<<1;
    for(i=1,j=0;i<=n;++i)
        if(p2[j+1]>i)
            lg2[i]=j;
        else
            lg2[i]=++j;
    for(i=n;i>0;--i)
        for(j=n;j>0;--j){
            s[i][j][0]=v[i][j];
            for(k=1;i+p2[k]<=n+1&&j+p2[k]<=n+1;++k){
                t=s[i][j][k-1];
                t=max(t,s[i+p2[k-1]][j+p2[k-1]][k-1]);
                t=max(t,s[i+p2[k-1]][j][k-1]);
                t=max(t,s[i][j+p2[k-1]][k-1]);
                s[i][j][k]=t;
            }
        }
}
void solv(){
    char c[N];
	int i,j,x,y,L,t,l;
    for(i=0;i<m;++i){
        fgets(c,N,stdin);
        j=t=x=y=L=0;
        while(c[j]>='0'&&c[j]<='9')
            x=x*10+c[j++]-'0';
        j++;
        while(c[j]>='0'&&c[j]<='9')
            y=y*10+c[j++]-'0';
        j++;
        while(c[j]>='0'&&c[j]<='9')
            L=L*10+c[j++]-'0';
        l=lg2[L];
        t=s[x][y][l];
        t=max(t,s[x+L-p2[l]][y][l]);
        t=max(t,s[x][y+L-p2[l]][l]);
        t=max(t,s[x+L-p2[l]][y+L-p2[l]][l]);
        printf("%d\n",t);
    }
}
int main(){
	char c[N];
	int i,j,l,t;
    freopen("plantatie.in","r",stdin);
    freopen("plantatie.out","w",stdout);
    fgets(c,N,stdin);
    i=n=m=0;
    while(c[i]>='0'&&c[i]<='9')
        n=n*10+c[i++]-'0';
    i++;
    while(c[i]>='0'&&c[i]<='9')
        m=m*10+c[i++]-'0';
    for(i=1;i<=n;++i){
        fgets(c,N,stdin);
        for(j=1,l=0;j<=n;++j,++l){
            t=0;
            while(c[l]>='0'&&c[l]<='9')
                t=t*10+c[l++]-'0';
            v[i][j]=t;
        }
    }
    plant();
    solv();
    fclose(stdin);
    fclose(stdout);
    return 0;
}