type
	coloana=array [0..18]of longint;
  linie=array [1..1024] of ^coloana;
	mat=array [0..245]of ^linie;
var a:mat;
    n,m,i,j,s,g,q,p:longint;
    max:integer;
    f1,f2:text;

function exponent(pas:longint):integer;
var k:integer;
begin
k:=0;
while pas>=(1 shl k) do
	k:=k+1;
exponent:=k-1
end;

procedure rec(nr:longint; exp:integer);
begin
a[i shr 10]^[i and 1023]^[exp]:=nr;
if exp<max then
	if nr=0 then
  	rec(0,exp+1)
  else
  	rec(a[nr shr 10]^[nr and 1023]^[exp],exp+1)
end;

procedure rec2(nod:longint; x:integer);
var e:integer;
begin
e:=exponent(x);
x:=x-(1 shl e);
nod:=a[nod shr 10]^[nod and 1023]^[e];
if nod=0 then
	g:=0
else
	if x=0 then
  	g:=nod
  else
  	rec2(nod,x)
end;

begin
assign(f1,'stramosi.in');
reset(f1);
readln(f1,n,m);
max:=exponent(n);
for i:=0 to (n shr 10) do
  begin
  new(a[i]);
  for j:=1 to 1024 do
	 	new(a[i]^[j])
	end;
i:=0;
repeat
	i:=i+1;
  read(f1,s);
  rec(s,0)
until i=n;
assign(f2,'stramosi.out');
rewrite(f2);
i:=0;
repeat
  i:=i+1;
  readln(f1,q,p);
  g:=0;
  rec2(q,p);
  writeln(f2,g)
until i=m;
close(f1);
close(f2)
end.