#include <cstdio>
#include <algorithm>
#define MAX 90005
#define QMAX 20005
FILE *f,*g;
using namespace std;

int N, K, M;
int TT[MAX], rang[MAX], X[MAX], dX[] = {-1, 0, 1, 0}, dY[] = {0, 1, 0, -1};

struct MATRICE
{
    int x, y, val;
} V[MAX];

struct QUERY
{
    int xStart, xStop, yStart, yStop, ind, rez;
} Q[QMAX];

bool MCMP(int a, int b)
{
    return V[a].val > V[b].val;
}

bool QCMP(QUERY a, QUERY b)
{
    return a.rez > b.rez;
}

bool ACMP(QUERY a, QUERY b)
{
    return a.ind < b.ind;
}

int Find(int x)
{
    int R, comp;
    for(R = x; TT[R] != R; R = TT[R]);
    while(comp != R)
    {
        comp = TT[x];
        TT[x] = R;
        x = comp;
    }
    return R;
}

void Unite(int x, int y)
{
    if(rang[x] > rang[y]) TT[y] = x;
    else TT[x] = y;
    if(rang[x] == rang[y]) rang[y]++;
}

void Merge(int element, int val)
{
    int x = V[element].x, y = V[element].y;
    for(int i = 0; i < 4; i++)
    {
        int X = x + dX[i], Y = y + dY[i], poz = (X - 1) * N + Y, a, b;
        if(X && Y && X <= N && Y <= N && V[poz].val >= val && (a = Find(element)) != (b = Find(poz)))
            Unite(a, b);
    }
}

int main()
{
    f=fopen("matrice2.in","r");
    fscanf(f,"%d%d",&N,&M);
    M = N * N;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
        {
            int poz = (i - 1) * N + j;
            fscanf(f,"%d",&V[poz].val);
            V[poz].x = i;
            V[poz].y = j;
        }
    for(int i = 1; i <= K; i++)
    {
        fscanf(f,"%d%d%d%d",&Q[i].xStart,&Q[i].yStart,&Q[i].xStop,&Q[i].yStop);
        Q[i].ind = i;
    }
    fclose(f);
    for(int i = 1; i <= M; i++)
        X[i] = i;
    sort(X + 1, X + M + 1, MCMP);
    for(int val = (1 << 20); val; val >>= 1)
    {
        sort(Q + 1, Q + K + 1, QCMP);
        for(int i = 1; i <= M; i++)
        {
            TT[i] = i;
            rang[i] = 1;
        }
        int j = 1;
        for(int i = 1; i <= K; i++)
        {
            int expected = Q[i].rez + val;
            for(; j <= M && V[X[j]].val >= expected; Merge(X[j], expected), j++);
            if(Find((Q[i].xStart - 1) * N + Q[i].yStart) == Find((Q[i].xStop - 1) * N + Q[i].yStop))
                Q[i].rez = expected;
        }
    }
    sort(Q + 1, Q + K + 1, ACMP);
    g=fopen("matrice2.out","w");
    for(int i = 1; i <= K; i++)
        fprintf(g,"%d\n",Q[i].rez);
    fclose(g);
    return 0;
}