a.c

#include"a.h"//thomn uar :+-*%&|<>=~ !@?#_^ ,.$ RE NLMSGVD g[&|<>= !@?#^] +*<= MS ?^  fft:5lx ai(+*ERSM)
#define e4(g,o,y,z...) D(e2,g,n=n4(n);r(ze,y;i(4,r=o(r,s0(2+i,r))))[15],z)
#define A(m,o,O,t,T) D(t##6,O##t,i(6-m,x=O##T(x,s0(m+i,x)))x,Vx)U(o##t,Iz=z0;I(n<<m,z=O##T(z,X_))O##t(z)[b(6-m)],in,GX)VD(o##T,T##z=z0;I(n<<m,A_=z=O##T(z[b(6-m)]-z##m,O##t(X_))),in,GA,GX)
A(0,m,M,g,G)A(0,s,S,g,G)A(2,m,M,i,I)A(2,s,S,i,I)VD(ve,n=n/16;i(n/4,Ez[4]={};h(m,i(4,zi+=A[h]*X[n*h+i]))X+=4;i(4,R_=zi))i(n%4,R_=r(ze,i(m,r+=Ai*X[n*i])++X)),im,in,ER,eA,EX)
e4(me,ME,i(n,r=ME(r,X_)),in,EX)e4(se,SE,Ez[4]={};i(n/4,i(4,zi+=X_))i(4,r+=zi)i(n%4,r+=X_),in,EX)e4(EE,SE,Ez[4]={};i(n/4,i(4,zi+=Ea*X_))i(4,r+=zi)i(n%4,r+=Ea*X_),in,EA,EX)
Z2 z[1<<18];Vf(ab,AB&LI(x,ba(x))|~AB&MI(x,ba(x)))VD(bk,IA=z;i(n4(m),A_=z0)i(n,++z[Xi>>k]),ik,im,in,iX)mn(m1,bk(0,i,n,X);sI(i,z,z);IA=R;i(n4(n),A_=z2)i(i,R[i?z[i-1]:0]=i)mI(n,R,R))
mn(n1,ik=lu(i)-lu(n);bk(k,i=1+(i-1>>k),n,X);ij=mi(i,z);sI(i,z,z);i=n;W(i--)R[--z[Xi>>k]]=Xi;IA=R--;*R=r(*R,*R=0;IX=R;i(1+j>>1,i(n4(n),Ai=ab(Ai))i(n4(n),Xi=ab(Xi)))))
Z2 b[]={3,0,2,2,3,0,0,3},o,W;ZU a[30],O[1<<17];g(_M,W-=1<<i;*(U*)x=ai;ai=x)Ui(M_,Ux=ai;P(x,ai=*(U*)x;W+=1<<i;x)OO(i>28)_M(i,M_(i+1))+(64L<<i))g(hn,x<<=b[i];64>x?0:lu(x)-6)
G(o_,Ub=o;o=O[o];O[b]=a;t(8+i,b<<38|x))f(_o,qx?_M(hx,(U)sx):_m((U)sx,nx);Ox=o;o=ox;x)f(_r,P(ax,x)P(63&Ox,--Ox;x)if(!tx)i(nx,_r(xj))_o(x))f(r_,P(ax,x)OO(!(63&++Ox))x)
g(T,i>tx?T(i,_x(RV(tx+1,nx,$3(tx-1,C(i6,X4),C(e6,(s6)X6),C(j6,(i5)X5))))):x)f(_T,_R(tx-1,nx,GA=sx;I(Nx,$3(tx-2,R4=C(g4,Ia);0,R6=ie(Ea);0,R5=C(i5,Ja);0))))f(uz,!qx|63&Ox?_X(G,):x)
#define H(K) h(4/K,ik=K;j(k/2,ii=2*h*k+j;Ez=X_;Ri=_P(z,r(X_,Rk=P_(z,r))))X+=k)X=R;
#define L(K) h(4/K,ik=K;j(k,ii=2*h*k+j;Ri+=r(c(xy[k|j],Rk),Rk=Ri-r)))
Vg(f8,g2*p2(x,i|h2)+g3*p2(x,i|h3))VD(HL,H(4)H(2)ik=1;j(4,ii=2*j;Ez=g0*p2(Ri,8|h0)+p2(Ri,h0);Ri=f8(0,z=g1*p2(z,2|h1)+p2(z,h1));Rk=f8(8,z))L(1)L(2)L(4),ER,EX)
f(fft,x=T(3,x);Qz(64-vx)_R(4,nx,i(mx?ux:1,HL(rZ+8*i,xZ+4*i))))

g_(ku,x?$4(i,_r(x),r_(x),(U)sx,ux):ti(W))g(u_,Ox|=(U)i<<47;1l<<32|x)f(_u,Ox&=b(47);~(1l<<32)&x)g(p,cc=Nx%64;if(c)$(i,xZ[Nx>>6]|=I0>=c)xZ[Nx>>6]&=I0<c;x)
void k_(){m_(0,0);i(30,ai=(1L<<32)+(64L<<i))i(1<<17,O[i]=i+1)i(8,if(i)Ai=Bi=i)i(1e4,JJ())}g_(tn,Ua=hn(i,x);a<<55|o_(i,M_(a),x))f(ms,x&=b(60);Ua=m_(&x,&x);Qz(x>>30)o_(1,a,x))
inx(ln,R(tx,n,M6(Nr,sr,sx+((int)i<<bx))))g(_i,mx?ln(i*vx,vx,x):tx?t(tx,$b(xg,xi,xj)):r_(xj))
f(_v,_x(_i(0,x)))f(v,R(tx,1,*(U*)sr=b(60)&x))f(_n,_x(ti(ux)))g(n_,RV(tx,i,$b((i0)ix-z0,ix-z2,jx-z3)))g(dz,hn(tx,i)>hx?_R(tx,i,M6(Nx,sr,sx)):x+i-nx)
g(e9,x=p(0,T(3,x));ee=1/$4(i,nx,se(nx,sx),eE(_q,EE(nx,sx,sx)/nx),e=me(nx,sx);x=p(0,X(Ex-e)));X(e*Ex))G(b3,Qr(!aa)2>tx?X(1&$3(i-6,ga<X_,ga>X_,ga==X_)):X(1&$3(i,ia<Ix,ia>Ix,ia==Ix)))
G(a1,im=iz(x);10>i?u_(m,6>i?n_(m*m,te(1)):R(3,m*m,j(m,*(i6*)(r2+m*j)=E1&$4(i-6,m-1-j==I2,j<I2,j>I2,j==I2)))):13-i?x(RV(2,m,I2|16*i),11-i?e9(0,x):x):RV(3,m,(e6)(E1|b(23)&(i6)JJ())-1))
f(m2,p(0,x);mi(nx,sx))f(sq,Qz(2-tx)in=nx;im=1+m2(x);Qz(17>n)_X(i,p(1,r);(m/4>n?n1:m1)(m,n,sr,sx)))f(uq,Qz(2-tx)in=nx;im=1+m2(x);Qz(17>m)Qn(m-1>>18)bk(0,m,n,sx);IA=z;_x(RV(2,m,A_)))
g(i_,0)//ij=i;Ua;GX=sx;I(Nx,$(2>tx,P(a=B0((i0)j==X_),l2(nx,64*i|iu(a))))P(a=B2(j==Ix),l(nx,16*i|iu(a))))nx)
F(S,Qt(ta-tx|3-tx)p(0,x);im=ma?ua:na;in=vx;_x(mx?ma?u_(m,R(3,m*n,i(m,ve(ux,n,r2+n*i,a2+m*i,sx)))):R(3,n,ve(ux,n,sr,sa,sx)):ma?R(3,m,i(m,re=EE(n,a2+n*i,sx))):te(EE(n,sa,sx))))
G(a9,ij=i-1;X($3(tx-1,5>j?LG(ga-z0,X_):MG(ga-z0,X_),$6(j,ia+Ix,ia-Ix,ia*Ix,z2,LI(ia-z2,Ix),MI(ia-z2,Ix)),$6(j,ea+Ex,ea-Ex,ea*Ex,ea/Ex,LE(ea-ze,Ex),ME(ea-ze,Ex)))))
G(A9,ij=i-1;_a(GA=sa;X($3(tx-1,5>j?LG(A_,X_):MG(A_,X_),$6(j,Ia+Ix,Ia-Ix,Ia*Ix,z2,LI(Ia-z2,Ix),MI(Ia-z2,Ix)),$6(j,Ea+Ex,Ea-Ex,Ea*Ex,Ea/Ex,LE(Ea,Ex),ME(Ea,Ex))))))
G(A0,it=m(4>i?2:5>i?3:0,m(ta,tx));a=aa?a:T(t,a);x=ax?x:T(t,x);ax?aa?3>t?t(7>i?t:1,$9(i-1,ia+ix,ia-ix,ia*ix,0,l(ia,ix),m(ia,ix),ia<ix,ia>ix,ia==ix)):_v(A0(i,a,v(x))):
A0(3>i?1:5>i?3:$3(i-7,8,7,i),$5(i-1,x,3>t?ti(-ix):te(-ex),x,te(1/ex),x),a):(7>i?aa?a9:A9:b3)(i,a,x))G(ep,Qz(a|2-i|2-tx)ii=*x2;IA=x2-1;x=X(Ix-A_);*x2=i;x)G(Nt,0)
G(a0,P(ax,_v(a0(i,a,v(x))))P(15==i,_T(x))x=T(4>i?2:3,x);ee=a&&aa?eE(l_,ea):1.442695;4>i?A0(i,3>i?0:r_(x),x):5>i?X(_q(Ex)):aa?1&i?X(_l(e*Ex)):X(l_(Ex)/e):_a(a=T(3,a);X(x(Ex,x/(1+_l(e*-x))*A6))))
G(a3,ij=i-11;in=(ia+65535)/ia;1==j|2<m(ta,tx)?A0(3,1<j?te(1/ea):a,x):ax?ti($3(j,ix%ia,ix*ia,ix/ia)):X(Iz=Ix;x(n*z>>16,j?x:z-ia*x)))
F(_I,Qn(na<=m2(x=T(2,x)))!ta?RU(nx,_i(xi,a)):2-x(a,bx)?_R(tx,nx,$(2>tx,I(Nx,R4=C(g4,(i6)G0(sa,X6))))I(Nr,R6=G3(sa,X5))):X(G2(sa,X6)))
F(I_,Qr(!ta)Qt(ta-tx)_R(2,nx,i(nx,ri=i_(xi,a))))
G(sS,0)G(dD,7>x?T(4,x):ms(x))
VD(m6,$(tx,cc=63&(U)d;GA=d-c;Va=*A;M6(c+(n<<bx),A,sx-c);*A=I0<c&a|I0>=c&*A)i(n,r_(Ud=xj);d+=8),in,sd,Ux)
G(cC,P(!a,ax?v(x):!tx|mx?R(0,1,*(U*)sr=x):u_(1,x))Qz(ta-tx|mx|(ma&&va-nx))a=aa?v(a):a;x=ax?v(x):x;x=_x(r(dz(na+nx,a),m6(nx,sr+Na,x)));ma?(1L<<32)+x:x)
inx(nt,n>nx?r(dz(n,x),n=Nx;W(n<nr)(m6(l(n,nr-n),sr+(n<<bx),r),n*=2)):i?ln(n,nx-n,x):x+n-nx)
G(td,i-=14;Qr(!aa)in=iz(a);P(ax,n_(n,x))P(1<i,u_(n,x))ih=i^n>>31;n+=(h^i)*ux;tx?mx?u_(n,nt(h,n*vx,x)):nt(h,n,x):RU(n,_i(i%nx,x)))
#define Z(K) h(8/K,ik=K;j(k,ii=2*h*k+j;zi=_P(zi,r(zk,zk=P_(zi,r)))))
f(ff,Qr(!mx)Qz(2-bx)in=vx;Qn(16-ux|16-n)u_(n,_X(G,Ez[16];i(16,zi=X6)Z(1)Z(2)Z(4)Z(8)i(16,Ri=zi))))
f(rr,Qr(mx)_X(G,GX=sx+Nx;I(Nx,R_=r0(bx,*--X))))f(aq,0)f(bq,0)f(fq,0)f(gq,0)
G(A1,$a(i-5-(9<i),ff,rr,aq,bq,fq,gq,_v,uq,_n,sq)(x))G(A3,i-=11;P(aa,a3(i,a,x))Qz(!i--)_a(ax?i?ti(i_(x,a)):_i(x,a):(i?I_:ma|mx?S:_I)(a,x)))G(er,Qr(!aa)ij=i;RU(nx,k(j,r_(a),_i(i,x))))
g(r9,Qz(1<--i)p(0,x);_x(3>tx?t(tx,$4(2*i+tx-1,mg,mi,sg,si)(nx,sx)):te((i?se:me)(nx,sx))))g(s9,Qz(1<--i|2<tx)r(uz(x),$4(2*i+tx-1,mG,mI,sG,sI)(nx,sr,sx)))Ui(q3,2>i-5?i-5:1-i?3:2)
G(R7,i-=22;Qr(ax)Qz(!i--)P(a,_a(S(a,x)))r9(i,x))G(O3,i-=29;Qr(ax|!tx)P(ta,Qz(i)ia?e9(ia,x):fft(x))Qr(!pa)a-=32;P(!i--,(11>a?ep:er)(a,0,x))P(17==a,_u(x))(i?s9:r9)(q3(a),x))
G_(k,(2>i-20||(a?10>i:5>i|10==i|15==i)?tx?a&&10>i?A0:a0:er:17>i?a?11>i?Nt:14>i?aa?a3:A3:td:ax?a1:A1:20>i?$3(i-17,cC,dD,sS):29>i?R7:O3)(i,a,x))