#include <cstdio>
#define s scanf
#define o(_,__)for(_=1;_<=__;_++)
#define f o(i, N)
#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,
__,N,M,I[1<<18],p,q,u,_[33][1<<18];main(){r(in,r),r(
out,w);s("%d%d",&N,&M);f s("%d_",I+*&i);f _[-0][i]=I
[i];o(__,l(+2*M-M))f _[__][i]=_[__+(-1)][_[__-1][i]]
;while(M--){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;}