#include <fstream>

using namespace std;

ifstream in("rover.in");
ofstream out("rover.out");

const int N=502, L=12;
short int dl[]={-1, 1, 0, 0};
short int dc[]={0, 0, -1, 1};
int v, n, g, a[N][N], d[N][N];
struct poz{
    short int l, c;
};
poz dq[2*N*N];

int pericol(int g)
{
    poz x, y;
    int st=n*n, dr=n*n-1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) d[i][j]=-1;
    x=(poz){1, 1};
    dq[++dr]=x;
    if(a[x.l][x.c]<g) d[x.l][x.c]=1;
    else d[x.l][x.c]=0;
    while(st<=dr)
    {
        x=dq[st++];
        for(int i=0; i<4; i++)
        {
            y.l=x.l+dl[i];
            y.c=x.c+dc[i];
            if(d[y.l][y.c]==-1)
            {
                if(a[y.l][y.c]<g)
                {
                    d[y.l][y.c]=1+d[x.l][x.c];
                    dq[++dr]=y;
                }
                else
                {
                    d[y.l][y.c]=d[x.l][x.c];
                    dq[--st]=y;
                }
            }
        }
    }
    x=(poz){n, n};
    return d[x.l][x.c];
}

int main()
{
    in>>v>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) in>>a[i][j];
    if(v==1)
    {
        in>>g;
        out<<pericol(g);
    }
    if(v==2)
    {
        int pas, r;
        pas=1<<L;
        r=0;
        while(pas!=0)
        {
            if(pericol(r+pas)==0 && r+pas<=n) r+=pas;
            pas/=2;
        }
        out<<r;
    }
    return 0;
}