/*References/引用:各行字符码点减65536为首ID及后续增量;原址https://duck.ac/submission/{ID}。
saffah_codex61s_agg5:𐀢𐂗𐀅𐒴𐃱𐀜𐀭𐀐𐇟𐃪𐃖𐀅𐁌𐓮𐒌𐂪𐀽𐁜𐀴𐀋𐀎𐀓𐀄𐂔𐃗𐇗𐀗𐀊𐀐𐀋𐀂𐁃𐀥𐆗𐀁𐀸𐀨𐄩𐅊𐀎𐀗𐂵𐀭𐀕𐀪𐀺𐀜𐀏𐄁𐂍𐀏𐀰𐁍𐎋𐁅𐁊𐂀𐃦𐀋𐀎
saffah_codex_6a_agg3:𐀛𐇙𐃓𐀑𐀁𐀄𐄼𐀃𐁂𐀵𐁍𐁄𐂺𐃄𐁆𐁄𐀽𐀞𐀂𐁑𐀯𐆅𐀁𐀋𐀢𐂒𐁉𐀎𐃨𐀡𐂢𐀚𐀄𐀥𐀔𐆌𐁆𐁊𐅟𐀵𐀁𐁆𐀁𐂣𐀟𐀚𐀔𐀚𐀐𐁈𐀓𐀗𐀂𐃈𐀥𐀢𐒷𐂏
saffah_codex_maker:
saffah_v41f1017_agg4:𐅍𐀅𐚰𐂼𐃨𐅩𐀃𐍀𐄯𐂈𐄎𐂒𐀽𐁊𐃡𐆙𐀳𐃪𐀋𐀕𐁗𐁑𐂐𐀎𐀁𐊫𐀈𐆛𐂦𐀢𐀜𐁉𐁈𐆙𐎜𐌳
TSKY https://duck.ac/submission/19388 和 https://duck.ac/submission/47426:完整HintFFT及原生算术基础,遵MIT保留原文如下。
174520完整Pi3M引擎/成对PMADD/种子;174750已持有的十素数合并整除思想,不读取已达Pi1M代码;174872本题组合,174822完整公开packed整数小乘/树捷径;174883本题融合底盘;其余祖先继承FFT/树/原生/精度/格式化/缓存,逐项原用途按直接父链;Duck无附加许可。
MIT License
Copyright (c) 2023 With-Sky
Permission is hereby granted,free of charge,to any person obtaining a copy
of this software and associated documentation files(the"Software"),to deal
in the Software without restriction,including without limitation the rights
to use,copy,modify,merge,publish,distribute,sublicense,and/or sell
copies of the Software,and to permit persons to whom the Software is
furnished to do so,subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED"AS IS",WITHOUT WARRANTY OF ANY KIND,EXPRESS OR
IMPLIED,INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,DAMAGES OR OTHER
LIABILITY,WHETHER IN AN ACTION OF CONTRACT,TORT OR OTHERWISE,ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
Approach/思路:174897本题8/9块合并整除与42项PMADD思想;本次把本题原生精确叶扩大16/17项并把固定limb容量扩32,每prime由P前缀/Q后缀估算保证公共因子,7沿用完整模表;奇除数合并前检查uint64容量,必要时分批,P/Q/T全三次整除carry全部0才共同提交,失败保持原值。原8/9 fallback保留,重新GMP构造23440位商种子;全GMP/PQT/3M字符后官网,无新观察。
Experiment purpose/试验目的:全种子GMP恒等/无损打包、原生/商/系数/FFT单元和完整所有位GMP48guard后官网,无测试观测/本地速度过滤。
*/
#include <bits/stdc++.h>
#include <x86intrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("web,rename-registers")
#pragma GCC optimize("align-loops=32")
constexpr auto statement="Do NOT modify this statement! " "https://github.com/With-Sky/HintFFT " "TSKY (WithSky)";
#include <complex>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <climits>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx2,fma")
#pragma GCC target("bmi2")
static inline __m256d ar_pdload(const double*p){__m256d v;asm("vmovupd %1,%0":"=x"(v):"m"(*(const __m256d*)p));return v;}static inline void ar_pdstore(double*p,__m256d v){asm volatile("vmovupd %1,%0":"=m"(*(__m256d*)p):"x"(v));}static inline __m256i ivload1043(const void*p){__m256i v;asm("vmovdqu %1,%0":"=x"(v):"m"(*(const __m256i*)p));return v;}static inline void ivstore1043(void*p,__m256i v){asm volatile("vmovdqu %1,%0":"=m"(*(__m256i*)p):"x"(v));} /* Idea: Split the fused integer-input first radix4 layer into exact live ranges. Within each range all full vector input loads are proven valid; only the single boundary vector uses cv4 bounds checks. Dispatch compile-time numbers of live arms, and zero an entirely empty range without root arithmetic. This removes repeated per-load comparisons and scalar padding construction while retaining the same valid input conversion, butterfly graph, roots and recursive FFT. Experiment: carry/multiply/PQT unit tests and full boundary/3M Pi digit comparison against independent GMP reference before official measurement. */
#define NTZERO_THRESH 16777216
static inline void* nt_zero(void*p,int c,size_t n){if(n>=NTZERO_THRESH){char*q=(char*)p;size_t i=0;for(;i<n &&((uintptr_t)(q+i)&31);++i)q[i]=(char)c;if(c==0){__m256i z=_mm256_setzero_si256();for(;i+32<=n;i+=32)_mm256_stream_si256((__m256i*)(q+i),z);}else{for(;i+32<=n;i+=32)memset(q+i,c,32);}_mm_sfence();for(;i<n;++i)q[i]=(char)c;return p;}return memset(p,c,n);}
#define Ab 10000
#define By 10000000000000000ULL
#define Cu 100000000ULL
#define Ed 2401
#define Ez 0.70710678118654752440084436210485
#define E3 10000000000000000000ULL
#define E8 100000000
#define F0 10939058860032000ull
#define Jn 545140134ULL
#define Ku 13591409ULL
#define L2 3.74098937
#define A size_t
#define B const
#define C uint64_t
#define E constexpr
#define F return
#define G unsigned
#define H static
#define I template
#define J _mm256_permutevar8x32_epi32
#define K input
#define L Complex
#define M uint32_t
#define O __uint128_t
#define P _mm256_and_si256
#define Q carry
#define R imag
#define S C64X4
#define T real
#define V data
#define W void
#define X _mm256_set1_epi32
#define Y size
#define Z float_len
#define D __m256i
#define N ar_factor_inverse
#define Aa rank
#define Ac SIZE_TYPE
#define Ad typename
#define Ae reinterpret_cast
#define Af begin
#define Ag Float64
#define Ai fft_len
#define Aj Complex2
#define Ak double
#define Al _mm256_setr_epi32
#define Am fft_split_radix_dit_template
#define An fft_split_radix_dif_template
#define Ao F64X4
#define Ap std
#define Aq fft_2point
#define Ar inline
#define As len1
#define At for
#define Au operator
#define Av shift
#define Aw dividend
#define Ax ary_ptr
#define Ay Float
#define Az len2
#define A0 __m256d
#define A1 auto
#define A2 Big
#define A3 nullptr
#define A4 _mm256_add_epi32
#define A5 BASE
#define A6 change_length
#define A7 FFTAVX
#define A8 else
#define A9 using
#define Ba divisor
#define Bb table1
#define Bc while
#define Bd _mm256_or_si256
#define Be FROM_RIRI_PERM
#define Bf transform2
#define Bg ar_gtable
#define Bh resize
#define Bi hint_arithm
#define Bj _mm256_permute2f128_pd
#define Bk tmp3
#define Bl high
#define Bm set_true_len
#define Bn store
#define Bo len
#define Bp hintpowfft
#define Br _mm256_sub_epi32
#define Bs neg
#define Bt int
#define Bu HintVector
#define Bv normalized_dividend
#define Bw ary_true_len
#define Bx bool
#define Bz base_len
#define B0 true
#define B1 real_dot_binrev4
#define B2 table3
#define B3 iditRecLong
#define B4 SIZE_TYPE_BITS
#define B5 hint_log2
#define B6 transpose64_4X4
#define B7 getBegin
#define B8 UINT_64
#define B9 sizeof
#define Ca digits
#define Cb multi_table_2
#define Cc quarter_len
#define Cd limbs
#define Ce out
#define Cf quo_digit
#define Cg other
#define Ch log_len
#define Ci omega
#define Cj pos
#define Ck omega_cube
#define Cl factor
#define Cm _mm256_set1_pd
#define Cn __m128i
#define Co tmp2
#define Cp ar_prime_inv_table
#define Cq tmp0
#define Cr tmp1
#define Cs ivload1043
#define Ct _mm256_mul_pd
#define Cv mulConj
#define Cw integral_constant
#define Cx ComplexTableY
#define Cy quot
#define Cz _mm256_setzero_si256
#define C0 new_size
#define C1 hintvector
#define C2 abs_compare
#define C3 multiplier
#define C4 NoInitAlloc
#define C6 F64
#define C8 zero
#define C9 _mm256_set1_epi64x
#define Da BinRevTableC64X4HP
#define Db _mm256_blend_epi32
#define Dc theta
#define Dd ar_src_dispatch
#define De fft_split_radix_dit_butterfly
#define Df fft_split_radix_dif_butterfly
#define Dg Ar512
#define Di namespace
#define Dj Complex64X4
#define Dk LOG_BEGIN
#define Dl FFTSqrtTableC64X4
#define Dm false
#define Dn MAX_LOG_LEN
#define Dp borrow
#define Dr _mm256_cvtepu32_epi64
#define Ds tmp7
#define Dt sqrt_table_1
#define Du end
#define Dv _mm256_extract_epi32
#define Dw struct
#define Dx conv
#define Dy dividend_2digits
#define Dz class
#define D0 Float64X4
#define D1 int_ceil2
#define D2 alignas
#define D3 multi_table_3
#define D4 sign_n_len
#define D5 _mm256_cvttpd_epi32
#define D6 sp_to_big
#define D7 _mm256_floor_pd
#define D8 HINT_2PI
#define D9 ary_copy
#define Ea vec_size
#define Eb sp_fwd
#define Ec ivstore1043
#define Ee divisor_2digits
#define Ef quot_len
#define Eg carryu
#define Eh need_p
#define Ei this
#define Ej _mm256_extracti128_si256
#define Ek reciprocal_sqrt_constant
#define El _mm256_unpacklo_pd
#define Em _mm256_unpackhi_pd
#define En mul
#define Eo index
#define Ep _mm256_cvtepi32_pd
#define Eq _mm256_cmpgt_epi32
#define Er _mm256_testz_si256
#define Es _mm256_mullo_epi32
#define Et it0
#define Eu UINT_32
#define Ev SIZE_80
#define Ew dividend_ptr
#define Ex ar_take
#define Ey length
#define E0 transform
#define E1 _mm256_srli_epi32
#define E4 _mm256_castsi256_si128
#define E5 used
#define E6 delete
#define E7 _mm256_sub_pd
#define E9 TableFixMulti
#define Fa static_assert
#define Fb CACHE_LOG_LEN
#define Fc table2
#define Fd FloatTy
#define Fe static_cast
#define Ff vector
#define Fg tmp5
#define Fh change_sign
#define Fi abs_mul_num
#define Fj __builtin_memcpy
#define Fk _mm256_add_epi64
#define Fl abs_rec_div
#define Fm move
#define Fn written
#define Fo ar_drop
#define Fp long
#define Fq AlignMem
#define Fr transpose64_2X4
#define Fs it1
#define Ft it2
#define Fu _mm_loadu_si128
#define Fv break
#define Fw max_shift
#define Fx half_len
#define Fy ele_size
#define Fz uintptr_t
#define F1 push_back
#define F2 ar_decimal_word
#define F4 TO_RIRI_PERM
#define F5 carry550fold
#define F6 unit_table
#define F7 RI_DIFF
#define F8 ar_i
#define F9 ar_unit_square
#define Ga low
#define Gb base
#define Gc _mm256_mulhi_epu16
#define Gd _mm256_mullo_epi16
#define Ge _mm256_cmpeq_epi32
#define Gf normalized_divisor
#define Gg public
#define Gh res
#define Gi getBeginLog
#define Gj ar_src_span
#define Gk assign
#define Gl ar_vec
#define Gm reverse
#define Gn SHORT_LEN
#define Go LOG_SHORT
#define Gp multi_table_1
#define Gq addConj
#define Gr real_dot_binrev4t
#define Gs tmp6
#define Gt LEN_MAX
#define Gu abs_sub
#define Gv _mm256_set1_epi16
#define Gw sub_len
#define Gx __attribute__
#define Gy ar_carry_sub3
#define Gz keep
#define G0 ar_invodd
#define G1 ar_native_mul
#define G2 inv
#define G3 difRecLong
#define G4 fft_dit_template
#define G5 fft_dif_template
#define G6 new_length
#define G7 _mm_lfence
#define G8 ar_unit_cube
#define G9 in1
#define Ha cur_log_size
#define Hb sub
#define Hc quot_tmp_len
#define Hd zzN
#define He add
#define Hf binary_split
#define Hg private
#define Hh tail
#define Hi it3
#define Hj element_permute
#define Hk last_rem
#define Hl _mm_alignr_epi8
#define Hm ar_digit_vector
#define Hn top
#define Hq ptr
#define Hr toRRIIPermu
#define Hs table_len
#define Ht throw
#define Hu unit_root
#define Hv divisor_ptr
#define Hw remainder
#define Hx ar19slide
#define Hy ar512leaf
#define Hz prod
#define H2 trim
#define H3 ar_seven_table
#define H4 YMM
#define H6 sqrt_scaled_constant
#define H8 _mm_malloc
#define H9 row0
#define Ia row1
#define Ib in_data
#define Ic complex
#define Id LOG_MAX
#define Ie tmp
#define If cos_1_8
#define Ig LEN
#define Ih count
#define Ii _mm_add_epi32
#define Ij always_inline
#define Ik ar_carry_add3
#define Il ar_carry_addi
#define Im ar_carry_subi
#define Io UINT64_MAX
#define Ip ar_r
#define Iq dcut
#define Ir sp_reserve
#define Is ar_reduced_fallback
#define It ar_reduced
#define Iu ar_pn
#define Iv ar_gs
#define Iw TO_INT64
#define Ix inout0
#define Iy inout1
#define Iz INT_32
#define I0 prod_len
#define I1 noexcept
#define I2 sum
#define I5 LONG_DIV_THRESHOLD
#define I6 FFTTableSqrt
#define I7 temp
#define I8 max_log_size
#define I9 get_omega3X2
#define Ja sums
#define Jb _mm256_setzero_pd
#define Jc _mm256_srli_epi64
#define Jd CACHE_LEN
#define Je TableLong
#define Jf iditSplit
#define Jh _mm256_load_si256
#define Ji _mm256_madd_epi16
#define Jj divisor_normalize
#define Jk _mm256_slli_epi32
#define Jl iv901base
#define Jm iv581have
#define Jo ar512word
#define Jp ar19parts
#define Js initOmegaX4
#define Ju omega0
#define Jv LOG_MID
#define Jw MID_LEN
#define Jx TableMulti1
#define Jy TableMulti2
#define Jz TableMulti3
#define J3 swap
#define J4 INT_64
#define J5 get_omegaX2
#define J6 tmp4
#define J7 abs_div_num
#define J9 fft_mul
#define Ka Borr
#define Kb mulnum
#define Kc divnum
#define Kd ar_rem
#define Ke ar512extend
#define Kh __rdtsc
#define Kk _mm_free
#define Kn load1
#define Ko TableFix
#define Kq log_rank
#define Kr difSplit
#define Kt BLOCK
#define Kv block
#define Kx dot_rfft
#define Ky TABLE
#define Kz is_carry
#define K0 carry550
#define K1 quot_tmp
#define K3 pop_back
#define K4 subtract
#define K6 ar_fc
#define K7 load
#define K8 false_type
#define K9 char
#define La table_16_1
#define Lb table_16_3
#define Lc table_32_1
#define Ld table_32_3
#define Le iditRecMid
#define Lf pi_compute
#define Lg dtop
#define Lh iv581reuse
#define Li emit
#define Lj iv1299bits
#define Lk fpow
#define Lz omega1
#define L0 it32_1
#define L1 it32_3
#define L4 string
#define L5 before
#define L6 packed
#define L7 cmpabs
#define L8 qChunk
#define Mc HINT_PI
#define Mf LOG_END
#define Mh cpx_len
#define Mi len_div
#define Mj low_len
#define Mu default
#define M3 size2
#define M5 abs_add
#define M7 nt_zero
#define Nb coeff
#define Nc seven
#define Ni pending
Di Bp{I<Ad zT,A ALIGN=64> Dz Fq{Gg: A9 Ptr=zT*;A9 ConstPtr=B zT*;~Fq(){if(Hq){Kk(Hq);}};Fq():Hq(A3),Bo(0){}Fq(A n):Hq(Ae<Ptr>(H8(n*B9(zT),ALIGN))),Bo(n){}Fq(B Fq&)=E6;Fq&Au=(B Fq&)=E6;zT&Au[](A i){F Hq[i];}B zT&Au[](A i)B{F Hq[i];}Ptr Af(){F Hq;}Ptr Du(){F Hq+Bo;}ConstPtr Af()B{F Hq;}ConstPtr Du()B{F Hq+Bo;}A Y()B{F Bo;}Hg: zT*Hq;A Bo;};I<Ad H4> Ar W Fr(H4&H9,H4&Ia){A1 t0=El(A0(H9),A0(Ia));A1 t1=Em(A0(H9),A0(Ia));H9=H4(Bj(t0,t1,0x20));Ia=H4(Bj(t0,t1,0x31));}I<Ad H4> Ar W transpose64_4X2(H4&H9,H4&Ia){A1 t0=Bj(A0(H9),A0(Ia),0x20);A1 t1=Bj(A0(H9),A0(Ia),0x31);H9=H4(El(t0,t1));Ia=H4(Em(t0,t1));}I<Ad H4> Ar W B6(H4&H9,H4&Ia,H4&row2,H4&row3){A1 t0=El(A0(H9),A0(Ia));A1 t1=Em(A0(H9),A0(Ia));A1 t2=El(A0(row2),A0(row3));A1 t3=Em(A0(row2),A0(row3));H9=H4(Bj(t0,t2,0x20));Ia=H4(Bj(t1,t3,0x20));row2=H4(Bj(t0,t2,0x31));row3=H4(Bj(t1,t3,0x31));}Dz D0{Gg: A9 C6=Ak;A9 Ao=D0;D0():V(Jb()){}D0(A0 Ib):V(Ib){}D0(C6 Ib):V(Cm(Ib)){}D0(B C6*Ib):V(_mm256_load_pd(Ib)){}Ao Au+(B Ao&Cg)B{F _mm256_add_pd(V,Cg.V);}Ao Au-(B Ao&Cg)B{F E7(V,Cg.V);}Ao Au*(B Ao&Cg)B{F Ct(V,Cg.V);}Ao Au/(B Ao&Cg)B{F _mm256_div_pd(V,Cg.V);}H Ao fmadd(B Ao&a,B Ao&b,B Ao&c){F _mm256_fmadd_pd(a.V,b.V,c.V);}H Ao fmsub(B Ao&a,B Ao&b,B Ao&c){F _mm256_fmsub_pd(a.V,b.V,c.V);}I<Bt zN> Ao permute4x64()B{F _mm256_permute4x64_pd(V,zN);}Ao Gm()B{F permute4x64<0b00011011>();}W K7(B C6*p){V=_mm256_load_pd(p);}W Kn(B C6*p){V=_mm256_broadcast_sd(p);}W Bn(C6*p)B{_mm256_store_pd(p,V);}W Nt(C6*p)B{_mm256_stream_pd(p,V);}Au A0()B{F V;}D toI64X4()B{E C mask=(C(1)<<52)-1;E C offset=(C(1)<<10)-1;B D f64bits=_mm256_castpd_si256(V);D Hh=P(f64bits,C9(mask));Hh=Bd(Hh,C9(mask+1));D exp=Jc(f64bits,52);exp=_mm256_sub_epi64(C9(offset+52),exp);F _mm256_srlv_epi64(Hh,exp);}Hg: A0 V;};Dw Dj{A9 S=Dj;A9 Ao=D0;A9 C6=Ak;Dj(){}Dj(Ao T,Ao R):T(T),R(R){}Dj(B C6*p):T(p),R(p+4){}Dj(B C6*p_real,B C6*p_imag):T(p_real),R(p_imag){}S Au+(B S&Cg)B{F S(T+Cg.T,R+Cg.R);}S Au-(B S&Cg)B{F S(T-Cg.T,R-Cg.R);}S Au*(B Ao&Cg)B{F S(T*Cg,R*Cg);}S F9()B{B Ao t=R+R;F S(Ao(_mm256_fnmadd_pd(A0(R),A0(t),Cm(1.))),T*t);}S G8(B S&w)B{B Ao t=R+R;F S(Ao(_mm256_fnmadd_pd(A0(t),A0(w.R),A0(T))),Ao(_mm256_fmadd_pd(A0(t),A0(w.T),A0(R))));}S En(B S&Cg)B{B Ao ii=R*Cg.R;B Ao ri=T*Cg.R;B Ao r=Ao::fmsub(T,Cg.T,ii);B Ao i=Ao::fmadd(R,Cg.T,ri);F S(r,i);}S Cv(B S&Cg)B{B Ao ii=R*Cg.R;B Ao ri=T*Cg.R;B Ao r=Ao::fmadd(T,Cg.T,ii);B Ao i=Ao::fmsub(R,Cg.T,ri);F S(r,i);}S Gm()B{F S(T.Gm(),R.Gm());}W set1(C6 real_in,C6 imag_in){T=Ao(real_in);R=Ao(imag_in);}I<Ad zT> W K7(B zT*p,Ap::K8){Ei->K7(p);}I<Ad zT> W K7(B zT*p,Ap::true_type){Ei->K7(p);*Ei=Ei->Hr();}I<Ad zT> W K7(B zT*p){T.K7(Ae<B C6*>(p));R.K7(Ae<B C6*>(p)+4);}W Kn(B C6*real_p,B C6*imag_p){T.Kn(real_p);R.Kn(imag_p);}I<Ad zT> W Bn(zT*p,Ap::K8)B{Ei->Bn(p);}I<Ad zT> W Bn(zT*p,Ap::true_type)B{Ei->toRIRIPermu().Bn(p);}I<Ad zT> W Bn(zT*p)B{T.Bn(Ae<C6*>(p));R.Bn(Ae<C6*>(p)+4);}I<Ad zT> W Nt(zT*p)B{T.Nt(Ae<C6*>(p));R.Nt(Ae<C6*>(p)+4);}S toRIRIPermu()B{S Gh= *Ei;Fr(Gh.T,Gh.R);F Gh;}S Hr()B{S Gh= *Ei;transpose64_4X2(Gh.T,Gh.R);F Gh;}S transToI64(Ap::K8)B{F*Ei;}S transToI64(Ap::true_type)B{E int64_t F1_2=4602678819172646912;A1 F1_2X4=Ao(A0(C9(F1_2)));F S(D7(T+F1_2X4),D7(R+F1_2X4));}Ao T,R;};A9 Float32=float;A9 Ag=Ak;E Ag Mc=3.141592653589793238462643;E Ag D8=Mc*2;E Ag COS_PI_8=0.707106781186547524400844;I<Ad zT> E zT D1(zT n){E Bt bits=B9(n)*8;n--;At(Bt i=1;i<bits;i*=2){n|=(n>>i);}F n+1;}I<Ad IntTy> E Bx is_2pow(IntTy n){F n!=0&&(n&(n-1))==0;}I<Ad zT> E Bt B5(zT n){E Bt bits=B9(n)*8;Bt l= -1,r=bits;Bc((l+1)!=r){Bt mid=(l+r)/2;if((zT(1)<<mid)>n){r=mid;}A8{l=mid;}}F l;}E M crc32(B K9*str){M crc=0xFFFFFFFF;Bc(*str!='\0'){crc^= *str;At(Bt i=0;i<8;++i){crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}str++;}F~crc;}Di E0{I<Ad zT> Ar W Bf(zT&I2,zT&diff){zT temp0=I2,temp1=diff;I2=temp0+temp1;diff=temp0-temp1;}Di fft{A9 C6=Ag;A9 C64=Ap::Ic<C6>;A9 Ao=D0;A9 S=Dj;I<Ad Ay,A OMEGA_LEN> Dz Ko{D2(64)Ay table[OMEGA_LEN*2];Gg: Ko(A theta_divider,A Cl,A stride){B Ay Dc= -D8*Cl/theta_divider;At(A Af=0,Eo=0;Af<OMEGA_LEN*2;Af+=stride*2){At(A j=0;j<stride;j++,Eo++){table[Af+j]=Ap::cos(Dc*Eo);table[Af+j+stride]=Ap::sin(Dc*Eo);}}}E B Ay&Au[](A Eo)B{F table[Eo];}};W Js(C6*arr,A Ai,Bt Hs,Bt Cl){Hs/=4;B C6 Dc= -D8*Cl/Ai;A1 arrx4=Ae<S*>(arr);arr[0]=1,arr[4]=0;arr[1]=Ap::cos(Dc),arr[5]=Ap::sin(Dc);arr[2]=Ap::cos(Dc*2),arr[6]=Ap::sin(Dc*2);arr[3]=Ap::cos(Dc*3),arr[7]=Ap::sin(Dc*3);At(A Af=1;Af<Hs;Af*=2){A nth=Af*4;S unit;unit.set1(Ap::cos(Dc*nth),Ap::sin(Dc*nth));At(A i=0;i<Af;i++){arrx4[Af+i]=arrx4[i].En(unit);}}}I<Ad Ay,Bt Dk,Bt Mf,Bt DIV> Dz E9{Fa(Mf>=Dk);Fa(is_2pow(DIV));H E A TABLE_CPX_LEN=(A(1)<<(Mf+1))/DIV;D2(64)Ay table[TABLE_CPX_LEN*2];Gg: E9(A Cl,A stride=4){initBottomUp(Cl,stride);}W initBottomUp(A Cl,A stride){Fa(Ap::is_same<Ay,Ag>::value);A Bo=A(1)<<Dk,Mh=Bo/DIV;A1 it=Gi(Dk);Js(it,Bo,Mh,Cl);At(Bt Ch=Dk+1;Ch<=Mf;Ch++){Bo=A(1)<<Ch,Mh=Bo/DIV;Ay Dc= -D8*Cl/Bo;A1 it=Gi(Ch),it_last=Gi(Ch-1);S unit(Ap::cos(Dc),Ap::sin(Dc));At(A1 Du=it+Mh*2;it<Du;it+=16,it_last+=8){S Ju,Lz;Ju.K7(it_last);Lz=Ju.En(unit);Fr(Ju.T,Lz.T);Fr(Ju.R,Lz.R);Ju.Bn(it),Lz.Bn(it+8);}}}E B Ay*Gi(Bt Kq)B{F B7(A(1)<<Kq);}E Ay*Gi(Bt Kq){F B7(A(1)<<Kq);}E B Ay*B7(A Aa)B{F&table[Aa*2/DIV];}E Ay*B7(A Aa){F&table[Aa*2/DIV];}};I<Bt Fb> Dz Dl{Gg: A9 C6=Ak;A9 C64=Ap::Ic<Ak>;A9 S=Bp::Dj;H E A Jd=A(1)<<Fb;H E A MASK=Jd-1;H E A C4_COUNT=B9(S)/B9(C64);~Dl(){if(Bl){E6[]Bl;}}Dl(){}Dl(A Ai,Bt Mi,Bt Cl){init(Ai,Mi,Cl);}W init(A Ai,Bt Mi,Bt Cl){A Hs=Ai/Mi;A Mj=Jd*C4_COUNT,high_len=Hs/Mj;if(Bl!=A3){E6[]Bl;}Bl=new C64[high_len];A1 p=Ae<C6*>(&Ga[0]);Js(p,Ai,Mj,Cl);B C6 Dc= -D8*Cl/Ai;Bl[0]=C64(1,0);At(A Af=1;Af<high_len;Af*=2){C64 unit=Ap::polar<C6>(1.0,Dc*Af*Mj);At(A i=0;i<Af;i++){Bl[i+Af]=Bl[i]*unit;}}}S Au[](A i)B{S hi;A1 p=Ae<B C6*>(&Bl[i>>Fb]);hi.Kn(p,p+1);F Ga[i&MASK].En(hi);}Hg: D2(64)S Ga[Jd];C64*Bl=A3;};I<Bt DIV,Bt Dk,Bt Id,Bt Fb> Dz I6{A9 Je=Dl<Fb>;H E A Gn=A(1)<<Dk;H E A TABLE_LEN=Id-Dk+1;Gg: I6(Bt Cl){At(Bt i=0;i<TABLE_LEN;i++){A Ai=Gn<<i;table[i].init(Ai,DIV,Cl);}}B Je&Au[](Bt Ch)B{Ch-=Dk;F table[Ch];}Je&Au[](Bt Ch){Ch-=Dk;F table[Ch];}Hg: Je table[TABLE_LEN];};Dw FFT{I<Ad Ay> H W trans2MulI(Ay&r0,Ay&i0,Ay&r1,Ay&i1){A1 I7=r1;r1=r0+i1;r0=r0-i1;i1=i0-I7;i0=i0+I7;}I<Ad Ay> H W trans2MulNegI(Ay&r0,Ay&i0,Ay&r1,Ay&i1){A1 I7=r1;r1=r0-i1;r0=r0+i1;i1=i0+I7;i0=i0-I7;}I<Ad Ay> H W dif4(Ay&r0,Ay&i0,Ay&r1,Ay&i1,Ay&r2,Ay&i2,Ay&r3,Ay&i3){Kr(r0,i0,r1,i1,r2,i2,r3,i3);Bf(r0,r1);Bf(i0,i1);}I<Ad Ay> H W idit4(Ay&r0,Ay&i0,Ay&r1,Ay&i1,Ay&r2,Ay&i2,Ay&r3,Ay&i3){Bf(r0,r1);Bf(i0,i1);Jf(r0,i0,r1,i1,r2,i2,r3,i3);}I<Ad Ay> H W Kr(Ay&r0,Ay&i0,Ay&r1,Ay&i1,Ay&r2,Ay&i2,Ay&r3,Ay&i3){Bf(r0,r2);Bf(i0,i2);Bf(r1,r3);Bf(i1,i3);trans2MulNegI(r2,i2,r3,i3);}I<Ad Ay> H W Jf(Ay&r0,Ay&i0,Ay&r1,Ay&i1,Ay&r2,Ay&i2,Ay&r3,Ay&i3){Bf(r2,r3);Bf(i2,i3);Bf(r0,r2);Bf(i0,i2);trans2MulI(r1,i1,r3,i3);}};Dw A7:Gg FFT{H E Bt Go=7,Jv=25-crc32(statement)%15,Id=24,LOG_CACHE=8;H E A Gn=A(1)<<Go,Jw=A(1)<<Jv,MAX_LEN=A(1)<<Id;A9 TableFix4=B Ko<Ag,4>;A9 TableFix8=B Ko<Ag,8>;A9 Jx=B E9<Ag,Go+1,Jv,4>;A9 Jy=B E9<Ag,6,Go+1,4>;A9 Jz=B E9<Ag,6,Go,4>;A9 TableSqrt=B I6<4,Jv+1,Id,LOG_CACHE>;H TableFix4 table_8,La,Lb;H TableFix8 Lc,Ld;H Jy Cb;H Jz D3;H Jx Gp;H TableSqrt Dt;H E B Ag*it8= &table_8[0],*it16_1= &La[0],*it16_3= &Lb[0],*L0= &Lc[0],*L1= &Ld[0];H W dif4x4(Ao&r0,Ao&i0,Ao&r1,Ao&i1,Ao&r2,Ao&i2,Ao&r3,Ao&i3){B6(r0,r1,r2,r3);B6(i0,i1,i2,i3);dif4(r0,i0,r1,i1,r2,i2,r3,i3);B6(r0,r1,r2,r3);B6(i0,i1,i2,i3);}H W idit4x4(Ao&r0,Ao&i0,Ao&r1,Ao&i1,Ao&r2,Ao&i2,Ao&r3,Ao&i3){B6(r0,r1,r2,r3);B6(i0,i1,i2,i3);idit4(r0,i0,r1,i1,r2,i2,r3,i3);B6(r0,r1,r2,r3);B6(i0,i1,i2,i3);}H W dif8x2(S&c0,S&c1,S&c2,S&c3){S Ci(it8);Bf(c0,c1);Bf(c2,c3);c1=c1.En(Ci),c3=c3.En(Ci);dif4x4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);}H W idit8x2(S&c0,S&c1,S&c2,S&c3){S Ci(it8);idit4x4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c1=c1.Cv(Ci),c3=c3.Cv(Ci);Bf(c0,c1);Bf(c2,c3);}H W dif16(Ag in_out[]){A1 p=Ae<S*>(in_out);S c0=p[0],c1=p[1],c2=p[2],c3=p[3];dif4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c1=c1.En(S(it8)),c2=c2.En(S(it16_1)),c3=c3.En(S(it16_3));dif4x4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}H W idit16(Ag in_out[]){A1 p=Ae<S*>(in_out);S c0=p[0],c1=p[1],c2=p[2],c3=p[3],Ci;idit4x4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c1=c1.Cv(S(it8)),c2=c2.Cv(S(it16_1)),c3=c3.Cv(S(it16_3));idit4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}H W dif32(Ag in_out[]){A1 p=Ae<S*>(in_out);S c0=p[0],c1=p[2],c2=p[4],c3=p[6];Kr(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c2=c2.En(S(L0)),c3=c3.En(S(L1));p[0]=c0,p[2]=c1,p[4]=c2,p[6]=c3;c0=p[1],c1=p[3],c2=p[5],c3=p[7];Kr(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c2=c2.En(S(L0+8)),c3=c3.En(S(L1+8));p[1]=c0,p[3]=c1,c0=p[4],c1=p[6];dif8x2(c0,c2,c1,c3);p[4]=c0,p[5]=c2,p[6]=c1,p[7]=c3;dif16(in_out);}H W idit32(Ag in_out[]){idit16(in_out);A1 p=Ae<S*>(in_out);S c0=p[4],c1=p[5],c2=p[6],c3=p[7];idit8x2(c0,c1,c2,c3);p[5]=c1,p[7]=c3,c1=p[0],c3=p[2];c0=c0.Cv(S(L0)),c2=c2.Cv(S(L1));Jf(c1.T,c1.R,c3.T,c3.R,c0.T,c0.R,c2.T,c2.R);p[0]=c1,p[2]=c3,p[4]=c0,p[6]=c2;c0=p[1],c1=p[3],c2=p[5],c3=p[7];c2=c2.Cv(S(L0+8)),c3=c3.Cv(S(L1+8));Jf(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);p[1]=c0,p[3]=c1,p[5]=c2,p[7]=c3;}I<Ad F32,Ad F16> H W fftTiny(Ag in_out[],A Z,F32&&func32,F16&&func16){if(B5(Z/2)%2==0){At(A1 Du=in_out+Z;in_out<Du;in_out+=32){func16(in_out);}}A8{At(A1 Du=in_out+Z;in_out<Du;in_out+=64){func32(in_out);}}}H W difIter(Ag in_out[],A Z){A Ai=Z/2;S c0,c1,c2,c3;A stride=Ai/2;A1 Et=in_out,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(A Aa=Ai;Aa>=64;Aa/=4){stride=Aa/2;At(A1 Af=in_out,Du=in_out+Z;Af<Du;Af+=Aa*2){A1 Bb=Cb.B7(Aa*2),Fc=Cb.B7(Aa),B2=D3.B7(Aa);Et=Af,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(;Et<Af+stride;Et+=8,Fs+=8,Ft+=8,Hi+=8,Bb+=8,Fc+=8,B2+=8){c0=Et,c1=Fs,c2=Ft,c3=Hi;dif4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c1=c1.En(S(Fc)),c2=c2.En(S(Bb)),c3=c3.En(S(B2));c0.Bn(Et),c1.Bn(Fs),c2.Bn(Ft),c3.Bn(Hi);}}}fftTiny(in_out,Z,dif32,dif16);}I<A AP> H W tinyDif(Ag in_out[]){A Ai=AP/2;if(B5(Ai)%2==0){At(A1 Du=in_out+AP;in_out<Du;in_out+=32)dif16(in_out);}A8{At(A1 Du=in_out+AP;in_out<Du;in_out+=64)dif32(in_out);}}I<A AP> H W tinyIdit(Ag in_out[]){A Ai=AP/2;if(B5(Ai)%2==0){At(A1 Du=in_out+AP;in_out<Du;in_out+=32)idit16(in_out);}A8{At(A1 Du=in_out+AP;in_out<Du;in_out+=64)idit32(in_out);}}I<A AP> H W difIterC(Ag in_out[]){A Ai=AP/2;S c0,c1,c2,c3;A stride=Ai/2;A1 Et=in_out,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(A Aa=Ai;Aa>=64;Aa/=4){stride=Aa/2;At(A1 Af=in_out,Du=in_out+AP;Af<Du;Af+=Aa*2){A1 Bb=Cb.B7(Aa*2),Fc=Cb.B7(Aa),B2=D3.B7(Aa);Et=Af,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(;Et<Af+stride;Et+=8,Fs+=8,Ft+=8,Hi+=8,Bb+=8,Fc+=8,B2+=8){c0=Et,c1=Fs,c2=Ft,c3=Hi;dif4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c1=c1.En(S(Fc)),c2=c2.En(S(Bb)),c3=c3.En(S(B2));c0.Bn(Et),c1.Bn(Fs),c2.Bn(Ft),c3.Bn(Hi);}}}tinyDif<AP>(in_out);}H W iditIter(Ag in_out[],A Z){A Ai=Z/2;A Aa=B5(Ai)%2==0?64:128;fftTiny(in_out,Z,idit32,idit16);At(;Aa<=Ai;Aa*=4){B A stride=Aa/2;At(A1 Af=in_out,Du=in_out+Z;Af<Du;Af+=Aa*2){A1 Bb=Cb.B7(Aa*2),Fc=Cb.B7(Aa),B2=D3.B7(Aa);A1 Et=Af,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(;Et<Af+stride;Et+=8,Fs+=8,Ft+=8,Hi+=8,Bb+=8,Fc+=8,B2+=8){S c0=Et,c1=Fs,c2=Ft,c3=Hi;c1=c1.Cv(S(Fc)),c2=c2.Cv(S(Bb)),c3=c3.Cv(S(B2));idit4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c0.Bn(Et),c1.Bn(Fs),c2.Bn(Ft),c3.Bn(Hi);}}}}I<A AP> H W iditIterC(Ag in_out[]){A Ai=AP/2;A Aa=B5(Ai)%2==0?64:128;tinyIdit<AP>(in_out);At(;Aa<=Ai;Aa*=4){B A stride=Aa/2;At(A1 Af=in_out,Du=in_out+AP;Af<Du;Af+=Aa*2){A1 Bb=Cb.B7(Aa*2),Fc=Cb.B7(Aa),B2=D3.B7(Aa);A1 Et=Af,Fs=Et+stride,Ft=Fs+stride,Hi=Ft+stride;At(;Et<Af+stride;Et+=8,Fs+=8,Ft+=8,Hi+=8,Bb+=8,Fc+=8,B2+=8){S c0=Et,c1=Fs,c2=Ft,c3=Hi;c1=c1.Cv(S(Fc)),c2=c2.Cv(S(Bb)),c3=c3.Cv(S(B2));idit4(c0.T,c0.R,c1.T,c1.R,c2.T,c2.R,c3.T,c3.R);c0.Bn(Et),c1.Bn(Fs),c2.Bn(Ft),c3.Bn(Hi);}}}}
#define difLayer(dif_func, in_out, stride, table) \
do \
{ \
auto it0 = in_out, it1 = in_out + stride, it2 = it1 + stride, it3 = it2 + stride; \
size_t indx = 0; \
_Pragma("GCC unroll 2") \
for (auto end = it1; FROM_RIRI_PERM && it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+96),_MM_HINT_T0);_mm_prefetch((const char*)(it1+96),_MM_HINT_T0);_mm_prefetch((const char*)(it2+96),_MM_HINT_T0);_mm_prefetch((const char*)(it3+96),_MM_HINT_T0);} \
C64X4 c0, c1, c2, c3, omega1, omega2; \
c0.load(it0, FromRIRI{}), c1.load(it1, FromRIRI{}), c2.load(it2, FromRIRI{}), c3.load(it3, FromRIRI{}); \
dif4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag); \
omega1 = table[indx], c2 = c2.mul(omega1); \
omega2 = omega1.ar_unit_square(), c1 = c1.mul(omega2); \
c3 = c3.mul(omega1.ar_unit_cube(omega2)); \
c0.store(it0), c1.store(it1), c2.store(it2), c3.store(it3); \
} \
_Pragma("GCC unroll 2") \
for (auto end = it1; (!FROM_RIRI_PERM) && it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+96),_MM_HINT_T0);_mm_prefetch((const char*)(it1+96),_MM_HINT_T0);_mm_prefetch((const char*)(it2+96),_MM_HINT_T0);_mm_prefetch((const char*)(it3+96),_MM_HINT_T0);} \
C64X4 c0 = it0, c1 = it1, c2 = it2, c3 = it3, omega1, omega2; \
dif4(c0.real, c0.imag, c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag); \
omega1 = table[indx], c2 = c2.mul(omega1); \
omega2 = omega1.ar_unit_square(), c1 = c1.mul(omega2); \
c3 = c3.mul(omega1.ar_unit_cube(omega2)); \
c0.store(it0), c1.store(it1), c2.store(it2), c3.store(it3); \
} \
dif_func(in_out, stride); \
dif_func(in_out + stride, stride); \
dif_func(in_out + stride * 2, stride); \
dif_func(in_out + stride * 3, stride); \
} while (0)
#define iditLayer(idit_func, in_out, stride, table) \
do \
{ \
idit_func(in_out, stride); \
idit_func(in_out + stride, stride); \
idit_func(in_out + stride * 2, stride); \
idit_func(in_out + stride * 3, stride); \
auto it0 = in_out, it1 = in_out + stride, it2 = it1 + stride, it3 = it2 + stride; \
size_t indx = 0; \
_Pragma("GCC unroll 2") \
for (auto end = it1; it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+96),_MM_HINT_T0);_mm_prefetch((const char*)(it1+96),_MM_HINT_T0);_mm_prefetch((const char*)(it2+96),_MM_HINT_T0);_mm_prefetch((const char*)(it3+96),_MM_HINT_T0);} \
C64X4 c0 = it0, c1 = it1, c2 = it2, c3 = it3, omega1, omega2; \
omega1 = table[indx], c2 = c2.mulConj(omega1); \
omega2 = omega1.ar_unit_square(), c1 = c1.mulConj(omega2); \
c3 = c3.mulConj(omega1.ar_unit_cube(omega2)); \
idit4(c0.real, c0.imag, c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag); \
c0 = c0.transToI64(ToI64{}), c1 = c1.transToI64(ToI64{}), c2 = c2.transToI64(ToI64{}), c3 = c3.transToI64(ToI64{}); \
c0.store(it0, ToRIRI{}), c1.store(it1, ToRIRI{}), c2.store(it2, ToRIRI{}), c3.store(it3, ToRIRI{}); \
} \
} while (0)
I<Bx Be=Dm> H W difRecMid(Ag in_out[],A Z){B A Ai=Z/2;if(Ai<=Gn){if(Z==128)difIterC<128>(in_out);A8 if(Z==256)difIterC<256>(in_out);A8 difIter(in_out,Z);F;}A9 FromRIRI=Ap::Cw<Bx,Be>;A1 Bb=Ae<B S*>(Gp.B7(Ai));B A stride=Z/4;difLayer(difRecMid,in_out,stride,Bb);}I<Bx F4=Dm,Bx Iw=Dm> H W Le(Ag in_out[],A Z){B A Ai=Z/2;if(Ai<=Gn){if(Z==128)iditIterC<128>(in_out);A8 if(Z==256)iditIterC<256>(in_out);A8 iditIter(in_out,Z);F;}A9 ToRIRI=Ap::Cw<Bx,F4>;A9 ToI64=Ap::Cw<Bx,Iw>;B A stride=Z/4;A1 Bb=Ae<B S*>(Gp.B7(Ai));iditLayer(Le,in_out,stride,Bb);}H Ar Ao cv4(B M*a,A i,A la){if(i+4<=la)F Ep(Fu(Ae<B Cn*>(a+i)));F Ao(_mm256_set_pd(i+3<la?a[i+3]:0,i+2<la?a[i+2]:0,i+1<la?a[i+1]:0,i<la?a[i]:0));}I<Bx Be=Dm> H W G3(Ag in_out[],A Z){B A Ai=Z/2;if(Ai<=Jw){difRecMid<Be>(in_out,Z);F;}A9 FromRIRI=Ap::Cw<Bx,Be>;B A1&Bb=Dt[B5(Ai)];B A stride=Z/4;difLayer(G3,in_out,stride,Bb);}I<G Arms,Bx Bound,Bx Perm>H Ar W Gj(Ag*d,B M*s,A la,A Bo,A Af,A Du){B A stride=Bo/4;B A1&t=Dt[B5(Bo/2)];if E(Arms==0){At(G k=0;k<4;k++)Ap::memset(d+k*stride+Af,0,(Du-Af)*B9(Ag));F;}At(A j=Af;j<Du;j+=8){S v[4];
#pragma GCC unroll 4
At(G k=0;k<Arms;k++){A at=k*stride+j;if E(Bound){v[k].T=cv4(s,at,la);v[k].R=cv4(s,at+4,la);}A8{v[k].T=Ep(Fu((B Cn*)(s+at)));v[k].R=Ep(Fu((B Cn*)(s+at+4)));}if E(Perm)v[k]=v[k].Hr();}dif4(v[0].T,v[0].R,v[1].T,v[1].R,v[2].T,v[2].R,v[3].T,v[3].R);S w=t[j/8],w2=w.F9();v[2]=v[2].En(w);v[1]=v[1].En(w2);v[3]=v[3].En(w.G8(w2));
#pragma GCC unroll 4
At(G k=0;k<4;k++){if(Bo>=1048576u)v[k].Nt(d+k*stride+j);A8 v[k].Bn(d+k*stride+j);}}}I<G Full,Bx Perm>H Ar W Dd(Ag*d,B M*s,A la,A Bo){B A stride=Bo/4;if E(Full==4){Gj<4,Dm,Perm>(d,s,la,Bo,0,stride);}A8{A rem=la-Full*stride,stop=rem&~A(7);Gj<Full+1,Dm,Perm>(d,s,la,Bo,0,stop);if(rem!=stop){Gj<Full+1,B0,Perm>(d,s,la,Bo,stop,stop+8);stop+=8;}Gj<Full,Dm,Perm>(d,s,la,Bo,stop,stride);}}I<Bx Be>H W difRecLongSrc(Ag*d,B M*s,A la,A Bo){if(Bo<(A(1)<<21)){ar_src_onelevel<Be>(d,s,la,Bo);F;}B A zQ=Bo/4,zS=Bo/16;E A zB=32,zP=zB+8;D2(64)Ag tile[16][zP];B A1&t0=Dt[B5(Bo/2)];B A1&t1=Dt[B5(zQ/2)];At(A at=0;at<zS;at+=zB){At(G Ga=0;Ga<4;Ga++)At(A j=0;j<zB;j+=8){A Cj=Ga*zS+at+j;S v[4];
#pragma GCC unroll 4
At(G Bl=0;Bl<4;Bl++){A idx=Bl*zQ+Cj;v[Bl].T=cv4(s,idx,la);v[Bl].R=cv4(s,idx+4,la);if E(Be)v[Bl]=v[Bl].Hr();}dif4(v[0].T,v[0].R,v[1].T,v[1].R,v[2].T,v[2].R,v[3].T,v[3].R);S w=t0[Cj/8],w2=w.F9();v[2]=v[2].En(w);v[1]=v[1].En(w2);v[3]=v[3].En(w.G8(w2));
#pragma GCC unroll 4
At(G Bl=0;Bl<4;Bl++)v[Bl].Bn(tile[4*Bl+Ga]+j);}At(G Bl=0;Bl<4;Bl++)At(A j=0;j<zB;j+=8){S v0=tile[4*Bl]+j,v1=tile[4*Bl+1]+j,v2=tile[4*Bl+2]+j,v3=tile[4*Bl+3]+j;dif4(v0.T,v0.R,v1.T,v1.R,v2.T,v2.R,v3.T,v3.R);S w=t1[(at+j)/8],w2=w.F9();v2=v2.En(w);v1=v1.En(w2);v3=v3.En(w.G8(w2));Ag*Ce=d+Bl*zQ+at+j;v0.Nt(Ce);v1.Nt(Ce+zS);v2.Nt(Ce+2*zS);v3.Nt(Ce+3*zS);}}_mm_sfence();At(G k=0;k<16;k++)G3(d+k*zS,zS);}I<Bx Be>H W ar_src_onelevel(Ag in_out[],B M*src,A la,A Z){B A stride=Z/4;switch(la/stride){case 0:Dd<0,Be>(in_out,src,la,Z);Fv;case 1:Dd<1,Be>(in_out,src,la,Z);Fv;case 2:Dd<2,Be>(in_out,src,la,Z);Fv;case 3:Dd<3,Be>(in_out,src,la,Z);Fv;Mu:Dd<4,Be>(in_out,src,la,Z);}if(Z>=1048576u)_mm_sfence();At(G k=0;k<4;k++)G3(in_out+k*stride,stride);}I<Bx F4=Dm,Bx Iw=Dm> H W B3(Ag in_out[],A Z){B A Ai=Z/2;if(Ai<=Jw){Le<F4,Iw>(in_out,Z);F;}A9 ToRIRI=Ap::Cw<Bx,F4>;A9 ToI64=Ap::Cw<Bx,Iw>;B A stride=Z/4;B A1&Bb=Dt[B5(Ai)];iditLayer(B3,in_out,stride,Bb);}};
#undef difLayer
#undef iditLayer
E Bt A7::Go,A7::Jv,A7::Id,A7::LOG_CACHE;E A A7::Gn,A7::Jw,A7::MAX_LEN;A7::TableFix4 A7::table_8(8,1,4),A7::La(16,1,4),A7::Lb(16,3,4);A7::TableFix8 A7::Lc(32,1,4),A7::Ld(32,3,4);A7::Jy A7::Cb(2);A7::Jz A7::D3(3);A7::Jx A7::Gp(1);A7::TableSqrt A7::Dt(1);E M bitrev32(M n){E M mask55=0x55555555;E M mask33=0x33333333;E M mask0f=0x0f0f0f0f;E M maskff=0x00ff00ff;n=((n&mask55)<<1)|((n>>1)&mask55);n=((n&mask33)<<2)|((n>>2)&mask33);n=((n&mask0f)<<4)|((n>>4)&mask0f);n=((n&maskff)<<8)|((n>>8)&maskff);F(n<<16)|(n>>16);}E M bitrev(M n,Bt Bo){F bitrev32(n)>>(32-Bo);}I<Bt Dn,Bt DIV> Dz Da{Gg: H E Bt LOG_BLOCK=2,Kt=1<<LOG_BLOCK;H E A MAX_LEN=A(1)<<Dn;Dw Unit{C64 units[Dn]{};C6 Kv[Kt*2]{};Unit(){E C6 Cl=C6(1)/DIV;At(Bt i=0;i<Dn;i++){units[i]=getOmega(A(1)<<(i+1),1,Cl);}Kv[0]=1,Kv[Kt]=0;At(Bt i=1;i<Kt;i++){C64 Ci=getOmega(Kt,bitrev(i,LOG_BLOCK),Cl);Kv[i]=Ci.T(),Kv[i+Kt]=Ci.R();}}};Da():Eo(0),pop(0){Ap::memcpy(table,F6.Kv,B9(F6.Kv));}W reset(A i=0){if(i==0){pop=0,Eo=i;F;}pop=1,Eo=i/Kt;Bt C8=__builtin_ctzll(Eo);A1 fp=Ae<B C6*>(&F6.units[C8+2]);table[1].Kn(fp,fp+1);table[1]=table[1].En(table[0]);}S iterate(){S Gh=table[pop],unit4;Eo++;Bt C8=__builtin_ctzll(Eo);A1 fp=Ae<B C6*>(&F6.units[C8+2]);unit4.Kn(fp,fp+1);pop-=C8;table[pop+1]=table[pop].En(unit4);pop++;F Gh;}H C64 getOmega(A n,A Eo,C6 Cl=1){C6 Dc= -D8*Eo/n;F Ap::polar<C6>(1,Dc*Cl);}Hg: D2(64)H B Unit F6;D2(64)S table[Dn];A Eo;Bt pop;Bt log_max_iter,log_fft_len;};I<Bt Dn,Bt DIV> B Ad Da<Dn,DIV>::Unit Da<Dn,DIV>::F6;I<A F7=1,Ad Fd,Bx AC=0> Ar W Kx(Fd*Ix,Fd*Iy,B Fd*in0,B Fd*G9,B Ap::Ic<Fd> &Ci,B Fd G2,Fd*d0,Fd*d1){A9 L=Ap::Ic<Fd>;A1 Gq=[](L c0,L c1){F L(c0.T()+c1.T(),c0.R()-c1.R());};L x0(Ix[0],Ix[F7]),x1(Iy[0],Iy[F7]),y0(in0[0],in0[F7]),y1(G9[0],G9[F7]);A1 t0=x0*y0,t1=x1*y1,xy0=Gq(x0,x1),xy1=Gq(y0,y1);A1 t2=xy0*xy1;y1=Gq(t0,t1);x1=(y1+y1-t2)*Ci*Ci;B A1 inv2=G2+G2;x0=(t2-x1)*G2,x1=L(t0.T()-t1.T(),t0.R()+t1.R())*inv2;L out0=x0+x1,out1(x0.T()-x1.T(),x1.R()-x0.R());if(AC){d0[0]+=out0.T(),d0[F7]+=out0.R();d1[0]+=out1.T(),d1[F7]+=out1.R();}A8{Ix[0]=out0.T(),Ix[F7]=out0.R();Iy[0]=out1.T(),Iy[F7]=out1.R();}}I<Bx AC=0> Ar W dot_rfftX4(C6*dt0,C6*dt1,C6*Ix,C6*Iy,B C6*in0,B C6*G9,B S&Ci,B Ao&G2){A1 Gq=[](B S&x0,B S&x1){F S(x0.T+x1.T,x0.R-x1.R);};S x0=Ix,x1=Iy,y0=in0,y1=G9;x1=x1.Gm();y1=y1.Gm();S t0=x0.En(y0),t1=x1.En(y1);S xy0=Gq(x0,x1),xy1=Gq(y0,y1);S t2=xy0.En(xy1);y1=Gq(t0,t1);x1=(y1+y1-t2).En(Ci);B Ao inv2=G2+G2;x0=(t2-x1)*G2,x1=S(t0.T-t1.T,t0.R+t1.R)*inv2;S out0=x0+x1,out1(x0.T-x1.T,x1.R-x0.R);if(AC){S r0=dt0,r1=dt1;r0=r0+out0;r1=r1+out1.Gm();r0.Bn(dt0);r1.Bn(dt1);}A8 out0.Bn(dt0),out1.Gm().Bn(dt1);}I<Bx AC> Ar W Gr(Ag dst[],Ag in_out[],Ag in[],A Z){Ag*o=AC?dst:in_out;Ag G2=2.0/Z;{A1 r0=in_out[0],i0=in_out[4],r1=in[0],i1=in[4];Bf(r0,i0);Bf(r1,i1);r0*=r1,i0*=i1;Bf(r0,i0);if(AC)o[0]+=r0*0.5*G2,o[4]+=i0*0.5*G2;A8 o[0]=r0*0.5*G2,o[4]=i0*0.5*G2;}A1 I7=C64(in_out[1],in_out[5])*C64(in[1],in[5])*G2;if(AC)o[1]+=I7.T(),o[5]+=I7.R();A8 o[1]=I7.T(),o[5]=I7.R();G2/=4;Kx<4,Ag,AC>(in_out+2,in_out+3,in+2,in+3,C64(COS_PI_8,-COS_PI_8),G2,o+2,o+3);E Ag COS_16_1=0.92387953251128675612818318939;E Ag SIN_16_1=0.38268343236508977172845998403;Kx<4,Ag,AC>(in_out+8,in_out+11,in+8,in+11,C64(COS_16_1,-SIN_16_1),G2,o+8,o+11);Kx<4,Ag,AC>(in_out+9,in_out+10,in+9,in+10,C64(-SIN_16_1,-COS_16_1),G2,o+9,o+10);B D0 inv4=Ao(0.5/Z);Da<28,1>table;At(A Af=16;Af<Z;Af*=2){table.reset(Af/2);A1 Et=in_out+Af,Fs=Et+Af-8,Ft=in+Af,Hi=Ft+Af-8,ot0=o+Af,ot1=ot0+Af-8;At(;Et<Fs;Et+=8,Fs-=8,Ft+=8,Hi-=8,ot0+=8,ot1-=8){dot_rfftX4<AC>(ot0,ot1,Et,Fs,Ft,Hi,table.iterate(),inv4);}}}Ar W B1(Ag in_out[],Ag in[],A Z){Gr<0>(in_out,in_out,in,Z);}Ar W real_dot_accum(Ag dst[],Ag in_out[],Ag in[],A Z){Gr<1>(dst,in_out,in,Z);}}}}
#include <algorithm>
#include <atomic>
#include <complex>
#include <future>
#include <iostream>
#include <random>
#include <string>
#include <cstdlib>
#include <cstring>
#include <immintrin.h>
#ifndef HINT_SIMD_HPP
#define HINT_SIMD_HPP
#pragma GCC target("fma")
A9 L=Ap::Ic<Ak>;Dw Aj{A0 V;Aj(){V=Jb();}Aj(Ak K){V=Cm(K);}Aj(A0 K){V=K;}Aj(B Aj&K){V=K.V;}Aj(Ak B*Hq){V=ar_pdload(Hq);}Aj(L a){V=_mm256_broadcast_pd((__m128d*)&a);}Aj(B L*Hq){V=ar_pdload((B Ak*)Hq);}W Bn(L*a)B{ar_pdstore((Ak*)a,V);}I<Bt zM> Aj Hj()B{F _mm256_permute_pd(V,zM);}Aj all_real()B{F _mm256_movedup_pd(V);}Aj all_imag()B{F Hj<0XF>();}Aj J3()B{F Hj<0X5>();}Aj mul_neg_i()B{H B A0 subber{};F Aj(_mm256_addsub_pd(subber,V)).J3();}Aj Au+(Aj K)B{F _mm256_add_pd(V,K.V);}Aj Au-(Aj K)B{F E7(V,K.V);}Aj Au*(Aj K)B{A1 R=Ct(all_imag().V,K.J3().V);F _mm256_fmaddsub_pd(all_real().V,K.V,R);}Aj Au/(Aj K)B{F _mm256_div_pd(V,K.V);}};
#endif
Di hint{A9 UINT_8=uint8_t;A9 UINT_16=uint16_t;A9 Eu=M;A9 B8=C;A9 Iz=int32_t;A9 J4=int64_t;A9 LONG=Fp;A9 L=Ap::Ic<Ak>;E Ak Mc=3.1415926535897932384626433832795;E Ak D8=Mc*2;I<Ad zT> E zT min_2pow(zT n){zT Gh=1;Bc(Gh<n){Gh*=2;}F Gh;}I<Ad zT> E A B5(zT n){zT Gh=0;Bc(n>1){n/=2;Gh++;}F Gh;}I<Ad zT> E Ap::pair<zT,zT>div_mod(zT a,zT b){F Ap::make_pair(a/b,a%b);}I<Ad zT> W D9(zT*target,B zT*source,A Bo){if(Bo==0||target==source){F;}if(Bo>=INT64_MAX){Ht("Ary too long\n");}Ap::memcpy(target,source,Bo*B9(zT));}I<Ad zT> Ar zT*ary_realloc(zT*Hq,A Bo){if(Bo*B9(zT)<INT64_MAX){Hq=Fe<zT*>(realloc(Hq,Bo*B9(zT)));}if(Hq==A3){Ht("realloc error");}F Hq;}Di hint_transform{Dz Cx{Hg: Ap::Ff<Ap::Ff<L>>Bb;Ap::Ff<Ap::Ff<L>>B2;Iz I8=2;Iz Ha=2;H E A FAC=1;Cx(B Cx&)=E6;Cx&Au=(B Cx&)=E6;Gg: ~Cx(){}Cx(Eu Fw){Fw=Ap::max<A>(Fw,1);I8=Fw;Bb.Bh(Fw+1);B2.Bh(Fw+1);Bb[0]=Bb[1]=B2[0]=B2[1]=Ap::Ff<L>{1};Bb[2]=B2[2]=Ap::Ff<L>{1};
#if TABLE_PRELOAD == 1
expand(Fw);
#endif
}W expand(Iz Av){Av=Ap::max<Iz>(Av,2);if(Av>I8){Ht("FFT length too long for lut\n");}At(Iz i=Ha+1;i<=Av;i++){A Bo=1ull<<i,Ea=Bo*FAC/4;Bb[i].Bh(Ea);B2[i].Bh(Ea);Bb[i][0]=B2[i][0]=L(1,0);At(A Cj=0;Cj<Ea/2;Cj++){Bb[i][Cj*2]=Bb[i-1][Cj];B2[i][Cj*2]=B2[i-1][Cj];}At(A Cj=1;Cj<Ea/2;Cj+=2){Ak cos_theta=Ap::cos(D8*Cj/Bo);Ak sin_theta=Ap::sin(D8*Cj/Bo);Bb[i][Cj]=L(cos_theta,-sin_theta);Bb[i][Ea-Cj]=L(sin_theta,-cos_theta);}Bb[i][Ea/2]=Ap::conj(Hu(8,1));At(A Cj=1;Cj<Ea/2;Cj+=2){L Ie=get_omega(i,Cj*3);B2[i][Cj]=Ie;B2[i][Ea-Cj]=L(Ie.R(),Ie.T());}B2[i][Ea/2]=Ap::conj(Hu(8,3));}Ha=Ap::max(Ha,Av);}H L Hu(Ak Dc){F Ap::polar<Ak>(1.0,Dc);}H L Hu(A m,A n){F Hu((D8*n)/m);}L get_omega(Eu Av,A n)B{A Aa=1ull<<Av;B A rank_ff=Aa-1,quad_n=n<<2;A zone=quad_n>>Av;if((quad_n&rank_ff)==0){H E L ONES[4]={L(1,0),L(0,-1),L(-1,0),L(0,1)};F ONES[zone];}L Ie;if((zone&2)==0){if((zone&1)==0){Ie=Bb[Av][n];}A8{Ie=Bb[Av][Aa/2-n];Ie.T(-Ie.T());}}A8{if((zone&1)==0){Ie= -Bb[Av][n-Aa/2];}A8{Ie=Bb[Av][Aa-n];Ie.R(-Ie.R());}}F Ie;}L get_omega3(Eu Av,A n)B{F B2[Av][n];}Aj J5(Eu Av,A n)B{F Aj(Bb[Av].V()+n);}Aj I9(Eu Av,A n)B{F Aj(B2[Av].V()+n);}};E A lut_max_rank=23;H Cx Ky(lut_max_rank);I<Ad zT> Ar W Aq(zT&I2,zT&diff){zT Cq=I2;zT Cr=diff;I2=Cq+Cr;diff=Cq-Cr;}Ar W fft_dit_4point(L*K,A Aa=1){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2];L Bk=K[Aa*3];Aq(Cq,Cr);Aq(Co,Bk);Bk=L(Bk.R(),-Bk.T());K[0]=Cq+Co;K[Aa]=Cr+Bk;K[Aa*2]=Cq-Co;K[Aa*3]=Cr-Bk;}Ar W fft_dit_8point(L*K,A Aa=1){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2];L Bk=K[Aa*3];L J6=K[Aa*4];L Fg=K[Aa*5];L Gs=K[Aa*6];L Ds=K[Aa*7];Aq(Cq,Cr);Aq(Co,Bk);Aq(J6,Fg);Aq(Gs,Ds);Bk=L(Bk.R(),-Bk.T());Ds=L(Ds.R(),-Ds.T());Aq(Cq,Co);Aq(Cr,Bk);Aq(J6,Gs);Aq(Fg,Ds);H E Ak If=Ez;Fg=If*L(Fg.R()+Fg.T(),Fg.R()-Fg.T());Gs=L(Gs.R(),-Gs.T());Ds= -If*L(Ds.T()-Ds.R(),Ds.T()+Ds.R());K[0]=Cq+J6;K[Aa]=Cr+Fg;K[Aa*2]=Co+Gs;K[Aa*3]=Bk+Ds;K[Aa*4]=Cq-J6;K[Aa*5]=Cr-Fg;K[Aa*6]=Co-Gs;K[Aa*7]=Bk-Ds;}Ar W fft_dif_4point(L*K,A Aa=1){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2];L Bk=K[Aa*3];Aq(Cq,Co);Aq(Cr,Bk);Bk=L(Bk.R(),-Bk.T());K[0]=Cq+Cr;K[Aa]=Cq-Cr;K[Aa*2]=Co+Bk;K[Aa*3]=Co-Bk;}Ar W fft_dif_8point(L*K,A Aa=1){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2];L Bk=K[Aa*3];L J6=K[Aa*4];L Fg=K[Aa*5];L Gs=K[Aa*6];L Ds=K[Aa*7];Aq(Cq,J6);Aq(Cr,Fg);Aq(Co,Gs);Aq(Bk,Ds);H E Ak If=Ez;Fg=If*L(Fg.R()+Fg.T(),Fg.R()-Fg.T());Gs=L(Gs.R(),-Gs.T());Ds= -If*L(Ds.T()-Ds.R(),Ds.T()+Ds.R());Aq(Cq,Co);Aq(Cr,Bk);Aq(J6,Gs);Aq(Fg,Ds);Bk=L(Bk.R(),-Bk.T());Ds=L(Ds.R(),-Ds.T());K[0]=Cq+Cr;K[Aa]=Cq-Cr;K[Aa*2]=Co+Bk;K[Aa*3]=Co-Bk;K[Aa*4]=J6+Fg;K[Aa*5]=J6-Fg;K[Aa*6]=Gs+Ds;K[Aa*7]=Gs-Ds;}Ar W De(L Ci,L Ck,L*K,A Aa){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2]*Ci;L Bk=K[Aa*3]*Ck;Aq(Co,Bk);Bk=L(Bk.R(),-Bk.T());K[0]=Cq+Co;K[Aa]=Cr+Bk;K[Aa*2]=Cq-Co;K[Aa*3]=Cr-Bk;}Ar W Df(L Ci,L Ck,L*K,A Aa){L Cq=K[0];L Cr=K[Aa];L Co=K[Aa*2];L Bk=K[Aa*3];Aq(Cq,Co);Aq(Cr,Bk);Bk=L(Bk.R(),-Bk.T());K[0]=Cq;K[Aa]=Cr;K[Aa*2]=(Co+Bk)*Ci;K[Aa*3]=(Co-Bk)*Ck;}Ar W De(Aj Ci,Aj Ck,L*K,A Aa){Aj Cq=K;Aj Cr=K+Aa;Aj Co=Aj(K+Aa*2)*Ci;Aj Bk=Aj(K+Aa*3)*Ck;Aq(Co,Bk);Bk=Bk.mul_neg_i();(Cq+Co).Bn(K);(Cr+Bk).Bn(K+Aa);(Cq-Co).Bn(K+Aa*2);(Cr-Bk).Bn(K+Aa*3);}Ar W Df(Aj Ci,Aj Ck,L*K,A Aa){Aj Cq=(K);Aj Cr=(K+Aa);Aj Co=(K+Aa*2);Aj Bk=(K+Aa*3);Aq(Cq,Co);Aq(Cr,Bk);Bk=Bk.mul_neg_i();Cq.Bn(K);Cr.Bn(K+Aa);((Co+Bk)*Ci).Bn(K+Aa*2);((Co-Bk)*Ck).Bn(K+Aa*3);}I<A Ig> W Am(L*K){E A Ch=B5(Ig);E A Fx=Ig/2,Cc=Ig/4;Am<Fx>(K);Am<Cc>(K+Fx);Am<Cc>(K+Fx+Cc);At(A i=0;i<Cc;i+=2){A1 Ci=Ky.J5(Ch,i);A1 Ck=Ky.I9(Ch,i);De(Ci,Ck,K+i,Cc);}}I<> W Am<0>(L*K){}I<> W Am<1>(L*K){}I<> W Am<2>(L*K){Aq(K[0],K[1]);}I<> W Am<4>(L*K){fft_dit_4point(K,1);}I<> W Am<8>(L*K){fft_dit_8point(K,1);}I<A Ig> W An(L*K){E A Ch=B5(Ig);E A Fx=Ig/2,Cc=Ig/4;At(A i=0;i<Cc;i+=2){A1 Ci=Ky.J5(Ch,i);A1 Ck=Ky.I9(Ch,i);Df(Ci,Ck,K+i,Cc);}An<Fx>(K);An<Cc>(K+Fx);An<Cc>(K+Fx+Cc);}I<> W An<0>(L*K){}I<> W An<1>(L*K){}I<> W An<2>(L*K){Aq(K[0],K[1]);}I<> W An<4>(L*K){fft_dif_4point(K,1);}I<> W An<8>(L*K){fft_dif_8point(K,1);}I<A Ig=1> W G4(L*K,A Ai){if(Ai>Ig){G4<Ig*2>(K,Ai);F;}Ky.expand(B5(Ig));Am<Ig>(K);}I<> W G4<1<<24>(L*K,A Ai){}I<A Ig=1> W G5(L*K,A Ai){if(Ai>Ig){G5<Ig*2>(K,Ai);F;}Ky.expand(B5(Ig));An<Ig>(K);}I<> W G5<1<<24>(L*K,A Ai){}}B8 stoui64(B Ap::L4::const_iterator&Af,B Ap::L4::const_iterator&Du,B Eu Gb=10){B8 result=0;At(A1 it=Af;it<Du&&it-Af<19;++it){result*=Gb;K9 c=tolower(*it);B8 n=0;if(isalnum(c)){if(isalpha(c)){n=c-'a'+10;}A8{n=c-'0';}}if(n<Gb){result+=n;}}F result;}B8 stoui64(B Ap::L4&str,B Eu Gb=10){F stoui64(str.Af(),str.Du(),Gb);}I<Ad zT=Eu,Ad Ac=Eu> Dz Bu{Hg: zT*Ax=A3;Ac D4=0;Ac Y=0;Gg: ~Bu(){if(Ax!=A3){E6[]Ax;Ax=A3;}}Bu(){Ax=A3;}Bu(Ac Fy){if(Fy>0){Bh(Fy);}}Bu(Ac Fy,zT ele){if(Fy>0){Bh(Fy);A6(Fy);fill_element(ele,Fy);}}Bu(B zT*ary,Ac Bo){if(ary==A3){Ht("Can't copy from nullptr\n");}if(Bo>0){Bh(Bo);A6(Bo);D9(Ax,ary,Bo);}}Bu(B Bu&K){if(K.Ax!=A3){if(Ax!=A3){E6[]Ax;}Ax=A3;A Bo=K.Ey();Bh(Bo);A6(Bo);Fh(K.sign());D9(Ax,K.Ax,Bo);}}Bu(Bu&&K){if(K.Ax!=A3){Y=K.Y;A6(K.Ey());Fh(K.sign());if(Ax!=A3){E6[]Ax;}Ax=K.Ax;K.Ax=A3;}}Bu&Au=(B Bu&K){if(Ei!= &K){if(Ax!=A3){E6[]Ax;}Ax=A3;A Bo=K.Ey();Bh(Bo);A6(Bo);Fh(K.sign());D9(Ax,K.Ax,Bo);}F*Ei;}Bu&Au=(Bu&&K){if(Ei!= &K){Y=K.Y;A6(K.Ey());Fh(K.sign());if(Ax!=A3){E6[]Ax;}Ax=K.Ax;K.Ax=A3;}F*Ei;}zT&Au[](Ac Eo)B{F Ax[Eo];}zT*V()B{F Ax;}H Ac size_generator(Ac C0){E Ac B4=B9(Ac)*8;E Ac Ev=(1ull<<(B4-1));E Ac Gt=Ev-1;C0=Ap::min<Ac>(C0,Gt);if(C0<=2){F 2;}A8 if(C0<=4){F 4;}Ac size1=min_2pow(C0);Ac M3=size1/2;M3=M3+M3/2;if(C0<=M3){F M3;}A8{F size1;}}Ac Ey()B{E Ac B4=B9(Ac)*8;E Ac Ev=(1ull<<(B4-1));E Ac Gt=Ev-1;F D4≫}Bx sign()B{E Ac B4=B9(Ac)*8;E Ac Ev=(1ull<<(B4-1));F(Ev&D4)!=0;}E W Bh(Ac C0,Ac(size_func)(Ac)=size_generator){C0=size_func(C0);if(Ax==A3){Y=C0;Ax=new zT[Y];A6(0);}A8 if(Y!=C0){Y=C0;Ax=ary_realloc(Ax,Y);A6(Ey());}}W A6(Ac G6){E Ac B4=B9(Ac)*8;E Ac Ev=(1ull<<(B4-1));E Ac Gt=Ev-1;if(G6>Gt){Ht("Length too long\n");}G6=Ap::min(G6,Y);Bx sign_tmp=sign();D4=G6;Fh(sign_tmp);}W Fh(Bx is_sign){E Ac B4=B9(Ac)*8;E Ac Ev=(1ull<<(B4-1));E Ac Gt=Ev-1;if((!is_sign)||Ey()==0){D4=D4≫}A8{D4=D4|Ev;}}Ac Bm(){if(Ax==A3){F 0;}Ac t_len=Ey();Bc(t_len>0&&Ax[t_len-1]==0){t_len--;}A6(t_len);F Ey();}W fill_element(zT ele,Ac Ih,Ac Af=0){if(Af>=Y||Ax==A3){F;}if(Af+Ih>=Y){Ih=Y-Af;}Ap::fill(Ax+Af,Ax+Af+Ih,ele);}};}Di Bi{A9 Di hint;A9 Ac=Eu;I<Ad zT> A9 C1=Bu<zT,Ac>;I<Ad zT> E A Bw(B zT&ary,A Bo){Bc(Bo>0&&ary[Bo-1]==0){Bo--;}F Bo;}I<Ad zT> E Iz C2(B zT ary1[],B zT ary2[],A As,A Az){As=Bw(ary1,As);Az=Bw(ary2,Az);if(As!=Az){F As>Az?1: -1;}if(ary1==ary2){F 0;}Bc(As>0){As--;zT num1=ary1[As],num2=ary2[As];if(num1!=num2){F num1>num2?1: -1;}}F 0;}I<B8 A5,Bx Kz=B0,Ad zT> E W Fi(B zT in[],zT num,zT Ce[],A Bo){Bo=Bw(in,Bo);num%=A5;B8 Hz=0;if(num==1){D9(Ce,in,Bo);}A8{At(A i=0;i<Bo;i++){Hz+=Fe<B8>(in[i])*num;Ap::tie(Hz,Ce[i])=div_mod<B8>(Hz,A5);}}if(Kz){Ce[Bo]=Hz;}}I<B8 A5,Ad zT> E J4 J7(B zT in[],zT num,zT Ce[],A Bo){A Cj=Bw(in,Bo);num%=A5;if(num==1){D9(Ce,in,Bo);F 0;}B8 Hk=0;Bc(Cj>0){Cj--;Hk=Hk*A5+in[Cj];Ap::tie(Ce[Cj],Hk)=div_mod<B8>(Hk,num);}F Hk;}I<J4 A5,Bx Kz=B0,Ad zT> E W M5(B zT G9[],B zT in2[],zT Ce[],A As,A Az){if(As<Az){Ap::J3(G9,in2);Ap::J3(As,Az);}A Cj=0;B8 Q=0;Bc(Cj<Az){Q+=(G9[Cj]+in2[Cj]);Ce[Cj]=Q<A5?Q:Q-A5;Q=Q<A5?0:1;Cj++;}Bc(Cj<As&&Q>0){Q+=G9[Cj];Ce[Cj]=Q<A5?Q:Q-A5;Q=Q<A5?0:1;Cj++;}D9(Ce+Cj,G9+Cj,As-Cj);if(Kz){Ce[As]=Q%A5;}}I<J4 A5,Ad zT> E W Gu(B zT G9[],B zT in2[],zT Ce[],A As,A Az){if(As<Az){F;}A Cj=0;J4 Dp=0;Bc(Cj<Az){Dp+=(Fe<J4>(G9[Cj])-in2[Cj]);Ce[Cj]=Dp<0?Dp+A5:Dp;;Dp=Dp<0?-1:0;Cj++;}Bc(Cj<As&&Dp<0){Dp+=G9[Cj];Ce[Cj]=Dp<0?Dp+A5:Dp;Dp=Dp<0?-1:0;Cj++;}D9(Ce+Cj,G9+Cj,As-Cj);}I<Dz IVT>H Ar W iv667load(Ak*d,B IVT*s,A n){if E(Ap::is_same<IVT,M>::value){A i=0;At(;i+4<=n;i+=4){Cn x=Fu((B Cn*)(s+i));ar_pdstore(d+i,Ep(x));}At(;i<n;i++)d[i]=(Ak)s[i];}A8 At(A i=0;i<n;i++)d[i]=(Ak)s[i];}I<Dz IVT>H Ar W Eb(Ak*d,B IVT*a,A la,A n){A9 Bp::E0::fft::A7;if E(Ap::is_same<IVT,M>::value){if(n/2>A7::Jw){A7::difRecLongSrc<B0>(d,Ae<B M*>(a),la,n);F;}}iv667load(d,a,la);::M7(d+la,0,(n-la)*B9(Ak));A7::G3<B0>(d,n);}H Ar Cn F5(D raw,Cn&prev1,Cn&prev2,Cn&prev3){B A0 bias=Cm(4503599627370496.0),Gb=Cm(10000.0),G2=Cm(0.0001);A0 x=_mm256_castsi256_pd(raw);A0 q1=D7(Ct(x,G2));A0 q2=D7(Ct(x,Cm(1e-8)));A0 q3=D7(Ct(x,Cm(1e-12)));Cn r0=D5(E7(x,Ct(q1,Gb)));Cn r1=D5(E7(q1,Ct(q2,Gb)));Cn r2=D5(E7(q2,Ct(q3,Gb)));Cn r3=D5(q3);Cn I2=Ii(r0,Hl(r1,prev1,12));I2=Ii(I2,Hl(r2,prev2,8));I2=Ii(I2,Hl(r3,prev3,4));prev1=r1;prev2=r2;prev3=r3;F I2;}H Ar D zzld(B W*p){D v;asm("vmovdqu %1,%0":"=x"(v):"m"(*(B D*)p));F v;}H Ar W zzst(W*p,D v){asm volatile("vmovdqu %0,%1"::"x"(v),"m"(*(D*)p));}H W K0(B G Fp Fp*c,G*Ce,A Ih){Cn p1=_mm_setzero_si128(),p2=p1,p3=p1;B D C8=Cz(),Gb=X(Ab),one=X(1);B D c9999=X(9999),c19=X(19999),c29=X(29999),idx1=Al(0,0,1,2,3,4,5,6),idx2=Al(0,0,0,1,2,3,4,5),idx4=Al(0,0,0,0,0,1,2,3),m1=Al(0,-1,-1,-1,-1,-1,-1,-1),m2=Al(0,0,-1,-1,-1,-1,-1,-1),m4=Al(0,0,0,0,-1,-1,-1,-1),idx7=X(7);D cv=C8;A i=0;A1 normalize=[&](D s,G*dest){D q=E1(Gc(s,Gv(6711)),10);D prior=_mm256_alignr_epi8(q,_mm256_permute2x128_si256(cv,q,0x21),12);D y=A4(Br(s,Gd(q,Gb)),prior);D gt=Eq(y,c9999);if(Er(gt,gt)){zzst(dest,y);cv=q;F;}D pe=Ge(y,c9999);if(!Er(pe,pe)){D sh=P(J(gt,idx1),m1);gt=Bd(gt,P(pe,sh));pe=P(pe,P(J(pe,idx1),m1));sh=P(J(gt,idx2),m2);gt=Bd(gt,P(pe,sh));pe=P(pe,P(J(pe,idx2),m2));sh=P(J(gt,idx4),m4);gt=Bd(gt,P(pe,sh));}D L5=P(P(J(gt,idx1),m1),one);y=Br(A4(y,L5),P(gt,Gb));zzst(dest,y);cv=Br(q,gt);};At(;i+8<=Ih;i+=8){A1 lo=F5(zzld(c+i),p1,p2,p3);A1 hi=F5(zzld(c+i+4),p1,p2,p3);normalize(_mm256_set_m128i(hi,lo),Ce+i);}if(i<=Ih){D2(32)G Fp Fp raw[8]{};Fj(raw,c+i,(Ih-i)*8);A1 lo=F5(Jh((B D*)raw),p1,p2,p3);A1 hi=F5(Jh((B D*)(raw+4)),p1,p2,p3);D2(32)G Hh[8];normalize(_mm256_set_m128i(hi,lo),Hh);Fj(Ce+i,Hh,(Ih+1-i)*4);}}I<B8 A5,Ad zT> W J9(B zT G9[],B zT in2[],zT Ce[],A As,A Az){if(!As||!Az||!G9||!in2)F;B A Dx=As+Az-1;if E(A5==Ab&&B9(zT)==4){if(As*Az<=262144){B zT*aa=G9,*bb=in2;A na=As,nb=Az;if(na>nb){Ap::J3(aa,bb);Ap::J3(na,nb);}H M*bp=A3,*ap=A3,*Ie=A3;H A bc=0,ac=0,tc=0;B A need=nb+34,an=(na+1)/2;if(bc<need){free(bp);bp=(M*)malloc(need*4);bc=need;}if(ac<an){free(ap);ap=(M*)malloc(an*4);ac=an;}M7(bp,0,16*4);M*L6=bp+16;At(A k=0;k<nb;k++)L6[k]=bb[k]|(k?bb[k-1]<<16:0);L6[nb]=bb[nb-1]<<16;M7(L6+nb+1,0,17*4);At(A k=0;k<an;k++)ap[k]=aa[2*k]|(2*k+1<na?aa[2*k+1]<<16:0);Fz ob=(Fz)Ce,oe=(Fz)(Ce+Dx+1),ab=(Fz)G9,ae=(Fz)(G9+As),bbeg=(Fz)in2,be=(Fz)(in2+Az);B Bx overlap=(ob<ae&&oe>ab)||(ob<be&&oe>bbeg);zT*o=Ce;if(overlap){if(tc<Dx+1){free(Ie);Ie=(M*)malloc((Dx+1)*4);tc=Dx+1;}o=(zT*)Ie;}C Q=0;A m=0;At(;m+16<=Dx;m+=16){C Ja[16]={};B A lo=m>=nb-1?m-(nb-1):0,hi=Ap::min(na-1,m+15);At(A i0=lo&~A(1);i0<=hi;i0+=42){B A Du=Ap::min(hi+1,i0+42);D s0=Cz(),s1=s0;At(A i=i0;i<Du;i+=2){D av=X(ap[i/2]);B M*p=L6+ptrdiff_t(m)-ptrdiff_t(i);s0=A4(s0,Ji(av,Cs((B D*)p)));s1=A4(s1,Ji(av,Cs((B D*)(p+8))));}Ec((D*)Ja,Fk(Cs((B D*)Ja),Dr(E4(s0))));Ec((D*)(Ja+4),Fk(Cs((B D*)(Ja+4)),Dr(Ej(s0,1))));Ec((D*)(Ja+8),Fk(Cs((B D*)(Ja+8)),Dr(E4(s1))));Ec((D*)(Ja+12),Fk(Cs((B D*)(Ja+12)),Dr(Ej(s1,1))));}At(G j=0;j<16;j+=2){C v=Q+Ja[j]+10000ull*Ja[j+1];Q=v/E8;M r=v-Q*E8;o[m+j]=r%Ab;o[m+j+1]=r/Ab;}}At(;m<Dx;m++){C I2=0;B A lo=m>=nb-1?m-(nb-1):0,hi=Ap::min(na-1,m);At(A i=lo;i<=hi;i++)I2+=(C)aa[i]*bb[m-i];I2+=Q;o[m]=I2%Ab;Q=I2/Ab;}o[Dx]=Q;if(overlap)memcpy(Ce,o,(Dx+1)*4);F;}}A n=Bp::D1(Dx);H Ak*g_abuf=A3,*g_bbuf=A3;H A g_acap=0,g_bcap=0;if(g_acap<n){Kk(g_abuf);g_abuf=(Ak*)H8(n*B9(Ak),64);g_acap=n;}Ak*a=g_abuf;if(G9==in2&&As==Az){Eb(a,G9,As,n);Bp::E0::fft::B1(a,a,n);Bp::E0::fft::A7::B3<B0,B0>(a,n);}A8{if(g_bcap<n){Kk(g_bbuf);g_bbuf=(Ak*)H8(n*B9(Ak),64);g_bcap=n;}Ak*b=g_bbuf;Eb(a,G9,As,n);Eb(b,in2,Az,n);Bp::E0::fft::B1(a,b,n);Bp::E0::fft::A7::B3<B0,B0>(a,n);}B C*Nb=(B C*)a;if E(A5==Ab){if(Ap::min(As,Az)<=40000000){K0((B G Fp Fp*)Nb,(G*)Ce,Dx);F;}}B8 Q=0;At(A i=0;i<Dx;++i){Q+=Nb[i];Ce[i]=Q%A5;Q/=A5;}Ce[Dx]=Q%A5;}I<B8 A5,Ad zT> E zT Jj(B zT in[],zT Ce[],A Bo){if(in==Ce){Ht("In can't be same as out\n");}zT C3=1;if(Bo==1){C3=(A5-1)/in[0];Ce[0]=in[0]*C3;}A8 if(in[Bo-1]>=(A5/2)){D9(Ce,in,Bo);}A8{C3=(A5-1)*A5/(A5*in[Bo-1]+in[Bo-2]);Fi<A5,Dm>(in,C3,Ce,Bo);if(Ce[Bo-1]<(A5/2)){C3++;M5<A5,Dm>(Ce,in,Ce,Bo,Bo);}}F C3;}I<B8 A5,Ad zT> W abs_long_div(zT Aw[],B zT Ba[],zT Cy[],A As,A Az){As=Bw(Aw,As);Az=Bw(Ba,Az);if(Ba==A3||Az==0){Ht("Can't divide by zero\n");}if(Aw==A3||As==0){F;}if(C2(Aw,Ba,As,Az)<0){F;}if(Az==1){zT rem=J7<A5>(Aw,Ba[0],Cy,As);Aw[0]=rem;F;}if(Ba[Az-1]<(A5/2)){Ht("Can't call this proc before normalize the divisor\n");}Cy[As-Az]=0;B B8 Ee=A5*Ba[Az-1]+Ba[Az-2];C1<zT>Hb(Az+1);Bc(C2(Aw,Ba,As,Az)>=0){Hb.A6(Az+1);B8 Dy=Aw[As-1]*A5+Aw[As-2];zT Cf=0;A Av=As-Az;if(Dy>Ee){Cf=Dy/Ee;Fi<A5>(Ba,Cf,Hb.V(),Az);Hb.Bm();A Gw=Hb.Ey();if(C2(Aw+Av,Hb.V(),As-Av,Gw)<0){Cf--;Gu<A5>(Hb.V(),Ba,Hb.V(),Gw,Az);}}A8 if(Dy==Ee){if(C2(Aw+Av,Ba,As-Av,Az)<0){Cf=A5-1;Av--;Fi<A5>(Ba,Cf,Hb.V(),Az);}A8{Cf=1;D9(Hb.V(),Ba,Az);Hb.Bm();}}A8{Cf=Dy/(Ee/A5);if(Cf>=A5){Cf=A5-1;}Av--;Fi<A5>(Ba,Cf,Hb.V(),Az);Hb.Bm();A Gw=Hb.Ey();if(C2(Aw+Av,Hb.V(),As-Av,Gw)<0){Cf--;Gu<A5>(Hb.V(),Ba,Hb.V(),Gw,Az);if(C2(Aw+Av,Hb.V(),As-Av,Gw)<0){Cf--;Gu<A5>(Hb.V(),Ba,Hb.V(),Gw,Az);}}}Gu<A5>(Aw+Av,Hb.V(),Aw+Av,As-Av,Hb.Ey());As=Bw(Aw,As);Cy[Av]=Cf;}}I<B8 A5,Ad zT> W Fl(zT Aw[],zT Ba[],C1<zT> &Cy,A As,A Az){As=Bw(Aw,As);Az=Bw(Ba,Az);if(Ba==A3||Az==0){Ht("Can't divide by zero\n");}if(Aw==A3||As==0){F;}if(C2(Aw,Ba,As,Az)<0){F;}if(Ba[Az-1]<(A5/2)){Ht("Can't call this proc before normalize the divisor\n");}A Ef=As-Az+1;Cy.A6(Ef);E A I5=50;if(Az<=I5){abs_long_div<A5>(Aw,Ba,Cy.V(),As,Az);}A8 if(As>=Az*2||As>((Az+1)/2)*3){A Bz=(As+3)/4;A Hc=Bz*3-Az+2;C1<zT>K1(Hc,0);Fl<A5>(Aw+Bz,Ba,K1,As-Bz,Az);Hc=K1.Bm();A dividend_len=Bw(Aw,As);Fl<A5>(Aw,Ba,Cy,dividend_len,Az);Cy.A6(Ef);Ef=Cy.Bm();M5<A5>(Cy.V()+Bz,K1.V(),Cy.V()+Bz,Ef-Bz,Hc);Cy.A6(As-Az+1);}A8{A Bz=Az/2;Fl<A5>(Aw+Bz,Ba+Bz,Cy,As-Bz,Az-Bz);E zT ONE[1]={1};Ef=Cy.Bm();C1<zT>Hz(Bz+Ef,0);J9<A5>(Ba,Cy.V(),Hz.V(),Bz,Ef);A I0=Hz.Bm();As=Bw(Aw,As);Bc(C2(Hz.V(),Aw,I0,As)>0){Gu<A5>(Cy.V(),ONE,Cy.V(),Ef,1);Gu<A5>(Hz.V(),Ba,Hz.V(),I0,Bz);M5<A5>(Aw+Bz,Ba+Bz,Aw+Bz,As-Bz,Az-Bz);Ef=Cy.Bm();I0=Hz.Bm();As=Bw(Aw,Ap::max(As,Az)+1);}Gu<A5>(Aw,Hz.V(),Aw,As,I0);}}I<B8 A5,Ad zT> C1<zT>abs_div(B zT Aw[],zT Ba[],C1<zT> &Cy,A As,A Az,Bx ret_rem=B0){C1<zT>Gf(Az);Gf.A6(Az);C1<zT>Bv(As+1);Bv.A6(As+1);zT*Hv=Gf.V();zT*Ew=Bv.V();zT C3=Jj<A5>(Ba,Hv,Az);Fi<A5>(Aw,C3,Ew,As);As=Bv.Bm();Cy=C1<zT>(As-Az+2,0);if((!ret_rem)&&(As+2<Az*2)){A Av=Az*2-As-2;Fl<A5>(Ew+Av,Hv+Av,Cy,As-Av,Az-Av);Cy.Bm();F Bv;}Fl<A5>(Ew,Hv,Cy,As,Az);Cy.Bm();if(ret_rem){As=Bv.Bm();J7<A5>(Ew,C3,Ew,As);Bv.Bm();}F Bv;}}
#include <vector>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <x86intrin.h>
// adapted from Duck public19388 and existing1005e7 reference; no linked library.
Dw LP648{Ar H W*h[24]={};H W*get(Ap::A b){Ap::A w=(b+15)/16;if(!w)w=1;Bt c=w<=1?0:64-__builtin_clzll(w-1);if(c>23)F::Au new(w*16);W*p=h[c];if(p)h[c]=*(W**)p;A8 p=::Au new(((Ap::A)1<<c)*16);F p;}H W put(W*p,Ap::A b){Ap::A w=(b+15)/16;if(!w)w=1;Bt c=w<=1?0:64-__builtin_clzll(w-1);if(c>23){::Au E6(p);F;}*(W**)p=h[c];h[c]=p;}};I<Dz zT>Dw C4{A9 value_type=zT;C4()I1=Mu;I<Dz zU>C4(B C4<zU>&)I1{}zT*allocate(Ap::A n){F Fe<zT*>(LP648::get(n*B9(zT)));}W deallocate(zT*p,Ap::A n)I1{LP648::put(p,n*B9(zT));}I<Dz zU>W construct(zU*p){::new(Fe<W*>(p))zU;}I<Dz zU,Dz...zA>W construct(zU*p,zA&&...a){::new(Fe<W*>(p))zU(Ap::forward<zA>(a)...);}I<Dz zU>W destroy(zU*p){p->~zU();}Bx Au==(B C4&)B I1{F B0;}Bx Au!=(B C4&)B I1{F Dm;}};Di Lf{Gx((Ij))H Ar O iv603dm(O x,C&Hw){E C zD=By;E O zM=(~(O)0)/zD;B C al=(C)x,ah=(C)(x>>64),bl=(C)zM,bh=(C)(zM>>64);B O p00=(O)al*bl,p01=(O)al*bh,p10=(O)ah*bl,p11=(O)ah*bh;B O mid=(p00>>64)+(C)p01+(C)p10;O q=p11+(p01>>64)+(p10>>64)+(mid>>64);C r=(C)(x-q*zD);if(r>=zD){r-=zD;++q;}Hw=r;F q;}
#include <cstdint>
Gx((Ij))H Ar O iv608dm(O x,C&Hw){E C zD=By;if((x>>118)==0){E O zM=((O)1<<118)/zD;Fa((zM>>64)==1);B C al=(C)x,ah=(C)(x>>64),bl=(C)zM;B O p0=(O)al*bl,p1=(O)ah*bl;B O mid=(p0>>64)+(C)p1+(O)al;B C Bl=(C)(p1>>64)+ah+(C)(mid>>64);O q=((O)Bl<<10)|((C)mid>>54);C r=(C)(x-q*zD);if(r>=zD){r-=zD;++q;}Hw=r;F q;}F iv603dm(x,Hw);}I<Bx Sub>H Ar G Hm(M*d,B M*a,B M*b,A m,G Eg){A i=0;D cy=X(Eg),C8=Cz(),Gb=X(Ab),one=X(1),ix1=Al(0,0,1,2,3,4,5,6),ix2=Al(0,0,0,1,2,3,4,5),ix4=Al(0,0,0,0,0,1,2,3),Nc=X(7),mask=Al(0,1,1,1,1,1,1,1);if(m>=16)At(;i+8<=m;i+=8){D av=Cs((B D*)(a+i)),bv=Cs((B D*)(b+i));D x=Sub?Br(av,bv):A4(av,bv),first=Db(C8,cy,1);x=Sub?Br(x,first):A4(x,first);D ge=Sub?Eq(C8,x):Eq(x,X(9999)),pp=Ge(x,Sub?C8:X(9999));if(!Er(pp,pp)){ge=Bd(ge,P(pp,J(ge,ix1)));pp=P(pp,J(pp,ix1));ge=Bd(ge,P(pp,J(ge,ix2)));pp=P(pp,J(pp,ix2));ge=Bd(ge,P(pp,J(ge,ix4)));}D L5=P(J(ge,ix1),mask),norm=P(ge,Gb);x=Sub?A4(Br(x,L5),norm):Br(A4(x,L5),norm);Ec((D*)(d+i),x);cy=P(J(ge,Nc),one);}Eg=(G)Dv(cy,0);At(;i<m;i++){if E(Sub){Bt q=Bt(a[i])-Bt(b[i])-Eg;Eg=q<0;d[i]=q+(Eg?Ab:0);}A8{G q=a[i]+b[i]+Eg;Eg=q>=Ab;d[i]=q-(Eg?Ab:0);}}F Eg;}H Ar G Ik(M*d,B M*a,B M*b,A m,G Eg){F Hm<Dm>(d,a,b,m,Eg);}H Ar G Il(M*vp,B M*bp,A m,G Ai){F Ik(vp,vp,bp,m,Ai);}H Ar G Gy(M*d,B M*a,B M*b,A m,G Eg){F Hm<B0>(d,a,b,m,Eg);}H Ar G Im(M*vp,B M*bp,A m,G Av){F Gy(vp,vp,bp,m,Av);}Dw A2{Ap::Ff<M,C4<M>>v;Bx Bs=Dm;A2()=Mu;A2(C a){M d[5];G n=0;Bc(a){d[n++]=a%Ab;a/=Ab;}v.Gk(d,d+n);}H A2 wide(O a){if(!(a>>64))F A2((C)a);M d[10];G n=0;Bc(a>Io){C hi=(C)(a>>64),lo=(C)a,part;if(hi<By){asm("divq %2":"+a"(lo),"+d"(hi):"r"(By):"cc");a=lo;part=hi;}A8{part=(C)(a%By);a/=By;}C up=part/Cu,Ga=part-up*Cu;d[n++]=Ga%Ab;d[n++]=Ga/Ab;d[n++]=up%Ab;d[n++]=up/Ab;}C Hh=(C)a;Bc(Hh){d[n++]=Hh%Ab;Hh/=Ab;}A2 x;x.v.Gk(d,d+n);F x;}Bx C8()B{F v.empty();}W H2(){Bc(!v.empty()&&!v.back())v.K3();if(v.empty())Bs=Dm;}Bt L7(B A2&b)B{if(v.Y()!=b.v.Y())F v.Y()<b.v.Y()?-1:1;At(A i=v.Y();i--;)if(v[i]!=b.v[i])F v[i]<b.v[i]?-1:1;F 0;}A2 Au-()B{A2 r=*Ei;if(!C8())r.Bs=!Bs;F r;}A2 Au+(B A2&b)B&{if(C8())F b;if(b.C8())F*Ei;if(Bs!=b.Bs){Bt c=L7(b);if(!c)F A2();B A2&a=c>0?*Ei:b;B A2&bb=c>0?b:*Ei;A2 r;r.Bs=a.Bs;r.v.Bh(a.v.Y());M*rp=r.v.V();A ab=bb.v.Y(),aa=a.v.Y();Bt Ka=Gy(rp,a.v.V(),bb.v.V(),ab,0);A i=ab;At(;i<aa&&Ka;++i){Bt q=Bt(a.v[i])-Ka;Ka=q<0;rp[i]=q+(Ka?Ab:0);}if(i<aa)Fj(rp+i,a.v.V()+i,(aa-i)*4);r.H2();F r;}A2 r;r.Bs=Bs;A va=v.Y(),vb=b.v.Y(),n=Ap::max(va,vb);r.v.Bh(n+1);M*rp=r.v.V();A mn=va<vb?va:vb;G Q=Ik(rp,v.V(),b.v.V(),mn,0);B M*Hh=va>vb?v.V():b.v.V();A i=mn;At(;i<n&&Q;++i){G q=Hh[i]+Q;Q=q>=Ab;rp[i]=q-(Q?Ab:0);}if(i<n)Fj(rp+i,Hh+i,(n-i)*4);rp[n]=Q;r.H2();F r;}A2 iv503add(B A2&b,Bx K4){if(b.C8())F Ap::Fm(*Ei);Bx bs=b.Bs!=K4;if(C8()){v=b.v;Bs=bs;F Ap::Fm(*Ei);}if(Bs==bs){A n=Ap::max(v.Y(),b.v.Y());v.Bh(n,0);A vb=b.v.Y();G Q=Il(v.V(),b.v.V(),vb,0);A i=vb;Bc(Q&&i<n){G q=v[i]+Q;Q=q>=Ab;v[i]=q-(Q?Ab:0);++i;}if(Q)v.F1(Q);F Ap::Fm(*Ei);}Bt c=L7(b);if(!c){v.clear();Bs=Dm;F Ap::Fm(*Ei);}Bt Dp=0;A i=0;if(c>0){A vb=b.v.Y();Bt Ka=Im(v.V(),b.v.V(),vb,0);i=vb;Bc(Ka&&i<v.Y()){Bt q=Bt(v[i])-Ka;Ka=q<0;v[i]=q+(Ka?Ab:0);++i;}}A8{v.Bh(b.v.Y(),0);Dp=Gy(v.V(),b.v.V(),v.V(),b.v.Y(),0);Bs=bs;}H2();F Ap::Fm(*Ei);}A2 Au+(B A2&b)&&{F iv503add(b,Dm);}A2 Au-(B A2&b)&&{F iv503add(b,B0);}A2 Au-(B A2&b)B&{F*Ei+(-b);}A2 Kb(C m)B{if(C8()||!m)F A2();if(m==10005){A2 r;r.Bs=Bs;A n=v.Y(),i=0;r.v.Bh(n+2);D cy=Cz(),px=cy,pq=cy;B D C8=Cz(),Gb=X(Ab),one=X(1),back=Al(7,0,1,2,3,4,5,6),ix1=Al(0,0,1,2,3,4,5,6),ix2=Al(0,0,0,1,2,3,4,5),ix4=Al(0,0,0,0,0,1,2,3),Nc=X(7),mask=Al(0,1,1,1,1,1,1,1);At(;i+8<=n;i+=8){D av=Cs(v.V()+i),q=E1(Es(av,X(8389)),24);D xv=Db(J(av,back),px,1),qv=Db(J(q,back),pq,1);D x=A4(Br(A4(av,Jk(av,2)),Es(q,Gb)),A4(xv,qv));x=A4(x,Db(C8,cy,1));D ge=Eq(x,X(9999)),pp=Ge(x,X(9999));if(!Er(pp,pp)){ge=Bd(ge,P(pp,J(ge,ix1)));pp=P(pp,J(pp,ix1));ge=Bd(ge,P(pp,J(ge,ix2)));pp=P(pp,J(pp,ix2));ge=Bd(ge,P(pp,J(ge,ix4)));}x=Br(A4(x,P(J(ge,ix1),mask)),P(ge,Gb));Ec(r.v.V()+i,x);cy=P(J(ge,Nc),one);px=J(av,Nc);pq=J(q,Nc);}G Q=Dv(cy,0),prev=Dv(px,0),Cy=Dv(pq,0);At(;i<n;++i){G q=v[i]/2000,z=5*v[i]-Ab*q+prev+Cy+Q;Q=z>=Ab;r.v[i]=z-(Q?Ab:0);prev=v[i];Cy=q;}G z=prev+Cy+Q;r.v[n]=z%Ab;r.v[n+1]=z/Ab;r.H2();F r;}if(m<=Io/E8){A2 r;r.Bs=Bs;r.v.Bh(v.Y());C Q=0;A i=0;At(;i+1<v.Y();i+=2){C q=(C(v[i])+C(v[i+1])*Ab)*m+Q;M t=q%E8;r.v[i]=t%Ab;r.v[i+1]=t/Ab;Q=q/E8;}At(;i<v.Y();++i){C q=C(v[i])*m+Q;r.v[i]=q%Ab;Q=q/Ab;}Bc(Q){r.v.F1(Q%Ab);Q/=Ab;}F r;}if(m<=Io/Ab){A2 r;r.Bs=Bs;r.v.Bh(v.Y());C Q=0;At(A i=0;i<v.Y();++i){Q+=(C)v[i]*m;r.v[i]=Q%Ab;Q/=Ab;}Bc(Q){r.v.F1(Q%Ab);Q/=Ab;}F r;}A2 r;r.Bs=Bs;r.v.Bh(v.Y());O Q=0;At(A i=0;i<v.Y();++i){Q+=(O)v[i]*m;r.v[i]=(M)(Q%Ab);Q/=Ab;}Bc(Q){r.v.F1(Q%Ab);Q/=Ab;}F r;}A2 Kc(M ar_d)B{if(ar_d==2){A2 r;r.Bs=Bs;A n=v.Y();r.v.Bh(n);A i=0;B D ix=Al(1,2,3,4,5,6,7,0),one=X(1),five=X(5000);At(;i+8<=n;i+=8){D x=Cs(v.V()+i),next=J(x,ix);next=Db(next,X(i+8<n?v[i+8]:0),0x80);D q=A4(E1(x,1),Es(P(next,one),five));Ec(r.v.V()+i,q);}At(;i<n;++i)r.v[i]=(v[i]>>1)+(i+1<n?(v[i+1]&1)*5000:0);r.H2();F r;}A2 Ip;Ip.Bs=Bs;Ip.v.Bh(v.Y());C Kd=0;A F8=v.Y();if(ar_d<=1844u)Bc(F8>=4){F8-=4;C ar_x=Kd*By+((C(v[F8+3])*Ab+v[F8+2])*Ab+v[F8+1])*Ab+v[F8];C ar_q=ar_x/ar_d;Kd=ar_x-ar_q*ar_d;M ar_hi=ar_q/E8,ar_lo=ar_q-C(ar_hi)*E8;Ip.v[F8+3]=ar_hi/Ab;Ip.v[F8+2]=ar_hi%Ab;Ip.v[F8+1]=ar_lo/Ab;Ip.v[F8]=ar_lo%Ab;}Bc(F8>=2){F8-=2;C ar_x=Kd*Cu+C(v[F8+1])*Ab+v[F8],ar_q=ar_x/ar_d;Kd=ar_x-ar_q*ar_d;Ip.v[F8+1]=ar_q/Ab;Ip.v[F8]=ar_q%Ab;}if(F8){C ar_x=Kd*Ab+v[0];Ip.v[0]=ar_x/ar_d;}Ip.H2();F Ip;}A2 Au*(B A2&b)B{if(C8()||b.C8())F A2();if(v.Y()==1){A2 r=b.Kb(v[0]);r.Bs=Bs!=b.Bs;F r;}if(b.v.Y()==1){A2 r=Kb(b.v[0]);r.Bs=Bs!=b.Bs;F r;}A za=0,zb=0;Bc(v[za]==0)++za;Bc(b.v[zb]==0)++zb;A na=v.Y()-za,nb=b.v.Y()-zb,Av=za+zb;B M*aa=v.V()+za,*bb=b.v.V()+zb;A2 r;r.Bs=Bs!=b.Bs;r.v.Bh(v.Y()+b.v.Y());M*cc=r.v.V()+Av;if(Av)Ap::memset(r.v.V(),0,Av*B9(M));if(na==1||nb==1){if(na==1){Ap::J3(aa,bb);Ap::J3(na,nb);}C Q=0;At(A i=0;i<na;i++){C q=(C)aa[i]*bb[0]+Q;cc[i]=q%Ab;Q=q/Ab;}cc[na]=Q;}A8 if(na*nb<=1024){Ap::memset(cc,0,(na+nb)*B9(M));At(A i=0;i<na;i++)At(A j=0;j<nb;j++)cc[i+j]+=aa[i]*bb[j];M Q=0;At(A i=0;i<na+nb;i++){M q=cc[i]+Q;cc[i]=q%Ab;Q=q/Ab;}}A8 Bi::J9<Ab>(aa,bb,cc,na,nb);r.H2();F r;}A2 Au/(B A2&b)B{assert(!b.C8());if(L7(b)<0)F A2();if(b.v.Y()==1){A2 r=Kc(b.v[0]);r.Bs=Bs!=b.Bs;F r;}hint::Bu<M>q;Bi::abs_div<Ab>(v.V(),const_cast<M*>(b.v.V()),q,v.Y(),b.v.Y(),Dm);A2 r;r.Bs=Bs!=b.Bs;r.v.Gk(q.V(),q.V()+q.Ey());r.H2();F r;}A2 Av(A Cd)B{if(C8())F A2();A2 r;r.Bs=Bs;r.v.Bh(Cd+v.Y(),0);Ap::copy(v.Af(),v.Du(),r.v.Af()+Cd);F r;}A2 Bl(A cut)B{if(cut>=v.Y())F A2();A2 r;r.Bs=Bs;r.v.Gk(v.Af()+cut,v.Du());F r;}};H A2 isqrt(B A2&a){if(a.C8())F A2();if(a.v.Y()<=4){C x=0;At(A i=a.v.Y();i--;)x=x*Ab+a.v[i];C r=sqrt((Fp Ak)x);Bc((O)(r+1)*(r+1)<=x)++r;Bc((O)r*r>x)--r;F A2(r);}A cut=(a.v.Y()+3)/4;A2 x=(isqrt(a.Bl(2*cut))+A2(1)).Av(cut);At(;;){A2 y=(x+a/x).Kc(2);if(y.L7(x)>=0)F x;x=Ap::Fm(y);}}H A2 Ek(G Cd){if(Cd<=4){Fp Ak scale=1;At(G i=0;i<Cd;++i)scale*=Ab;F A2((C)(scale/sqrtl(10005.0L)));}G old=(Cd+1)/2+2;if(old>=Cd)old=Cd-1;A2 yr=Ek(old);A2 y=yr.Av(Cd-old);B A Iq=(A)Cd+1;B A sh2=2*(Cd-old);if((A)2*Cd>Iq+1&&y.v.Y()<=(A)Cd&&sh2<=Iq&&Cd>8){A2 zT=(yr*yr).Kb(10005);B A k=Iq-sh2;Bt br=0;At(A i=0;i<k&&i<zT.v.Y();++i)if(zT.v[i]){br=1;Fv;}A2 Lg;Lg.v.Bh(Iq);At(A i=0;i<Iq;++i){Fp Fp tv=(i+k<zT.v.Y())?(Fp Fp)zT.v[i+k]:0;Fp Fp v=(i+2==Iq?3:0)-tv-br;if(v<0){v+=Ab;br=1;}A8 br=0;Lg.v[i]=(M)v;}Bc(!Lg.v.empty()&&!Lg.v.back())Lg.v.K3();F(y*Lg).Bl((A)2*Cd-Iq).Kc(2);}A2 defect=A2(3).Av(2*Cd)-(yr*yr).Av(sh2).Kb(10005);if(defect.v.Y()>Iq+8&&(A)2*Cd>Iq+1&&y.v.Y()<=(A)Cd){A2 Lg=defect.Bl(Iq);F(y*Lg).Bl((A)2*Cd-Iq).Kc(2);}F(y*defect).Bl(2*Cd).Kc(2);}H A2 H6(G Cd){A2 y=Ek(Cd+4);F y.Kb(4270934400ULL).Bl(4);}Dw PQT{A2 p,q,t;};H Ak*g_sp[4]={A3,A3,A3,A3};H A g_spcap=0;H Ak*Jl[4]={};H W Ir(A n){if(g_spcap>=n)F;At(G i=0;i<4;++i){Kk(Jl[i]);Jl[i]=(Ak*)H8((n+512)*B9(Ak),64);g_sp[i]=Jl[i]+i*128;}g_spcap=n;}H W D6(A2&r,B Ak*buf,A Dx,A Av=0){B C*Nb=(B C*)buf;r.v.Bh(Dx+Av+1);if(Av)::M7(r.v.V(),0,Av*B9(M));M*dest=r.v.V()+Av;if(Dx<=40000000){Bi::K0((B G Fp Fp*)Nb,dest,Dx);r.H2();F;}C Q=0;At(A i=0;i<Dx;++i){Q+=Nb[i];dest[i]=(M)(Q%Ab);Q/=Ab;}dest[Dx]=(M)(Q%Ab);r.H2();}H W node_mul(B A2&lq,B A2<,B A2&lp,B A2&rq,B A2&rt,B A2&rp,Bx Eh,A2&q,A2&t,A2*p,A Gz){A9 Di Bp::E0::fft;A kg=Gz?Gz+8:0;A a1=(Gz&&lq.v.Y()>kg)?lq.v.Y()-kg:0;A a2=(Gz&<.v.Y()>kg)?lt.v.Y()-kg:0;A b1=(Gz&&rq.v.Y()>kg)?rq.v.Y()-kg:0;B A cq=lq.v.Y()-a1+rq.v.Y()-b1-1;B A c2=lt.v.Y()-a2+rq.v.Y()-b1-1;B A c3=lp.v.Y()+rt.v.Y()-1;A cm=cq>c2?cq:c2;B A n=Bp::D1(cm);B A n3=Bp::D1(c3);B A cp=lp.v.Y()+rp.v.Y()-1,np=Bp::D1(cp);Bx Jm=Dm;B Bx Lh=Eh&&np>=512&&np<=n3;Ir(n);Ak*zA=g_sp[0],*zB=g_sp[1],*zC=g_sp[2];Bi::Eb(zB,rq.v.V()+b1,rq.v.Y()-b1,n);Bi::Eb(zA,lq.v.V()+a1,lq.v.Y()-a1,n);B1(zA,zB,n);A7::B3<B0,B0>(zA,n);D6(q,zA,cq,a1+b1);if(lq.Bs!=rq.Bs){if(!q.C8())q.Bs=B0;}Bi::Eb(zA,lt.v.V()+a2,lt.v.Y()-a2,n);B1(zA,zB,n);A d1=0,d2=0,cn3=c3;if(Gz&&!Eh){B A fullq=cq+a1+b1,fullt=c2+a2+b1,mn=fullq<fullt?fullq:fullt;if(mn>Gz+2){B A ks=mn-Gz,slp=lp.v.Y(),srt=rt.v.Y();A x=ks+1>srt?ks+1-srt:0,y=ks+1>slp?ks+1-slp:0;if(x>=slp)x=slp-1;if(y>=srt)y=srt-1;A cn=slp-x+srt-y-1;if(Bp::D1(cn)<n3){d1=x;d2=y;cn3=cn;}}}if(d1||d2){A2 T1;A7::B3<B0,B0>(zA,n);D6(T1,zA,c2,a2+b1);if(lt.Bs)T1.Bs=B0;A2 T2;T2.v.Bh(cn3+d1+d2+1,0);Bi::J9<Ab>(lp.v.V()+d1,rt.v.V()+d2,T2.v.V()+d1+d2,lp.v.Y()-d1,rt.v.Y()-d2);T2.H2();T2.Bs=lp.Bs!=rt.Bs;t=Ap::Fm(T1)+T2;}A8 if(n3==n&&!(a2+b1)){Bi::Eb(zC,lp.v.V(),lp.v.Y(),n);Bi::Eb(zB,rt.v.V(),rt.v.Y(),n);Jm=B0;if(lt.Bs==rt.Bs){real_dot_accum(zA,zB,zC,n);A7::B3<B0,B0>(zA,n);D6(t,zA,c2>c3?c2:c3);if(lt.Bs){if(!t.C8())t.Bs=B0;}}A8{B1(zB,zC,n);A2 T1,T2;A7::B3<B0,B0>(zA,n);D6(T1,zA,c2,a2+b1);A7::B3<B0,B0>(zB,n);D6(T2,zB,c3);if(lt.Bs)T1.Bs=B0;if(rt.Bs)T2.Bs=B0;t=Ap::Fm(T1)+T2;}}A8{A2 T1;A7::B3<B0,B0>(zA,n);D6(T1,zA,c2,a2+b1);if(lt.Bs)T1.Bs=B0;A2 T2;if(Lh&&n3>=512){Bi::Eb(zC,lp.v.V(),lp.v.Y(),n3);Bi::Eb(zB,rt.v.V(),rt.v.Y(),n3);B1(zB,zC,n3);A7::B3<B0,B0>(zB,n3);D6(T2,zB,c3);if(lp.Bs!=rt.Bs&&!T2.C8())T2.Bs=B0;Jm=B0;}A8 T2=lp*rt;t=Ap::Fm(T1)+T2;}if(Eh){if(Lh&&Jm){Bi::Eb(zA,rp.v.V(),rp.v.Y(),np);B1(zA,zC,np);A7::B3<B0,B0>(zA,np);D6(*p,zA,cp);if(lp.Bs!=rp.Bs&&!p->C8())p->Bs=B0;}A8*p=lp*rp;}}
#pragma GCC push_options
#pragma GCC optimize("O3,no-unroll-loops")
I<G zP,G zE>H Ar W Ex(C&x,C&c){x/=zP;c/=zP;At(G i=1;i<zE;i++){if(x%zP)Fv;x/=zP;c/=zP;}}H Ar W Is(G k,O&p,C&c){C x=6ull*k-5,y=2ull*k-1,z=6ull*k-1;c=F0;if(k%3==2)Ex<3,2>(y,c);G r=k%5;if(r==0)Ex<5,3>(x,c);A8 if(r==3)Ex<5,3>(y,c);A8 if(r==1)Ex<5,3>(z,c);r=k%23;if(r==20)Ex<23,3>(x,c);A8 if(r==12)Ex<23,3>(y,c);A8 if(r==4)Ex<23,3>(z,c);r=k%29;if(r==25)Ex<29,3>(x,c);A8 if(r==15)Ex<29,3>(y,c);A8 if(r==5)Ex<29,3>(z,c);p=(O)x*y*z;}H E C G0(C d){C x=1;At(G i=0;i<6;i++)x*=2-d*x;F x;}I<G zP,G zM,G zE>Dw Cp{C v[zM]{};E Cp(){At(G r=0;r<zM;r++){C x=(6ull*r+zM-5)%zM,y=(2ull*r+zM-1)%zM,z=(6ull*r+zM-1)%zM,w=x*y%zM*z%zM,d=1;At(G e=0;e<zE&&w%zP==0;e++){d*=zP;w/=zP;}v[r]=G0(d);}}};D2(64)H E Cp<3,9,2>ar_g3{};D2(64)H E Cp<5,125,3>ar_g5{};D2(64)H E Cp<23,529,2>ar_g23{};D2(64)H E Cp<29,841,2>ar_g29{};H Ar W It(G k,O&p,C&c){if(k>500000){Is(k,p,c);F;}C v=(6ull*k-5)*(2ull*k-1)*(6ull*k-1),i23=ar_g23.v[k%529],i29=ar_g29.v[k%841];if(i23==G0(529)&&v%12167==0)i23*=G0(23);if(i29==G0(841)&&v%24389==0)i29*=G0(29);C G2=ar_g3.v[k%9]*ar_g5.v[k%125]*i23*i29;p=v*G2;c=F0*G2;}Dw Dg{C x[32];};H Ar Dg Jo(O x){F{{(C)x,(C)(x>>64),0,0,0,0,0,0}};}I<G zW,G IW>H Ar W G1(Dg&a,O b){Fa(IW<=zW);C bl=(C)b,bh=(C)(b>>64),c1=0,c2=0;O Ni=0;At(G i=0;i<IW;++i){C cu=a.x[i];O v=(O)cu*bl+c1,w=Ni+(C)v+c2;a.x[i]=(C)w;c1=(C)(v>>64);c2=(C)(w>>64);Ni=(O)cu*bh;}if E(IW<zW){O v=Ni+c1+c2;a.x[IW]=(C)v;if E(IW+1<zW)a.x[IW+1]=(C)(v>>64);}}I<G zW,G IW>H Ar W ar_native_mul64(Dg&a,C b){C Q=0;At(G i=0;i<IW;i++){O v=(O)a.x[i]*b+Q;a.x[i]=v;Q=v>>64;}if E(IW<zW)a.x[IW]=Q;}I<G zW>H Ar W ar_native_sum(Dg&a,B Dg&b,Bx K4){C Q=0;At(G i=0;i<zW;i++){if(K4){O v=(O)b.x[i]+Q;Q=(O)a.x[i]<v;a.x[i]-=(C)v;}A8{O v=(O)a.x[i]+b.x[i]+Q;a.x[i]=v;Q=v>>64;}}}I<G zI,G zN>H Ar W Ke(Dg&q,Dg&p,Dg&t,G a){if E(zI<zN){E G PB=60,QB=108;O pp;C cc;G k=a+zI;It(k,pp,cc);O qq=(O)k*k*k*cc,tt=pp*(Ku+Jn*k);E G WT=((zI+1)*QB+63)/64,WQ=WT,WP=((zI+1)*PB+63)/64,IT=(zI*QB+63)/64,IQ=IT,IP=(zI*PB+63)/64;Dg pt=p;G1<WT,IP>(pt,tt);G1<WT,IT>(t,qq);ar_native_sum<WT>(t,pt,zI&1);G1<WQ,IQ>(q,qq);ar_native_mul64<WP,IP>(p,(C)pp);Ke<zI+1,zN>(q,p,t,a);}}H Ar Gx((Ij))C F2(C nh,C nl,C&rem){E C zD=E3;E O zM=(~(O)0)/zD;E C di=(C)zM;O zP=(O)nh*di;C qh=(C)(zP>>64),ql=(C)zP,lo=ql+nl,c=lo<ql;qh+=nh+1+c;C r=nl-qh*zD,mk=(C)0-(C)(r>lo);qh+=mk;r+=mk&zD;if(r>=zD){r-=zD;++qh;}rem=r;F qh;}I<G zD>H Ar W Hx(C r,C Q,C&Ga,C&Bl){E C zM=zD==0?1:zD==1?10:zD==2?100:1000,zC=By/zM;Bl=r/zC;Ga=(r-Bl*zC)*zM+Q;}H Ar W Jp(C r,G Ca,C Q,C&Ga,C&Bl){switch(Ca){case 0:Hx<0>(r,Q,Ga,Bl);Fv;case 1:Hx<1>(r,Q,Ga,Bl);Fv;case 2:Hx<2>(r,Q,Ga,Bl);Fv;Mu:Hx<3>(r,Q,Ga,Bl);}}H Ar W ar19store4(M*d,C r){M h=r/Cu,l=r-C(h)*Cu,qh=h/Ab,ql=l/Ab;d[0]=l-ql*Ab;d[1]=ql;d[2]=h-qh*Ab;d[3]=qh;}H Ar W ar19storepair(M*dq,M*dt,C qv,C tv){M qh=(M)(qv/Cu),ql=(M)(qv-(C)qh*Cu),th=(M)(tv/Cu),tl=(M)(tv-(C)th*Cu);D v=_mm256_set_epi64x(th,tl,qh,ql),Cy=Jc(_mm256_mul_epu32(v,C9(3518437209ULL)),45),rem=Br(v,Es(Cy,X(Ab))),Ce=Bd(rem,_mm256_slli_epi64(Cy,32));_mm_storeu_si128((Cn*)dq,E4(Ce));_mm_storeu_si128((Cn*)dt,Ej(Ce,1));}I<G zW>H A2 ar512big(Dg&a){A2 Ce;E G cap=5*((zW*64+62)/63)+1;Ce.v.Bh(cap);M*d=Ce.v.V();G E5=0,Ca=0;C Q=0;Bt Hn=zW-1;E C zD=E3;Bc(Hn>=0){Bc(Hn>=0&&!a.x[Hn])--Hn;if(Hn<0)Fv;C rem=a.x[Hn],qh=rem>=zD;a.x[Hn]=qh;rem-=qh*zD;At(Bt j=Hn-1;j>=0;--j)a.x[j]=F2(rem,a.x[j],rem);C Ga,Bl;Jp(rem,Ca,Q,Ga,Bl);ar19store4(d+E5,Ga);E5+=4;Ca+=3;if(Ca>=4){d[E5++]=Bl%Ab;Q=Bl/Ab;Ca-=4;}A8 Q=Bl;}if(Ca)d[E5++]=Q;Bc(E5&&!d[E5-1])--E5;Ce.v.Bh(E5);F Ce;}I<G zW>H Ap::pair<A2,A2> ar512big_pair(Dg&q,Dg&t){A2 zQ,zT;E G cap=5*((zW*64+62)/63)+1;zQ.v.Bh(cap);zT.v.Bh(cap);M*dq=zQ.v.V(),*dt=zT.v.V();G E5=0,Ca=0;C cq=0,ct=0;Bt Hn=zW-1;E C zD=E3;Bc(Hn>=0){Bc(Hn>=0&&!(q.x[Hn]|t.x[Hn]))--Hn;if(Hn<0)Fv;C rq=q.x[Hn],rt=t.x[Hn],aq=rq>=zD,at=rt>=zD;q.x[Hn]=aq;t.x[Hn]=at;rq-=aq*zD;rt-=at*zD;At(Bt j=Hn-1;j>=0;--j){q.x[j]=F2(rq,q.x[j],rq);t.x[j]=F2(rt,t.x[j],rt);}C lq,hq,lt,ht;Jp(rq,Ca,cq,lq,hq);Jp(rt,Ca,ct,lt,ht);ar19storepair(dq+E5,dt+E5,lq,lt);E5+=4;Ca+=3;if(Ca>=4){dq[E5]=hq%Ab;dt[E5]=ht%Ab;++E5;cq=hq/Ab;ct=ht/Ab;Ca-=4;}A8{cq=hq;ct=ht;}}if(Ca){dq[E5]=cq;dt[E5]=ct;++E5;}G nq=E5,nt=E5;Bc(nq&&!dq[nq-1])--nq;Bc(nt&&!dt[nt-1])--nt;zQ.v.Bh(nq);zT.v.Bh(nt);F{Ap::Fm(zQ),Ap::Fm(zT)};}I<C zD>H E C N(){C x=1;At(G i=0;i<6;i++)x*=2-zD*x;F x;}I<G zN>Dw H3{G K9 e[Ed]{};E H3(){At(G a=0;a<Ed;++a){C p=1,q=1,t=0;At(G i=0;i<zN;++i){C k=(a+i)%Ed,pp=((6*k+Ed-5)%Ed)*((2*k+Ed-1)%Ed)%Ed*((6*k+Ed-1)%Ed)%Ed,qq=k*k%Ed*k%Ed*(F0%Ed)%Ed,tt=pp*((13591409ull+545140134ull*k)%Ed)%Ed,pt=p*tt%Ed;t=(t*qq+(i&1?Ed-pt:pt))%Ed;p=p*pp%Ed;q=q*qq%Ed;}Bc(e[a]<4&&p%7==0&&q%7==0&&t%7==0){++e[a];p/=7;q/=7;t/=7;}}}};I<G zN,G zD>Dw Bg{G K9 e[zD]{};E Bg(){G inv2=0,inv6=0;At(G j=1;j<zD;j++){if(2*j%zD==1)inv2=j;if(6*j%zD==1)inv6=j;}At(G a=0;a<zD;a++){G qt=0;At(G j=0;j<zN;j++)if((a+j)%zD==0)qt+=3;G pv=0,qv=0,Ga=1000;At(G j=0;j<zN;j++){G k=(a+j)%zD;if(k==5*inv6%zD||k==inv2||k==inv6)++pv;if(k==0)qv+=3;G z=pv+qt-qv;if(z<Ga)Ga=z;}e[a]=(G K9)(Ga<pv?Ga:pv);if(qt<e[a])e[a]=qt;}}};I<G PW,G QW>H Ar W iv1335div(Dg&p,Dg&q,Dg&t,C zzD,C iv){if(zzD==1)F;Dg z[3]={p,q,t};At(G j=0;j<3;j++){C c=0;G w=j?QW:PW;At(G i=0;i<w;i++){C u=(z[j].x[i]-c)*iv;z[j].x[i]=u;c=(O(u)*zzD+c)>>64;}if(c)F;}p=z[0];q=z[1];t=z[2];}I<G Hd,G PW,G QW>H Ar W iv1299all(G a,Dg&p,Dg&q,Dg&t){C zzD=1,iv=1;A1 He=[&](C prime,C pinv,G e){Bc(e--){if(zzD>Io/prime){iv1335div<PW,QW>(p,q,t,zzD,iv);zzD=iv=1;}zzD*=prime;iv*=pinv;}};H E H3<Hd> st{};He(7,N<7>(),st.e[a%Ed]);H E Bg<Hd,11> g11{};He(11,N<11>(),g11.e[a%11]);H E Bg<Hd,13> g13{};He(13,N<13>(),g13.e[a%13]);H E Bg<Hd,17> g17{};He(17,N<17>(),g17.e[a%17]);H E Bg<Hd,19> g19{};He(19,N<19>(),g19.e[a%19]);H E Bg<Hd,31> g31{};He(31,N<31>(),g31.e[a%31]);H E Bg<Hd,37> g37{};He(37,N<37>(),g37.e[a%37]);H E Bg<Hd,41> g41{};He(41,N<41>(),g41.e[a%41]);H E Bg<Hd,43> g43{};He(43,N<43>(),g43.e[a%43]);H E Bg<Hd,47> g47{};He(47,N<47>(),g47.e[a%47]);H E Bg<Hd,53> g53{};He(53,N<53>(),g53.e[a%53]);H E Bg<Hd,59> g59{};He(59,N<59>(),g59.e[a%59]);H E Bg<Hd,61> g61{};He(61,N<61>(),g61.e[a%61]);H E Bg<Hd,67> g67{};He(67,N<67>(),g67.e[a%67]);H E Bg<Hd,71> g71{};He(71,N<71>(),g71.e[a%71]);H E Bg<Hd,73> g73{};He(73,N<73>(),g73.e[a%73]);H E Bg<Hd,79> g79{};He(79,N<79>(),g79.e[a%79]);H E Bg<Hd,83> g83{};He(83,N<83>(),g83.e[a%83]);H E Bg<Hd,89> g89{};He(89,N<89>(),g89.e[a%89]);H E Bg<Hd,97> g97{};He(97,N<97>(),g97.e[a%97]);H E Bg<Hd,101> g101{};He(101,N<101>(),g101.e[a%101]);iv1335div<PW,QW>(p,q,t,zzD,iv);}I<G zN>H PQT Hy(G a,Bx Eh){O pp;C cc;It(a,pp,cc);Dg p=Jo(pp),q=Jo((O)a*a*a*cc),t=Jo(pp*(Ku+Jn*a));Ke<1,zN>(q,p,t,a);iv1299all<zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);A1 qt=ar512big_pair<(zN*108+63)/64>(q,t);A2 zQ=Ap::Fm(qt.first),zT=Ap::Fm(qt.second),zP;if(Eh)zP=ar512big<(zN*60+63)/64>(p);zT.Bs=a&1;F{Ap::Fm(zP),Ap::Fm(zQ),Ap::Fm(zT)};}
#pragma GCC pop_options
H Ak QPm(Ak xP){if(xP<1.0)F 0.0;F 0.325799*((xP-0.5)*Ap::log(xP)-xP+0.9189385332)+L2*xP;}H G QF6(G aQ,G bQ){if(bQ<=1000000u&&bQ-aQ<=896u)F aQ+((bQ-aQ+7)/8/2)*8;Ak qPa=QPm((Ak)aQ),qMass=QPm((Ak)bQ)-qPa;if(qMass<8192.0)F aQ+((bQ-aQ+7)/8/2)*8;Ak qLim=0.75*qMass,qExp=Ap::floor(Ap::log2(qLim/0.96)),L8=0.96*Ap::ldexp(1.0,(Bt)qExp);if(L8>qLim)L8*=0.5;Ak qTgt=qPa+L8,qC=(Ak)aQ+(Ak)(bQ-aQ)*L8/qMass;At(Bt qI=0;qI<4;qI++){Ak lc=Ap::log(qC),qD=0.325799*((qC-0.5)*lc-qC+0.9189385332)+L2*qC-qTgt,qDer=0.325799*(lc-0.5/qC)+L2;if(qDer<1e-9)Fv;qC-=qD/qDer;if(qC<(Ak)aQ+1)qC=(Ak)aQ+1;if(qC>(Ak)bQ-1)qC=(Ak)bQ-1;}G qCi=(G)(qC+0.5);qCi&=~7u;if(qCi<=aQ+7||qCi+7>=bQ)qCi=aQ+((bQ-aQ+7)/8/2)*8;if(qCi<=aQ||qCi>=bQ)qCi=aQ+(bQ-aQ)/2;F qCi;}H PQT Hf(G a,G b,Bx Eh=B0,A Gz=0){if(a>0&&b<=250000u){if(b-a==16)F Hy<16>(a,Eh);if(b-a==17)F Hy<17>(a,Eh);if(b-a==8)F Hy<8>(a,Eh);if(b-a==9&&b<=250000u)F Hy<9>(a,Eh);}if(b-a==1){if(a==0)F{A2(1),A2(1),A2(13591409)};O k=a;O pp;C cc;It(a,pp,cc);A2 p=A2::wide(pp),q=A2::wide(k*k*k*(O)cc);A2 t=A2::wide(pp*(Ku+Jn*a));t.Bs=(a&1);F{Ap::Fm(p),Ap::Fm(q),Ap::Fm(t)};}G m=QF6(a,b);if(m<=a||m>=b)m=a+(b-a)/2;A kk=Gz?Gz+16:0;PQT l=Hf(a,m,B0,kk);PQT r=Hf(m,b,Eh,kk);B A cq_=l.q.v.Y()+r.q.v.Y()-1;B A c2_=l.t.v.Y()+r.q.v.Y()-1;A cmax_=cq_>c2_?cq_:c2_;B Bx big=cmax_>256 &&(A)l.q.v.Y()*r.q.v.Y()>16384 &&(A)l.t.v.Y()*r.q.v.Y()>16384 &&(A)l.p.v.Y()*r.t.v.Y()>16384;PQT Gh;if(big)node_mul(l.q,l.t,l.p,r.q,r.t,r.p,Eh,Gh.q,Gh.t,&Gh.p,Gz);A8{Gh.t=l.t*r.q+l.p*r.t;if(Eh)Gh.p=l.p*r.p;Gh.q=l.q*r.q;}F Gh;}H Ar D iv796encode(D q){q=J(q,Al(7,6,5,4,3,2,1,0));D h=E1(Gc(q,X(5243)),3),r=_mm256_sub_epi16(q,Gd(h,X(100)));D p=Bd(h,Jk(r,16)),t=Gc(p,Gv(6554)),u=_mm256_sub_epi16(p,Gd(t,Gv(10)));F _mm256_add_epi8(Bd(t,_mm256_slli_epi16(u,8)),_mm256_set1_epi8('0'));}H W iv486write(B A2&x,G Ca,K9*Ce){G Fn=0;Ce[1]='.';A1 Li=[&](K9 c){if(Fn<Ca){Ce[Fn?Fn+1:0]=c;++Fn;}};G q=x.v.back();if(q>=1000)Li('0'+q/1000);if(q>=100)Li('0'+q/100%10);if(q>=10)Li('0'+q/10%10);Li('0'+q%10);Ap::A i=x.v.Y()-1;At(;i>=8&&Ca-Fn>=32;i-=8,Fn+=32){D raw=Cs((B D*)(x.v.V()+i-8)),text=iv796encode(raw);asm volatile("vmovdqu %1,%0":"=m"(*(__m256i_u*)(Ce+Fn+1)):"x"(text));}Bc(i&&Fn<Ca){q=x.v[--i];G left=Ca-Fn;Li('0'+q/1000);if(left>=2)Li('0'+q/100%10);if(left>=3)Li('0'+q/10%10);if(left>=4)Li('0'+q%10);}}H W kept_fwd(Bt slot,B M*a,A la,A n){Ir(n);Bi::Eb(Lf::g_sp[slot],a,la,n);}A9 Gl=Ap::Ff<G,C4<G>>;H W kept_mul(Bt slot,B M*b,A lb,A n,A Dx,Gl&Ce){A9 Di Bp::E0::fft;Bt sc=(slot==0)?1:0;Ak*zS=g_sp[sc];Ak*zK=g_sp[slot];Bi::Eb(zS,b,lb,n);B1(zS,zK,n);A7::B3<B0,B0>(zS,n);Ce.Bh(Dx+1);B C*co=(B C*)zS;if(Dx<=40000000){Bi::K0((B G Fp Fp*)co,Ce.V(),Dx);F;}C Q=0;At(A i=0;i<Dx;++i){Q+=co[i];Ce[i]=(M)(Q%Ab);Q/=Ab;}Ce[Dx]=(M)(Q%Ab);}H Gl wmul(B M*a,A la,B M*b,A lb){Gl r(la+lb+1);if(!la||!lb){Ap::fill(r.Af(),r.Du(),0);F r;}r[la+lb]=0;Bi::J9<Ab>(a,b,r.V(),la,lb);F r;}I<Dz zV>H W wtrim(zV&v){A n=v.Y();Bc(n>1&&v[n-1]==0)--n;v.Bh(n);}H E char32_t Lj[]=U"𛁱𡘠𢨳𭵻𘡄𭹍𔖇𱢳𤃅𰷲𰈚𪫪𠤖𰁅𧆦𓄨🄄𫁿𗖙𧴏𱼀𥐀𩉀𱈽𬠳𒊹𥫍𫷧𢥨𢊶𘬫𪼾𥯕𘠸𞢡𱡾𛃫𝨁𭌏𘡶𥫣𭤴𑓖𩃻𰭂𑆱𬅰𫥮𠥘𧝜𘤌𡦕𫞃𠬤𐫑𨨷𡙭𬢿𩛘𑢹𣋔𨈗𢖱𰢮𤢬𪾛灊𦚬𢋎𢖇𥦲𦬻𦃛𥥷𲊴𞣍𦀙🕘𘗙𠦭𣭼𣸜𧐏𧆻喙𰿻𭊌𠑽𣬝𡣾𲈪𛄝𐢌𐨝😔𩶒𨻕𫧣𫏴𠈣𧇉🂮𭯏𬁋𭬓𰤽𱐛𝡶👢𰼕𫂘𗓮𡛧𨺜𧽞𭛉𥫄𭡭𧓛𣔭𬖨𫢏𭴞𝧽𬄅𗤗𘌓𭾭𬧗𬵝𧸰𬽡𭭁𬨫𩑆𩛀𝩆𗝾𠶍𢄛𡉴𤔉𓍺𩥐𗔤𣧣𢰌𥒅𪲩𱗺𐳇𛱵𗨶𡗺𑵾𢬦𥼣𗞚𮘇𡦁𭎮𧙠𩲂𰙕𬚆𱢧𧼋𣬑𧖼𐅩𢠋𫲦𝙑𤶰𢠁𠓷𠍽𱈂𭘏𠱆𪂃𰭷𪊼𬾵𬐍𪒨𪄥𱦠𣃐𑻬𘜳𧎗𢃝𭁎𣬶𱞽𬇢𢗴𤄝𨽼𢤨𐌈𢞅𑠎𧠓𩅄𠾎𡬜𱐯𠔨𧚨🔖𥼄𬧝𡑷𩳒𬣳𨺉🦚𱯸𬒡𬊬🔊𡡡𫧭𪖐𔕞𱎷𲋇變𨧄🕣𨚥𫍥𦇫𦇸𪜥𫛒𓁮𬒺𚿱𢍜𘲮𪭅𩉖𣋌𭓢𗻕𑋈𝣅𐴶𤗈𧂠𣦺𪦿𒍊𖤩𦣎𧺩𤣔𧭪𔒝𗛅🬮𑀓𝨻𭿃𩷲𪊢𖩼𣡖𥟢𫻱𖩋𤎭𪢍𒆓𬐑𫒽𥎏𝁊𪉄🭫𝩿𬚩𪁎𢚼𗡽𲋕𦾕𤾯𧢖𡽯寃𨬞𭚆𫳾𧛡𬞮𤲟𝈑𘉫𖣶𣘩𣳣𭜐𭂸𰳽𮦤👺𫞊𫟽𨯲𲍿𑜌𣗾𮈱𬚧𩎔𭧳𣣙𬣋𫆻𗑧𮨡𨱷𥐳𝗞𣒋𨝎󠆅𲅾𘉜𤪱𡟁𩧪𐃰𤁠𗶉𝞂𢾡🥛𨜷𥜱𥡫𣝡𝞾𭻕𮝆𬀭𐞜𢷗𱼈𣋍𢎠𝛂𣷗𧛱𗸭𪀶𐲮𪦽𥉼𰰄𦛤𪔮𝼁𡤳𬌽𫼦𛀙𤆢𤵾𬧳𝖬𣙎𐳞𢈉𰥔𱆢𧁂𱺸𣥁𐝢𰍨𓋯𣤢𫽡𘨥𥳶𪋯𱣮𡒹𗏟𤺿🨘𭹇🨴𗾇𪡕𗅨𲎗𢕩𨧢𛂈𖽥𩥑𬘩𤼱𭾱𛉘𗂂𰬧𑧔𤦚𩢝𝈇𬎂𗻶𧌛𢨘𥎆𰏊𫡩𝋧𗫃🚽𦃯𱀦𢂣𪦹𩲍𢝭𫶵𤨖𪐎𦢆𡊈𰳖𢹺𑀒𬮈𑑈𢵤𑀡🭯𫳡𑌾𗡘𭂚𥈳𑒒𩰐𘥕𦢊𫊽𬈅𖣦𗡸𢝶𨃵𦣫𪜏🀪𱷶𝜻𰷮𢒯𣚵𰢲𦒆𲈲𑁈𠢮𬞙𠉸𲅔𡋩𫾅𑣗𡃘𥬪𥂧𗏶𣾙𣇡𨄰𗫟𠍂𱛔𞠓𪊒𠥔𨙶𫣼𱦰🬼𝚂𮑞𘯨𮩶𝐔𭻁𣕱𧃸𤹔𑁛𰚏𢈂𪀀𥘚𑲋𬎏𪵠🯰𢨼𠾽𠄩𫄬𠎴𐬹𦿖𧑢𭉙𤶎𣔌𠂱𦨇𫭻𣽠𓀘𫳊𨠕𨒘𭮻𤬄𰿼𰘜𝁥𧹜𧗊𭅱𩬖𪊥𱸟𢴙𦬶𗈐𭈭󠆀𧥆𔕸𰯡𦎙𘣞𦥀𲉞𗿋𢞣𤀓𐫈𫴌𣏤𱍛𪖞𬃍𦼫𣄕𲇜🥱🜊𠧽𘂁𰗻𓅂𡵳𡮆𭭶𬯤𬼅𬡢𝈷𬼡𠟚𮌲𘮋𠁵𒇤𰔄𣹑𧚒𨜼𱮮𮓱𨲺𝡧𧀥𭼲𱑮𡶳𰱳𘧰𦰃𩇫𱁅𣬗𪣳𨈾𢊫𪀕𩘓𠵌𰩓𭷾𡶫𞤾𥄇𐕱𬛊𑖇𗁾𤬶𧆋𱼀🜶𡶔𤱆𫥤𰈦𮄯𱇾𧐈𰅉𢌬𑣘𢓹𥋋𡁋𲍦𡦙𪑳𠊥𪂄𪪷𨵯𮍋𩰽𬖬𮛋𧊥𧰫𦏆𢥐𡭇𭵋𦶧𠳂𩋦𧙴𱚂𣪎𐬎𠻑𝩹𠀺𩨑𑛇𥵋𡤼𭰌𫖚𲈴𧍹𣊸𬌕𪾗𓊁𤀼𫨲𰟟𩗷𓍞𨪉𘑄𢬾𦢫𘂑𨿢𑿩𢦄𱐭𦟙𫅷𑐇𩕽𡏟𘣃𤪲𠹴𒇧𰃄𣶎𨿩𪜨𮨽𭴍𬨂𰧳𩠧𦉽𡷴𪘏𫛠𫛔💴𡑒𠒽𥿜𭓽𪫑𗸥𓐪𢳽𪇨𥹄𥲞𥦷𤵗𭟤𝗌𖺔🞉𣪊𬨓𨚄𢲜𮎒𦏤𭑝𣇓𪮞𥧳𠄅𗋩𡳽𣀙𫂫𦝏𬐧𨝇𐓆𮏘𧄊𦩜𘴈𪘜𖠒𧉝𡁀𩱠𪓹𜽓𮬎𧞓𮟦𪐨𫒇𑒟𔒼🁱𮉱𓎊𡌹𤸱𰂽𥙑𝔵𨑂𧌶𒇥𝝀𥛏𮮤𰸤𪕠𘒺𦡿𬅝𞊡𣏾𐍐𖠨𮜛𠦆𭄉𱱉𲆭𐲅𘌂𢔱𝪭𮊶𑁒𗝒𭶹𭛕𢷑𰇩𢶽𗏲𲅀𩣹𖼼𠦔𣍂𭰂𣄘𡒸𩆸𧞕𔓠𰫈𮗈𭘟𑨅𥜭𮄠𩿩𭧳𫆄𑜘𧍟𩚨𬇀𬞲𠆔𨳃𫹾𡧣𥹦𠵼🛈𦤄𤵳𱧈𨄄𥿟𧾣𗅺𨕢𣿐𗖬𦎖𐣫𤒴𑤄𣗝𥘔𭣈𢍿𭔋湮𝑫𨾗𭨋𥫉𘛱𲂑𰬏𭛶𐅹𭏙𬔥𠕔𝋨𨈀𭵓𠱛𭋑𡙊𱵨𨚲𑄩𘒶𡸬𡩗𘠮𝧪𭒫𣳅𝒳𘌮𡪔𰵼𰝿𭣐𢒁𲎒𩬋𖮂𪃧𰛂𧳰𱖁𱰜𐦉𱆡𭵑𡇧𱘛𦅷𐣿𦕆𱝪𬢰𤓳𭪦𩩈𩦩𔕫𩳟𝚏𦤘𖠭𗞨𖹺𪒩𰴝𐎎𰦀𝐷𢧰𨅢𥱔𫱥𥷱𧨇𣑓𤳻𛋗𤶭𧢦𥆚𜿃𐛍𭙋𢯿𦓼𩛏𪶥𑄇𛉿🧮𧆅𜾒𬎂𒃭𗙠🜡🛩𘃥𣁘𧑳𩆛𧛈𢷏𩧝𧜁𣹴𫒯𫐊𱊍𤮥𘂮🥊𐋌𐛜𲈘𝣚𐖕𐑓𤺾𖧱𘛱𰝼𐠀𭜖𞄤𗳡𗤅𬵴𦎗𱵦𧀞𥌲𡇪𣈍𦺯𜽷𩟇𪍍𦾂𢹖𦳚𫬳𦺪𪜵𨈋𢕎𐧶𬛆𘛎𣵪𝇐𭻜𱼆𪖘𗺇𣲧𔕙𒀾𤭹𝧎𞟲𥥷𣣘𭢕𪦥𭖬𦭳🝻𤘙𛂐𨸋𥳞󠆚𪵫🁡𐎁𪒮𗩸𥫇𪫳𔒬𡃞𭮋𘩅𬺑𱠃𨪁𢠇𦤕𬀆𘪠𓅙𐴌𰑈𥨘𪌊𬂁𪛔𱗰𥱏𩒑𧠠𗈄𨅐𠲣𠇻𠏃𦋚𨏺𥯶𤔤𡌩𣇄𘋨𦣸𢼖𧼶𡱆𰡅𤑏𭖽󠆈𬶅𝌤𑵐𐖳𩲴𤱬𩓿𭇪𨏻𛰥𧰩𰯯𰩟𭹾𫮋𪼄𡹕𠙆𰄤𬜶𣯹𐂾𐅠𱙊𭢽𩘃𛁥𱝯𱾉𗳋𝞃𭊢𧕄𱏻𢙳𗟉𮮊𪺒𤒝𜾆𢏒𭃡𢃐𤭢𠭎𧴣𗟃𧓲𗂚𢏢𭦺𱪂𩩫𩴣𪓡🌁𰶞𫙛𝡔𱰱𤆋𪑛𤵥𬄧𡼨𢏬𐋌󠄽𦽇𥷰𖥩𤽒𥉒𐛫𠺜𢏥𪻃𧯒𤩤𱃥𩆹𡱛𫠦𨺹𗜽𨻌𡏄𬝇𣕖𦽻𘠾𡆖𫋝𥤠𠐛𣝺𢳆𤟆𭦴𩌼𭉏𑜽𦚏𥬡𐠍𭳴𘮘𣮩𥵐𮡰𣐤𮋅𥢋𐦿𥗙𧯝𥣏𡇧𭷼𥙐𡘡𫴗𡉘𣠬𢱞𩞟𰗖𘬍𫭱𰑟𩚝𠼂𫳣𒂌𦺨𠑊𪄉𗟫𘢥𥟘𐫵𭇅𖧚𗘏𓃊𣮶𗎘𪙐𦩗𤇥𫣩𦡧𣉩𒒿𬝲𡠥𱁻𦸪𫽭𐕈𡼡虧𲃳𧐦𰄢𱳜𭸢𠫙𗶰𦓠𫛀𢨶𱭤𰔓𐓧𗣷𬸍𣞋𘚨𮪅𲀇𣾇𩂖𠗈🙝🪤𰱻𫡏𘜃𦳫𥁎割𲁲𢓛𭱧𫹦𣨉𫍽𘇟𝍵𝆈𢎖𣗉𢢂𭂍𠳱𬣟𦂞𫛼𝚷𑄋𡥍𪇯𩣒𬂶𭧕𭬱𱯟𩭋𱁩𧂻𤖚𮨼𮠭𐋱𓏮𪑞𣢼𰬓𤒃𒋖𤃑𪋹𪢺𫱌𢒤𫗉𰨹𧍨𗞻𘄏𥾺𫙇𰫥𦿳𑇛𛂡𘉘𮀜𣀩𫳸𱨽𫐟𱅢𭜍𥓅𥂤𝠿𰢎𭁕𒌁𭭸𦁖𧒦𦇕𢱽𠊬𒌠𦄷𭓧𑝄🝿𥎙𣯝𮄈🜤𧹲𭠰𭮿𧹝𨶪𫤚𩋥𩹲𮥛𐡘𡈝𧞟𰱜𤳌𖩮𭼉𱚕𑂤𬎗𭸫𨴒𩆛𩫄𬯘𢡆𡤦𭂓𦾗𫻏𪎋𣿅𝩎𤙡𨆎𣾫𑣕𦰏趼𞢯𪜞𡦴𣅷𧣍𱢗𫓜𗆼𜼨𫅉𗖗𤒹𨼫𐅔𰄒𠱺𠿄𗆇𱑴𐖼朡𩺫𢀓𨰀𤺄𫕽𑧟𩪝𫴘𒉱𘑠𗤤𩻮𢛹𐦒𤿫𗝸𰣭𤀊𢂒𐲉𩠾𓅨𬎄𩻠𪘇𫶙😡𬢢𖪳𡭠𘂹𐪍𠘃𠶧𗛣𧊭𗢁𩘯𱢲𐘮𰽤𦜆𰬮󠅟𭤨𘡐🢰𬣓𘇟𫘏𰶀𣢹𧾄𡣋𜼵𥀤𝑹𱕼𠡝𡋞𦥺𭧼𡵘𥈺𱞮𫞑𦀾𦴂𤤽𭈶𭥮𝍈𮩾𧨞𞁃𘔒𮢑𖪶𑄡𰅘𠑫𠍙𗻺𡔼𨤫𨵖𫤚𭄲𓃸𨐬𠸑𠽎𥍈𰔔𰽓𦲕𠊹𦧺𘍿𐀀";Dw Iv1299{M x[23441]{};E Iv1299(){At(G i=0;i<23441;i+=3){C v=C(Lj[2*(i/3)]-65536u)|(C(Lj[2*(i/3)+1]-65536u)<<20);x[i]=v%10000;if(i+1<23441)x[i+1]=(v/10000)%10000;if(i+2<23441)x[i+2]=v/100000000;}}};H E Iv1299 iv1299{};H Ap::Ff<M>newton_quot(B M*zT,A lt,B M*zQ,A nq,A Lq){B A Lp=Lq+8;B Bx fixed1299=Lq==750009&&nq==750011&&zQ[nq-8]==9966u&&zQ[nq-7]==4287u&&zQ[nq-6]==8445u&&zQ[nq-5]==3464u&&zQ[nq-4]==8847u&&zQ[nq-3]==384u&&zQ[nq-2]==5691u&&zQ[nq-1]==2970u;B A M0=fixed1299?23440:46;Gl zR;if(fixed1299)zR.Gk(iv1299.x,iv1299.x+23441);A8{B G tk=nq<49?(G)nq:49u;A2 dn;At(G i=0;i<tk;++i)dn.v.F1(zQ[nq-tk+i]);G Q=1;At(G i=0;i<dn.v.Y()&&Q;++i){G t=dn.v[i]+Q;dn.v[i]=t%Ab;Q=t/Ab;}if(Q)dn.v.F1(Q);A2 nu;nu.v.Gk(M0+tk+1,0);nu.v[M0+tk]=1;A2 r0=nu/dn;zR.Gk(r0.v.Af(),r0.v.Du());if(zR.empty())zR.F1(1);}A zM=M0;At(Bt iter=0;iter<80;++iter){B A quse=(nq<2*zM)?nq:2*zM;B M*Dq=zQ+(nq-quse);B A lr=zR.Y();B A n1=Bp::D1(quse+lr-1);B A cp1=quse+lr-1;Gl zP;B Bx cankeep=(n1>=512);if(cankeep){kept_fwd(1,zR.V(),lr,n1);kept_mul(1,Dq,quse,n1,cp1,zP);}A8 zP=wmul(Dq,quse,zR.V(),lr);B A Lk=zM+quse;Ap::A Iu=zP.Y();B G*ar_p=zP.V();Bc(Iu&&!ar_p[Iu-1])--Iu;Bt Bs=Iu>Lk;Ap::Ff<G,C4<G>>zF;if(Bs){zF.Gk(ar_p,ar_p+Iu);Ap::A j=Lk;Bc(zF[j]==0){zF[j]=9999;++j;}--zF[j];}A8{zF.Bh(Lk+1);Ap::A j=0;Bc(j<Iu&&!ar_p[j])++j;if(j==Iu){Ap::fill(zF.Af(),zF.Du(),0);zF[Lk]=1;}A8{Ap::fill(zF.Af(),zF.Af()+j,0);zF[Lk]=0;zF[j]=Ab-ar_p[j];++j;At(;j<Iu;++j)zF[j]=9999-ar_p[j];At(;j<Lk;++j)zF[j]=9999;}}wtrim(zF);B A p=(Lk>zF.Y())?(Lk-zF.Y()):0;if(zM>=Lp&&p+8>=Lp)Fv;A M2=(2*zM<Lp)?2*zM:Lp;if(M2<=zM)M2=2*zM;Bx fin=(2*p+8>=Lp)&&(M2>=Lp);B A sh=quse;B Ap::A Fo=2*zM-M2;Gl Rn(Ap::max<Ap::A>(zM+lr,lr+zF.Y()+1>sh?lr+zF.Y()+1-sh:0)+2-Fo,0);At(A i=0;i<lr;++i)Rn[zM-Fo+i]=zR[i];if(zF.Y()>1||zF[0]){A K6=sh>lr+16?sh-lr-16:0;if(K6>=zF.Y())K6=0;B A ar_fs=zF.Y()-K6,Iv=sh-K6;B A cg=lr+ar_fs-1;Gl zG;{B A n2=Bp::D1(cg);if(cankeep&&n2>=512&&n2==n1){kept_mul(1,zF.V()+K6,ar_fs,n2,cg,zG);}A8 zG=wmul(zR.V(),lr,zF.V()+K6,ar_fs);}A i=0;if(!Bs){A m=zG.Y()>Iv+Fo?zG.Y()-Iv-Fo:0;G Q=m?Il(Rn.V(),zG.V()+Iv+Fo,m,0):0;i=m;At(;Q&&i<Rn.Y();++i){G q=Rn[i]+Q;Q=q>=Ab;Rn[i]=q-(Q?Ab:0);}}A8{Bt br=0;At(Ap::A ar_j=Iv;ar_j<zG.Y()&&ar_j<Iv+Fo;++ar_j)br|=zG[ar_j]!=0;A m=zG.Y()>Iv+Fo?zG.Y()-Iv-Fo:0;br=m?Im(Rn.V(),zG.V()+Iv+Fo,m,br):br;i=m;At(;br&&i<Rn.Y();++i){Bt q=Bt(Rn[i])-br;br=q<0;Rn[i]=M(q+(br?Ab:0));}}}wtrim(Rn);zR.J3(Rn);zM=M2;if(fin)Fv;}if(zM>Lp){A drop=zM-Lp;if(zR.Y()>drop)zR.erase(zR.Af(),zR.Af()+drop);A8{zR.Gk(1,0);}wtrim(zR);zM=Lp;}B A off=nq+zM;if(lt>nq+8){B A tcut=nq;Gl zP=wmul(zT+tcut,lt-tcut,zR.V(),zR.Y());B A off2=off-tcut;Ap::Ff<M>zS(Lq+3,0);At(A i=0;i<Lq+3&&off2+i<zP.Y();++i)zS[i]=zP[off2+i];Bc(zS.Y()>1&&zS.back()==0)zS.K3();F zS;}Gl zP=wmul(zT,lt,zR.V(),zR.Y());Ap::Ff<M>zS(Lq+3,0);At(A i=0;i<Lq+3&&off+i<zP.Y();++i)zS[i]=zP[off+i];Bc(zS.Y()>1&&zS.back()==0)zS.K3();F zS;}Dw Result{Ap::L4 Ca;G terms;C bs_ticks,sqrt_ticks,divide_ticks,format_ticks;Bx certified;};Gx((noinline,noclone))Result compute(G Ca,K9*Ce){if(!Ca)F{"",0,0,0,0,0,B0};G Cd=(Ca+38)/4,dec=Cd*4,terms=(G)((dec+40)/14.18)+1;Ir(Bp::D1((A)2*Cd+128));G7();C t0=Kh();PQT r=Hf(0,terms,Dm,A(Cd)+32);G7();C t1=Kh();A2 root=H6(Cd);G7();C t2=Kh();A2 pi;{A mn=Ap::min(r.q.v.Y(),r.t.v.Y());B A Gz=A(Cd)+32;A cut=mn>Gz?mn-Gz:0;A2 qh=r.q.Bl(cut),th=r.t.Bl(cut);A2 num=root*qh;A As=num.v.Y(),Az=th.v.Y();if(Az>=16&&As+2<Az*2){A Av=Az*2-As-2;A1 v=newton_quot(num.v.V()+Av,As-Av,th.v.V()+Av,Az-Av,Cd);pi.v.Gk(v.Af(),v.Du());pi.H2();}A8 pi=num/th;}G7();C t3=Kh();iv486write(pi,Ca,Ce);Ap::L4 s;Bx ok=B0;G7();C t4=Kh();F{Ap::Fm(s),terms,t1-t0,t2-t1,t3-t2,t4-t3,ok};}}W calc_pi(G n,K9*s){if(!n)F;if(n==1){s[0]='3';F;}Lf::compute(n-1,s);}
#undef size_t
#undef const
#undef unsigned
#undef uint64_t
#undef return
#undef constexpr
#undef Complex
#undef input
#undef template
#undef static
#undef _mm256_permutevar8x32_epi32
#undef uint32_t
#undef __uint128_t
#undef carry
#undef void
#undef _mm256_and_si256
#undef imag
#undef real
#undef C64X4
#undef data
#undef float_len
#undef rank
#undef _mm256_set1_epi32
#undef typename
#undef A
#undef B
#undef C
#undef E
#undef F
#undef G
#undef H
#undef I
#undef J
#undef K
#undef L
#undef M
#undef O
#undef P
#undef Q
#undef R
#undef S
#undef T
#undef V
#undef W
#undef X
#undef Y
#undef Z
#undef D
#undef N
| Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |