#pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); char wbuf[1<<25]; #define rd_skip() while(*rp++>=48) #define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define WTHI(v) {long _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;} #define WTLO(v) {long _z=v,_n=8,_d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;} #define wt(v) WTHI(v) #define rep(v,e) for(long v=0;v<e;++v) #define rep3(v,s,e) for(long v=s;v<e;++v) int ab[200002]; int nc[200002]; int pa[200002]; int st[100002]; main(){ char*rp=mmap(0l,1l<<25,1,2,0,0ll); char*wp=wbuf; rd(n); rd_skip(); long sn=0; st[sn++]=0; rep3(i,1,n+1){ if(!(*rp++&1)){ pa[i]=st[sn-1]; ++nc[st[sn-1]]; st[sn++]=i; }else{ long j=st[--sn]; ab[i]=j; ab[j]=i; } } ++rp; ab[0]=n+1; ab[n+1]=0; rep3(i,1,n+1){ if(nc[pa[i]]==1){ pa[i]=pa[pa[i]]; } } while(*rp){ rd(x); if(ab[x]<x) x=ab[x]; rd(y); if(ab[y]<y) y=ab[y]; if(ab[x]>ab[y]){ long t=x; x=y; y=t; } while(x<y){ y=pa[y]; } if(y==0){ *(int*)wp=*(int*)"-1\n"; wp+=3; }else{ wt(y); *wp++=' '; y=ab[y]; wt(y); *wp++='\n'; } } write(1,wbuf,wp-wbuf); _exit(0); }