#include <cstdio>
#define s scanf
#define o(_,__)for(_=1;_<=__;_++)
#define f o(i, k)
#define r(x,y)freopen("stramosi."#x,#y,std##x)
int l(int x){return x==1?x!=1:(1==1)+l(x>>1);}int i,
__,k,g,I[1<<18],p,q,u,_[33][1<<18];main(){r(in,r),r(
out,w);s("%d%d",&k,&g);f s("%d_",I+*&i);f _[-0][i]=I
[i];o(__,l(+2*g-g))f _[__][i]=_[__+(-1)][_[__-1][i]]
;while(g--){s("%d%d",&q,&p);while(*&u=(p&(p-1)))q=_[
l(p-u)][q],p=u;printf("%d\n",_[l(p)][q]);}return 0;}