type ref=^nod;
nod=record
nr:longint;
adr:ref;
end;
elem=record
val:longint;
x,y:word;
end;
per=record
x,y:word;
end;
var a,rang:array[1..305,1..305] of longint;
pad:array[1..305,1..305] of per;
c,sf:array[1..305,1..305] of ref;
v:array[1..90005] of elem;
sol:array[1..20005] of longint;
n,q,i,j,x1,y1,x2,y2,poz,ln,col,strx,stry:longint;
u,u2,last,p:ref;
f,g:text;
function sort2(min,max:longint):longint;
var i,j,piv:longint;
aux:elem;
k:boolean;
begin
piv:=v[min+(max-min) shr 1].val;
i:=min-1;
j:=max+1;
k:=true;
repeat
repeat
inc(i);
until v[i].val<=piv;
repeat
dec(j);
until v[j].val>=piv;
if i<j then
begin
aux:=v[i];
v[i]:=v[j];
v[j]:=aux;
end
else
begin
sort2:=j;
exit;
end;
until k=false;
end;
procedure sort(min,max:longint);
var p:longint;
begin
if min<max then
begin
p:=sort2(min,max);
sort(min,p);
sort(p+1,max);
end;
end;
procedure str(x,y:longint;var p,q:longint);
var xi,yi,auxx:word;
begin
xi:=x;
yi:=y;
while not ((pad[x,y].x=x) and (pad[x,y].y=y)) do
begin
auxx:=pad[x,y].x;
y:=pad[x,y].y;
x:=auxx;
end;
p:=x;
q:=y;
x:=xi;
y:=yi;
while not ((pad[x,y].x=x) and (pad[x,y].y=y)) do
begin
xi:=x;
yi:=y;
auxx:=pad[x,y].x;
y:=pad[x,y].y;
x:=auxx;
pad[xi,yi].x:=p;
pad[xi,yi].y:=q;
end;
end;
procedure join(xmic,ymic,ln,col:word);
begin
u:=c[xmic,ymic];
u2:=c[ln,col];
last:=nil;
while u<>nil do
begin
while (u2<>nil) and (u2^.nr<u^.nr) do
begin
last:=u2;
u2:=u2^.adr;
end;
if u2=nil then
begin
new(p);
p^.nr:=u^.nr;
p^.adr:=nil;
if last<>nil then
begin
last^.adr:=p;
u2:=p;
end
else
begin
c[ln,col]:=p;
u2:=p;
end;
end
else
if u2^.nr=u^.nr then
begin
sol[u2^.nr]:=v[i].val;
if last<>nil then
last^.adr:=u2^.adr
else
c[ln,col]:=u2^.adr;
p:=u2;
u2:=u2^.adr;
dispose(p);
end
else
begin
new(p);
p^.nr:=u^.nr;
p^.adr:=u2;
if last<>nil then
begin
last^.adr:=p;
last:=p;
end
else
begin
c[ln,col]:=p;
last:=p;
end;
end;
u:=u^.adr;
end;
u:=c[xmic,ymic];
c[xmic,ymic]:=nil;
while u<>nil do
begin
p:=u;
u:=u^.adr;
dispose(p);
end;
end;
begin
assign(f,'matrice2.in');
assign(g,'matrice2.out');
reset(f);rewrite(g);
readln(f,n,q);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(f,a[i,j]);
inc(poz);
v[poz].val:=a[i,j];
v[poz].x:=i;
v[poz].y:=j;
end;
readln(f);
end;
for i:=1 to q do
begin
readln(f,x1,y1,x2,y2);
if c[x1,y1]=nil then
begin
new(c[x1,y1]);
c[x1,y1]^.nr:=i;
c[x1,y1]^.adr:=nil;
sf[x1,y1]:=c[x1,y1];
end
else
begin
new(u);
u^.nr:=i;
u^.adr:=nil;
sf[x1,y1]^.adr:=u;
sf[x1,y1]:=u;
end;
if c[x2,y2]=nil then
begin
new(c[x2,y2]);
c[x2,y2]^.nr:=i;
c[x2,y2]^.adr:=nil;
sf[x2,y2]:=c[x2,y2];
end
else
begin
new(u);
u^.nr:=i;
u^.adr:=nil;
sf[x2,y2]^.adr:=u;
sf[x2,y2]:=u;
end;
end;
sort(1,n*n);
for i:=1 to n*n do
begin
pad[v[i].x,v[i].y].x:=v[i].x;
pad[v[i].x,v[i].y].y:=v[i].y;
rang[v[i].x,v[i].y]:=1;
if (v[i].x>1) and (pad[v[i].x-1,v[i].y].x>0) then
begin
str(v[i].x-1,v[i].y,ln,col);
if rang[ln,col]>1 then
begin
pad[v[i].x,v[i].y].x:=ln;
pad[v[i].x,v[i].y].y:=col;
strx:=ln;
stry:=col;
join(v[i].x,v[i].y,ln,col);
end
else
begin
pad[ln,col].x:=v[i].x;
pad[ln,col].y:=v[i].y;
inc(rang[v[i].x,v[i].y]);
strx:=v[i].x;
stry:=v[i].y;
join(ln,col,v[i].x,v[i].y);
end;
end
else
begin
strx:=v[i].x;
stry:=v[i].y;
end;
if (v[i].y>1) and (pad[v[i].x,v[i].y-1].x>0) then
begin
str(v[i].x,v[i].y-1,ln,col);
if (ln<>strx) or (col<>stry) then
if rang[ln,col]>rang[strx,stry] then
begin
pad[strx,stry].x:=ln;
pad[strx,stry].y:=col;
join(strx,stry,ln,col);
strx:=ln;
stry:=col;
end
else
if rang[ln,col]<rang[strx,stry] then
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
end
else
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
inc(rang[strx,stry]);
end;
end;
if (v[i].y<n) and (pad[v[i].x,v[i].y+1].x>0) then
begin
str(v[i].x,v[i].y+1,ln,col);
if (ln<>strx) or (col<>stry) then
if rang[ln,col]>rang[strx,stry] then
begin
pad[strx,stry].x:=ln;
pad[strx,stry].y:=col;
join(strx,stry,ln,col);
strx:=ln;
stry:=col;
end
else
if rang[ln,col]<rang[strx,stry] then
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
end
else
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
inc(rang[strx,stry]);
end;
end;
if (v[i].x<n) and (pad[v[i].x+1,v[i].y].x>0) then
begin
str(v[i].x+1,v[i].y,ln,col);
if (ln<>strx) or (col<>stry) then
if rang[ln,col]>rang[strx,stry] then
begin
pad[strx,stry].x:=ln;
pad[strx,stry].y:=col;
join(strx,stry,ln,col);
strx:=ln;
stry:=col;
end
else
if rang[ln,col]<rang[strx,stry] then
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
end
else
begin
pad[ln,col].x:=strx;
pad[ln,col].y:=stry;
join(ln,col,strx,stry);
inc(rang[strx,stry]);
end;
end;
end;
for i:=1 to q do
writeln(g,sol[i]);
close(f);close(g);
end.
Ilie Ionut ionutz32