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