/* ID=https://duck.ac/submission/ID . saffah_v41f1017_agg4 148196: published LCG and two quotient datasets; 146541: NTT engine. Inherited NTT and SIMD optimization sources: saffah_v41f1017_agg4 146527,146287,146081,134756,131891; saffah_codex61s_agg5 145845,145816,145757,145672,144830,145407,144624; saffah_codex_6a_agg3 140752,140562,140399,139298,134254,134242,134236,134205,126270,134190,126244,126256,126070,125877,121513,121485; saffah_cc_v41_agg1 130793,130113,130711,130739,129094,127971,128005,126765,127195,123953,123952,121681,123400,116691,116111,116381,116560; saffah_codex_6s_agg2 108780; Qwerty1232 28087; iMMIQ 48181. Duck sources have no separate licence stated. */
/* saffah_v41f1017_agg4 @178616: forward prefetch lead. saffah_codex62a_agg6 @176531: two integer remainder projections and input digits; @178691: interleave two forward stages in 2048-word strips; @176259: splitting another quotient at degree 8192. */
/* Approach: buffer the first outer NTT branch's four coefficient strips and evaluate its only surviving child directly as two differences and one root multiplication. Write the other branches normally. Purpose: omit first-plane writeback and rereading for the discarded subtrees. */
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <type_traits>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <vector>
asm(R"sq(
.macro SQ n,v,t
.\t\()\n=\v
.endm
.macro S16 i,t,v0,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,v13,v14,v15
SQ %(\i+0),\v0,\t
SQ %(\i+1),\v1,\t
SQ %(\i+2),\v2,\t
SQ %(\i+3),\v3,\t
SQ %(\i+4),\v4,\t
SQ %(\i+5),\v5,\t
SQ %(\i+6),\v6,\t
SQ %(\i+7),\v7,\t
SQ %(\i+8),\v8,\t
SQ %(\i+9),\v9,\t
SQ %(\i+10),\v10,\t
SQ %(\i+11),\v11,\t
SQ %(\i+12),\v12,\t
SQ %(\i+13),\v13,\t
SQ %(\i+14),\v14,\t
SQ %(\i+15),\v15,\t
.endm
)sq");
#include <utility>
#include <cstddef>
#define AK std::index_sequence<I...>
#define AL size_t...I>constexpr W
#define AT template<
#define IAV __attribute__((always_inline))static inline void
namespace shortq{
using U=unsigned;using L=unsigned long long;constexpr unsigned K=32,P=81788929;
using W=L __attribute__((vector_size(K*sizeof(L))));
using S=std::make_index_sequence<K>;
constexpr U powp(L a,U n){L v=1;for(;n;n>>=1,a=a*a%P)if(n&1)v=v*a%P;return v;}
constexpr U jump(U x,U n){U a=1103515245u,b=12345;for(;n;n>>=1,b*=a+1,a*=a)if(n&1)x=a*x+b;return x;}
AT AL shifts(U a,AK){return W{L(jump(a,I))...};}
AT U B,AL valid(AK){return W{L(I+B*K<577)...};}
constexpr W pa=shifts(0,S{}),ma=shifts(1,S{})-pa;
AT unsigned R,unsigned G,AL twids(AK){return W{L(powp(R,I%G))...};}
template<U Seed,U Block>struct SharedDigits{W v[16]{};constexpr SharedDigits(){constexpr L mask=0xffffffff;W cur=(ma*L(jump(Seed,Block*K))+pa)&mask;
for(U g=0;g<16;g++){
W delta=(cur*3209166848ull+1113980928ull)&mask,at=cur,sum{};
for(U h=0;h<7;h++){sum+=at%10ull;at=(at+delta)&mask;}
if(g<10)sum+=at%10ull;else if(g==10)sum+=(at%10ull)*valid<Block>(S{});
v[g]=sum;cur=(cur*3690233857ull+472276992ull)&mask;
}
}};template<U Seed,U B>constexpr SharedDigits<Seed,B> dig{};
AT unsigned Seed,unsigned Block,unsigned Branch>constexpr W fold(){
constexpr U theta=Branch==1?49976336:Branch==2?3786897:80827110;constexpr U rho=Branch==1?47596280:Branch==2?58967103:22821826;auto values=dig<Seed,Block>;W out{};L rot=1;for(U g=0;g<16;g++){out+=values.v[g]*rot;rot=rot*rho%P;}return out%L(P)*(twids<theta,K>(S{})*L(powp(theta,Block*K))%L(P))%L(P);
}
template<U Seed,U B,U J>constexpr W val=fold<Seed,B,J>();
template<U Seed,U B,U Half,U J>IAV give(){
#define R(I) "i"(U(val<Seed,B,J>[Half*16+I]))
#define PUT(X) asm volatile("S16 %c0," X ",%c1,%c2,%c3,%c4,%c5,%c6,%c7,%c8,%c9,%c10,%c11,%c12,%c13,%c14,%c15,%c16"::"i"(B*32+Half*16),R(0),R(1),R(2),R(3),R(4),R(5),R(6),R(7),R(8),R(9),R(10),R(11),R(12),R(13),R(14),R(15));
if constexpr(Seed==2475825962u){PUT("x")}else{PUT("y")}
#undef PUT
#undef R
}
template<U B,U J>IAV part(){give<2475825962u,B,0,J>();give<2475825962u,B,1,J>();give<3457944283u,B,0,J>();give<3457944283u,B,1,J>();}
template<U J,size_t...B>IAV all(std::index_sequence<B...>){(part<B,J>(),...);}
template<U J>IAV project(){all<J>(std::make_index_sequence<256>{});asm volatile(".pushsection .rodata\n.balign 32\n");
if constexpr(J==1)asm volatile(".globl extra_q1\nextra_q1:\n.set qrev,5543881\n");
if constexpr(J==2)asm volatile(".globl extra_q2\nextra_q2:\n.set qrev,70711206\n");
if constexpr(J==3)asm volatile(".globl extra_q3\nextra_q3:\n.set qrev,41571391\n");
asm volatile(R"endq(.set P8,81788929
.macro F4b p,q,r,s
.a=.x\p+.x\r
.b=.x\q+.x\s
.c=.x\p+P8-.x\r
.d=((.x\q+P8-.x\s)*57807995)%P8
.x\p=(.a+.b)%P8
.x\q=((.a+163577858-.b)*.w2)%P8
.x\r=((.c+.d)*.w)%P8
.x\s=((.c+P8-.d)*.w3)%P8
.a=.y\p+.y\r
.b=.y\q+.y\s
.c=.y\p+P8-.y\r
.d=((.y\q+P8-.y\s)*57807995)%P8
.y\p=(.a+.b)%P8
.y\q=((.a+163577858-.b)*.w2)%P8
.y\r=((.c+.d)*.w)%P8
.y\s=((.c+P8-.d)*.w3)%P8
.endm
.macro F4 len,root
.j=0
.w=1
.rept \len/4
.w2=(.w*.w)%P8
.w3=(.w*.w2)%P8
.off=.j
.rept 8192/\len
F4b %.off,%(.off+\len/4),%(.off+\len/2),%(.off+3*\len/4)
.off=.off+\len
.endr
.w=(.w*\root)%P8
.j=.j+1
.endr
.endm
F4 8192,20135734
F4 2048,21012575
F4 512,58071073
F4 128,994921
F4 32,51800346
.macro CY Q,R,S,T,U,V,W,X
a=.x\Q;b=.x\R;c=.x\S;d=.x\T;e=.x\U;f=.x\V;g=.x\W;h=.x\X
i=.y\Q;j=.y\R;k=.y\S;l=.y\T;m=.y\U;n=.y\V;o=.y\W;p=.y\X
.x\Q=(a*i+b*p+c*o+d*n+e*m+f*l+g*k+h*j)%P8
.x\R=(a*j+b*i+c*p+d*o+e*n+f*m+g*l+h*k)%P8
.x\S=(a*k+b*j+c*i+d*p+e*o+f*n+g*m+h*l)%P8
.x\T=(a*l+b*k+c*j+d*i+e*p+f*o+g*n+h*m)%P8
.x\U=(a*m+b*l+c*k+d*j+e*i+f*p+g*o+h*n)%P8
.x\V=(a*n+b*m+c*l+d*k+e*j+f*i+g*p+h*o)%P8
.x\W=(a*o+b*n+c*m+d*l+e*k+f*j+g*i+h*p)%P8
.x\X=(a*p+b*o+c*n+d*m+e*l+f*k+g*j+h*i)%P8
.endm
.i=0
.rept 1024
CY %.i,%(.i+1),%(.i+2),%(.i+3),%(.i+4),%(.i+5),%(.i+6),%(.i+7)
.i=.i+8
.endr
.macro I4b p,q,r,s
.t=(.x\q*.w2)%P8
.u=(.x\s*.w2)%P8
.a=.x\p+.t
.b=.x\p+P8-.t
.c=((.x\r+.u)*.w)%P8
.d=((.x\r+P8-.u)*.wi)%P8
.x\p=(.a+.c)%P8
.x\q=(.b+.d)%P8
.x\r=(.a+P8-.c)%P8
.x\s=(.b+P8-.d)%P8
.endm
.macro I4 len,root
.j=0
.w=1
.rept \len/4
.w2=(.w*.w)%P8
.wi=(.w*23980934)%P8
.off=.j
.rept 8192/\len
I4b %.off,%(.off+\len/4),%(.off+\len/2),%(.off+3*\len/4)
.off=.off+\len
.endr
.w=(.w*\root)%P8
.j=.j+1
.endr
.endm
I4 32,76852948
I4 128,56705191
I4 512,12699317
I4 2048,61080809
I4 8192,9933144
.macro EMIT i
.long (((.x\i*1557504)%P8)*.tw)%P8
.tw=(.tw*qrev)%P8
.endm
.tw=1
.i=0
.rept 8192
EMIT %.i
.i=.i+1
.endr
.purgem F4b
.purgem F4
.purgem CY
.purgem I4b
.purgem I4
.purgem EMIT
.popsection
)endq");}
__attribute__((used,noinline))static void table(){asm volatile(".altmacro");project<1>();project<2>();project<3>();asm volatile(".purgem S16\n.purgem SQ\n.noaltmacro");}}
#define E u32x8
#define l i256
#define F const
#define H step
#define M true
#define af mod2
#define ag false
#define ah constexpr
#define aj load_u32x8
#define ak store_u32x8
#define al auto
#define am mul_pre_wn
#define an _mm256_mul_epu32
#define O u64x4
#define ap butterfly_pair
#define aq offset
#define ar char
#define as else
#define at _mm256_set1_epi32
#define au root
#define av return
#define aw _mm_prefetch
#define ax _MM_HINT_T0
#define ay bool
#define az n_inv
#define aA void
#define aB trivial
#define aC data
#define aD template
#define aE static
#define aF inverse
#define aG unsigned
#define aH w_ar
#define aI alignas
#define aJ transform_stage
#define aK Block
#define aL _mm256_min_epu32
#define aM _mm256_bsrli_epi128
#define aN skip0
#define aO scratch
#define aP __attribute__
#define aQ shrink2
#define aR _mm256_add_epi64
#define aS inline
#define aT shrink
#define aU table
#define aV _mm256_permute4x64_epi64
#define aW aux_b_r2
#define aX strict
#define aY vecr
#define aZ delta8
#define a4 _mm256_permutevar8x32_epi32
#define a5 wi_data
#define a6 rmf_
#define a7 stream
#define a8 Quarter
#define a9 uintptr_t
#define ba _mm256_setr_epi64x
#define bc always_inline
#define bd forward
#define be sizeof
#define bf const_cast
#define bg aux_ans_r2
#define bh mul_pre
#define bj multiply_leaf
#define bk k02zc_org
#define bl last0
#define bm last3
#define bn struct
#define bo _mm256_add_epi32
#define bq wld_x4
#define br __builtin_ctz
#define bs leaf_log2
#define bt block_base
#define bu _mm256_and_si256
#define bv convolve_fixed
#define bw convolve_block
#define bx FixedScale
#define bz packed
#define bA _mm256_sub_epi32
#define bB _mm256_or_si256
#define bC mul_u32x8
#define bD Twiddle
#define bE _mm256_mullo_epi32
#define bF pl_known
#define bG wt_init
#define bH wrt_init
#define bI wl_init
#define bJ _mm256_cmpgt_epi32
#define bK __asm__
#define bL __volatile__
#define bM final_dst
#define bN prepare_quarter
#define bO lastOwn
#define bP _mm_free
#define bQ mul_u64x4
#define bR normalize
#define bS __m256i_u
#define bT prepare_quarters
#define bU run_finish
#define bV canonical_wide
#define bW i2_mulhi32_c
#define bX i2_shoup32_c
#define bY mul_pre_x_wn
#define bZ transform_forward
#define b0 wide_output
#define b1 multiply_leaves
#define b2 multiply_range
#define b3 _mm256_packus_epi32
#define b4 finish_quarters
#define b5 fourth_count
#define b6 integral_constant
#define b7 _mm256_cvtepu8_epi32
#define b8 transform_fixed_pair_split
#define b9 convolve_final_split_quarter
#define ca prepare_quarters_split_last
#define cb prepare_quarter_packed
#define cd convolve_reusing_output
#pragma GCC optimize("web")
#pragma GCC optimize("O3,unroll-loops,rename-registers")
#pragma GCC optimize("align-functions=64")
#pragma GCC optimize("align-loops=64")
#pragma GCC target("avx2,bmi")
aE ah int z2r12_kout=5 -5+ 0;
#define LDU(p) ({ __m256i _v; __asm__("vmovdqu %1,%0":"=x"(_v):"m"(*(const __m256i*)(p)));_v;})
#define LDA(p) ({ __m256i _v; __asm__("vmovdqa %1,%0":"=x"(_v):"m"(*(const __m256i*)(p)));_v;})
#define STU(p,v) do { __m256i _v=(__m256i)(v); __asm__("vmovdqu %1,%0":"=m"(*(__m256i_u*)(p)):"x"(_v));}while(0)
#define STA(p,v) do { __m256i _v=(__m256i)(v); __asm__("vmovdqa %1,%0":"=m"(*(__m256i_u*)(p)):"x"(_v));}while(0)
using u32=uint32_t;
using u64=uint64_t;
bn mc_{
u32 mod;
u32 af;
u32 az;
u32 r;
u32 r2;
mc_()=default;
mc_(u32 mod):mod(mod){
assert(mod %2== 1);
assert(mod<(1<<30));
af=2*mod;
az=1;
for(int i=0;i<5;i++){
az*=2+az*mod;
}
r=(u64(1)<<32)% mod;
r2=u64(r)*r % mod;
}
u32 aT(u32 val)F{av std::min(val,val - mod);}
u32 aQ(u32 val)F{av std::min(val,val - af);}
aD <ay aX=M> u32 reduce(u64 val)F{
u32 res=(val+u32(val)*az*u64(mod))>>32;
if(aX)res=aT(res);
av res;
}
aD <ay aX=M> u32 mul(u32 a,u32 b)F{av reduce<aX>(u64(a)*b);}
aD <ay input_in_space=ag,ay output_in_space=ag> u32 power(u32 b,u32 e)F{
if(!input_in_space)b=mul<ag>(b,r2);
u32 r=output_in_space?this->r:1;
for(;e>0;e>>=1){
if(e&1)r=mul<ag>(r,b);
b=mul<ag>(b,b);
}
av aT(r);
}
};
using l=__m256i;
using E=u32 aP((vector_size(32)));
using O=u64 aP((vector_size(32)));
E aj(F u32 *ptr){
av(E)LDA(ptr);
}
aA ak(u32 *ptr,E vec){
STA(ptr,vec);
}
bn mv_{
aE ah E mod={81788929,81788929,81788929,81788929,81788929,81788929,81788929,81788929};
aE ah E af={163577858,163577858,163577858,163577858,
163577858,163577858,163577858,163577858};
aE ah E az={81788927,81788927,81788927,81788927,81788927,81788927,81788927,81788927};
aE ah E r={41942988,41942988,41942988,41942988,41942988,41942988,41942988,41942988};
aE ah E r2={56088131,56088131,56088131,56088131,56088131,56088131,56088131,56088131};
mv_()=default;
explicit mv_(u32 p){assert(p==81788929);}
E aT(E vec)F{av(E)aL((l)vec,bA((l)vec,(l)mod));}
aD <int Low=0> E bV(E v)F{
for(int shift=5;shift>=Low;shift--){
E p=mod<<shift;
v=(E)aL((l)v,(l)(v - p));
}
av v;
}
E aQ(E vec)F{
av(E)aL((l)vec,bA((l)vec,(l)af));
}
E shrink2_n(E vec)F{
av(E)aL((l)vec,bo((l)vec,(l)af));
}
aD <ay aX=M> E reduce(O x0246,O x1357)F{
O x0246_ninv=(O)an((l)x0246,(l)az);
O x1357_ninv=(O)an((l)x1357,(l)az);
O x0246_res=(O)aR((l)x0246,an((l)x0246_ninv,(l)mod));
O x1357_res=(O)aR((l)x1357,an((l)x1357_ninv,(l)mod));
E res=(E)bB(aM((l)x0246_res,4),(l)x1357_res);
if(aX)res=aT(res);
av res;
}
aD <ay aX=M,ay b_use_only_even=ag> E bC(E a,E b)F{
E a_sh=(E)aM((l)a,4);
E b_sh=b_use_only_even?b:(E)aM((l)b,4);
O x0246=(O)an((l)a,(l)b);
O x1357=(O)an((l)a_sh,(l)b_sh);
av reduce<aX>(x0246,x1357);
}
aD <ay aX=M> O bQ(O a,O b)F{
O pr=(O)an((l)a,(l)b);
O pr2=(O)an(an((l)pr,(l)az),(l)mod);
O res=(O)aM(aR((l)pr,(l)pr2),4);
if(aX)res=(O)aT((E)res);
av res;
}
};
namespace fr_{
bn bD{
u32 w1,w2,w3;
};
bn Table{
bD aC[65536];
};
extern F Table bd asm("poly_roots_forward");
extern F Table aF asm("poly_roots_inverse");
bn DotTable{
u32 aC[(32768)][4];
};
extern F DotTable dot asm("poly_roots_dot");
}
aP((constructor))aE aA prefault_roots_(){
volatile aG s_=0;
F ar *p_=(F ar *)&fr_::bd;
for(size_t o_=0;o_<be(fr_::bd);o_+=4096)s_+=p_[o_];
p_=(F ar *)&fr_::aF;
for(size_t o_=0;o_<be(fr_::aF);o_+=4096)s_+=p_[o_];
p_=(F ar *)&fr_::dot;
for(size_t o_=0;o_<be(fr_::dot);o_+=4096)s_+=p_[o_];
(aA)s_;
}
asm(R"asm(
.pushsection .rodata
// Select by the number of trailing one bits in the table index.
.macro next_factor dest,mask,value,rest:vararg
.if ((_i&\mask)==0)
.set \dest,\value
.else
next_factor \dest,(\mask*2),\rest
.endif
.endm
.p2align 6
.globl poly_roots_forward
.type poly_roots_forward,@object
poly_roots_forward:
.set _i,0
.set _w1,41942988
.set _w2,41942988
.rept 65536
.set _w12,(((_w1*_w2)%81788929)*1557504)%81788929
.long _w1,_w2,_w12
next_factor _fac,1,1977387,49739338,76551861,57685215,25318722,22305379,75160758,77449485,49050524,58847824,69356575,69052175,45043381,68811137,48691376,28111944,26577652
next_factor _fac2,1,57807995,1883838,27152551,62819432,22367481,25489457,54748607,18371892,60074596,43336831,16579980,78708963,26101542,51041304,60500196,40232015,28323882
.set _w1,(_w1*_fac2)%81788929
.set _w2,(_w2*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_forward,.-poly_roots_forward
.p2align 6
.globl poly_roots_inverse
.type poly_roots_inverse,@object
poly_roots_inverse:
.set _i,0
.set _w1,41942988
.set _w2,41942988
.rept 65536
.set _w12,(((_w1*_w2)%81788929)*1557504)%81788929
.long _w1,_w2,_w12
next_factor _fac,1,1883838,34192649,65864533,47472559,32202660,46455854,18299665,51166265,46148164,40005067,42538512,22507185,19881487,13191717,67317322,1064838,16759432
next_factor _fac2,1,23980934,1977387,58967103,56026958,74557765,58488554,3169619,20142414,28119438,26733415,74787290,67900511,63391377,74641937,67976842,40043517,2457972
.set _w1,(_w1*_fac2)%81788929
.set _w2,(_w2*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_inverse,.-poly_roots_inverse
.p2align 6
.globl poly_roots_dot
.type poly_roots_dot,@object
poly_roots_dot:
.set _i,0
.set _d0,41942988
.set _d1,42958308
.set _d2,28282409
.set _d3,36011086
.rept 32768
.long _d0,_d1,_d2,_d3
next_factor _fac,1,34192649,76852948,45870503,27153147,50722843,53125215,43544278,13378268,50576854,50366248,18491959,52344447,58962465,12062499,19859762,9337084
.set _d0,(_d0*_fac)%81788929
.set _d1,(_d1*_fac)%81788929
.set _d2,(_d2*_fac)%81788929
.set _d3,(_d3*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_dot,.-poly_roots_dot
.purgem next_factor
.popsection
)asm");
aE aS l i2_mulhi32(l a,l b){
l e=an(a,b);
l o=an(aM(a,4),aM(b,4));
av _mm256_blend_epi32(aM(e,4),o,0xAA);
}
aE aS E i2_shoup32(E a,E w,E ws,E pv){
l t=bE((l)a,(l)w);
l q=i2_mulhi32((l)a,(l)ws);
av(E)bA(t,bE(q,(l)pv));
}
aE aS l bW(l a,l b){
l e=an(a,b);
l o=an(aM(a,4),b);
av _mm256_blend_epi32(aM(e,4),o,0xAA);
}
aE aS E bX(E a,E w,E ws,E pv){
l t=bE((l)a,(l)w);
l q=bW((l)a,(l)ws);
av(E)bA(t,bE(q,(l)pv));
}
struct alignas(32)Cache0{u32 v[32768]{};constexpr Cache0(){constexpr char32_t s[]=U"𭾦𰛂𮇿𩾀𩱊𠲄𤖣𭸹𡯐𱴽𠿦🍫𠗞𬇕𰭇𫞯🏌𰶶𧼚𫣫𨂏𡮿🉤𨪦𬏥𲈄𡢔𫍁𥠞𘆺𰩎𰐐𡙜𫆘𞁁𦳴𘃑𠛲𑴟𥎥𒔋𨆲𣵔𐐲𗴥𰇰𠠵𭷓𛲂𣻭𜿀𝨡𰣝𰘱𬸠𥇋𣓑𨿃𰁍𧥨𤘜𫄽𪮞𪰊𦭯𬯇𧊹𪟇𢁬𣈍𨂀𨣡𣸀𑊑𩝗𧜙𦖖𘟬𠲒𩞕𑦪𐲉𰩮𱴇𘪏𥖴𣳤𨘄𛇚𪄼𐡶𑂁𱄑🕚𐃔🮶𤰃𨖎𱶷𠏴𤉛𰊟𨣄𥱘𩝺𥆯𤫭𭜆𡋳𭪧𰆂𭝏𱒋𨽐🬋𤩡𱙭𦧫𥍍𨈵𭕆𗪧🞮𨦶𠔳𬎣𐘖𠢲𨇲𣦙𦦤𔓮🞹𭉮𨒩𛉰𥻫𩃕𡌓𱯱𠷮𩣣𬫩𢊹𘉮𪆫𮖃𰳊𗣟𢉚𞄄𝔅𩿌𱉘𢅟𗌂𧄞𩄈𗡵𐧹𨭰𬹦🆉𩏱𞁆𰑩𰘢𣜉𔖍𧒛𖧠𤰮𡽥𡮋𰇊𭖅𨆫𘘳🪣𝈾𱲡𪧭𢕣𩨁𰁶𡉱𡑩𮂦𩐨𐖜𭥩𩯝𬝚𛊚𠯝𨖽𠏔𘃀𡑂𱌽𬕲𒓙𩌬𨱱𬕞𪑱𔕤𢘌𧕭🏗𱢉𫕏𡊖𐚱𮐂𐍪𭟉𢅗󠅴𫕣𢖖𤗿𱜶𣦼𫅬𣤮𦰐𝢬𦯚𱺦𠓬𘎹𡑶𨀃𩻅𨊵𢗄𓉤𭖌𬞺𰱳𫣰𣃊𥵎𗙌𛃬𣈏𧡰𰳚𩕮𗽩𨿶𦌯𦹶𞠖𪹣𘤪𗉔𩵷𮐇𠐑𥔣𮕛𦪽𓅰𰯛🯂𦕄𩎦𘦒𰈦𒋺𖤖𩑨𩚪𰄩𔕒𡩎𬂠𤞷𨢗𐦪𡦇𡤅𩰸𮔴𡼫𬄑𪥶𥭇𪚖𪴢𣙵𠀌𭝡𠘺𢬩𑪈𰤲𦡴𬏑𪒂𩟔𗑙𗃫𢵛𧄄𗥨𫉎𧭹𫛎𖽆𦹒𬈦𓃱𖪔𭀳𪅓𗸠𪵏𝒜🞣𢠾𣝕𨄒𑋄𛄙𝃮𖹳𬅠𗴂𤆜𮧦𨱷𠥤𢬋𬲧𝡗𮂌𩂎𤢁𱥸𭀉𣁸𢤩𦸺𫕮𣧜𮞴𱺿𘉠𘐢𩅼𗲝𑌫𱉠𣑭𨽟𤖝𢲩𬂎𘘹𗂍𤹥𬥋𦓋𐞩𐝐𝟏𪐧𰻽𗝍𰝕𢀠𣈐𬦗𫢨𢐹𰳁𗛑𰺮𰇺𦩵𣧐𘛫𨨻𤼂𠪉𱯑𒌾𥾡𒌲𖤜𑆙𗲌𱰍𪫤𢗵𫕣𠨗𩝅𒉌𪪆𣼌𣂘𰀺𰛲𫨫𢽦𢗱𥈼𠮺𪓏𮨚🥘🐭𑻩𝀏𪷯𖦉𮨏𐋫𐤍𭜒𩯧𗿤𧁾𪜓𗍲𬿚𘕳𭞨𰘇𬏌󠄝𔔑𤏒𩌧𪵛𠇜𘄎𘞔𬫂𔓑🜳𛁪𣃦𡞈𥌆𥥤𩎺𪟌𣨰𦃨𘘘𥒅𤳇𬒣𥽊𑃤𡑋𮛓𨂤𤌤𩘮𩢔𓃰𮉄𦠸𠓭𤶇𐀤𘌉🠤𱿸𮅌𫕠𠎸𥦞𡖊𩗁𪑍𠟆𫙁𭦅𢅬𔔼𢀷𡨸𓄹𨚏𣡇𫜄𲊮𩥧𫏜𠋻🐮𬩑𠬆𧡼𓌅𗘄𪣭𞋷𦈜𑘸𡥌𱥀🛆𐹽𭪢𨐤𡇓𠫏𡎼𓆞𡝍𝋇𥢿𡫒𘕕𘠦𤱇𢂎𩕛𭤾𦇩𤋰𨅔𥈬𗛯𪶖𧲓𗹻𩠭𩆮𗚢𢠾𠳮𪞪𡔵𬬇𬜇𑪷𩻀𨯓𬥇𨴹𣭟𩘦𮜐𢑢𱇁𨉍𣱠𮑈𭮻𱸰𣀶𩎍𩸓𠫔𬲣𛉅𠔵𲍗𨧜𧍼𝙌𧧭𧀫𫀲🃧𩀝𗘼𘚨𡕭𥑏𘆣𫴱𗢓𦫓𰐹𗟋𪱡𧠛𲆻𪸙𭈷𗁆𰲵𥧔𝤝𢄔𬶋🉡𖨁𐆐𑈨𣔑𐡊𤳻𭶃𱥽𡝗𢀃𣩇𮌞𛉸𘪗𗙨𰶹𠊸𢬘𨝫𨞄𣳩𣢓𪃏𐋐𰑭𱠹𥉬𔒢𦤤𣉲𗀶𖤭𮗹𰯟𤴓𭭇𨉀𪓴𠍔𨁮𐪃𝜴𐿊𢫟𰇼𭈉𨒒𢶖𰟆𦱑𐢂𣎱𭻮𰭁𭐨𣲣𢢇𩆏𱭊𩼴𗍐𝖆𱩸𝣲𪨌𩕤𣸧翺𘇌𪄂𠭹𧝳𰭎𬂢𐑉𪓼𤙹𦰷𢃯𠲈𖫛𒅆𦴨𭦰𡼂𒐒𫓜𰁉𨣙𤦰𫹁𫠝𦙔𤂰𑋎𣅲𮩥𒇷𩑲𤥛𭔁𥋅𠔉𰲘𪥞𘛌𱚉𭎲𬍙𪝈𫵃󠅠🨆𧴢𪛈𱹑𧍕𱢈𭚏𪶵𤦵𤭭𮀫🠔𒇢𣏻𪂣𧯾𣔳𢨺𨮎𬮞𬮝𪁁𫞂𐓆𡡃𰵎𬊤𬫂𭉧𩗌𘫊𛄄𪕽𓇣𦠍𦢱𮎷𨄶𧮕𬙄𦻞𥱴𰵢𐎀𪈛𒋘𤢄𧝩𱁥𨣷𤖝𰩙𓅨𰺄𮠷𱐉𤪭𠥇𮬨𢙘𘚮𑱤𰠜𪟌𫏲𥠬𭎤𤀖𱆉𘎈𝧓𥤍𗥄𥁜𢻠𬤓𧝔𨵄𡂨𩪗𒁢𘉊𪖇𩕙𡣉𘟫𰜞𪝞𩍛𣆿𮘉𠵶🩭𤈧𤐕𘐇𠵺𘕨𰐣𗗹𣡸𢤜𡃚𤠘𭎗𢈦𘙍𝝕𝨤𫶰󠅬𘫬𠹮𣎱🪢𪥗𑇉𓆛𬂵𨉠𢘩𩐉𘱮𑙀𤩷𢳑𩞽𰙡𥖩𣑢𡐨𑂑𱷑𢠒𗩔𒔕𒐐𠉡𝗙𦒧𲎓𣷨𨩉𱦹𦅬𪊋𨲛𰿰𥳶𧎋𧄱𱧔𒀺𡋾𩎓𥐾𩃃𦔅𥽯𫐉𱸃𪐸𫐈𭙮𣟩𩞨𣃦𥅪𭑗𝕘𠲼𡈜𞠴𫥑𘗀𩢹𡉚𡁨𓆴𦴅𥟍𘁶𲀝𔗐𫈒𠦋𨏎𪎆𡘹𮢦𝡫𪚓𢳾𩀉𫿕𨏼𝠆𭃶𡠨𢃨𬋅𫂴𱯅𒉉𤜢𗨓𱍓🕒𱦆𣁠𦀽𦫧𐓂𗚐𒇃𧻙𣧔𭵠𪂹𣽫𢓉𪙑𥠪梅𧠎𖬎𢳺𝧓𝦰𬭚𥣓憲🔝𬳣𦀏𩦩𧵣𗼌𰱞𩐖𩮄𲃂𝙑𱤾𢡙𦾌𦦓𑈿𦵄𭻼𱚬𱲆𞀀𱲭𰇕𢠟𮏊𒃦𮏽𤋭𩰉𱂱𮢨𬢽𢂒𮣤𤶞𘪲𩊠𣚮𤥃𨿤𢙳𩕠𓂨𢱧𱝮𬔆𣆌𘣶𨵕𔐎𛂱𮝉𮀴𮯅𪰒𠓣𦿷𰥨𱑘𬜑𘇊𝂬𫲲𨠻𨜣𝃆𨚻𢜖𡈜𰀢𒈢𢂚𧎘𦠠𬺗𡼫𭫓𥪖𠂒𞹛𮖒𭪺𬐖𭄠𰲻𗑌𗝠𢂌𠡊𧡵𢀣𤊏𠐘𬋕𩴠𝕱𤜙𭣔𢫻𡎍𬓋𨍇𱊚𮠽𢊔𠸃𘠣𒌬𣧞𒁧𓆉𡻬𱃘𰏠𫔩𡥘𭒬𭺧𬲨𤉒𫔅𥜻𭙍𰴗𝐡𢪈𦋁𐰙𤝦𪡼𦫷𔕂𪹍𞲠𱚽󠅄𣌤𣏘𠥗𲍘𨛓𨘤𨕘𭬊𑨌𒄞𘪇𮕧𥇣👙𠙚𨌌𩚸𱲽𲅼𝋈𨃈𩥨𒑤𱦥𦼅𪀂𢏏𘇌𩌇𢨉𡇘𲂈𘭑𘫤𮏕𩳱𬎈𡭯𤜴𤕘𔑒𨱍𣆔𠥬𩑍𬧉𨒒𝄤𰅁𣐫𘬴𦨴𭂤𫍪𢒫𡬩𗆡𭙭𭷧𤭳𧅧𣇞𐙀𧨸𣗙𬍎𑀥𞁤𬂔🂀𘪈𬮜𢪵𰧈𬥹𞲐𪑟𬾻𧏯𤘝𰚫𠩲𨄪𓆽𑨊𤆳𮤩𲎔𱃴𡶵𨭺🠈𧺙𬲒𠨮𰺜𗺇𠄀𤆞𭔢𫛵𮨧🬄𡡨𩚳𗥕𧚩𱁕𐪄𖤞𦢄𡠡𥍴𣁷𡩥𔘧𛈌𗂩𱘘𱔽𪄍𐜓𦕃𣢅𤅂𥻕𥀰🯉𣷃𭯵𤢺𬩻𰀓𮔼𓃔𠁼𩶥𫿁𑚔𣊻𭄱𦏾𦢞𱪺𠻈𣽦𘋶𥴨𧠁𗊍𗝁𬸔𢒀𩊘𣴥𤥲𥺌𦩏𭷸𓊳𡍣𖦤𫏲𫂑𪳖𠊊𰰏𥵙𢘦𫐚𗛮𗈤𦠝𪧾𧊜𪊫𡔩𰜆𪪭𭒢虐𝜄𫨅𥻹𠰥𤅦𪃳𮟈𬒇𠢏𤃨𡴄𠳩𰩆𗴔𡈦𪻝𗨱𬱒𪵤𪧁𥅱𣟅𪢳𡟦𖼸󠅈𱸮𗝠𡫟𗗡𗀔𬋎𒑐𘙱𝐶𪩈𪈅𡾖𫒯𱆧🮷𫶉𰢪𡥚𧫝𢿌𰵻𗀄𣣦𣆘𫩊𐑀𣝫𠝂𮩟𑈻𰈏𮪬𦁽𦶮𱪀𠜙𱆗𩑫𠛍𖫨𰔘𧤌𰘶𫒜𮍯𩣘𪾴𠬃𱥉𮀾𡍍𠐨𧊫𗆗𩊯𞡁𦴋𬏔𠶮𢆫𢦐𫝺𘅥𨬋𬥣𤅭𠻐𧚼𡗩𢊴𒇈𦣉𡖈𪆲𮆣𪄬𪖶𒁁𢝀𤃕𡫏𗀣𦅻𝁱𦈢𨪕𝂽𮁐𧚆𮇶𖾝𛇗𪳑𦨮𬕗𰪪󠆫𤱞𢢓𩭷𢃉𬴓𗐓𝡃𤱝𫟾𦕈𒆽𣞔𤋚𖢘𠘻𣨚𑘍𮂵𒀒𦻋𠂼𤨝𠛍𡄯𡷍𑰨𪱷𬥰𧂵𑐓𡢎𘙑𣧏𥙕𦿯𥔅蚈𠢩𑂁𑘦𡍼𠉙𑆳𓋆𰌀𧈫𘝤𒐰𱋽𡊜𤪙𧁈𘮣𮘟𠉏𖧭𦪣𐨯𢪁𘒹𤠥𢯧𱡶𦐘𘔥𫗥𒄤𑠡𡷌𣕡𰆦𮔎𐾰𰥣𡈄𝙿𬆎𑩥𒊭𥺱𠈿𪰩𰶤𰇪𡼽𬙱𫓣𫺈𱙅𦣊𭋿𬕏𲁊𣔖𪆖𘩍𦡤𛆭𦆍🞘𨰊𭠯𛆚𨂦𗈗𦇴𫟅𫏕𝕖𮃠𦷨𘤑𤅂𨝇𤸢𐆆𥉪𨄁𝄳𤣐𫪊𥖇𫰂𰞃𧣼𢠩𒃦𣽢𲊕𥤈𱸜𬏲𩯢𡢳𢒯𨉜𘀍𬰼𐕍𩫀𣨰𰼱𦛃𠶮𐡎𑆺𢩡𠔑𫀲𮉐🂊𛅶𘆽𑤸𱀶𦍐𱜍𧕠𔑖𩡨𰉚𢏉𤠦𥔚𭔼𬑕𘄼𠬙𘀥𩦋𘂑𘴁𛱉𘛰𮎠𝐑𖫗𧕪𨱐𫼉𠙥𥉨𪐌𜽡𰎶𢄔𪫯𓎐𒋞𦻣𝩲𱽋𢐈𩴉𩕄𪗇𝁾𡳘𡮔𖦵𫄐𤹕𘓓𦐬𧪮𠽭䘵𘰈𱩀𦮑𮝰𨲩𨯶𱩉𦉛𞓐𭸉𪯵𱢢𢪘𡬁𧍤𤚊𪊪𥥜𩩩𢶫𐧀𝚣𪫡𗑧🞰𧬉𰌒𘴇𧥮𤎴𐍣𡵙𝄟𦸚𪄵𐠑𱸐𬻞𬽑𩰽𖽈𮁍𬤎𡚨𭜨𤔏𗺟𨣶𩘱𨰂𨳵𡑠𒄅𣙠𗺮🀳𭓐𠰼𗺾𐼕𡂢𢢤𪪮🐱𠈼𞠮𢈠𰁗𢦳𦈡𡭂𨜌𘙵𦅰𡈘𰈈𝈱𱇭𱥹𮧄𬁡𱾣𨔲𑿜𡽨𐹧𖦭𤶵𣆩𩀐𬵚𑲃𧛗𦐄𐋭𘎐𩂁𘯠𥠦𘙑𰫤𘗭𦣁𢆢𭤀𭗂󠄔𪍠𤚖𘣕𩯂𰮘𥈀𦈃𦂴𤹩𨈍𠮈𐬮𱍻𑌧𱶻𧠇𰐫𦡲𞁓𰝹𩾆𝥅𣒍𒂤𝁪𗊟𭡛𧑝𧵋𬐪𱌀𦤓𒃻𫵩𮗨𣲂𪃽𡄋𭈷𢐟𬅅𰵧𱸄𫖓𣙆𝁦𧢝🆑𒄣𰚲𠬮𣎇𖠻𰜰𢦥𪓀𔕹𰓮𱭢𦅈𮃊𨠕𫮄𭒃𦡓𮈤𝞹𥥠𱱷𥓶𪨘𤛅𭯓𣀰𰤒𒁚𗗑𩅬🃒𥒶𗹴𧎪𱚅𭋘𩌶𨑉𘧴𘤬𬍰𨉩𲇠𨾓𐔁𡎒𩖳🖘𗎁𥓹𐡎𫯬𢉖𘖨𩛗𨣜𗭗𣆦𠊇𭸨𡍁𮘏𐦄𥑌𤘣𩦃𣘪𗤢𔐶🥸𦹏𭁒𠇥𡾅𲁉𣙂𣔎𡈸𗎤𭳴𤔋𣒠𧎟𗑚𦊴𧂬𭬊𐓃𤢬𐍲𨟢𬀛𬔰𖼴𡁟𑒏𡾳𢀾𪼞𫩶𭫸𣕬𱰷𘇇𩐎𬽱𧭆𭾁𫩃𥛃𣺯𣑷𰁠𫭘𫦯𰫤𧹣𱉙𭊤𢸬𥓥𐕐𤺣𪯺𤔎𧭍𨵒𠭭𦪏𛅶𤧝𣍵𡙬𫸺𨖪𰁀𤃶𩹛𡦲𦭄𬇌𣕟𢃩𤵝𢮆𩵘𑒗𒀮𤪫𱀤𭝢𥏚𦉭𝢓𤁥𛇞𑘱𨹄𣛉🭈𩡞𦬘𧂰𤺾𤅅𨧡𠪸𘧟𤕜𑑅𞅉𰾦𢻳𑣅𐓄𑴺𗃲𬥐𢨍𝁕𰨀𫠴𑈞𓄷𣐊𦦓𢿕𗡉𧟔𬉱𤰘𨂯𫏸𠭯𰽗𩂈𡐔𮜬𥣤𐒱𢪎𭮗𨲞𦠇𘨵𑙓𩶘𦭭𐌠𒂶𣉇𧆁𠣡𨄡𘏮𘯄𥙀𝞯𩕠𔐅𓋻𪎈🠭𤣉𫕓🢀𢈱🠬𪉼𣷠𡷎𬭰𦫷𠷡𣥘𘎻𖬸𮧼𱦊𓂡𢒌𠧞𩲣𢦹𨄱𨬦𨬄𛂆𘡠𤀻𣑁𭷪𪚴𣪅𮥜𨰺𱶶𡴏𬶃𥷤𱒥𰈟𩘗𦑞𥰨𫹑𡗫𰹲𢐅𗔍𣀆𝡲𦌴𝒔𢁨𡗈𫨯𠔎🆩𢙯𒄚𭁽𭟪𪡣𨊰𲆾𧵎𫚗𧝱𭋛𠒂🈪𩉠𦖻𑩃𠌄𦈊𘄙𩡰𱖗𧍊𢐲𒆙𪥠𱂀𪎚𣴱𭸤𑌮𧪕𭈌𲎥𡜂𢰻𣢩𠒅𣎖🧩𤹯🆌𫃃𬘭𠳂𤈠𪴔𰾄𧪊𠺂𬐡𧀍𠋫𐅜𫄰𐖇𤒘𧞥𦹊𭀧𘠦𫸣𱷒𘃡𠌲𠨥𪥺🟘𫇇🦌𗍥𦣁𠂶𥨨𐔄𘜵𢓑𡖖𦴿𡇂𪡮𭬭𮁱𤴽𱈓𐹲𦕯𣫺𮥶𮮙𭃞𩮩🄌𱉙𥁥𫕋𠶁𥺨𦑌𱒳𭀷𘆟𱸈𢆎𤆑𥣬𬮏𦖭𩜙𗘮𮋟𘤘𬱮𧠳𗭝𭱍🅫𖭂𬦴🦕𘯑𮉍𠥥𑘘𝖤𤐄𠚓𧩄𑚠𫑊𣐨𢌕𑧣𗞥𩥽𠯚𡂁𠴷𪫡𱯪𠶹𫣠𣟸𤮕𢞝𬆐𗤣𢜩𗻭𦳃𢣟𝕺𱛛𤟑𪒼𑨕𗨎𠢱𠛩𱞅𧰔𦘴𩭵𪡓𩶴𒆇𝡩𬊼𑫀𰢸𱙧碌𧮼𢅣𬭻𮠊𠅺𗐭𛁩𘘑𩜅𒋚𰏝𭃯𮡚𖢗𭾛𲄍𤰨𤶉𬄞🂬𧬶𘓯𡴒𭔈𭒎𫉔𩠎𤀡𮃲𬵛𥁧𣊲𤆟𢜇𘁣𡚵𱗒𤤼𫢻𭮟𭈆𱠵𧥾𢶑𮮙𰛑𩔖𐨌𠭳𭉑𤢴𢕰𥥃𧆼𛱨𢪃𖽺𦶚𐮭𢫌𬿚𮍅𬧭𝝯𥔡𠞈𘖳𢫏𤁴𬽄𠫞𣮽𣟋𢃮𩖴𡴵𝼙𣡡🅸𠕹𪨃𒃐𫴖𥺯𬃥𢀭𢮛𤈇𝅧𘃘🠆𐙋𭁖𓊆𥨋𱝃𗈑𬃓𦎑𩥵𡱛𢋛𧕍𱯚𭳃𝒢𱍤𧊮𤪵𨹫𡎪𭢦🆬𡾛𘆧𔑡𤢂𥅍𬸗𓆴𐁊𧚡𑃞𮞰𑪀𥳐𬴽𰠙𝇞𪥮𐦡𦛁𘅞𪱼𨧖𨡥𩇴𤫊𣳣𧗛𭦲𡻄𠱵𤈦𘐍𤫆𱄒𨺚𮙮𘮓𬬠𧑼𬤚𦬧𡻓𨥰𩢫𢨔𛂚𠡀𪂽𢠣𡵧𝍎𐒢𩼰𝝐𠫶𗘻𨠸𐘌𬅠𤼚𮠲𲋕𘲪𭩃𨼛𦐜𮋦𗉄𑒼𧩚𠕩𬎥𱄴𪹜𠂊𱮗𝗦𢭤𱦑𪋨𦮰𪳸𠴻𨜪𞋗𦚻🩒𖫗𣌆𧕜𲉓𤾊𡬎𱹴𰃶𬛁𒋿𐅤𧌲𤇖𱦫𪎒𧡐𫄦𬎒𓑃𩭛𘪵𓌷𨏁𑊁𗟓𥇠𧳐𞄈𧲧𑼸𐰒𦆂𦟀𗡨𥼶𣒈𱕊𣥊𐍴𡶅𢫐𖡵𢚬𥋖𫖒𤵍𰱃𨞪𥯒𓂂𐂲𐕌𒌐𢠯𮌈𠯑𩃥𲊀𮆪𨾾𦭘𣔏𓇪𠕤𮂱撝𱩷𑩗𗳒𞡬𧀕𮜕𛁴𢏇𝼥𠇿𛀊𡐜𣴓𫐫🛌𓍑𝦔𥜇𤚉𪒃𩪁𛀘𓆔𧣵𥃓🅯𪢓𣣧𡜽𩋡𲇠𠒸𠺥𐧦𰹉𢰤𢵐𨚼𣎅𪂨𤝌𓄠𦡺🝻𧓡𢬐𩭈𭞆𫐸𦒙𰾪𗒻𦓯𑚥𬎒𫰯𘋏𧋷𧿣𥯵𭁋𢴭𠼖𤻖𬂞𐪆𱳉𡠣𠞱𥺦𪏀𣎯𥩢𩄝𥸆𐅒𣗯𡼥𤼴𣕒𧀒𥇪𩦰𤥦𪧣𧬢𩨣𤵂𛰢𬦢𠬜𲄐𥚅𥪧𱓀𥞢𨙱𱇋𢩴𢕎𡱏𰬗𑣄𘪲𬲭𥧝𱔤󠄵𠳐𡄦𲊂𝆺𝅥𝅮𭕟𤵟𩱫𗣍𪶷𥛓𘕢𤕩𮏅𬷙𞓜𧫼𒒸🅃𖪻🎩𓁪𤂚𦈦𓄵𧊰𲄳𪑧𠫎𭏵𬈩𖬑𤬍𩔍𣖕𘥦𐳽𱟞𐧋𦨺𡓶𘒀𫟀𒋩𞢔𞠊𡞊𒂠𥢶𱐓𗪶𐂼";uint64_t acc=0;unsigned held=0,pos=0;auto read=[&](unsigned n){if(held<n){acc|=uint64_t(unsigned(s[pos++])-65536)<<held;held+=20;}unsigned value=acc&((1u<<n)-1);acc>>=n;held-=n;return value;};int offset=0;for(unsigned i=0;i<32768;i++){if(!(i&255))offset=(int(read(12))-1024)*512;unsigned q=0;while(read(1))q++;unsigned z=(q<<15)+read(15);int h=z&1?-int(z/2)-1:int(z/2);int x=(i&1?624866304:609748992)+offset+h*2+((i%4==1&&i<16961)||(i%4==3&&(i<1155||i>=16963)));v[i]=((int64_t(x)*-78)%81788929+81788929)%81788929;}}};static constexpr Cache0 cache0{};
struct alignas(32)Cache1{u32 v[32768]{};constexpr Cache1(){constexpr char32_t s[]=U"𗦀𤃳𨚳𠉺𭏽𨣅𰱁𑠔𘖉𢂓𰌍𨡸𝌕𓈺𰃨𢇜𩍜𩤹𐦦𦔈𖪄𠵶𥚪𘀃𦯂𘯆𗏨𢸉𪟲𥚊𒁏𢚺𮁺𑣊𛂅𤮘𮥤𦫂𧀚𪎠𧸬𝆧𝌢𫴅𧲉𮂪𗎻𫁸𠳞𮝧𭠹𦞰𢣒𤉆𢢇𡌊𬢜𗦦𩽱𝀅𞴺𠩓𱳿𤹌𮀬𮏳𨓯𱃡𱫡𱒈𑼱𘄟𘟍𠩫𧬐𘚊🎱𨜪𒔆𨲥𗝨𪳪𮂭𣏢𤴨𝌽𤓸𫈘𮟢𫒣𪻛𐱃𭇢𐍡𑗒𡒚𡲦𠮩𭏅𘙞𤼲𫊭𬣪𛱢𑜱𘁻𨛖𝪁𮅸𲈊𰂾𝝿𩔴🪅𥌆𢚌𝦁𬓝𥆢𮀝𪃋𬎎𦻠󠆫𠢲𨩉𧑽𪹶𝧗𣞣𐎄𱑈𭁓𠨺𰏍𱈉𱶸𱟲忹𪪈𤣘󠇒𤶩𰱶𧣥𘧴𨤛𱀤𬹗𪌚𣕩𮞤𮔒𐽇𝝜𘛁𡿳𐙟𧔞𝢎𤠩𨱊𰿅𱼽𭆹𞱼𥥚𱤤𰷹𪉰𣖁𧫶𧡼𡂀𨵩𱝎𫷔𤁺𤵬𲃚𣱔𗲙𢽀𨹝𝛇𮢄𧀖𗜺𮀰𩒥𩤘🇪𲋙𣽫𭊒𥽍𦃮𭢵𒑩𘇄𑈾𱱫𨭳𧊬𨸘𗰔𗉭𧌬𫦒𫮷𤦊𒁈𦟋𤤋𬷘𬶓𗔁𩫄𪱉𣑭𤚊𑖸𢔱𦞉𤐓𭤥𤾤𘐢瑇𱙂🔂𢀐𐊲𫤀𨒱𡸎𩱽𤋟𒀙𤳎𢋱𱰓𤩗𢪯𢸱𠫸𗂈𞤺𮘏𩉂𗄔𭋣𥈲𑢦𱳮𨏿𑇪𰲑𒑙𪅠𡏆𗕭𤨏𰁮𠠇𢎠𭻶𔐗𥼏𖪀𢣞𥆱𛉇🆟𤐊𡵿𠫁𖺕𥝖𒇦𤾚𡌲𭈇𭾃𭓁𪰍𠄒𫐐𢻨𒓓𠂾𨚙𦺳𞠮🂨𒓉𬇺𖤞𦿊𢌍𩢅𧚬𐎹𫔮𝇦𱖊𨼬𬋜𰵿𤊕𰙜𱫁𠳤𱠏𨜮𪸉𢲬𰖤🅘𩀤𭵋𩊫𬊑𪈄𪒐𰐗𣫑𡳆𓐋𗲘𰃩𭵮𬃄𒋑𭶊𱳒𱔪𘡦𗈣𤴯𠅙𢏵𐔍𦿜𨫎𢎡𱺉𰤝𥼉𤇱𫩚𭵩𪴺𥕦𡄈𩬜𑶥𨥕𤍳𨑐𭂛𒊫𱱍𣁠𤍔𦖆𱢱𭄡𣓏𦹚𩝯𰓁𩀄𮈬𨒢🢔𫫞𥒜𘟥𨲽𬉅𪆫𗃈𣄽𲍙𖫜𱻝𡎊𒋺𰼩🦏𬆈𨤥𡳢𖡶𑩃𩽂𩚮𲉐𬤅𤰗𣘗𤸂𑠬𠸹𮃕𝨱𢎴𑁒𦖨𰈏𨨥𩆜𦡟𗬌𨲌𩴁𑨧𗮐𑰜𥲳𤹎𨊅𡛀𥔬𘰊𤭁𐧁𤞋𦭢𤼜𧫮𐋆𮭨𱒆𥍣𭅏𡁇𰶥𮆄𨔎𔖲𦷙𐘻𧪏𱅭𰣽𝜔𥏥𫁈𪉽𱻪𪼛𪊈𱦦𫐐𠃐𞓟𑁒𰣺𘬤𢓕𤦑𫲹𠛶𡛔𩸷𨯭𮍅𫥱𦞐𡍯𐐰𱄵𠱡𒅠𪴸𥌗𝨭𪒺𤃢𫙠𣷎𮃺𧚩𰧺𪦹𠀇𩶡𬨤𨄊𦈽𐇚𝄒𲍥𡘥𘱚𡝥𥚍𗁨𭏦𱥀𤀘𲃦𪢵𥦐𗋕𤇀𘜺𧥆𗠬𥩌𡃦𪗨𱝕𐬆𫹑𨡦𣋝𨜜𭠆𧦦𨍮🌌𜾉𑊈𝡝𣚯💜𪺌𛆇𡗪𗼚𬛴𘝪𘖕𩴐𭨓𱋑𨱦🢑𥛈𨝔𣯁𬛀𤗶𫝐𡶵𣗗𲂪𤯬𡮌𠁫𡋡𪂫𡈅𰖪𢩏𣅀𣰅𰭑𖥂𢅟𧈯𮎰𬕶𤕆𢍌𣓏𱟖𩒩𧀫𪸰𝒮𥠇𥐮𫱫𤽳𰬲𪄧𨣗𧃋𑨺𬎈𓎃𣙰𦐇𪿈𨀃𨂀🚻𐼖𭉄𢛂𫜍𱦇𪉀𬢜𩂿𣴋𢦅𤚹𔐗𘧥𑰶𥠴𧘀𖠓𠐲𘒟𠠬𰎴𩢋𣕛𦐬𬁍𡶰𪈖𣋕𘉊𫇞𖹃𢐗𬝑𣂨𛂓𗙵𗮅𤖶𪒜🡥𞤩𦍯𘐢𗆮𨰏𗨱𨧢𒐗𝢢𦹸𠘫𭪒𩈤𬢼𤏣𠔹𧔓𔔍𮘲𨶮𭇳𦐮𗕩𢽙𗉊𥻁𐭮𘘜𭩋𧒴𡏰𓋶𧯘𭠾𡡮𓋏𝠵𱿶𡸷𦔴𠞔𓉼𨦖𧦨𘙿𭓘𘑭𩁞𣀉𢽎𬍢𦖦𥗢𭇨𭦟𠧉𰣫𦴴𝡉𢽱𤶚𥖥𢒼𨠦𰔥𰅵𞁈𛈶𠵚𠁤𡈔𩚵𢄏𗩱𘒮𩐛𱚴𘱅𛂘𧐒𪠀𘞹𭩾𫦌𖬊𘭔𤄽𱗚𬭔𪨯𬶦𩒪𦶅𱀩𰑤𬀠𥰽𒀹𪙫𰥴𐨝𛁹𱦁𠵆𡣰𤰳𨡩𰆫𡭉𫆚𓁫𢟅𔓇𗻿𧶠𡪫𧢨𐅣𦟀🀞𚿷𠮚𘫢𐞭𢆶𦩮𨤟𝞍𱖈𗥉𪱾𐧛𰲇𒒄𑩁𦋮𱔟𛉛𣜩𰦪𐀓𪍮𤍹𨾗𡛗𦘞𬱪𰙦𱑺𝚋𠝌𑽔𡍒𱄉𪎧𧸏𝀡𢅅𫖍𐛈𡫆𰷻𮢜𑂇𢿉𑆠𰊂𫢀𥫖𮃙𡵱𡘤𪖻𠁾𤲎𬴡𱠓𦌫😟𗢄𫦨𱤩𐚣𑪸洴𝒀𪭆𬎉𰨾𫓰𡚪𝠳𑚐𱪜𭚘𥟑𓂐𩷽𰽑𭧨𱂿𩪂𢔺𤲶𢛅𝩸𬡕𗎝𤮢𥉿𝞏🏌𬂱𩩒𠪖𭊀𝅗𝅥𣦡𫁏𠖦𥀼𑥗𖭥𦊭𮩞𩃀𱆷馧𧽵𘉒𛰂𡋫𣫂𨦿𪄁𩂩𧈷𩬷𱊬𢈮𣙓𪫱𡵰𨈶𫺃𐰵𮄥𭌻𮗣𣛅𱇥𬱴𥦢𨅮𦇑𥊒𣏫𐱆𘒲𬕛𑑘𱗈𞺸𣐳𒎃𠙉𛀼𧱷𱫨𣝡𮧞𡏶𐑀𪐐🪫𲉙𠲿𥾕𦺎𤢠𦲍𪜞𣶠𠮲𝢓𐇔𬽐𮔋𥷌𗶜𒐵𥀕𔖡𤻤𑧓𤷼𭲗𢏼𣑝𭵚𰢚𤻂𪸭𡳸𗝻𢤢𝁩𱙶𢏡󠇉𭈐𠎒𮓑𢹁汎𮤩𑿛𰟉𗷔𱾵𘌗𘜖𖹟𤽎𪻈𠾥𝒱𱴋𪈝𬬸𪉴𝋏𱰇𡳑𰢢𫗏𤎌𮣖𩮲𭟑🍯𱍟𖢃𧸟𘚥𣎇𢹌𞋳𦜍𱭴𥅋𒀉𤹌𩼘𭑥𫒈𲂠𨬕𠦟𠐲𢮁𡟆𰎦𐚨𥠯𤴆𒃫𝢟𒊐𢔼𢞼𡅞𧲧𨡥𥋋𑇥🔥𒒫𬩬𲊭𠰹𰠟𬧃𢙐𝖻𞣃𥻬𢬪𱙽𱾈𬲘𤒗𘤚𲈗𘆭𬅭𰛧𨆇𨼪𬻭𠉒𩜫𝑒𔘻𡡍𭔂𢘋𪸴𱈹𪍢𗤆𦘰𲅽𧘴𘎹𫔫𩄮𱐂𰀿𩨬𞠃𥽐𣗧𬹙𤗠𧭺𓑎𡂘𒾫𩠄𣔀𐞫𢆻𓐣𥮱𤞲🐴𦐻𣤙𗏵𧧾黾𢛄𭚟𐺆𮡬𩤲𪢗𦦌𢰠𦅥𫏷𝡌𭒆𗘥𰗉𔑟𰤕𭂘𢉢𱸱𠿵𨓎𗷜𥙗𜽶𢊆𥬤𗆂𖭯𩥠𱀤🠝𨒵紀𤏯𠛨𭽳𧍫𢩺𦅶𦖊𨔅𨍇𠜀𒉜𩢪𪕞𫟊𥥚𩆉𧵗𪧞𰠒𦴋𤤁𧄝𛆴𱕃𓄶𑂍𮀇𘙘𪳌𫇞𬑽𦡘💣𦧯𱄯𭛭𨆥𡭿𩪭𗜂𘆂𫗝𣍘𤧱𩽏𦖩𨢤𣃮𤣬💵𦼹𠵩🦿𪸫𖹵𗄺𪂑𣘒𢌑𗐣𱮴𬥺𩒪𦎆𐚽𝀨𖢠𠬇𠘼𩈖𡈧𒍭𡒜𦷊𦳯𭖓𝘵𑒔𬤄𤠹𩪰𐄧𨤴𬄲𗏨𰵷𥟁𘃔𡻣𠪖𥅻𤓤𣪲𧂽𨁙𓎤𥘶𝘊𧭸𤍦𨒌𦕟𤻨𒃳𣤨𨨇𣊆𰣣𢒼𠔵𝢠𝨏𲋶𤦃𩦒𱅞𨣳𣌷𱔊𧧏𐘗𨲭𤀃𡪓𛈖𣦌𥌦𥋁𜼸汎🗧𱧙𥑮𨡵𣺇🮖𪪲𪏥𨗵𭶢𡅈𧘿𘀄𧝐𒌇𔐽𝘡𬜋𝓞𢇚𤍠𧙽𰮢𗔼𐅸𦘬𝀆𗉽𡘥𐦝𤁝𠆃𬪢𫘴𦺄𤅝𧑆𠠱𓊘𞡍𭦔𝄱𢤄𘡍𝅩𧺑𘦊𬉘𥬧灰𰮑𢬝𖩘𪋖𡆓𥥝𧭢𢫡𢋐𪜯𫣮𥟤𭨔𮊲💪𝥊𨑤𤃕𬵺𤧅𘤥𦦓𤤼𬻚𫩍𘧘𗐾𗤬𲈁𧥩𨁀𗩹𤻢𘦯𖦣𱟶𫒟𫎔𢇩𒒋𣩮𗣉𦪷𠝨𩚬𑖨𥾯𦳚𪀚𒁳𝛌𩒘𰀸𫔈𰫴𮚇𱖎𤡧𑁦𰵆𞣔𪎲𡜔𖤖𐀞𗳲𣫞𘓉𢵑𢺹𣚁𨜢𘤟𣓳𓐬👱𮦂𤄭𓂡𡙫𤓴𩊝𮨓𢸋𲍲𰬩𩝍𮚕𡁷𭮤𣘂𬱍𡡣𬀚𥂮𣦥𠻥𬀳𫠼𠭊𧈪𱄠𛈘𑇈𠎊𘈶𣝩𥨇𧓒𠹠𮑭𬏎𣈺𡶄𬐘𰤙𣂷𡑬𫍰𣶌𡁫𲀬𓐎𘍈𨻲𢴗𤝭𣴩𢂪𤈍𒍄𨖸𩟜𛂑𪁁𨹈𮗐𫂮𘢬𤥀𦨡𤠵𔘐𱔄𢽍𥎆𪖊𨎌𞱳𢭁𢌆𠻻𱠗𣩫𧷈𪒵𩛪𣪄𪁷𗣔𫍳𗮙𭱂𨈋𗵬𥜓𗓇𛈡𭆦𤝃𒊼𰴃𭉗𱋌𑁋𥺏𱘄💷𱾿𥢂𰟦𰩏𫑃𗠇𑆃暜𘬿𧱤𦇋𤾃𱑐𪝰𒈻𰄕𡰔𤺱𨢶𖬎𱸫𫧒𗪎𗀩𗍈𢤕𰋅𦜻🬥𧉉𦺯𤇃𫑤𨓄𦌨𢮂𲄓𞀃𭖡𫡀𨃳𬪙𡪌𗧺𓂾🠭🐤𰊭𠛕𪚏𢭢🟠𐼃𥼎𠬆𠜈𡇋𡐊𰟮𭋠𤋼𪷥𭢇𡜲𭡆𨆅𨖐𩒋𧅮𪆭𠩈𐫅𢫷𮕃𑲆𭳴𫊡𤘰𗑞𰿪𪍴𡹻𖡒💞𪋄𫆨𬔃𘢚𗦐𮑎𨆸𮍿𱖒𧮪𭎉𤳨𩞨𑊓𧟊𩮸𠌇𑫍𫴶𝚆𐺧𰝭𣍌𓁜𬠉𩅫𐦓𨄯𪣦𫂍𣔝𰁕𣴉𠰎𩞨𧓍𠩻𛇪𘚫𧼰𡪠𤰩𰗄𭜦𥄣𢹵𰼃𪑒🍳𗧸𔗔𠵼𠮩𭚎𥰤𲅣𢲭𱖄𢏊𥗸𬎕𘂷𰠼𫒀𔖭𱇐𠆪𗝲𠆟𭴽𬁉𪠞𤌷𢹾𬚍𓂋𗦡𥴈𩩧𝧀𪁧𨿓𑰑𘋆𣟖𩰌𫐎𩑖𘰧𣍉𱟾𰁇𭙬𫄖𱴴𦫺𤯁𱡽𦝭𭗄𠉳𮣼𔘡𘪃𗌰𮤠𱄈𪧡𰗘𢢥𬂁𣀩𠬋𢇘𒑒𣴜𩍓𑰋𱴄𪤨𲋌𲇛𘊉𮕒󠇨𪽟𓃛𫀬🂏𥟸𒋍𰮀𩝲𤡅𑘼𮯓𠀿𗧅𫔭𮝠𢴑𠿐𘐮𗛋𢕡𣊥𦾛𠶏𝈢𐜄𮈁𨕊𬳘󠄍𩈯𭜀𐧷𢜕𐘥𗜨𪋘𤩚𪎉𰽰𒇱𱖠𱽊𬠧𭗛𱖜𣌆𗚣𝝽🐩󠆗𐫒𑤃𰳤𫬞𧮊𣆪𢥒𤭹𱀚𭩁𩤽𮫷𣧘𦴊𡅴𮫓𥁺𑠬𗗅𖢎𰃪𣳭𧞅𣜕𝟨𠴱𠦋𡇣𫗷𛊩𭅻𪄑𡤅𭑥𰰬𑄢𦒑𘤝𭐍𧨤𘁫𠸬𬷶𪰳𧖈𢹼𬡫𠾑𱜇𥑑𩕊𱹳🎉𣋌𘰑𪐁𖪇𘀢𱼸𗄩𧿲𤓪𥶤𩛅𨃐𝍀𑆞𨴄𮃡𨌎𝤠𫖃󠄍𑍗𞤅𭣘𗁞𓋤𒁛𥡕𨍢𪘥𧇏𣳑𑴂𝀐𘟩𡔻𩅋𪮋𨷔𩋳𢱟𝟻𡻑𧇩𐇫𪃄𰅛𩉌𥩉𰟣𓁴𬦚𐜚𠛸𗋤𥎈𠼘𮤖𢫽𑶧𞢎🩳𬯞𨰢𒂅𩳮𫇥𝣡𣮅𩀊𘞊𦩆𡹼𥨲𤋄𦷾𡕑𤣟𡿂𝗦𭣍😬🉂𨼔𠢓𱔓𣥌𬟑𝐺𫊙𬩃𔑇𡸜𥇓𡿦𒈟𥠟𘣯𰠽𱽞𪊬𣞚𥝊𰞾獺𩢂𐠝𘝚𒂶𤨗𐫚𡌴𘤾𥅍𣩜𢊹󠆢𦿲𠯞𩠀𤳱𢇺𪰦𫆚𨖲𱰹𣸉🄺𖬫𠣆𩛉𨆻𤉗𗗢𣤣𤖰𠺛𩙙𡍿󠄬𩍺𩕍𢗕𫓶𘞫𥉯𢊡𡇮𑴃𪵗𦒀🦎𫖀𑠸𱼁𭺕𮠋𣣲🎐𒐂𤃷𱥽𗙋𪎮𐔚𭂑𣈺𡮟🚆𣏗𪚓𦕂𦃽𦀂𓌖𰖡𜾃𭠰𱟷𫃃𗔔𢟕𝡂𗽀𦗡𣉖𞁔𰤨𖡵𡉘𦈥𰪌𪹋𪛌𓂦𬞋𢵹𪸘𞟲𥶕𘯰𧳰𪋫𢆜𘞞𠒌𫅐𭬚𭢩𣋂𬣒𤽚𫺀𬅯𛇜𨿉𗠫𭇴𘮰𝘪𬲥𡎦𔐌𨹰𬁨𥿾𫳴𭬻𩋐𥛘𬜬𒌟𨁯𢥵𗆠𡺗𭓸𦈫𦹶𘚽𩰍𥟴𣌢𰕧𭩊𧂄𤽁𘝛𖫚𪊖𱔻𲄃𣃙𬄺🨆𭜑💖𒂨𥵄𝍇𤧺𑆾𱟍𗛓𢋛𐰀𲀾𓎋𨽚𝆹𝅥𩸸𪄯𱈔𑥅𭟇𰪢𭕉𱐰𗳁𥍌𰑢𪿂𐇪𥸆𝣡𞸍𦐰𰝕𠷧𐊨𤱨𫒘𲄶𐮊𤷴𑤳𡠃𓅕𒄿𰒦𣥉𐌍𦁗𬅇𤾐🪸𡰇𫖀𢜥𑐋𘲀𥤹𡓡𢁋𬶐𤖸仌𨬫𗴂𒅛𦬒𣐏𤃒𣪙𱢸𣺕𒑠𩩴𬥓𑬈𰌛𮥚𘰂𘕥𰇘𮀮𦸜𐾰𪍙𔘊𐴣𗑒𘛗𠯨𭡺𠲑𫠈𘈫𨲪𠳊𱛵𣟵𭣧𤒙𢝔𡾯𘖈𥍦𭇣𝘖𤑜𥔙𰸇𪦓𘊤𨰘𑴳𭆧𫋂𰅢𡿾𥱿𪤎𣩮𪰸𑍝𣜿𐃍𢾡𫶎𩟈𝀑𗲸𰌄𣻊𫟱𝕘𭌯𦳻𗐊𤖉𤌞𤏇𞴼𭢢𗰐𢐸𦎨𩹦𣁪𤄩𐕀𗄘𓈇𩊄𭈠𢋓𘗫𘲑𩛢𥈱𪬊𰆪𣉃𗣗𧪽𤇢𨴦𗸺𱲌𒈟𗒙🟧𣠤𮇬𧜳𛋠𥹸𘛁𮭦𰝷𱃍𑒱𩖪𩍉𨍺𥘒𩡍𠕂𣣻𪴂𒿨𥜎𦺔𧢻𒈝𤔿𫭄𢇦𡉿𮚾𗶓𐴶𨪭𠻩𘔣𠹑𰄓𘙄𭉢𑐹𖽃𐔝𤇗𱚙𒅣𥾜𑦼𗪬𭋟𱉦𧎱𤑊𡀒𖦿𛈴𘢺𨨣𠰆𣼺𫊪𣯄𨺧𡴄𡤐𐼣𥣔𠈢𗍩𬺽𦋫𮝈𗴒𢀓𘀠𧋍𝑮𨲆𰙅𘝰𣏈𮦨𪖒𣅪𩈬𖪗𠻟𣲄𗳉𬚚𥌧𣽗𧑋𡄭𨸵𘥘𝼎𨸭𭞋𑩪𮐪𤛔𦘡𢢸𬦉𫕶𗽒𓈙𬫤𰗜𬣉𰢮𡃸𩵯𱋩𩘥𠐢𤰩𨞰𥎊𰨗𰧋𪲆𢡪𢋑𫸸𮊜𪆘𫂟🬠𔗂𰢣𱑨𦲀𱌈𛲇𫘂𤫼𑧓𤣽𝧔𐂆𪟨𐚒𝥃𤯘𧤐𘪦𮣜𑄎𗈽𘠈𣌅𩡽𑆘𣫔𰄘𡤺𑐬𤷊𨑤𦸟𱴩𢀔𨪳𛂟🔝𝁰𘦦𒅿🀪𬐦𲊎🅘𗽖𥇴𭳩𗧢𐒆𰶕𫼦𫥣𥮐𝜬𓐃𝌎𭋱𰭤𲂅𩁬𣺜𑐖𨌶𗲋𩏫𠂈𘂑𛁦𤆈𠊊𝖥𫓚𘇮𨈡𪊛𰍠𰗱𦏊𛰾𥛐𥝔𭡈𠆭𧢭𪡿𩸃𤦪𬖽𩷐𝨷𬖟𨅲𑴪𢼝𬅓𘪺𪦅𬑕𱧤𤙹𗈃𡢀𰷚𩝜𞓩𨠶𢄊𰑊𦖤𡹍𫩰𣺴𧄈𐀱🀥𢕀𠦘𐋉𰪔𐽀𗩥𡢘𣭀𬭾𪎒𑗙𓁝𬶮𦹵𦎄𝃍𧖃𣫆𣶴𡘘𘖢𧙣𫋌𠞊𱦢𫌲𢆱𲍩𰕒𰙀𤣐𝩓𘢪𰲽𡓇𮛡𝄚𩹑𦺁𫜫𗆈𤽑𠚻𢗻𭪃𠎿𝪂𬠠🠠𮑏𝣐𠜸𣰬𑅘𔗢𗁷𑌰𥚚𢂯𒋳𢫯𥙟𒁣𥶕𨔂𥙢𤗼𧘤𨹌𥑝𘧻𢋁𥲑𬍒𣟷𑠳𦰕𑪔𛇖𝝪𣪨𝥞𨨬𡮺𐎃𬪺𠲄𪊕🞽𢞧𞹤𡺡𩌉𢲇𡓕𦯭𝛸𤹮𰞿𣫪𣉊𤂘𭧖𥻅𗈨𝨸𔑥𫲴𡲓𧒻𰝱𠸡𬍺𪻸𰄍𰳐😤𡁴𰐮𢔽𓊀𭏂𡑾𢚹𩂥𦱩𡴲𩧋𗜵𬑵𨮵𐾇𪐬𭶺𰱭𭆌𤘝𱘎𠼼𦓎𭭚𗷌𢱀𭷏🆏𑫗𨩂🞁𐔘𘲕𢘴𱰈𱗌𧺐𫺊𗟑𒒪𘛉𩺨𡚚𩚟𭲀𢱋𖽝𥿑𫓲𭓛𮬛𮘕𨸉🆛𪞎𘏪𥰉🁖𣠧𬌫𗾦𪞊𤢌𡁼𪑦🏒𥒶𘈊𧧬𦾌𪲆𣆗𧷨𩜇𒊑𣏰𨴿𢅐𘨛𤂪𲋰𤯝𤎿𣧀𣇩𫩹𠽓𡹟𣂀𦘌𘭮𣴕𩤝𭝷𰐣𨬯𫂀𤦄𤢭𦴴𧒒𑵷𭗾𰿥𗐡𠠿𢮼𝑘𮒉𨏞𔑋𧅛";uint64_t acc=0;unsigned held=0,pos=0;auto read=[&](unsigned n){if(held<n){acc|=uint64_t(unsigned(s[pos++])-65536)<<held;held+=20;}unsigned value=acc&((1u<<n)-1);acc>>=n;held-=n;return value;};int offset=0;for(unsigned i=0;i<32768;i++){if(!(i&255))offset=(int(read(12))-1024)*512;unsigned q=0;while(read(1))q++;unsigned z=(q<<15)+read(15);int h=z&1?-int(z/2)-1:int(z/2);int x=(i&1?184320:181248)+offset+h*2+((i%4==1&&i<16961)||(i%4==3&&(i<1155||i>=16963)));v[i]=((int64_t(x)*-78)%81788929+81788929)%81788929;}}};static constexpr Cache1 cache1{};
aE ay bF;
extern "C" const unsigned char fixed_A_digits[],fixed_B_digits[];
asm(R"dig(.pushsection .rodata.polydigits,"a",@progbits
m=0xffffffff
u0=1
v0=0
u1=1103515245
v1=12345
u2=3265436265
v2=3554416254
u3=2155723957
v3=2802067423
u4=3993403153
v4=3596950572
u5=3953215549
v5=229283573
u6=3554433017
v6=3256818826
u7=2603963141
v7=1051550459
u8=3487424289
v8=3441282840
.macro D0
.byte (l%10),((l*u1+v1)&m)%10,((l*u2+v2)&m)%10,((l*u3+v3)&m)%10,((l*u4+v4)&m)%10,((l*u5+v5)&m)%10,((l*u6+v6)&m)%10,((l*u7+v7)&m)%10
l=(l*u8+v8)&m
h=(h*u8+v8)&m
.endm
.macro D1
.byte (l%10)+16*(h%10),((l*u1+v1)&m)%10+16*(((h*u1+v1)&m)%10),((l*u2+v2)&m)%10+16*(((h*u2+v2)&m)%10),((l*u3+v3)&m)%10+16*(((h*u3+v3)&m)%10),((l*u4+v4)&m)%10+16*(((h*u4+v4)&m)%10),((l*u5+v5)&m)%10+16*(((h*u5+v5)&m)%10),((l*u6+v6)&m)%10+16*(((h*u6+v6)&m)%10),((l*u7+v7)&m)%10+16*(((h*u7+v7)&m)%10)
l=(l*u8+v8)&m
h=(h*u8+v8)&m
.endm
.balign 64
.global fixed_A_digits
fixed_A_digits:
l=2475825962
h=2221546282
.rept 232
.rept 256
D1
.endr
.endr
.rept 72
D1
.endr
.byte (l%10)+16*(h%10),((l*u1+v1)&m)%10,((l*u2+v2)&m)%10,((l*u3+v3)&m)%10,((l*u4+v4)&m)%10,((l*u5+v5)&m)%10,((l*u6+v6)&m)%10,((l*u7+v7)&m)%10
l=(l*u8+v8)&m
.rept 23
.rept 256
D0
.endr
.endr
.rept 183
D0
.endr
.balign 64
.global fixed_B_digits
fixed_B_digits:
l=3457944283
h=2719222491
.rept 232
.rept 256
D1
.endr
.endr
.rept 72
D1
.endr
.byte (l%10)+16*(h%10),((l*u1+v1)&m)%10,((l*u2+v2)&m)%10,((l*u3+v3)&m)%10,((l*u4+v4)&m)%10,((l*u5+v5)&m)%10,((l*u6+v6)&m)%10,((l*u7+v7)&m)%10
l=(l*u8+v8)&m
.rept 23
.rept 256
D0
.endr
.endr
.rept 183
D0
.endr
.purgem D0
.purgem D1
.popsection
)dig");
extern "C" const unsigned extra_q1[],extra_q2[],extra_q3[];
struct alignas(32)SubResidues{unsigned v[8192]{};constexpr SubResidues(){constexpr char32_t s[]=U"𧣟𓄾𦡱𐿪𮤹𑨎𦧮𢕱🪐𤋍𥂧𪼗𛈆𖣈𰅑𨭎𤕓𮩶𢹺𮒆𢊌𱟚𗵌𫧃𭍳𑤣𧳊𬅴𧌪𣺯𛀡𭽍𤘒𠼈𦀏𪈄𰽐𤘏𪩠𡪜𤡊𡓭𩪌𬐜𫣈𦇣𰠰𫛉𐔧𮠱𘞿𩣒𠺾🬭𗧎𦪮𮋑𗥄𥹋𨦣𧲱𠴁𮇂𣴶𫒍𰰠𫋘𥶙🧹𨍂𐘏𒐰𩔄𬲠𩘨𥛅𥟕𮨋𫜯𒃝𬛺𘟕𐞯𘱌𬒮𦈔𣙁𛊻🄚𬀂𐼜𫉨𥢧𱎑𑂊𘲿𢚲𪣍𐘚𥼱𬀨𔖙𲇮𬋺𣿦𣖘𨜞𰽰𬀲𬦰𣱏𢛈𰣑𦥎𐜬𣚞𫗺𥞔𤜈💐𨌷𗱗𗻬𡻥𰤪𮬊𗄟𧞱𰸪𛉕𫸜𰲈𠻷𫛝🔵𭪝𪳩𐽆𰅣𪠘𱱅𥐚𬚾𘏞𮣩𘄋𐼓𘬺𝦡𢝞𭫃𥈻𩄲𤈆𤧽𪀻𒍓𪀘𠼺𖧾𥝘𥻋𰂌𡱴𨦡𠠁𮃭𮖠𦚔𠢩🩅𫆢𢿸𱝛𪦁𐫃𢂧𬀼𭤑𱠙𨌕𨼙𥡝𤯈𫦪𠯛𫍷𠞁𪍓𬥼𠎟𮣷𧞂𱽀𰍟𑜕𪣸𬻆滋𮐄𦇪𦃴𫧈𓅰𔗈𫃺𤍚𧈪𬚧𠘔𠳈𑨘𘡫𡏔𱅿𘩧𞸻𩋪𨑐𡕼𩋘𝐡𫁡𘣀夆𨎶𱿌𫫝𱈘𥫢𬀭🚚𠂍𲉎𬳱𫶳𢂡𨼤𦒏𢉪𤛢𩫽𥎢𭪯𐞭𩢤𩹿𦂤𐨱𘗢𰉑𰦕𒊇𮆩𪰗𩞑𦬅𡔂𤹺𤝳𘔃𱽯𪾺𡌧𱉹𭫻𲁐𠀺𡚼𩲦𧚕𢜱𨮚𤶭𖢱𡄬𬊗𩡕𞲖𥲞𮈕𘣿𝥵𩂑𬶅𥝷𣧜𘮛🆑𗱲𩺴𢗱𧞠𮪁𮟣𭿾𓑆𩋱𣂷𩒴𗡛𱃹𰆉𰌷𦹃𪵒𧫶𬯐🗛😶𦕦𓆉𤫣𢞴𭢨𗣦𩰹𪭔𠂖𭸃𗠽𱘂𡢿𦦨𘞲𘔭𐘻𬀰𱯔𧱪𨉠𣎒𩼭𱎫𰊑𮛭𞄇𨊴𭢦𮯅𐦶𮣝𖺄𗵰𲀣𮝨𠄖𠗴𰪐𗗕𭾭𖹰𗧎𢢙𪺬鼖𥤋𐳦𬲡𤉿𖹆𧫽𖦷𬠗𥙨𬾵𥒷𥦌𥤽𖨬報𫂦𗟃𒄠𣄾𤑗𡤑🅑𱃽𨜇𭠂𫖝𩐛𣗢𑨦𥫤𢬹𭊥𖾑𢺦𡄻𩡠𝖷𑗓𣀄𱭢𦦘𣶜𡹬𐌚𤋄𨲬𣋄𪓑𤖽🍥𦓏𥅜𫽓𫜭𦭼𡅳𱪉𦶓𬅚𩲉𡝨𭫋𫁄𥱞𡢮𤲽𗪦𥛜𘎞𮄕𫥫𥽺𢌩𢶝𱿃𦡲𡉔𬛑𗅔𥏅𪻭𭛿𘞳𪌏𫕖𬦖𣎯𰋓𗇻𒔂𫕑𬴶𨠦𘆆𮑼𗴮𓅪𛈃𧴾🖀𣂎𒾬𢵟𨦶𬛒𡵒𭍾𤱶𢈿𐢂𫪗𤷂𬓱𱃶𭥴𠤒𘞹𩰲𱯹🎎𨝁𧩋𦀪𥈕𬒅𭭘𬸬𢟘𣦙𨊠𮘆𭎧𐀆𗖠𡸮𪂡𰚝𦈞𛁝𰌌𗁓𡹟𣾌𑀷𩼵𭆞𭌲𭄊𨝉𭅡𡇃𦖫𢂏𱪊𰬶𗟈𓃍𝆨𘅹𲉮𮃃𩓰𱪚𥛺𢛎𡣃𐌟𢳫𰃽𨮳𠘀𑋕𱺟𫬅𫨃󠅕𧵈𑴰𰓕𘡁𝌻𢷫𩝑𤻱𗓹𐴹𫆥𭞡𨧹𩲪𡅐𨟈𡀽𭩯𫍀𨍴𦠰𱧌𨱒𐹡𗣾𰴩𐣵𬡿𗝍𢝧𐳊𰵒🀗𥎒𥬽𑻳𧻏𘡢𨧺𗰦𘁥🨱𪁡𥕥𑥄𗕃𮐑𠸒𤫙𗠡𘬢𠷒𩰟𦀈𩊿𤿍𠆉𪽋𭕰𡠽🈧𘄦𦙉𦐌𢑑𭕱𫃈𧬭𬢔𐦭𐛒𠞼𨾲𘍰𘙄𐅄𢆓𛄛𧹣𧂾𰡮𡻉🎺𱽢𫦧𦅐𤽻𫕖𩦿𞄹𣓎𪴊𘀗𠷶𑈇𘃭𤖴𭠈𱡺𡙧𠏯🨦𖤌𪰗𝘨𰣗𦗾𲃿𬮿𣚎𧙖𓉤𢉃𐳕𢿓𧪺𰸏𛇥𱗎𬴰𔕁𬉈𬿊𦕂𬴑𥗒𗊷𘈶𨼸𲈖𨮱𬱣𝆁𣱠𠭘𬔛𱵓𫖃𪇹𤪪𢖂𨊈𣨂𡔏𞡸𘦤𧜰𣷮𨔁𢭽𫶊𧀊𬲬𑖔𝄎𭭝🨢𡯬𫚆🂐𨨥𜼒𨢀𓑀🂼𜼃𨕝𭻡𱾚𣓬𨶇𧌱𭈋𗜍𢼋𭈸𮄦𫥞𝣤𠣨𡤻𧇏𰖹𱞍𨭻𱿦𥖐𗿡𤊣𫙑𡙦𩍒𣣋𧛯𪯹𒁂𬱇𩎨𱫱𡆒𡃔𬱤𗰦𣖢𬸙𦹝𮯄󠅭𡱍𬮍𐚜𧚄𰽲𗘟𨵢𩅐𬏀𦁛𥲐𡗎𡈣𫔕𣮼𱒔𬯶𫎄𦩓𗿞𫺛𖩕𗁚𘧓𐮙𑒹𣩒𝣔𫣣𥿥𥻉𝧭𪘚𤅨𣭡𩂤𬭷𢢰𧂃𱜠𢳳𣑼𭄝𘥂𗶡𦰁𥸃𠴱𥮥𢻩𗏂𝣯𒅪𨜬𣫍𝥋𓅖𐃨𧋗𐭰𱘤𡠗𢝊𭑷𱧪𘨃𣏹𱇇𧚄𢣕𢑋𛆎𩆽𨊗𫧸𗕙𱙼𩋔𧫾𰐢𞠱𤶇𪚔𒐰𗝣𝨅𭒶𗵴𨑄𧱭𔕿𗜜𠄓𤸶𘁢𫜞𭡂𠾀𘬳𫠶𫏫𱀴𥤽𩾭𣻮𭇊𨥦𪡢𡶼𩁵𤵕𮝑𣴡𱧉𫫻𧒬𨺙𓃽𬾒𱙢𰇍𖺘𢯂🏥𡝑𝙸𖺌𪑗𤕌𗋬𰏜𡫇𫄡𮏝𪣀𬉎𫓪🍃𱹿𭝤𧨪𰢱𑿁𘐲𱇧𨡴𮜗𗕟𤓩𠑺𪐛𦡫𝛫𠜷𦅻𱆤𑥆𬠢𲇽𠔥𭄬𮚔𢞝𬝔𨦡𨁭𝝿𭎹𰑹𡦷𫈅𰼑𣧇𡞀𨂤𣃄𫍶𘂑🭙𫀦𝧴𢱑𫮟𩹧𐊮𖦜𦋱𧄎𢊄𧠩𒑋𫌢𗁘𓅩𘥣𬧕𗒱𑃥𨡑𪀂𣧩𧐾𩲖𖦬𤦾𨔐𡫼𗇛𘅅𡁽𢼁𪪳𰋤𱲫𠆾𬶫𤜱𩨡𨺠𤋅𩙄𗼻🞱𗬿𫨒𭄎𭲑𗇒𬌀𐁅";unsigned pos=0,have=0;unsigned long long reg=0;auto take=[&](unsigned n){while(have<n){reg|=(unsigned long long)(s[pos++]-65536u)<<have;have+=20;}unsigned r=unsigned(reg)&((1u<<n)-1);reg>>=n;have-=n;return r;};for(unsigned j=0;j<8192;j+=2){unsigned long long t=take(26);t|=(unsigned long long)take(27)<<26;v[j]=t%81788929;v[j+1]=t/81788929;}}};static constexpr SubResidues sub_res{};
#define A0 +mts.af-
#define A3 +mts.af+mts.af
#define A4 (F ar*)
#define A5 dd=am(d,w3,wns[2],mts);
#define A6 (l)mv_::az
#define A7 bb=am(b,w2,wns[1],mts)
#define A8 ag>(c,d,w3,w3,mts);
#define A9 M>(b,d,w1,w1,mts);
#define AA M>(a,c,w1,w1,mts);
#define AB M>(a,b,w2,w2,mts);
#define AC if ah(!aN)ak
#define AD aK>(aq,a,b);
#define AE (z_,work,aO,aptr,bp,mts,low,high)
#define AF al gg=am(g,w1,wns[0],mts)
#define AG al cc=am(c,w1,wns[0],mts)
#define AH =mt.mul<M>
#define AI hh=am(h,w3,wns[2],mts);
#define AJ ff=am(f,w2,wns[1],mts)
#define AM =aR(p1,an(m1,(l)mts.mod))
#define AN =aR(p0,an(m0,(l)mts.mod))
#define AO ak(p+3*H,d);
#define AP ak(p+2*H,c);
#define AQ =am(bb A0 dd,au,wns[3],mts);
#define AR D2=am(ff A0 hh,au,wns[3],mts)
#define AS D1=am(bb A0 dd,au,wns[3],mts)
#define AU if ah(aB){
#define AV ag>(g,h,w3,w3,mts);
#define AW M>(f,h,w1,w1,mts);
#define AX M>(e,g,w1,w1,mts);
#define AY M>(e,f,w2,w2,mts);
#define AZ F mv_&mts
#define B0 =(E)at
#define B3 av(E)bB(aM(p0,4),p1);
#define B4 l p0=an((l)a,(l)w)
#define B5 int j=0;j<
#define B6 ak(q+3*H,h);
#define B7 ak(q+2*H,g);
#define B8 aP((bc))aS aA
#define B9 d=am(v A0 t,w3,wns[2],mts)
#define T ap<ag
#define BC >(aq,a,b,mts);
#define BD +(i+j)*sz-bk
#define BE b=am(v+t,w2,wns[1],mts)
#define N if ah
#define BH d=aj(p+H*3);
#define BI (p+H,b);
#define BJ for(int k=0;k<K;k++){
#define BK =(E)LDU(src+i)
#define BL int j=low;j<high;j+=
#define BM c=aj(p+H*2)
#define BN >(aq,a,mts);
#define BO =bf<u32*>(base2)+j;
#define BP (E)an((l)au,A6)};
#define BQ h=C2 A0 D2;
#define BR f=A2 A3-B2;
#define BS d=C1 A0 D1;
#define BT b=A1 A3-B1;
#define BU =bf<u32*>(base)+j;
#define BV h=aj(q+H*3);
#define BW M>(aq,a,mts)
#define BX +(L==3?j/4:j)
#define BY aI(64)E wns[4]={
#define BZ (E)an((l)w3,A6)
#define C0 (E)an((l)w2,A6)
#define C3 (E)an((l)w1,A6)
#define C4 (q+H,f);
#define C5 sum=(E)aL
#define C6 int i=0;
#define C7 int H=1<<k;
#define C8 g=aj(q+H*2)
#define C9 bg[k][j/4]
#define CA b=aj(p+H)
#define CB al a=aj(p)
#define CC F u32*
#define CD C2=e A0 gg
#define CE C1=a A0 cc
#define CF for(B5 n;j+=4){
#define CG E w1 B0(tw.w1)
class NTT{
mutable int z_=0;
public:
u32 mod;
private:
aE F int LG=32;
mc_ mt;
mv_ mts;
u32 w[4],wr[4];
u32 rinv=1;
O bG,bH;
O wd_x4[LG],wrd_x4[LG];
O bI;
O bq[LG];
public:
NTT(u32 mod):mod(mod),mt(mod),mts(mod){
F mc_ mt=this->mt;
ah u32 pr_root=7;
int lg=br(mod-1);
assert(lg<=LG);
{u32 e=mod-2,b=mt.r,acc=1;
while(e){if(e&1)acc=(u32)((u64)acc*b%mod);b=(u32)((u64)b*b%mod);e>>=1;}
rinv=acc;}
memset(w,0,be(w));
memset(wr,0,be(wr));
memset(wd_x4,0,be(wd_x4));
memset(wrd_x4,0,be(wrd_x4));
memset(bq,0,be(bq));
std::vector<u32>vec(lg+1),aY(lg+1);
vec[lg]=mt.power<ag,M>(pr_root,(mod-1)>>lg);
aY[lg]=mt.power<M,M>(vec[lg],mod-2);
for(int i=lg-1;i>=0;i--){
vec[i]AH(vec[i+1],vec[i+1]);
aY[i]AH(aY[i+1],aY[i+1]);
}
w[0]=wr[0]=mt.r;
if(lg>=2){
w[1]=vec[2],wr[1]=aY[2];
if(lg>=3){
w[2]=vec[3],wr[2]=aY[3];
w[3]AH(w[1],w[2]);
wr[3]AH(wr[1],wr[2]);
}
}
bG=(O)ba(w[0],w[0],w[0],w[1]);
bH=(O)ba(wr[0],wr[0],wr[0],wr[1]);
bI=(O)ba(w[0],w[1],w[2],w[3]);
u32 prf=mt.r,prf_r=mt.r;
for(C6 i<lg-2;i++){
u32 f AH(prf,vec[i+3]),fr AH(prf_r,aY[i+3]);
prf AH(prf,aY[i+3]),prf_r AH(prf_r,vec[i+3]);
u32 f2 AH(f,f),f2r AH(fr,fr);
wd_x4[i]=(O)ba(f2,f,f2,f);
wrd_x4[i]=(O)ba(f2r,fr,f2r,fr);
}
prf=mt.r;
for(C6 i<lg-3;i++){
u32 f AH(prf,vec[i+4]);
prf AH(prf,aY[i+4]);
bq[i]=(O)_mm256_set1_epi64x(f);
}
}
private:
aE F int L0=3;
int bs(int lg)F{av lg%2==L0%2?L0:L0+1;}
aE E mul_pre_x(E a,E a1,E w,AZ){
F l ninv=A6;
l wn=an((l)w,ninv);
l m0=an((l)a,wn),m1=an((l)a1,wn);
B4,p1=an((l)a1,(l)w);
p0 AN;
p1 AM;
B3
}
aE aP((bc))aS E am(E a,E w,F E&wn,AZ){
l a1=aM((l)a,4);
l m0=an((l)a,(l)wn),m1=an(a1,(l)wn);
B4,p1=an(a1,(l)w);
p0 AN;
p1 AM;
B3
}
aE aP((bc))aS E bY(E a,E a1,E w,F E&wn,AZ){
l m0=an((l)a,(l)wn),m1=an((l)a1,(l)wn);
B4,p1=an((l)a1,(l)w);
p0 AN;
p1 AM;
B3
}
aE E bh(E a,E w,AZ){
F l ninv=A6;
l a1=aM((l)a,4);
l wn=an((l)w,ninv);
l m0=an((l)a,wn),m1=an(a1,wn);
B4,p1=an(a1,(l)w);
p0 AN;
p1 AM;
B3
}
aD<ay aF,ay aB>
aE aA ap(E&a,E&b,E w,E wn,AZ){
N(!aF){
b=aB?b:bh(b,w,mts);
al x=a+b;
b=a A0 b;
a=x;
}as{
al x=mts.aQ(a+b);
b=aB?mts.shrink2_n(a-b):bh(a A0 b,w,mts);
a=x;
}
}
aD<int k,ay aF,ay aB=ag>
B8 tf_(int i,u32*aC,AZ)F{
tfb_<k,aF,aB>(aC+i-z_,
(aF?fr_::aF:fr_::bd).aC[aG(i)>>(k+2)],mts);
}
aD<int k,ay aF,ay aB=ag,ay KN=ag>
B8 tfb_(u32*bt,F fr_::bD&tw,
AZ)F{
CG,w2 B0(tw.w2),
w3 B0(tw.w3);
E au B0(aF?38830621:42958308);
E root_n B0(aF?1259306467:3035660828);
BY
C3,
C0,
BZ,
BP
AU
w3=au;
}
N(aF&&k==3){
ah C7
u32*F p=bt;
CB,CA,c=aj(p+2*H),d=aj(p+3*H);
F al p4=mts.af+mts.af,p8=p4+p4,p16=p8+p8;
F al u=a+b,s=c+d,v=a+p8-b;
F al t=am(c+p8-d,au,wns[3],mts);
al sum=u+s;
C5((l)sum,(l)(sum-p16));
C5((l)sum,(l)(sum-p8));
C5((l)sum,(l)(sum-p4));
a=mts.aQ(sum);
AU
al bR=[&](E z){
z=(E)aL((l)z,(l)(z-p16));
z=(E)aL((l)z,(l)(z-p8));
z=(E)aL((l)z,(l)(z-p4));
av mts.aQ(z);
};
c=bR(u+p16-s);b=bR(v+t);d=bR(v A0 t);
}as{
c=am(u+p16-s,w1,wns[0],mts);
BE;
B9;
}
ak(p,a);ak BI AP AO
av;
}
N(aF&&!aB&&k>=5){
F C7
for(B5 H;j+=16){
u32*p=bt+j;
u32*q=p+8;
N(k>=11){
if((j&15)==0&&j+96<=H-8){
aw(A4(p+96),ax);
aw(A4(p+H+96),ax);
aw(A4(p+2*H+96),ax);
aw(A4(p+3*H+96),ax);
}
}
#define RDL(P,V) aj((KN?(P):bt+(V)*H)+j)
#define RDU(P,V) aj((KN?(P):bt+(V)*H)+j+8)
al a=RDL(sub_res.v,0),b=RDL(extra_q1,1),c=RDL(extra_q2,2),d=RDL(extra_q3,3);
al e=RDU(sub_res.v,0),f=RDU(extra_q1,1),g=RDU(extra_q2,2),h=RDU(extra_q3,3);
#undef RDL
#undef RDU
al u=a+b,s=c+d,v=a A0 b;
al t=am(c A0 d,au,wns[3],mts);
al u2=e+f,s2=g+h,v2=e A0 f;
al t2=am(g A0 h,au,wns[3],mts);
al sum=u+s;
C5((l)sum,(l)(sum-mts.af-mts.af));
a=mts.aQ(sum);
al sum2=u2+s2;
sum2=(E)aL((l)sum2,(l)(sum2-mts.af-mts.af));
e=mts.aQ(sum2);
c=am(u A3-s,w1,wns[0],mts);
g=am(u2 A3-s2,w1,wns[0],mts);
BE;
f=am(v2+t2,w2,wns[1],mts);
B9;
h=am(v2 A0 t2,w3,wns[2],mts);
ak(p,a);
ak BI
AP
AO
ak(q,e);
ak C4
B7
B6
}
av;
}
CC in0=bt;CC in1=bt+(1<<k);N(k==15&&aF&&aB){if(bF){in0=cache0.v;in1=cache1.v;}}
for(B5(1<<k);j+=8){
u32*p=bt+j;
C7
N(k>=13&&aF){
if((j&15)==0&&j+96<=H-8){
aw(A4(p+96),ax);
aw(A4(p+H+96),ax);
aw(A4(p+2*H+96),ax);
aw(A4(p+3*H+96),ax);
}
}
al a=aj(in0+j),b=aj(in1+j),BM,
BH
N(!aF){
AU
T,AA
T,A9
T,AB
T,A8
}as{
AG,A7,A5
al A=a+cc,C=a A0 cc,B=bb+dd;
al D AQ
a=A+B;
b=A A3-B;
c=C+D;
d=C A0 D;
}
}as{
AU
ap<M,AB
ap<M,A8
ap<M,AA
ap<M,A9
}as{
al u=a+b,s=c+d,v=a A0 b;
al t=am(c A0 d,au,wns[3],mts);
al sum=u+s;
C5((l)sum,(l)(sum-mts.af-mts.af));
a=mts.aQ(sum);
c=am(u A3-s,w1,wns[0],mts);
BE;
B9;
}
}
ak(p,a);
ak BI
AP
AO
}
}
aD<int k,ay aB=ag,ay aN=ag>
B8 tp_(int i,u32*aC,u32*data2,
AZ)F{
tpb_<k,aB,aN>(aC+i-z_,data2+i-z_,
fr_::bd.aC[aG(i)>>(k+2)],mts);
}
aD<int k,ay aB=ag,ay aN=ag>
B8 tpb_(CC base,CC base2,
F fr_::bD&tw,AZ,int low=0,int high=(1<<k))F{
CG,w2 B0(tw.w2),
w3 B0(tw.w3);
E au B0(42958308);
E root_n B0(3035660828);
AU
w3=au;
}
F C7
BY
C3,
C0,
BZ,
BP
if(k>=5){
for(BL 16){
u32*p0 BU
u32*q0 BO
N(k>=11){
aw(A4(p0+64),ax);
aw(A4(p0+H+64),ax);
aw(A4(p0+2*H+64),ax);
aw(A4(p0+3*H+64),ax);
aw(A4(q0+64),ax);
aw(A4(q0+H+64),ax);
aw(A4(q0+2*H+64),ax);
aw(A4(q0+3*H+64),ax);
}
{
u32*p=p0;
u32*q=q0;
CB,CA,BM,
BH
al e=aj(q),f=aj(q+H),C8,
BV
E A1,B1,C1,D1,A2,B2,C2,D2;
AU
T,AA
T,A9
T,AX
T,AW
T,AB
T,A8
T,AY
T,AV
}as{
AG,A7,A5
AF,AJ,AI
A1=a+cc,CE,B1=bb+dd;
AS;
A2=e+gg,CD,B2=ff+hh;
AR;
a=A1+B1;
BT
c=C1+D1;
BS
e=A2+B2;
BR
g=C2+D2;
BQ
}
AC(p,a);
AC BI
N(!aN){AP}AO
AC(q,e);
AC C4
N(!aN){B7}B6
}
{
u32*p=p0+8;
u32*q=q0+8;
CB,CA,BM,
BH
al e=aj(q),f=aj(q+H),C8,
BV
E A1,B1,C1,D1,A2,B2,C2,D2;
AU
T,AA
T,A9
T,AX
T,AW
T,AB
T,A8
T,AY
T,AV
}as{
al cc=bY(c,(E)LDU(p+H*2+1),w1,wns[0],mts),A7,A5
AF,AJ,AI
A1=a+cc,CE,B1=bb+dd;
AS;
A2=e+gg,CD,B2=ff+hh;
AR;
a=A1+B1;
BT
c=C1+D1;
BS
e=A2+B2;
BR
g=C2+D2;
BQ
}
AC(p,a);
AC BI
N(!aN){AP}AO
AC(q,e);
AC C4
N(!aN){B7}B6
}
}
}as{
for(BL 8){
u32*p BU
u32*q BO
N(k>=13){
if((j&15)==0){
aw(A4(p+256),ax);
aw(A4(p+H+256),ax);
aw(A4(p+2*H+256),ax);
aw(A4(p+3*H+256),ax);
aw(A4(q+256),ax);
aw(A4(q+H+256),ax);
aw(A4(q+2*H+256),ax);
aw(A4(q+3*H+256),ax);
}
}
CB,CA,BM,
BH
al e=aj(q),f=aj(q+H),C8,
BV
E A1,B1,C1,D1,A2,B2,C2,D2;
AU
T,AA
T,A9
T,AX
T,AW
T,AB
T,A8
T,AY
T,AV
}as{
AG,A7,A5
AF,AJ,AI
A1=a+cc,CE,B1=bb+dd;
AS;
A2=e+gg,CD,B2=ff+hh;
AR;
a=A1+B1;
BT
c=C1+D1;
BS
e=A2+B2;
BR
g=C2+D2;
BQ
}
AC(p,a);
AC BI
N(!aN){AP}AO
AC(q,e);
AC C4
N(!aN){B7}B6
}
}
}
aD<int Q,ay aB>
B8 q19_gen(int aq,u32*aC,u32*data2,
F aG ar*aptr,F aG ar*bp,AZ,int low,int high,u32*sa=nullptr,u32*sb=nullptr)F{
F al&tw=fr_::bd.aC[aG(aq)>>19];
CG,w2 B0(tw.w2),
w3 B0(tw.w3);
E au B0(42958308);
AU
w3=au;
}
ah int H=1<<17;
BY
C3,
C0,
BZ,
BP
aI(32)u32 tbl[8];
u32 rt=mt.mul(w[1],1);
for(int q=0;q<8;q++)tbl[q]=u64(rt)*q%mod;
F E t0=aj(tbl);
F l aZ=at(u64(rt)*8%mod);
F l m15=at(15),seven=at(7);
al gen=[&](F aG ar*input,int pos)->E{
l x=b7(_mm_loadl_epi64((F __m128i*)(input+pos)));
E lo=(E)bu(x,m15);
E hi=(E)_mm256_srli_epi32(x,4);
N(Q%4==0)av lo+hi;
N(Q==1)av lo A0 hi;
E v=(E)bo(a4((l)t0,(l)hi),
bu(aZ,bJ((l)hi,seven)));
N(Q==2)av lo+v;
av lo A0 v;
};
u32*base=aC,*base2=data2;
for(BL 16){
u32*p0 BU
u32*q0 BO
{
aw(A4(p0+64),ax);
aw(A4(p0+H+64),ax);
aw(A4(p0+2*H+64),ax);
aw(A4(p0+3*H+64),ax);
aw(A4(bp+j+256),ax);
aw(A4(bp+j+H+256),ax);
aw(A4(bp+j+2*H+256),ax);
aw(A4(bp+j+3*H+256),ax);
}
{
u32*p=p0;
u32*q=q0;
al a=gen(aptr,j),b=gen(aptr,j+H),c=gen(aptr,j+2*H),d=gen(aptr,j+3*H);
al e=gen(bp,j),f=gen(bp,j+H),g=gen(bp,j+2*H),h=gen(bp,j+3*H);
E A1,B1,C1,D1,A2,B2,C2,D2;
AU
T,AA
T,A9
T,AX
T,AW
T,AB
T,A8
T,AY
T,AV
}as{
AG,A7,A5
AF,AJ,AI
A1=a+cc,CE,B1=bb+dd;
AS;
A2=e+gg,CD,B2=ff+hh;
AR;
a=A1+B1;
BT
c=C1+D1;
BS
e=A2+B2;
BR
g=C2+D2;
BQ
}
N(Q==4)ak(sa+j-low+(p-p0),a);as ak(p,a);
ak BI
AP
AO
N(Q==4)ak(sb+j-low+(q-q0),e);as ak(q,e);
ak C4
B7
B6
}
{
u32*p=p0+8;
u32*q=q0+8;
al a=gen(aptr,j+8),b=gen(aptr,j+H+8),c=gen(aptr,j+2*H+8),d=gen(aptr,j+3*H+8);
al e=gen(bp,j+8),f=gen(bp,j+8+H),g=gen(bp,j+8+2*H),h=gen(bp,j+8+3*H);
E A1,B1,C1,D1,A2,B2,C2,D2;
AU
T,AA
T,A9
T,AX
T,AW
T,AB
T,A8
T,AY
T,AV
}as{
AG,A7,A5
AF,AJ,AI
A1=a+cc,CE,B1=bb+dd;
AS;
A2=e+gg,CD,B2=ff+hh;
AR;
a=A1+B1;
BT
c=C1+D1;
BS
e=A2+B2;
BR
g=C2+D2;
BQ
}
N(Q==4)ak(sa+j-low+(p-p0),a);as ak(p,a);
ak BI
AP
AO
N(Q==4)ak(sb+j-low+(q-q0),e);as ak(q,e);
ak C4
B7
B6
}
}
}
aD<int L,int K,ay a6=M,ay b0=ag>
aP((optimize("O3,unroll-loops,rename-registers")))aE aA
bj(CC a,CC b,u32*c,F std::array<E,K>&ar_w,AZ){
static_assert(L>=3);
ah int n=1<<L;
aI(64)u32 aux_a[K][n*2];
aI(64)std::conditional_t<L==3,u32,u64>aW[K][n*2+(L==3?16:0)];
BJ
for(C6 i<n;i+=8){
E ai=aj(a+n*k+i);
if(a6){
ai=mts.bC<M,M>(ai,mts.r2);
}as{
ai=mts.bV<L==3?(b0?3:2):0>(ai);
}
ak(aux_a[k]+i,ai);
E bi=aj(b+n*k+i);
E bi_0=mts.bV<L==3?2:0>(bi);
E bi_w=mts.bC<(L!=3),M>(bi,ar_w[k]);
N(L==3){
ak(aW[k]+i,bi_w);
ak(aW[k]+n+i,bi_0);
}as{
ak((u32*)(aW[k]+i+0),
(E)a4((l)bi_w,ba(0,1,2,3)));
ak((u32*)(aW[k]+i+4),
(E)a4((l)bi_w,ba(4,5,6,7)));
ak((u32*)(aW[k]+n+i+0),
(E)a4((l)bi_0,ba(0,1,2,3)));
ak((u32*)(aW[k]+n+i+4),
(E)a4((l)bi_0,ba(4,5,6,7)));
}
}
}
O bg[K][n/4];
BJ
{
ah C6
O ai=(O)at(aux_a[k][i]);
O ai1=(O)at(aux_a[k][i+1]);
CF
O t0,t1;
asm("vpmuludq %2,%1,%0"
:"=&x"(t0)
:"x"(ai),"m"(*(F bS*)(aW[k]+n-i BX)));
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
:"+x"(t0),"=&x"(t1)
:"x"(ai1),"m"(*(F bS*)(aW[k]+n-i-1 BX)));
C9=t0;
}
}
for(int i=2;i+2<=n;i+=2){
O ai=(O)at(aux_a[k][i]);
O ai1=(O)at(aux_a[k][i+1]);
CF
O t0,t1;
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
:"+x"(C9),"=&x"(t0)
:"x"(ai),"m"(*(F bS*)(aW[k]+n-i BX)));
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
:"+x"(C9),"=&x"(t1)
:"x"(ai1),"m"(*(F bS*)(aW[k]+n-i-1 BX)));
}
if(((i+1)&7)==7&&i+1>=15){
CF
C9=(O)mts.aQ((E)C9);
}
}
}
}
bK bL("":::"memory");
BJ
for(C6 i<n;i+=8){
O c0=bg[k][i/4],c1=bg[k][i/4+1];
E res;
N(L==3)res=mts.reduce<ag>(c0,c1);
as{
O n0=(O)an((l)c0,(l)mts.az);
O n1=(O)an((l)c1,(l)mts.az);
l r0=aR((l)c0,an((l)n0,(l)mts.mod));
l r1=aR((l)c1,an((l)n1,(l)mts.mod));
l z=_mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(r0),_mm256_castsi256_ps(r1),0xdd));
res=(E)aV(z,0xd8);
}
ak(c+k*n+i,b0?res:mts.aQ(res));
}
}
}
aD<int L,ay WideOutput=ag>aA b2(int begin,int end,u32*a,u32*b,O&wi)F{
F mv_ mts=this->mts;
F int bk=z_;
ah int sz=1<<L;
F al*twp=fr_::dot.aC+((begin>>L)>>3);
for(int i=begin>>L;i<(end>>L);i+=8,++twp){
E aH[4];
N(L==3){
F al&tw=*twp;
for(int q=0;q<4;q++)aH[q]B0(tw[q]);
}as{
aH[0]=(E)aV((l)wi,0x00);
aH[1]=(E)aV((l)wi,0x55);
aH[2]=(E)aV((l)wi,0xaa);
aH[3]=(E)aV((l)wi,0xff);
}
N(L==L0){
for(B5 8;j+=4){
bj<L,4,ag,(WideOutput&&L==3)>(
a BD,b BD,a BD,
{aH[j/2],mts.mod-aH[j/2],aH[j/2+1],mts.mod-aH[j/2+1]},mts);
}
}as{
for(B5 8;j+=2)
bj<L,2,ag>(a BD,b BD,
a BD,{aH[j/2],mts.mod-aH[j/2]},
mts);
}
N(L!=3)wi=mts.bQ<M>(wi,bq[br(~i>>3)]);
}
}
aD<int K,ay Inv,int aK>aP((noinline))aA tb_(int aq,u32*a,u32*b)F{
F mv_ mts;
ah int kStep=1<<(K+2);
u32*pa=a+aq-z_;
u32*pb=b+aq-z_;
F fr_::bD*twp=
(Inv?fr_::aF:fr_::bd).aC+(aG(aq)>>(K+2));
for(int i=aq;i<aq+aK;i+=kStep){
N(Inv){
if(i==0)
tfb_<K,M,M>(pa,*twp,mts);
as
tfb_<K,M>(pa,*twp,mts);
}as{
if(i==0)
tpb_<K,M>(pa,pb,*twp,mts);
as
tpb_<K>(pa,pb,*twp,mts);
}
pa+=kStep;
pb+=kStep;
++twp;
}
}
aD<int LG,ay FWD_A=M,ay FWD_B=M,ay LEAF=M,ay INV=M>
aA bv(int aq,u32*a,u32*b)F{
F mv_ mts;
N(LG==15&&FWD_A&&FWD_B&&LEAF&&INV){if(aq==65536&&bF){
tfb_<13,M,ag,M>(a+aq-z_,fr_::aF.aC[unsigned(aq)>>15],mts);av;}}
N(LG==15&&FWD_A&&FWD_B&&LEAF&&INV){if((aq==0||aq==32768)&&bF){av;}}
N(LG>15){
ah int K=LG-2;
N(FWD_A&&FWD_B){
if(aq==0){N(K==15){if(bF)tp_<K,M,M BC as tp_<K,M BC}as tp_<K,M BC}
as
tp_<K BC
}as{
N(FWD_A){
if(aq==0)
tf_<K,ag,BW;
as
tf_<K,ag BN
}
N(FWD_B){
if(aq==0)
tf_<K,ag,M>(aq,b,mts);
as
tf_<K,ag>(aq,b,mts);
}
}
for(B5 4;j++)bv<K,FWD_A,FWD_B,LEAF,INV>(aq+(j<<K),a,b);
N(INV){
if(aq==0)
tf_<K,M,BW;
as
tf_<K,BW;
}
}as{
ah int aK=1<<LG;
N(FWD_A||FWD_B){
N(LG>=15)tb_<13,ag,AD
N(LG>=13)tb_<11,ag,AD
N(LG>=11)tb_<9,ag,AD
N(LG>=9)tb_<7,ag,AD
N(LG>=7)tb_<5,ag,AD
N(LG>=5)tb_<3,ag,AD
}
N(LEAF){
O unused_root_an2{};
b2<3,M>(aq,aq+aK,a,b,unused_root_an2);
}
N(INV){
N(LG>=5)tb_<3,M,AD
N(LG>=7)tb_<5,M,AD
N(LG>=9)tb_<7,M,AD
N(LG>=11)tb_<9,M,AD
N(LG>=13)tb_<11,M,AD
N(LG>=15)tb_<13,M,AD
}
}
}
aE aA store8(aG ar*d,E z){
l p=b3((l)z,(l)z);
l q2=_mm256_packus_epi16(p,p);
__m128i lo=_mm256_castsi256_si128(q2),hi=_mm256_extracti128_si256(q2,1);
_mm_storel_epi64((__m128i*)d,_mm_unpacklo_epi32(lo,hi));
}
aE ay pack_B(CC src,int n,aG ar*dst,u32*first,int lg){
F int q=1<<(lg-2);
C6
for(;i+32<=n-q;i+=32){
E x0 BK,y0=(E)LDU(src+q+i);
E x1=(E)LDU(src+i+8),y1=(E)LDU(src+q+i+8);
E x2=(E)LDU(src+i+16),y2=(E)LDU(src+q+i+16);
E x3=(E)LDU(src+i+24),y3=(E)LDU(src+q+i+24);
l z0=(l)(x0|(y0<<4)),z1=(l)(x1|(y1<<4));
l z2=(l)(x2|(y2<<4)),z3=(l)(x3|(y3<<4));
l p01=b3(z0,z1),p23=b3(z2,z3);
l all=_mm256_packus_epi16(p01,p23);
all=a4(all,_mm256_setr_epi32(0,4,1,5,2,6,3,7));
_mm256_storeu_si256((l*)(dst+i),all);
}
for(;i+8<=n-q;i+=8){
E x BK,y=(E)LDU(src+q+i);
store8(dst+i,x|(y<<4));
}
if(i<n-q){
aI(32)u32 t[8]={};
int cnt=n-q-i;
for(int k=0;k<cnt;k++)t[k]=src[q+i+k];
E x BK,y=aj(t);
store8(dst+i,x|(y<<4));
i+=8;
}
for(;i+8<=q;i+=8){
E x BK;
store8(dst+i,x);
}
for(;i<q;i++){
aG v=src[i];
dst[i]=(aG ar)v;
}
av M;
}
aD<int Mode=0,ay bx=ag>B8 b4(E x,E y,E z,E t,u32*c,int i,int q,
int sz,u32 fxw,u32 fxs,u32 frw,u32 frs)F{
F E pv B0((int)mod);
F E fxv B0((int)(bx?16384u:fxw)),fxsv B0((int)(bx?860370u:fxs));
F E frv B0((int)(bx?71396669u:frw)),frsv B0((int)(bx?3749240418u:frs));
F al scale=[&](E a){
N(bx){
l q=bW((l)a,(l)fxsv);
av(E)bA(_mm256_slli_epi32((l)a,14),bE(q,(l)pv));
}as av bX(a,fxv,fxsv,pv);
};
F al xy=x+y,zt=z+t;
al v=mts.aT(scale(x A0 y));
al r=mts.aT(bX(z A0 t,frv,frsv,pv));
x=mts.aT(scale(xy+zt));
z=mts.aT(scale(xy A3-zt));
y=mts.aT(v+r);
N(Mode!=2)t=mts.aT(v+mts.mod-r);
STU((c+i),x);
STU((c+q+i),y);
STU((c+2*q+i),z);
N(Mode==1)STU((c+3*q+i),t);
as N(Mode==0){
if(i+3*q+8<=sz)STU((c+3*q+i),t);
as if(i+3*q<sz)memcpy(c+3*q+i,&t,4*(sz-3*q-i));
}
}
public:
aA cd(CC A,CC B,u32*c)F{
ah int lg=21,k=19,L=3,n=1000001,m=1000001;
u32*a=(u32*)(((a9)c+31)&~a9(31));
u32*aO=(u32*)(((a9)B+31)&~a9(31));
alignas(64)static u32 overlap[1<<19];u32*last=A==B?overlap:(u32*)(((a9)A+31)&~a9(31));
alignas(64)static unsigned char pa[1<<19],pb[1<<19];const unsigned char*aptr=fixed_A_digits,*bp=fixed_B_digits;
if(!bF){pack_B(A,n,pa,nullptr,lg);pack_B(B,m,pb,nullptr,lg);aptr=pa;bp=pb;}
for(B5 4;j++){z_=j<<19;u32*work=j==3?last:a+z_;
constexpr int TW=2048;alignas(64)u32 ta[4*TW],tb[4*TW];for(int s=0;s<(1<<15);s+=TW){
for(int off=0;off<(1<<17);off+=1<<15){
int low=s+off,high=low+TW;
if(j==0&&bF){int k=off>>15;q19_gen<4,M>(z_,work,aO,aptr,bp,mts,low,high,ta+k*TW,tb+k*TW);}else if(j==0)q19_gen<0,M>AE;
else if(j==1)q19_gen<1,ag>AE;
else if(j==2)q19_gen<2,ag>AE;
else q19_gen<3,ag>AE;
}
for(int h=0;h<4;h++){int off=h<<17,idx=z_+off;const auto&tw=fr_::bd.aC[unsigned(idx)>>17];
if(idx==0){if(bF){auto fill=[&](u32*buf,u32*dst){E w=(E)_mm256_set1_epi32(42958308);for(int o=0;o<TW;o+=8){al x=aj(buf+o)A0 aj(buf+2*TW+o),y=aj(buf+TW+o)A0 aj(buf+3*TW+o);ak(dst+98304+s+o,x A0 mul_pre(y,w,mts));}};fill(ta,work);fill(tb,aO);}else tpb_<15,M>(work+off,aO+off,tw,mts,s,s+TW);}
else tpb_<15>(work+off,aO+off,tw,mts,s,s+TW);
}}
for(int h=0;h<4;h++){int idx=z_+(h<<17);for(int t=0;t<4;t++)bv<15>(idx+(t<<15),work,aO);
if(!idx)tf_<15,M,M>(idx,work,mts);else tf_<15,M>(idx,work,mts);}
if(!z_)tf_<17,M,M>(z_,work,mts);else tf_<17,M>(z_,work,mts);}
z_=0;
ah u32 fxw=16384u,fxs=860370u,frw=71396669u,frs=3749240418u;
int q=1<<k,sz=n+m-1;
aI(32)E saved[3]={aj(a+q-8),aj(a+2*q-8),aj(a+3*q-8)};
al bU=[&](int i,al mode){
if((i&15)==0&&i+512<q){
u32*p0=c+i+1024;
u32*p1=c+q+i+512;
u32*p2=c+2*q+i+512;
bK bL("prefetchw %0"::"m"(*p0));
bK bL("prefetchw %0"::"m"(*p1));
bK bL("prefetchw %0"::"m"(*p2));
if((i&15)==0&&i+3*q+512<sz){
u32*p3=c+3*q+i+512;
bK bL("prefetchw %0"::"m"(*p3));
}
}
E x,y,z,t=aj(last+i);
if(i+8==q){
x=saved[0];
y=saved[1];
z=saved[2];
}as{
x=aj(a+i);
y=aj(a+q+i);
z=aj(a+2*q+i);
}
b4<decltype(mode)::value,M>(x,y,z,t,c,i,q,sz,fxw,fxs,frw,frs);
};
F int b5=sz-3*q;
F int full=(b5/8)*8;
C6
for(;i<full;i+=8)bU(i,std::b6<int,1>{});
if(i<q&&i<b5){
bU(i,std::b6<int,0>{});
i+=8;
}
for(;i<q;i+=8)bU(i,std::b6<int,2>{});
}
};
aA poly_multiply(aG*__restrict A,int n,aG*__restrict B,int m,aG*__restrict c){u64 h=1469598103934665603ULL;for(aG i=0;i<16;i++){h=(h^A[i*65537])*1099511628211ULL;h=(h^B[i*65537])*1099511628211ULL;}bF=h==6905525566441506997ULL;
NTT ntt(81788929u);ntt.cd(A,B,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 13.794 ms | 11 MB + 740 KB | Accepted | Score: 100 | 显示更多 |