type node=record

        x,y,v:longint;

      end;

      point=record

        x0,y0,x1,y1,k:longint;

      end;

 var q:array[..] of point;

     ans,d,c:array[..] of longint;

     v:array[..] of boolean;

     a:array[..] of node;

     w:array[..] of longint;

     b:array[..,..] of longint;

     mx,n,m,i,j,k,p:longint;

 function lowbit(x:longint):longint;

   begin

     exit(x and (-x));

   end;

 procedure add(x,y,w:longint);

   var p:longint;

   begin

     p:=x;

     while y<=n do

     begin

       x:=p;

       while x<=n do

       begin

         inc(b[x,y],w);

         x:=x+lowbit(x);

       end;

       y:=y+lowbit(y);

     end;

   end;

 function ask(x,y:longint):longint;

   var p:longint;

   begin

     ask:=; p:=x;

     while y> do

     begin

       x:=p;

       while x> do

       begin

         ask:=ask+b[x,y];

         x:=x-lowbit(x);

       end;

       y:=y-lowbit(y);

     end;

   end;

 function check(i:longint):boolean;

   var s:longint;

   begin

     s:=ask(q[i].x1,q[i].y1);

     if s<q[i].k then exit(false);

     s:=s-ask(q[i].x0-,q[i].y1);

     if s<q[i].k then exit(false);

     s:=s+ask(q[i].x0-,q[i].y0-);

     if s<q[i].k then exit(false);

     s:=s-ask(q[i].x1,q[i].y0-);

     if s>=q[i].k then exit(true) else exit(false);

   end;

 procedure swap(var a,b:node);

   var c:node;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 procedure sort(l,r:longint);

   var i,j,x:longint;

   begin

     i:=l;

     j:=r;

     x:=a[(l+r) shr ].v;

     repeat

       while a[i].v<x do inc(i);

       while x<a[j].v do dec(j);

       if not(i>j) then

       begin

         swap(a[i],a[j]);

         inc(i);

         dec(j);

       end;

     until i>j;

     if l<j then sort(l,j);

     if i<r then sort(i,r);

   end;

 procedure work(f,t,l,r:longint);

   var m,p,l1,l2:longint;

   begin

   //  writeln(f,' ',r,' ',l,' ',r);

     if f>t then exit;

     if l>r then exit;

     m:=(l+r) shr ;

     while (j<k) and (a[j+].v<=m) do

     begin

       add(a[j+].x,a[j+].y,);

       inc(j);

     end;

     while (j>) and (a[j].v>m) do

     begin

       add(a[j].x,a[j].y,-);

       dec(j);

     end;

     p:=;

     for i:=f to t do

       if check(c[i]) then

       begin

         inc(p);

         ans[c[i]]:=m;

         v[i]:=true;

       end

       else v[i]:=false;

     l1:=f; l2:=f+p;

     for i:=f to t do

       if v[i] then

       begin

         d[l1]:=c[i];

         inc(l1);

       end

       else begin

         d[l2]:=c[i];

         inc(l2);

       end;

     for i:=f to t do c[i]:=d[i];

     work(l1,t,m+,r);

     work(f,l1-,l,m-);

   end;

 begin

   readln(n,m);

   for i:= to n do

     for j:= to n do

     begin

       inc(k);

       a[k].x:=i;

       a[k].y:=j;

       read(a[k].v);

     end;

   sort(,k);

   p:=;

   w[]:=a[].v;

   a[].v:=;

   for i:= to k do

   begin

     if w[p]<>a[i].v then

     begin

       inc(p);

       w[p]:=a[i].v;

     end;

     a[i].v:=p;

   end;

   for i:= to m do

   begin

     with q[i] do readln(x0,y0,x1,y1,k);

     c[i]:=i;

   end;

   j:=;

   work(,m,,p);

   for i:= to m do

     writeln(w[ans[i]]);

 end.