//#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") #define rd() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;}) #define rdf() ({long neg=*rp=='-'?++rp:0,a=rd(),b=rd();(neg?-1:1)*(a+b*1e-6);}) #define WTHI(v) {ulong _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(ulong*)wp=_d;wp+=_n;} #define wtf(v) ({double _a=v;if(_a<0)*wp++='-',_a=-_a;ulong x=(ulong)_a;WTHI(x);*wp++='.';long y=(ulong)((_a-x)*1e3);*wp++='0'+(y/100)%10;*wp++='0'+(y/10)%10;*wp++='0'+y%10;}) typedef unsigned long ulong; char wbuf[1<<25]; typedef __typeof(1.j) C; struct{C r,t} ms[100001]; main(){ char*mmap(); char*rp=mmap(0l,1l<<25,1,2,0,0ll); long n=rd(); ms[0].r=1; ms[0].t=0; for(long i=0;i