/* Reference:saffah_codex_6a_agg3 https://duck.ac/submission/174593: full paired-carry Pi3M engine. */
/* Reference:saffah_codex61s_agg5 https://duck.ac/submission/174520: complete Pi3M engine, pure-mathematical reciprocal seed and paired carry. Full inherited notices below. */
/* References / 引用:组内base36首ID及后续增量,逐项累加;原址https://duck.ac/submission/{ID}。
TSKY https://duck.ac/submission/19388:HintFFT/MIT。
TSKY https://duck.ac/submission/47426:HintFFT/MIT。
B=saffah_codex61s_agg5:3hfh,y,c0,47,5,xg,bv,6p,s,19,g,db,6i,5y,5,24,z2,wc,4q,1p,2k,2o,1g,b,e,j,4,44,5z,d3,n,a,g,b,2,1q,1v,11,c,bb,3b,1,1k,14,2o,31,89,96,e,n,51,19,l,16,1m,c,s,3d,2z,f,75,2m,3x,f,1c,bp,25,p7,1x
C=saffah_codex_6a_agg3:3hd8,r,d5,8k,159,5v,h,1,4,8s,26,3,1u,1h,2w,25,1w,56,5g,1y,ez,1kj,1w,1p,u,2,29,1b,at,1,b,y,42,21,e,6g,x,4i,q,fc,4,11,bl,k,b0,1y,22,9r,1h,1,1y,1,4j,2w,v,q,k,q,g,20,j,37,n,2,5k,11,y,xj
D=saffah_codex_maker:3h8q
E=saffah_v41f1017_agg4:3hls,99,5,1q,1bk,58,ej,3e,6g,a1,3,n4,8f,3s,7i,42,1p,22,69,bd,1f,6i,b,l,2f,29,40,bn,e,1,iz,8,bf,2y,71,4m,y,s,21,20,bd,cj,f1,po
174318完整Pi引擎/原继承索引;174344复用ar_reduced的奇除数逆元表/完整fallback;余祖先继承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.
saffah_codex61s_agg5 https://duck.ac/submission/174392:完整Pi3M引擎/逆元约分/pending乘法;https://duck.ac/submission/173423:三base10000位打40bit思想,只复用打包;https://duck.ac/submission/174409:固定数学商种子机制。
思路:用本题纯数学PQT和GMP构造23440位商倒数种子,仅固定数学规模/分母首8位匹配时直接载入;完整fallback/精度保持;自建单字ASCII宏/数值字典与安全空白压缩只压缩源编码,不改数学。目的:种子全位GMP恒等/单元/完整3M字符后官网,无测试数据观测。
saffah_codex_6a_agg3 https://duck.ac/submission/174487:借用小PMADD相邻两系数合并base1e8进位;https://duck.ac/submission/174428:该成对进位原始思想。其余代码保持本题174392和自己174475的数学23440位种子路径。新思路:成对PMADD与Pi3M量化树/纯数学商种子合并。试验目的:完整独立GMP/全部3M字符后官网,不以本地速度过滤。
*/
/* Idea: Bypass two logarithms in small quantized-tree splits. Through b<=1e6 the existing mass derivative is below8.25 limbs/term, so intervals<=896 have mass<7392<8192 and must select the identical aligned midpoint. Larger intervals keep the original optimizer. Purpose: native/PQT/carry/multiply and full3M GMP digits before official timing. */
/* Idea: Use paired-carry PMADD multiplication up to262144 scalar products, avoiding FFT setup for the next small-size band. Purpose: full arithmetic/GMP3M validation and official timing. */
#include <bits/stdc++.h>
#include <x86intrin.h>
#pragma GCC optimize("O3,unroll-loops")
// Adapted from https://duck.ac/submission/47426 (TSKY), HintFFT MIT.
// Full attribution and complete MIT notice are retained in the leading reference block.
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 H size_t
#define J const
#define L unsigned
#define O uint64_t
#define X return
#define Y constexpr
#define Z Complex
#define K input
#define V template
#define E static
#define I _mm256_permutevar8x32_epi32
#define C uint32_t
#define G __uint128_t
#define W carry
#define B void
#define R _mm256_and_si256
#define Q imag
#define S real
#define F C64X4
#define P data
#define M float_len
#define D rank
#define N _mm256_set1_epi32
#define T typename
#define Aa size
#define Ab 10000
#define Ac fft_len
#define Ad __m256i
#define Ae inline
#define Af SIZE_TYPE
#define Ag fft_2point
#define Ah reinterpret_cast
#define Ai double
#define Ak begin
#define Al Float64
#define Am ar_factor_triplet
#define An Complex2
#define Ao std
#define Ap _mm256_setr_epi32
#define Aq fft_split_radix_dit_template
#define Ar fft_split_radix_dif_template
#define As F64X4
#define At for
#define Au len1
#define Av operator
#define Aw shift
#define Ax dividend
#define Ay len2
#define Az ary_ptr
#define A0 Float
#define A1 tmp3
#define A2 __m256d
#define A3 while
#define A4 Big
#define A5 nullptr
#define A6 auto
#define A7 _mm256_add_epi32
#define A8 BASE
#define A9 FFTAVX
#define Ba else
#define Bb UINT_64
#define Bc change_length
#define Bd using
#define Be divisor
#define Bf table1
#define Bg _mm256_or_si256
#define Bh FROM_RIRI_PERM
#define Bi len
#define Bj transform2
#define Bk hint_arithm
#define Bm bool
#define Bn resize
#define Bo _mm256_permute2f128_pd
#define Bp high
#define Bq set_true_len
#define Br store
#define Bs digits
#define Bt true
#define Bu hintpowfft
#define Bv tmp0
#define Bw tmp1
#define Bx int
#define By 10000000000000000ULL
#define Bz Ar512
#define B0 real_dot_binrev4
#define B1 _mm256_sub_epi32
#define B2 neg
#define B3 sizeof
#define B4 omega_cube
#define B5 HintVector
#define B6 normalized_dividend
#define B7 ary_true_len
#define B8 omega
#define B9 iditRecLong
#define Ca base_len
#define Cb tmp2
#define Cc hint_log2
#define Cd table3
#define Ce SIZE_TYPE_BITS
#define Cf transpose64_4X4
#define Cg getBegin
#define Ch multi_table_2
#define Ci quarter_len
#define Cj limbs
#define Ck out
#define Cl quo_digit
#define Cm other
#define Cn log_len
#define Co pos
#define Cp factor
#define Cq _mm256_set1_pd
#define Cr __m128i
#define Cs ar_prime_inv_table
#define Ct ivload1043
#define Cu 100000000ULL
#define Cv ar_factor_extra
#define Cw _mm256_mul_pd
#define Cx mulConj
#define Cy integral_constant
#define Cz break
#define C0 ComplexTableY
#define C1 quot
#define C2 _mm256_setzero_si256
#define C3 F64
#define C4 false
#define C5 new_size
#define C6 static_cast
#define C7 hintvector
#define C8 abs_compare
#define C9 multiplier
#define Da NoInitAlloc
#define Dd zero
#define De _mm256_set1_epi64x
#define Df BinRevTableC64X4HP
#define Dg _mm256_blend_epi32
#define Dh theta
#define Di index
#define Dj ar_src_dispatch
#define Dk fft_split_radix_dit_butterfly
#define Dl fft_split_radix_dif_butterfly
#define Dn namespace
#define Dp Complex64X4
#define Dr LOG_BEGIN
#define Ds FFTSqrtTableC64X4
#define Dt MAX_LOG_LEN
#define Du borrow
#define Dv _mm256_cvtepu32_epi64
#define Dw tmp7
#define Dx sqrt_table_1
#define Dy end
#define Dz _mm256_extract_epi32
#define D1 struct
#define D2 conv
#define D3 dividend_2digits
#define D4 class
#define D5 Float64X4
#define D6 int_ceil2
#define D7 alignas
#define D8 multi_table_3
#define D9 UINT_32
#define Ea sign_n_len
#define Eb _mm256_cvttpd_epi32
#define Ec sp_to_big
#define Ed 2401
#define Ee _mm256_floor_pd
#define Ef HINT_2PI
#define Eg ary_copy
#define Eh vec_size
#define Ei sp_fwd
#define Ej ivstore1043
#define Ek divisor_2digits
#define El quot_len
#define Em carryu
#define En this
#define Eo _mm256_extracti128_si256
#define Ep reciprocal_sqrt_constant
#define Eq _mm256_unpacklo_pd
#define Er _mm256_unpackhi_pd
#define Es mul
#define Et _mm256_cvtepi32_pd
#define Eu _mm256_cmpgt_epi32
#define Ev _mm256_testz_si256
#define Ew _mm256_mullo_epi32
#define Ex ar_factor_quotient
#define Ey it0
#define Ez 0.70710678118654752440084436210485
#define E0 SIZE_80
#define E1 dividend_ptr
#define E2 ar_take
#define E3 10000000000000000000ULL
#define E4 delete
#define E5 length
#define E6 transform
#define E7 _mm256_srli_epi32
#define E8 100000000
#define Fa difRecLong
#define Fb _mm256_castsi256_si128
#define Fc used
#define Fd _mm256_sub_pd
#define Fe res
#define Ff TableFixMulti
#define Fg static_assert
#define Fh CACHE_LOG_LEN
#define Fi table2
#define Fj FloatTy
#define Fk vector
#define Fl tmp5
#define Fm fft_dit_template
#define Fn fft_dif_template
#define Fo change_sign
#define Fp abs_mul_num
#define Fq __builtin_memcpy
#define Fr _mm256_add_epi64
#define Fs abs_rec_div
#define Ft move
#define Fu need_p
#define Fv written
#define Fw ar_drop
#define Fy long
#define F0 10939058860032000ull
#define F1 AlignMem
#define F2 transpose64_2X4
#define F3 it1
#define F4 it2
#define F5 _mm_loadu_si128
#define F6 max_shift
#define F7 half_len
#define F8 ele_size
#define F9 uintptr_t
#define Ga push_back
#define Gb ar_decimal_word
#define Gc TO_RIRI_PERM
#define Gd result
#define Ge carry550fold
#define Gf unit_table
#define Gg RI_DIFF
#define Gh binary_reverse_swap
#define Gi ar_i
#define Gj ar_unit_square
#define Gk low
#define Gl case
#define Gm base
#define Gn _mm256_mulhi_epu16
#define Go _mm256_mullo_epi16
#define Gp _mm256_cmpeq_epi32
#define Gq normalized_divisor
#define Gr public
#define Gs getBeginLog
#define Gt ar_src_span
#define Gu assign
#define Gv ar_vec
#define Gw _mm256_setzero_pd
#define Gx reverse
#define Gy SHORT_LEN
#define Gz LOG_SHORT
#define G0 multi_table_1
#define G1 addConj
#define G2 real_dot_binrev4t
#define G3 tmp6
#define G4 LEN_MAX
#define G5 abs_sub
#define G6 _mm256_set1_epi16
#define G7 sub_len
#define G8 __attribute__
#define G9 ar_carry_sub3
#define Ha keep
#define Hb ar_invodd
#define Hc ar_native_mul
#define Hd inv
#define He new_length
#define Hf _mm_lfence
#define Hg ptr
#define Hh ar_unit_cube
#define Hi in1
#define Hj cur_log_size
#define Hk sub
#define Hl quot_tmp_len
#define Hm binary_split
#define Ho private
#define Hp tail
#define Hq it3
#define Hr element_permute
#define Hs SizeType
#define Ht last_rem
#define Hu _mm_alignr_epi8
#define Hv ar_digit_vector
#define Hx top
#define H0 toRRIIPermu
#define H1 table_len
#define H2 throw
#define H3 unit_root
#define H4 string
#define H5 divisor_ptr
#define H6 remainder
#define H7 ar19slide
#define H8 prod
#define H9 trim
#define Ia ar_seven_table
#define Ib YMM
#define Ic sqrt_scaled_constant
#define Ie _mm_malloc
#define If row0
#define Ig row1
#define Ih in_data
#define Ii complex
#define Ij LOG_MAX
#define Ik swap
#define Il nt_zero
#define Im tmp
#define Io cos_1_8
#define Ip LEN
#define Iq count
#define Ir _mm_add_epi32
#define Is always_inline
#define It ar_carry_add3
#define Iu ar_carry_addi
#define Iv ar_carry_subi
#define Iw ar_r
#define Ix dcut
#define Iy sp_reserve
#define Iz ar_reduced_fallback
#define I0 ar_reduced
#define I1 ar_gpow
#define I2 ar_factor_seventeen
#define I3 ar_pn
#define I4 ar_gs
#define I5 TO_INT64
#define I6 inout0
#define I7 inout1
#define I8 INT_32
#define I9 target
#define Ja prod_len
#define Jb noexcept
#define Jc sum
#define Jf LONG_DIV_THRESHOLD
#define Jg ar_factor_thirteen
#define Jh ar_factor_nineteen
#define Ji FFTTableSqrt
#define Jj temp
#define Jk max_log_size
#define Jl get_omega3X2
#define Jm sums
#define Jn 545140134ULL
#define Jo _mm256_srli_epi64
#define Jp CACHE_LEN
#define Jq TableLong
#define Jr iditSplit
#define Jt omega_sqr
#define Ju _mm256_load_si256
#define Jv _mm256_madd_epi16
#define Jw divisor_normalize
#define Jx _mm256_slli_epi32
#define Jy iv901base
#define Jz iv581have
#define J0 ar512word
#define J1 ar19parts
#define J2 ar_factor_inverse
#define J4 char
#define J6 initOmegaX4
#define J7 omega0
#define J8 LOG_MID
#define J9 MID_LEN
#define Ka TableMulti1
#define Kb TableMulti2
#define Kc TableMulti3
#define Kh INT_64
#define Ki get_omegaX2
#define Kj tmp4
#define Kl abs_div_num
#define Kn fft_mul
#define Ko back
#define Kp Borr
#define Kq mulnum
#define Kr divnum
#define Ks ar_rem
#define Kt ar512extend
#define Ku 13591409ULL
#define Ky __rdtsc
#define K2 _mm_free
#define K5 load1
#define K6 TableFix
#define K8 log_rank
#define K9 difSplit
#define Lb BLOCK
#define Lc block
#define Le dot_rfft
#define Lf TABLE
#define Lg is_carry
#define Lh carry550
#define Li quot_tmp
#define Lk pop_back
#define Ll subtract
#define Ln ar_fc
#define Lo load
#define Lr false_type
#define Ls table_16_1
#define Lt table_16_3
#define Lu table_32_1
#define Lv table_32_3
#define Lw iditRecMid
#define Lx pi_compute
#define Ly UINT64_MAX
#define Lz dtop
#define L0 iv581reuse
#define L2 3.74098937
#define L3 emit
#define L4 iv1261bits
#define L5 fpow
#define Mm omega1
#define Mn it32_1
#define Mo it32_3
#define Mq before
#define Mr packed
#define Ms cmpabs
#define Mt qChunk
#define Mx HINT_PI
#define M1 LOG_END
#define M4 cpx_len
#define M5 len_div
#define M6 low_len
#define Nh default
#define Nl in_out1
#define Np bit_rev
#define Nq size2
#define Nr abs_add
#define Nx coeff
#define Ny seven
#define N3 pending
Dn Bu{V<T zT,H ALIGN=64> D4 F1{Gr: Bd Ptr=zT*;Bd ConstPtr=J zT*;~F1(){if(Hg){K2(Hg);}};F1():Hg(A5),Bi(0){}F1(H n):Hg(Ah<Ptr>(Ie(n*B3(zT),ALIGN))),Bi(n){}F1(J F1&)=E4;F1&Av=(J F1&)=E4;zT&Av[](H i){X Hg[i];}J zT&Av[](H i)J{X Hg[i];}Ptr Ak(){X Hg;}Ptr Dy(){X Hg+Bi;}ConstPtr Ak()J{X Hg;}ConstPtr Dy()J{X Hg+Bi;}H Aa()J{X Bi;}Ho: zT*Hg;H Bi;};V<T Ib> Ae B F2(Ib&If,Ib&Ig){A6 t0=Eq(A2(If),A2(Ig));A6 t1=Er(A2(If),A2(Ig));If=Ib(Bo(t0,t1,0x20));Ig=Ib(Bo(t0,t1,0x31));}V<T Ib> Ae B transpose64_4X2(Ib&If,Ib&Ig){A6 t0=Bo(A2(If),A2(Ig),0x20);A6 t1=Bo(A2(If),A2(Ig),0x31);If=Ib(Eq(t0,t1));Ig=Ib(Er(t0,t1));}V<T Ib> Ae B Cf(Ib&If,Ib&Ig,Ib&row2,Ib&row3){A6 t0=Eq(A2(If),A2(Ig));A6 t1=Er(A2(If),A2(Ig));A6 t2=Eq(A2(row2),A2(row3));A6 t3=Er(A2(row2),A2(row3));If=Ib(Bo(t0,t2,0x20));Ig=Ib(Bo(t1,t3,0x20));row2=Ib(Bo(t0,t2,0x31));row3=Ib(Bo(t1,t3,0x31));}D4 D5{Gr: Bd C3=Ai;Bd As=D5;D5():P(Gw()){}D5(A2 Ih):P(Ih){}D5(C3 Ih):P(Cq(Ih)){}D5(J C3*Ih):P(_mm256_load_pd(Ih)){}As Av+(J As&Cm)J{X _mm256_add_pd(P,Cm.P);}As Av-(J As&Cm)J{X Fd(P,Cm.P);}As Av*(J As&Cm)J{X Cw(P,Cm.P);}As Av/(J As&Cm)J{X _mm256_div_pd(P,Cm.P);}E As fmadd(J As&a,J As&b,J As&c){X _mm256_fmadd_pd(a.P,b.P,c.P);}E As fmsub(J As&a,J As&b,J As&c){X _mm256_fmsub_pd(a.P,b.P,c.P);}V<Bx zN> As permute4x64()J{X _mm256_permute4x64_pd(P,zN);}As Gx()J{X permute4x64<0b00011011>();}B Lo(J C3*p){P=_mm256_load_pd(p);}B K5(J C3*p){P=_mm256_broadcast_sd(p);}B Br(C3*p)J{_mm256_store_pd(p,P);}B Nt(C3*p)J{_mm256_stream_pd(p,P);}Av A2()J{X P;}Ad toI64X4()J{Y O mask=(O(1)<<52)-1;Y O offset=(O(1)<<10)-1;J Ad f64bits=_mm256_castpd_si256(P);Ad Hp=R(f64bits,De(mask));Hp=Bg(Hp,De(mask+1));Ad exp=Jo(f64bits,52);exp=_mm256_sub_epi64(De(offset+52),exp);X _mm256_srlv_epi64(Hp,exp);}Ho: A2 P;};D1 Dp{Bd F=Dp;Bd As=D5;Bd C3=Ai;Dp(){}Dp(As S,As Q):S(S),Q(Q){}Dp(J C3*p):S(p),Q(p+4){}Dp(J C3*p_real,J C3*p_imag):S(p_real),Q(p_imag){}F Av+(J F&Cm)J{X F(S+Cm.S,Q+Cm.Q);}F Av-(J F&Cm)J{X F(S-Cm.S,Q-Cm.Q);}F Av*(J As&Cm)J{X F(S*Cm,Q*Cm);}F Gj()J{J As t=Q+Q;X F(As(_mm256_fnmadd_pd(A2(Q),A2(t),Cq(1.))),S*t);}F Hh(J F&w)J{J As t=Q+Q;X F(As(_mm256_fnmadd_pd(A2(t),A2(w.Q),A2(S))),As(_mm256_fmadd_pd(A2(t),A2(w.S),A2(Q))));}F Es(J F&Cm)J{J As ii=Q*Cm.Q;J As ri=S*Cm.Q;J As r=As::fmsub(S,Cm.S,ii);J As i=As::fmadd(Q,Cm.S,ri);X F(r,i);}F Cx(J F&Cm)J{J As ii=Q*Cm.Q;J As ri=S*Cm.Q;J As r=As::fmadd(S,Cm.S,ii);J As i=As::fmsub(Q,Cm.S,ri);X F(r,i);}F Gx()J{X F(S.Gx(),Q.Gx());}B set1(C3 real_in,C3 imag_in){S=As(real_in);Q=As(imag_in);}V<T zT> B Lo(J zT*p,Ao::Lr){En->Lo(p);}V<T zT> B Lo(J zT*p,Ao::true_type){En->Lo(p);*En=En->H0();}V<T zT> B Lo(J zT*p){S.Lo(Ah<J C3*>(p));Q.Lo(Ah<J C3*>(p)+4);}B K5(J C3*real_p,J C3*imag_p){S.K5(real_p);Q.K5(imag_p);}V<T zT> B Br(zT*p,Ao::Lr)J{En->Br(p);}V<T zT> B Br(zT*p,Ao::true_type)J{En->toRIRIPermu().Br(p);}V<T zT> B Br(zT*p)J{S.Br(Ah<C3*>(p));Q.Br(Ah<C3*>(p)+4);}V<T zT> B Nt(zT*p)J{S.Nt(Ah<C3*>(p));Q.Nt(Ah<C3*>(p)+4);}F toRIRIPermu()J{F Fe= *En;F2(Fe.S,Fe.Q);X Fe;}F H0()J{F Fe= *En;transpose64_4X2(Fe.S,Fe.Q);X Fe;}F transToI64(Ao::Lr)J{X*En;}F transToI64(Ao::true_type)J{Y int64_t F1_2=4602678819172646912;A6 F1_2X4=As(A2(De(F1_2)));X F(Ee(S+F1_2X4),Ee(Q+F1_2X4));}As S,Q;};Bd Float32=float;Bd Al=Ai;Y Al Mx=3.141592653589793238462643;Y Al Ef=Mx*2;Y Al COS_PI_8=0.707106781186547524400844;V<T zT> Y zT int_floor2(zT n){Y Bx bits=B3(n)*8;At(Bx i=1;i<bits;i*=2){n|=(n>>i);}X(n>>1)+1;}V<T zT> Y zT D6(zT n){Y Bx bits=B3(n)*8;n--;At(Bx i=1;i<bits;i*=2){n|=(n>>i);}X n+1;}V<T IntTy> Y Bm is_2pow(IntTy n){X n!=0&&(n&(n-1))==0;}V<T zT> Y Bx Cc(zT n){Y Bx bits=B3(n)*8;Bx l= -1,r=bits;A3((l+1)!=r){Bx mid=(l+r)/2;if((zT(1)<<mid)>n){r=mid;}Ba{l=mid;}}X l;}Y C crc32(J J4*str){C crc=0xFFFFFFFF;A3(*str!='\0'){crc^= *str;At(Bx i=0;i<8;++i){crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}str++;}X~crc;}Dn E6{V<T zT> Ae B Bj(zT&Jc,zT&diff){zT temp0=Jc,temp1=diff;Jc=temp0+temp1;diff=temp0-temp1;}Dn fft{Bd C3=Al;Bd C64=Ao::Ii<C3>;Bd As=D5;Bd F=Dp;V<T A0,H OMEGA_LEN> D4 K6{D7(64)A0 table[OMEGA_LEN*2];Gr: K6(H theta_divider,H Cp,H stride){J A0 Dh= -Ef*Cp/theta_divider;At(H Ak=0,Di=0;Ak<OMEGA_LEN*2;Ak+=stride*2){At(H j=0;j<stride;j++,Di++){table[Ak+j]=Ao::cos(Dh*Di);table[Ak+j+stride]=Ao::sin(Dh*Di);}}}Y J A0&Av[](H Di)J{X table[Di];}};B J6(C3*arr,H Ac,Bx H1,Bx Cp){H1/=4;J C3 Dh= -Ef*Cp/Ac;A6 arrx4=Ah<F*>(arr);arr[0]=1,arr[4]=0;arr[1]=Ao::cos(Dh),arr[5]=Ao::sin(Dh);arr[2]=Ao::cos(Dh*2),arr[6]=Ao::sin(Dh*2);arr[3]=Ao::cos(Dh*3),arr[7]=Ao::sin(Dh*3);At(H Ak=1;Ak<H1;Ak*=2){H nth=Ak*4;F unit;unit.set1(Ao::cos(Dh*nth),Ao::sin(Dh*nth));At(H i=0;i<Ak;i++){arrx4[Ak+i]=arrx4[i].Es(unit);}}}V<T A0,Bx Dr,Bx M1,Bx DIV> D4 Ff{Fg(M1>=Dr);Fg(is_2pow(DIV));E Y H TABLE_CPX_LEN=(H(1)<<(M1+1))/DIV;D7(64)A0 table[TABLE_CPX_LEN*2];Gr: Ff(H Cp,H stride=4){initBottomUp(Cp,stride);}B initBottomUp(H Cp,H stride){Fg(Ao::is_same<A0,Al>::value);H Bi=H(1)<<Dr,M4=Bi/DIV;A6 it=Gs(Dr);J6(it,Bi,M4,Cp);At(Bx Cn=Dr+1;Cn<=M1;Cn++){Bi=H(1)<<Cn,M4=Bi/DIV;A0 Dh= -Ef*Cp/Bi;A6 it=Gs(Cn),it_last=Gs(Cn-1);F unit(Ao::cos(Dh),Ao::sin(Dh));At(A6 Dy=it+M4*2;it<Dy;it+=16,it_last+=8){F J7,Mm;J7.Lo(it_last);Mm=J7.Es(unit);F2(J7.S,Mm.S);F2(J7.Q,Mm.Q);J7.Br(it),Mm.Br(it+8);}}}Y J A0*Gs(Bx K8)J{X Cg(H(1)<<K8);}Y A0*Gs(Bx K8){X Cg(H(1)<<K8);}Y J A0*Cg(H D)J{X&table[D*2/DIV];}Y A0*Cg(H D){X&table[D*2/DIV];}};V<Bx Fh> D4 Ds{Gr: Bd C3=Ai;Bd C64=Ao::Ii<Ai>;Bd F=Bu::Dp;E Y H Jp=H(1)<<Fh;E Y H MASK=Jp-1;E Y H C4_COUNT=B3(F)/B3(C64);~Ds(){if(Bp){E4[]Bp;}}Ds(){}Ds(H Ac,Bx M5,Bx Cp){init(Ac,M5,Cp);}B init(H Ac,Bx M5,Bx Cp){H H1=Ac/M5;H M6=Jp*C4_COUNT,high_len=H1/M6;if(Bp!=A5){E4[]Bp;}Bp=new C64[high_len];A6 p=Ah<C3*>(&Gk[0]);J6(p,Ac,M6,Cp);J C3 Dh= -Ef*Cp/Ac;Bp[0]=C64(1,0);At(H Ak=1;Ak<high_len;Ak*=2){C64 unit=Ao::polar<C3>(1.0,Dh*Ak*M6);At(H i=0;i<Ak;i++){Bp[i+Ak]=Bp[i]*unit;}}}F Av[](H i)J{F hi;A6 p=Ah<J C3*>(&Bp[i>>Fh]);hi.K5(p,p+1);X Gk[i&MASK].Es(hi);}Ho: D7(64)F Gk[Jp];C64*Bp=A5;};V<Bx DIV,Bx Dr,Bx Ij,Bx Fh> D4 Ji{Bd Jq=Ds<Fh>;E Y H Gy=H(1)<<Dr;E Y H TABLE_LEN=Ij-Dr+1;Gr: Ji(Bx Cp){At(Bx i=0;i<TABLE_LEN;i++){H Ac=Gy<<i;table[i].init(Ac,DIV,Cp);}}J Jq&Av[](Bx Cn)J{Cn-=Dr;X table[Cn];}Jq&Av[](Bx Cn){Cn-=Dr;X table[Cn];}Ho: Jq table[TABLE_LEN];};D1 FFT{V<T A0> E B trans2MulI(A0&r0,A0&i0,A0&r1,A0&i1){A6 Jj=r1;r1=r0+i1;r0=r0-i1;i1=i0-Jj;i0=i0+Jj;}V<T A0> E B trans2MulNegI(A0&r0,A0&i0,A0&r1,A0&i1){A6 Jj=r1;r1=r0-i1;r0=r0+i1;i1=i0+Jj;i0=i0-Jj;}V<T A0> E B dif4(A0&r0,A0&i0,A0&r1,A0&i1,A0&r2,A0&i2,A0&r3,A0&i3){K9(r0,i0,r1,i1,r2,i2,r3,i3);Bj(r0,r1);Bj(i0,i1);}V<T A0> E B idit4(A0&r0,A0&i0,A0&r1,A0&i1,A0&r2,A0&i2,A0&r3,A0&i3){Bj(r0,r1);Bj(i0,i1);Jr(r0,i0,r1,i1,r2,i2,r3,i3);}V<T A0> E B K9(A0&r0,A0&i0,A0&r1,A0&i1,A0&r2,A0&i2,A0&r3,A0&i3){Bj(r0,r2);Bj(i0,i2);Bj(r1,r3);Bj(i1,i3);trans2MulNegI(r2,i2,r3,i3);}V<T A0> E B Jr(A0&r0,A0&i0,A0&r1,A0&i1,A0&r2,A0&i2,A0&r3,A0&i3){Bj(r2,r3);Bj(i2,i3);Bj(r0,r2);Bj(i0,i2);trans2MulI(r1,i1,r3,i3);}};D1 A9:Gr FFT{E Y Bx Gz=7,J8=25-crc32(statement)%15,Ij=24,LOG_CACHE=8;E Y H Gy=H(1)<<Gz,J9=H(1)<<J8,MAX_LEN=H(1)<<Ij;Bd TableFix4=J K6<Al,4>;Bd TableFix8=J K6<Al,8>;Bd Ka=J Ff<Al,Gz+1,J8,4>;Bd Kb=J Ff<Al,6,Gz+1,4>;Bd Kc=J Ff<Al,6,Gz,4>;Bd TableSqrt=J Ji<4,J8+1,Ij,LOG_CACHE>;E TableFix4 table_8,Ls,Lt;E TableFix8 Lu,Lv;E Kb Ch;E Kc D8;E Ka G0;E TableSqrt Dx;E Y J Al*it8= &table_8[0],*it16_1= &Ls[0],*it16_3= &Lt[0],*Mn= &Lu[0],*Mo= &Lv[0];E B dif4x4(As&r0,As&i0,As&r1,As&i1,As&r2,As&i2,As&r3,As&i3){Cf(r0,r1,r2,r3);Cf(i0,i1,i2,i3);dif4(r0,i0,r1,i1,r2,i2,r3,i3);Cf(r0,r1,r2,r3);Cf(i0,i1,i2,i3);}E B idit4x4(As&r0,As&i0,As&r1,As&i1,As&r2,As&i2,As&r3,As&i3){Cf(r0,r1,r2,r3);Cf(i0,i1,i2,i3);idit4(r0,i0,r1,i1,r2,i2,r3,i3);Cf(r0,r1,r2,r3);Cf(i0,i1,i2,i3);}E B dif8x2(F&c0,F&c1,F&c2,F&c3){F B8(it8);Bj(c0,c1);Bj(c2,c3);c1=c1.Es(B8),c3=c3.Es(B8);dif4x4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);}E B idit8x2(F&c0,F&c1,F&c2,F&c3){F B8(it8);idit4x4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c1=c1.Cx(B8),c3=c3.Cx(B8);Bj(c0,c1);Bj(c2,c3);}E B dif16(Al in_out[]){A6 p=Ah<F*>(in_out);F c0=p[0],c1=p[1],c2=p[2],c3=p[3];dif4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c1=c1.Es(F(it8)),c2=c2.Es(F(it16_1)),c3=c3.Es(F(it16_3));dif4x4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}E B idit16(Al in_out[]){A6 p=Ah<F*>(in_out);F c0=p[0],c1=p[1],c2=p[2],c3=p[3],B8;idit4x4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c1=c1.Cx(F(it8)),c2=c2.Cx(F(it16_1)),c3=c3.Cx(F(it16_3));idit4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}E B dif32(Al in_out[]){A6 p=Ah<F*>(in_out);F c0=p[0],c1=p[2],c2=p[4],c3=p[6];K9(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c2=c2.Es(F(Mn)),c3=c3.Es(F(Mo));p[0]=c0,p[2]=c1,p[4]=c2,p[6]=c3;c0=p[1],c1=p[3],c2=p[5],c3=p[7];K9(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c2=c2.Es(F(Mn+8)),c3=c3.Es(F(Mo+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);}E B idit32(Al in_out[]){idit16(in_out);A6 p=Ah<F*>(in_out);F 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.Cx(F(Mn)),c2=c2.Cx(F(Mo));Jr(c1.S,c1.Q,c3.S,c3.Q,c0.S,c0.Q,c2.S,c2.Q);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.Cx(F(Mn+8)),c3=c3.Cx(F(Mo+8));Jr(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);p[1]=c0,p[3]=c1,p[5]=c2,p[7]=c3;}V<T F32,T F16> E B fftTiny(Al in_out[],H M,F32&&func32,F16&&func16){if(Cc(M/2)%2==0){At(A6 Dy=in_out+M;in_out<Dy;in_out+=32){func16(in_out);}}Ba{At(A6 Dy=in_out+M;in_out<Dy;in_out+=64){func32(in_out);}}}E B difIter(Al in_out[],H M){H Ac=M/2;F c0,c1,c2,c3;H stride=Ac/2;A6 Ey=in_out,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(H D=Ac;D>=64;D/=4){stride=D/2;At(A6 Ak=in_out,Dy=in_out+M;Ak<Dy;Ak+=D*2){A6 Bf=Ch.Cg(D*2),Fi=Ch.Cg(D),Cd=D8.Cg(D);Ey=Ak,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(;Ey<Ak+stride;Ey+=8,F3+=8,F4+=8,Hq+=8,Bf+=8,Fi+=8,Cd+=8){c0=Ey,c1=F3,c2=F4,c3=Hq;dif4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c1=c1.Es(F(Fi)),c2=c2.Es(F(Bf)),c3=c3.Es(F(Cd));c0.Br(Ey),c1.Br(F3),c2.Br(F4),c3.Br(Hq);}}}fftTiny(in_out,M,dif32,dif16);}V<H AP> E B tinyDif(Al in_out[]){H Ac=AP/2;if(Cc(Ac)%2==0){At(A6 Dy=in_out+AP;in_out<Dy;in_out+=32)dif16(in_out);}Ba{At(A6 Dy=in_out+AP;in_out<Dy;in_out+=64)dif32(in_out);}}V<H AP> E B tinyIdit(Al in_out[]){H Ac=AP/2;if(Cc(Ac)%2==0){At(A6 Dy=in_out+AP;in_out<Dy;in_out+=32)idit16(in_out);}Ba{At(A6 Dy=in_out+AP;in_out<Dy;in_out+=64)idit32(in_out);}}V<H AP> E B difIterC(Al in_out[]){H Ac=AP/2;F c0,c1,c2,c3;H stride=Ac/2;A6 Ey=in_out,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(H D=Ac;D>=64;D/=4){stride=D/2;At(A6 Ak=in_out,Dy=in_out+AP;Ak<Dy;Ak+=D*2){A6 Bf=Ch.Cg(D*2),Fi=Ch.Cg(D),Cd=D8.Cg(D);Ey=Ak,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(;Ey<Ak+stride;Ey+=8,F3+=8,F4+=8,Hq+=8,Bf+=8,Fi+=8,Cd+=8){c0=Ey,c1=F3,c2=F4,c3=Hq;dif4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c1=c1.Es(F(Fi)),c2=c2.Es(F(Bf)),c3=c3.Es(F(Cd));c0.Br(Ey),c1.Br(F3),c2.Br(F4),c3.Br(Hq);}}}tinyDif<AP>(in_out);}E B iditIter(Al in_out[],H M){H Ac=M/2;H D=Cc(Ac)%2==0?64:128;fftTiny(in_out,M,idit32,idit16);At(;D<=Ac;D*=4){J H stride=D/2;At(A6 Ak=in_out,Dy=in_out+M;Ak<Dy;Ak+=D*2){A6 Bf=Ch.Cg(D*2),Fi=Ch.Cg(D),Cd=D8.Cg(D);A6 Ey=Ak,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(;Ey<Ak+stride;Ey+=8,F3+=8,F4+=8,Hq+=8,Bf+=8,Fi+=8,Cd+=8){F c0=Ey,c1=F3,c2=F4,c3=Hq;c1=c1.Cx(F(Fi)),c2=c2.Cx(F(Bf)),c3=c3.Cx(F(Cd));idit4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c0.Br(Ey),c1.Br(F3),c2.Br(F4),c3.Br(Hq);}}}}V<H AP> E B iditIterC(Al in_out[]){H Ac=AP/2;H D=Cc(Ac)%2==0?64:128;tinyIdit<AP>(in_out);At(;D<=Ac;D*=4){J H stride=D/2;At(A6 Ak=in_out,Dy=in_out+AP;Ak<Dy;Ak+=D*2){A6 Bf=Ch.Cg(D*2),Fi=Ch.Cg(D),Cd=D8.Cg(D);A6 Ey=Ak,F3=Ey+stride,F4=F3+stride,Hq=F4+stride;At(;Ey<Ak+stride;Ey+=8,F3+=8,F4+=8,Hq+=8,Bf+=8,Fi+=8,Cd+=8){F c0=Ey,c1=F3,c2=F4,c3=Hq;c1=c1.Cx(F(Fi)),c2=c2.Cx(F(Bf)),c3=c3.Cx(F(Cd));idit4(c0.S,c0.Q,c1.S,c1.Q,c2.S,c2.Q,c3.S,c3.Q);c0.Br(Ey),c1.Br(F3),c2.Br(F4),c3.Br(Hq);}}}}
#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)
V<Bm Bh=C4> E B difRecMid(Al in_out[],H M){J H Ac=M/2;if(Ac<=Gy){if(M==128)difIterC<128>(in_out);Ba if(M==256)difIterC<256>(in_out);Ba difIter(in_out,M);X;}Bd FromRIRI=Ao::Cy<Bm,Bh>;A6 Bf=Ah<J F*>(G0.Cg(Ac));J H stride=M/4;difLayer(difRecMid,in_out,stride,Bf);}V<Bm Gc=C4,Bm I5=C4> E B Lw(Al in_out[],H M){J H Ac=M/2;if(Ac<=Gy){if(M==128)iditIterC<128>(in_out);Ba if(M==256)iditIterC<256>(in_out);Ba iditIter(in_out,M);X;}Bd ToRIRI=Ao::Cy<Bm,Gc>;Bd ToI64=Ao::Cy<Bm,I5>;J H stride=M/4;A6 Bf=Ah<J F*>(G0.Cg(Ac));iditLayer(Lw,in_out,stride,Bf);}E Ae As cv4(J C*a,H i,H la){if(i+4<=la)X Et(F5(Ah<J Cr*>(a+i)));X As(_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));}V<Bm Bh=C4> E B Fa(Al in_out[],H M){J H Ac=M/2;if(Ac<=J9){difRecMid<Bh>(in_out,M);X;}Bd FromRIRI=Ao::Cy<Bm,Bh>;J A6&Bf=Dx[Cc(Ac)];J H stride=M/4;difLayer(Fa,in_out,stride,Bf);}V<L Arms,Bm Bound,Bm Perm>E Ae B Gt(Al*d,J C*s,H la,H Bi,H Ak,H Dy){J H stride=Bi/4;J A6&t=Dx[Cc(Bi/2)];if Y(Arms==0){At(L k=0;k<4;k++)Ao::memset(d+k*stride+Ak,0,(Dy-Ak)*B3(Al));X;}At(H j=Ak;j<Dy;j+=8){F v[4];
#pragma GCC unroll 4
At(L k=0;k<Arms;k++){H at=k*stride+j;if Y(Bound){v[k].S=cv4(s,at,la);v[k].Q=cv4(s,at+4,la);}Ba{v[k].S=Et(F5((J Cr*)(s+at)));v[k].Q=Et(F5((J Cr*)(s+at+4)));}if Y(Perm)v[k]=v[k].H0();}dif4(v[0].S,v[0].Q,v[1].S,v[1].Q,v[2].S,v[2].Q,v[3].S,v[3].Q);F w=t[j/8],w2=w.Gj();v[2]=v[2].Es(w);v[1]=v[1].Es(w2);v[3]=v[3].Es(w.Hh(w2));
#pragma GCC unroll 4
At(L k=0;k<4;k++){if(Bi>=1048576u)v[k].Nt(d+k*stride+j);Ba v[k].Br(d+k*stride+j);}}}V<L Full,Bm Perm>E Ae B Dj(Al*d,J C*s,H la,H Bi){J H stride=Bi/4;if Y(Full==4){Gt<4,C4,Perm>(d,s,la,Bi,0,stride);}Ba{H rem=la-Full*stride,stop=rem&~H(7);Gt<Full+1,C4,Perm>(d,s,la,Bi,0,stop);if(rem!=stop){Gt<Full+1,Bt,Perm>(d,s,la,Bi,stop,stop+8);stop+=8;}Gt<Full,C4,Perm>(d,s,la,Bi,stop,stride);}}V<Bm Bh>E B difRecLongSrc(Al*d,J C*s,H la,H Bi){if(Bi<(H(1)<<21)){ar_src_onelevel<Bh>(d,s,la,Bi);X;}J H zQ=Bi/4,zS=Bi/16;Y H zB=32,zP=zB+8;D7(64)Al tile[16][zP];J A6&t0=Dx[Cc(Bi/2)];J A6&t1=Dx[Cc(zQ/2)];At(H at=0;at<zS;at+=zB){At(L Gk=0;Gk<4;Gk++)At(H j=0;j<zB;j+=8){H Co=Gk*zS+at+j;F v[4];
#pragma GCC unroll 4
At(L Bp=0;Bp<4;Bp++){H idx=Bp*zQ+Co;v[Bp].S=cv4(s,idx,la);v[Bp].Q=cv4(s,idx+4,la);if Y(Bh)v[Bp]=v[Bp].H0();}dif4(v[0].S,v[0].Q,v[1].S,v[1].Q,v[2].S,v[2].Q,v[3].S,v[3].Q);F w=t0[Co/8],w2=w.Gj();v[2]=v[2].Es(w);v[1]=v[1].Es(w2);v[3]=v[3].Es(w.Hh(w2));
#pragma GCC unroll 4
At(L Bp=0;Bp<4;Bp++)v[Bp].Br(tile[4*Bp+Gk]+j);}At(L Bp=0;Bp<4;Bp++)At(H j=0;j<zB;j+=8){F v0=tile[4*Bp]+j,v1=tile[4*Bp+1]+j,v2=tile[4*Bp+2]+j,v3=tile[4*Bp+3]+j;dif4(v0.S,v0.Q,v1.S,v1.Q,v2.S,v2.Q,v3.S,v3.Q);F w=t1[(at+j)/8],w2=w.Gj();v2=v2.Es(w);v1=v1.Es(w2);v3=v3.Es(w.Hh(w2));Al*Ck=d+Bp*zQ+at+j;v0.Nt(Ck);v1.Nt(Ck+zS);v2.Nt(Ck+2*zS);v3.Nt(Ck+3*zS);}}_mm_sfence();At(L k=0;k<16;k++)Fa(d+k*zS,zS);}V<Bm Bh>E B ar_src_onelevel(Al in_out[],J C*src,H la,H M){J H stride=M/4;switch(la/stride){Gl 0:Dj<0,Bh>(in_out,src,la,M);Cz;Gl 1:Dj<1,Bh>(in_out,src,la,M);Cz;Gl 2:Dj<2,Bh>(in_out,src,la,M);Cz;Gl 3:Dj<3,Bh>(in_out,src,la,M);Cz;Nh:Dj<4,Bh>(in_out,src,la,M);}if(M>=1048576u)_mm_sfence();At(L k=0;k<4;k++)Fa(in_out+k*stride,stride);}V<Bm Gc=C4,Bm I5=C4> E B B9(Al in_out[],H M){J H Ac=M/2;if(Ac<=J9){Lw<Gc,I5>(in_out,M);X;}Bd ToRIRI=Ao::Cy<Bm,Gc>;Bd ToI64=Ao::Cy<Bm,I5>;J H stride=M/4;J A6&Bf=Dx[Cc(Ac)];iditLayer(B9,in_out,stride,Bf);}};
#undef difLayer
#undef iditLayer
Y Bx A9::Gz,A9::J8,A9::Ij,A9::LOG_CACHE;Y H A9::Gy,A9::J9,A9::MAX_LEN;A9::TableFix4 A9::table_8(8,1,4),A9::Ls(16,1,4),A9::Lt(16,3,4);A9::TableFix8 A9::Lu(32,1,4),A9::Lv(32,3,4);A9::Kb A9::Ch(2);A9::Kc A9::D8(3);A9::Ka A9::G0(1);A9::TableSqrt A9::Dx(1);Y C bitrev32(C n){Y C mask55=0x55555555;Y C mask33=0x33333333;Y C mask0f=0x0f0f0f0f;Y C 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);X(n<<16)|(n>>16);}Y C bitrev(C n,Bx Bi){X bitrev32(n)>>(32-Bi);}V<Bx Dt,Bx DIV> D4 Df{Gr: E Y Bx LOG_BLOCK=2,Lb=1<<LOG_BLOCK;E Y H MAX_LEN=H(1)<<Dt;D1 Unit{C64 units[Dt]{};C3 Lc[Lb*2]{};Unit(){Y C3 Cp=C3(1)/DIV;At(Bx i=0;i<Dt;i++){units[i]=getOmega(H(1)<<(i+1),1,Cp);}Lc[0]=1,Lc[Lb]=0;At(Bx i=1;i<Lb;i++){C64 B8=getOmega(Lb,bitrev(i,LOG_BLOCK),Cp);Lc[i]=B8.S(),Lc[i+Lb]=B8.Q();}}};Df():Di(0),pop(0){Ao::memcpy(table,Gf.Lc,B3(Gf.Lc));}B reset(H i=0){if(i==0){pop=0,Di=i;X;}pop=1,Di=i/Lb;Bx Dd=__builtin_ctzll(Di);A6 fp=Ah<J C3*>(&Gf.units[Dd+2]);table[1].K5(fp,fp+1);table[1]=table[1].Es(table[0]);}F iterate(){F Fe=table[pop],unit4;Di++;Bx Dd=__builtin_ctzll(Di);A6 fp=Ah<J C3*>(&Gf.units[Dd+2]);unit4.K5(fp,fp+1);pop-=Dd;table[pop+1]=table[pop].Es(unit4);pop++;X Fe;}E C64 getOmega(H n,H Di,C3 Cp=1){C3 Dh= -Ef*Di/n;X Ao::polar<C3>(1,Dh*Cp);}Ho: D7(64)E J Unit Gf;D7(64)F table[Dt];H Di;Bx pop;Bx log_max_iter,log_fft_len;};V<Bx Dt,Bx DIV> J T Df<Dt,DIV>::Unit Df<Dt,DIV>::Gf;V<H Gg=1,T Fj,Bm AC=0> Ae B Le(Fj*I6,Fj*I7,J Fj*in0,J Fj*Hi,J Ao::Ii<Fj> &B8,J Fj Hd,Fj*d0,Fj*d1){Bd Z=Ao::Ii<Fj>;A6 G1=[](Z c0,Z c1){X Z(c0.S()+c1.S(),c0.Q()-c1.Q());};Z x0(I6[0],I6[Gg]),x1(I7[0],I7[Gg]),y0(in0[0],in0[Gg]),y1(Hi[0],Hi[Gg]);A6 t0=x0*y0,t1=x1*y1,xy0=G1(x0,x1),xy1=G1(y0,y1);A6 t2=xy0*xy1;y1=G1(t0,t1);x1=(y1+y1-t2)*B8*B8;J A6 inv2=Hd+Hd;x0=(t2-x1)*Hd,x1=Z(t0.S()-t1.S(),t0.Q()+t1.Q())*inv2;Z out0=x0+x1,out1(x0.S()-x1.S(),x1.Q()-x0.Q());if(AC){d0[0]+=out0.S(),d0[Gg]+=out0.Q();d1[0]+=out1.S(),d1[Gg]+=out1.Q();}Ba{I6[0]=out0.S(),I6[Gg]=out0.Q();I7[0]=out1.S(),I7[Gg]=out1.Q();}}V<Bm AC=0> Ae B dot_rfftX4(C3*dt0,C3*dt1,C3*I6,C3*I7,J C3*in0,J C3*Hi,J F&B8,J As&Hd){A6 G1=[](J F&x0,J F&x1){X F(x0.S+x1.S,x0.Q-x1.Q);};F x0=I6,x1=I7,y0=in0,y1=Hi;x1=x1.Gx();y1=y1.Gx();F t0=x0.Es(y0),t1=x1.Es(y1);F xy0=G1(x0,x1),xy1=G1(y0,y1);F t2=xy0.Es(xy1);y1=G1(t0,t1);x1=(y1+y1-t2).Es(B8);J As inv2=Hd+Hd;x0=(t2-x1)*Hd,x1=F(t0.S-t1.S,t0.Q+t1.Q)*inv2;F out0=x0+x1,out1(x0.S-x1.S,x1.Q-x0.Q);if(AC){F r0=dt0,r1=dt1;r0=r0+out0;r1=r1+out1.Gx();r0.Br(dt0);r1.Br(dt1);}Ba out0.Br(dt0),out1.Gx().Br(dt1);}V<Bm AC> Ae B G2(Al dst[],Al in_out[],Al in[],H M){Al*o=AC?dst:in_out;Al Hd=2.0/M;{A6 r0=in_out[0],i0=in_out[4],r1=in[0],i1=in[4];Bj(r0,i0);Bj(r1,i1);r0*=r1,i0*=i1;Bj(r0,i0);if(AC)o[0]+=r0*0.5*Hd,o[4]+=i0*0.5*Hd;Ba o[0]=r0*0.5*Hd,o[4]=i0*0.5*Hd;}A6 Jj=C64(in_out[1],in_out[5])*C64(in[1],in[5])*Hd;if(AC)o[1]+=Jj.S(),o[5]+=Jj.Q();Ba o[1]=Jj.S(),o[5]=Jj.Q();Hd/=4;Le<4,Al,AC>(in_out+2,in_out+3,in+2,in+3,C64(COS_PI_8,-COS_PI_8),Hd,o+2,o+3);Y Al COS_16_1=0.92387953251128675612818318939;Y Al SIN_16_1=0.38268343236508977172845998403;Le<4,Al,AC>(in_out+8,in_out+11,in+8,in+11,C64(COS_16_1,-SIN_16_1),Hd,o+8,o+11);Le<4,Al,AC>(in_out+9,in_out+10,in+9,in+10,C64(-SIN_16_1,-COS_16_1),Hd,o+9,o+10);J D5 inv4=As(0.5/M);Df<28,1>table;At(H Ak=16;Ak<M;Ak*=2){table.reset(Ak/2);A6 Ey=in_out+Ak,F3=Ey+Ak-8,F4=in+Ak,Hq=F4+Ak-8,ot0=o+Ak,ot1=ot0+Ak-8;At(;Ey<F3;Ey+=8,F3-=8,F4+=8,Hq-=8,ot0+=8,ot1-=8){dot_rfftX4<AC>(ot0,ot1,Ey,F3,F4,Hq,table.iterate(),inv4);}}}Ae B B0(Al in_out[],Al in[],H M){G2<0>(in_out,in_out,in,M);}Ae B real_dot_accum(Al dst[],Al in_out[],Al in[],H M){G2<1>(dst,in_out,in,M);}V<Bm TO_INT=C4> Ae B real_conv_avx(C3*Nl,C3*in2,H M){A9::Fa<Bt>(Nl,M);A9::Fa<Bt>(in2,M);B0(Nl,in2,M);A9::B9<Bt,TO_INT>(Nl,M);}}}} /*
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.
*/
#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")
Bd Z=Ao::Ii<Ai>;D1 An{A2 P;An(){P=Gw();}An(Ai K){P=Cq(K);}An(A2 K){P=K;}An(J An&K){P=K.P;}An(Ai J*Hg){P=ar_pdload(Hg);}An(Z a){P=_mm256_broadcast_pd((__m128d*)&a);}An(J Z*Hg){P=ar_pdload((J Ai*)Hg);}B clr(){P=Gw();}B Br(Z*a)J{ar_pdstore((Ai*)a,P);}V<Bx zM> An Hr()J{X _mm256_permute_pd(P,zM);}An all_real()J{X _mm256_movedup_pd(P);}An all_imag()J{X Hr<0XF>();}An Ik()J{X Hr<0X5>();}An mul_neg_i()J{E J A2 subber{};X An(_mm256_addsub_pd(subber,P)).Ik();}An Av+(An K)J{X _mm256_add_pd(P,K.P);}An Av-(An K)J{X Fd(P,K.P);}An Av*(An K)J{A6 Q=Cw(all_imag().P,K.Ik().P);X _mm256_fmaddsub_pd(all_real().P,K.P,Q);}An Av/(An K)J{X _mm256_div_pd(P,K.P);}};
#endif
Dn hint{Bd UINT_8=uint8_t;Bd UINT_16=uint16_t;Bd D9=C;Bd Bb=O;Bd I8=int32_t;Bd Kh=int64_t;Bd LONG=Fy;Bd Z=Ao::Ii<Ai>;Y Ai Mx=3.1415926535897932384626433832795;Y Ai Ef=Mx*2;V<T zT> Y zT min_2pow(zT n){zT Fe=1;A3(Fe<n){Fe*=2;}X Fe;}V<T zT> Ae B ary_clr(zT*Hg,H Bi){Il(Hg,0,Bi*B3(zT));}V<T zT> Y Bm is_neg(zT x){X x<0;}V<T zT> Y H Cc(zT n){zT Fe=0;A3(n>1){n/=2;Fe++;}X Fe;}V<T zT> Y Bm is_odd(zT x){X C6<Bm>(x&1);}V<T zT> Y Ao::pair<zT,zT>div_mod(zT a,zT b){X Ao::make_pair(a/b,a%b);}V<T zT> B Eg(zT*I9,J zT*source,H Bi){if(Bi==0||I9==source){X;}if(Bi>=INT64_MAX){H2("Ary too long\n");}Ao::memcpy(I9,source,Bi*B3(zT));}V<T zT> Ae zT*ary_realloc(zT*Hg,H Bi){if(Bi*B3(zT)<INT64_MAX){Hg=C6<zT*>(realloc(Hg,Bi*B3(zT)));}if(Hg==A5){H2("realloc error");}X Hg;}V<T zT> Y zT max_2pow(zT n){zT Fe=1;Fe<<=(B3(zT)*8-1);A3(Fe>n){Fe/=2;}X Fe;}Y Bb qpow(Bb m,Bb n,Bb mod){if(m<=1){X m;}Bb Gd=1;A3(n>0){if((n&1)!=0){Gd=Gd*m%mod;}m=m*m%mod;n>>=1;}X Gd;}Y Bb mod_inv(Bb n,Bb mod){X qpow(n,mod-2,mod);}V<T zT> Ae B com_ary_combine_copy(Z*I9,J zT&source1,H Au,J zT&source2,H Ay){H min_len=Ao::min(Au,Ay);H i=0;A3(i<min_len){I9[i]=Z(source1[i],source2[i]);i++;}A3(i<Au){I9[i].S(source1[i]);i++;}A3(i<Ay){I9[i].Q(source2[i]);i++;}}Dn hint_transform{D4 C0{Ho: Ao::Fk<Ao::Fk<Z>>Bf;Ao::Fk<Ao::Fk<Z>>Cd;I8 Jk=2;I8 Hj=2;E Y H FAC=1;C0(J C0&)=E4;C0&Av=(J C0&)=E4;Gr: ~C0(){}C0(D9 F6){F6=Ao::max<H>(F6,1);Jk=F6;Bf.Bn(F6+1);Cd.Bn(F6+1);Bf[0]=Bf[1]=Cd[0]=Cd[1]=Ao::Fk<Z>{1};Bf[2]=Cd[2]=Ao::Fk<Z>{1};
#if TABLE_PRELOAD == 1
expand(F6);
#endif
}B expand(I8 Aw){Aw=Ao::max<I8>(Aw,2);if(Aw>Jk){H2("FFT length too long for lut\n");}At(I8 i=Hj+1;i<=Aw;i++){H Bi=1ull<<i,Eh=Bi*FAC/4;Bf[i].Bn(Eh);Cd[i].Bn(Eh);Bf[i][0]=Cd[i][0]=Z(1,0);At(H Co=0;Co<Eh/2;Co++){Bf[i][Co*2]=Bf[i-1][Co];Cd[i][Co*2]=Cd[i-1][Co];}At(H Co=1;Co<Eh/2;Co+=2){Ai cos_theta=Ao::cos(Ef*Co/Bi);Ai sin_theta=Ao::sin(Ef*Co/Bi);Bf[i][Co]=Z(cos_theta,-sin_theta);Bf[i][Eh-Co]=Z(sin_theta,-cos_theta);}Bf[i][Eh/2]=Ao::conj(H3(8,1));At(H Co=1;Co<Eh/2;Co+=2){Z Im=get_omega(i,Co*3);Cd[i][Co]=Im;Cd[i][Eh-Co]=Z(Im.Q(),Im.S());}Cd[i][Eh/2]=Ao::conj(H3(8,3));}Hj=Ao::max(Hj,Aw);}E Z H3(Ai Dh){X Ao::polar<Ai>(1.0,Dh);}E Z H3(H m,H n){X H3((Ef*n)/m);}Z get_omega(D9 Aw,H n)J{H D=1ull<<Aw;J H rank_ff=D-1,quad_n=n<<2;H zone=quad_n>>Aw;if((quad_n&rank_ff)==0){E Y Z ONES[4]={Z(1,0),Z(0,-1),Z(-1,0),Z(0,1)};X ONES[zone];}Z Im;if((zone&2)==0){if((zone&1)==0){Im=Bf[Aw][n];}Ba{Im=Bf[Aw][D/2-n];Im.S(-Im.S());}}Ba{if((zone&1)==0){Im= -Bf[Aw][n-D/2];}Ba{Im=Bf[Aw][D-n];Im.Q(-Im.Q());}}X Im;}Z get_omega3(D9 Aw,H n)J{X Cd[Aw][n];}An Ki(D9 Aw,H n)J{X An(Bf[Aw].P()+n);}An Jl(D9 Aw,H n)J{X An(Cd[Aw].P()+n);}};Y H lut_max_rank=23;E C0 Lf(lut_max_rank);V<T zT> B Gh(zT&ary,H Bi){H i=0;At(H j=1;j<Bi-1;j++){H k=Bi>>1;i^=k;A3(k>i){k>>=1;i^=k;};if(j<i){Ao::Ik(ary[i],ary[j]);}}}V<T Hs=D9,T zT> B quaternary_reverse_swap(zT&ary,H Bi){Hs log_n=Cc(Bi);Hs*rev=new Hs[Bi/4];rev[0]=0;At(Hs i=1;i<Bi;i++){Hs Di=(rev[i>>2]>>2)|((i&3)<<(log_n-2));if(i<Bi/4){rev[i]=Di;}if(i<Di){Ao::Ik(ary[i],ary[Di]);}}E4[]rev;}V<T zT> Ae B Ag(zT&Jc,zT&diff){zT Bv=Jc;zT Bw=diff;Jc=Bv+Bw;diff=Bv-Bw;}Ae B fft_4point(Z*K,H D=1){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Ag(Bv,Cb);Ag(Bw,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Bw;K[D]=Cb+A1;K[D*2]=Bv-Bw;K[D*3]=Cb-A1;}Ae B fft_dit_4point(Z*K,H D=1){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Ag(Bv,Bw);Ag(Cb,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Cb;K[D]=Bw+A1;K[D*2]=Bv-Cb;K[D*3]=Bw-A1;}Ae B fft_dit_8point(Z*K,H D=1){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Z Kj=K[D*4];Z Fl=K[D*5];Z G3=K[D*6];Z Dw=K[D*7];Ag(Bv,Bw);Ag(Cb,A1);Ag(Kj,Fl);Ag(G3,Dw);A1=Z(A1.Q(),-A1.S());Dw=Z(Dw.Q(),-Dw.S());Ag(Bv,Cb);Ag(Bw,A1);Ag(Kj,G3);Ag(Fl,Dw);E Y Ai Io=Ez;Fl=Io*Z(Fl.Q()+Fl.S(),Fl.Q()-Fl.S());G3=Z(G3.Q(),-G3.S());Dw= -Io*Z(Dw.S()-Dw.Q(),Dw.S()+Dw.Q());K[0]=Bv+Kj;K[D]=Bw+Fl;K[D*2]=Cb+G3;K[D*3]=A1+Dw;K[D*4]=Bv-Kj;K[D*5]=Bw-Fl;K[D*6]=Cb-G3;K[D*7]=A1-Dw;}Ae B fft_dif_4point(Z*K,H D=1){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Ag(Bv,Cb);Ag(Bw,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Bw;K[D]=Bv-Bw;K[D*2]=Cb+A1;K[D*3]=Cb-A1;}Ae B fft_dif_8point(Z*K,H D=1){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Z Kj=K[D*4];Z Fl=K[D*5];Z G3=K[D*6];Z Dw=K[D*7];Ag(Bv,Kj);Ag(Bw,Fl);Ag(Cb,G3);Ag(A1,Dw);E Y Ai Io=Ez;Fl=Io*Z(Fl.Q()+Fl.S(),Fl.Q()-Fl.S());G3=Z(G3.Q(),-G3.S());Dw= -Io*Z(Dw.S()-Dw.Q(),Dw.S()+Dw.Q());Ag(Bv,Cb);Ag(Bw,A1);Ag(Kj,G3);Ag(Fl,Dw);A1=Z(A1.Q(),-A1.S());Dw=Z(Dw.Q(),-Dw.S());K[0]=Bv+Bw;K[D]=Bv-Bw;K[D*2]=Cb+A1;K[D*3]=Cb-A1;K[D*4]=Kj+Fl;K[D*5]=Kj-Fl;K[D*6]=G3+Dw;K[D*7]=G3-Dw;}Ae B fft_radix2_dit_butterfly(Z B8,Z*K,H D){Z Bv=K[0];Z Bw=K[D]*B8;K[0]=Bv+Bw;K[D]=Bv-Bw;}Ae B fft_radix2_dif_butterfly(Z B8,Z*K,H D){Z Bv=K[0];Z Bw=K[D];K[0]=Bv+Bw;K[D]=(Bv-Bw)*B8;}Ae B Dk(Z B8,Z B4,Z*K,H D){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2]*B8;Z A1=K[D*3]*B4;Ag(Cb,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Cb;K[D]=Bw+A1;K[D*2]=Bv-Cb;K[D*3]=Bw-A1;}Ae B Dl(Z B8,Z B4,Z*K,H D){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Ag(Bv,Cb);Ag(Bw,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv;K[D]=Bw;K[D*2]=(Cb+A1)*B8;K[D*3]=(Cb-A1)*B4;}Ae B Dk(An B8,An B4,Z*K,H D){An Bv=K;An Bw=K+D;An Cb=An(K+D*2)*B8;An A1=An(K+D*3)*B4;Ag(Cb,A1);A1=A1.mul_neg_i();(Bv+Cb).Br(K);(Bw+A1).Br(K+D);(Bv-Cb).Br(K+D*2);(Bw-A1).Br(K+D*3);}Ae B Dl(An B8,An B4,Z*K,H D){An Bv=(K);An Bw=(K+D);An Cb=(K+D*2);An A1=(K+D*3);Ag(Bv,Cb);Ag(Bw,A1);A1=A1.mul_neg_i();Bv.Br(K);Bw.Br(K+D);((Cb+A1)*B8).Br(K+D*2);((Cb-A1)*B4).Br(K+D*3);}Ae B fft_radix4_dit_butterfly(Z B8,Z Jt,Z B4,Z*K,H D){Z Bv=K[0];Z Bw=K[D]*B8;Z Cb=K[D*2]*Jt;Z A1=K[D*3]*B4;Ag(Bv,Cb);Ag(Bw,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Bw;K[D]=Cb+A1;K[D*2]=Bv-Bw;K[D*3]=Cb-A1;}Ae B fft_radix4_dif_butterfly(Z B8,Z Jt,Z B4,Z*K,H D){Z Bv=K[0];Z Bw=K[D];Z Cb=K[D*2];Z A1=K[D*3];Ag(Bv,Cb);Ag(Bw,A1);A1=Z(A1.Q(),-A1.S());K[0]=Bv+Bw;K[D]=(Cb+A1)*B8;K[D*2]=(Bv-Bw)*Jt;K[D*3]=(Cb-A1)*B4;}Ae B fft_conj(Z*K,H Ac,Ai div=1){At(H i=0;i<Ac;i++){K[i]=Ao::conj(K[i])/div;}}Ae B fft_normalize(Z*K,H Ac){Ai Bi=C6<Ai>(Ac);At(H i=0;i<Ac;i++){K[i]/=Bi;}}V<H Ip> B Aq(Z*K){Y H Cn=Cc(Ip);Y H F7=Ip/2,Ci=Ip/4;Aq<F7>(K);Aq<Ci>(K+F7);Aq<Ci>(K+F7+Ci);At(H i=0;i<Ci;i+=2){A6 B8=Lf.Ki(Cn,i);A6 B4=Lf.Jl(Cn,i);Dk(B8,B4,K+i,Ci);}}V<> B Aq<0>(Z*K){}V<> B Aq<1>(Z*K){}V<> B Aq<2>(Z*K){Ag(K[0],K[1]);}V<> B Aq<4>(Z*K){fft_dit_4point(K,1);}V<> B Aq<8>(Z*K){fft_dit_8point(K,1);}V<H Ip> B Ar(Z*K){Y H Cn=Cc(Ip);Y H F7=Ip/2,Ci=Ip/4;At(H i=0;i<Ci;i+=2){A6 B8=Lf.Ki(Cn,i);A6 B4=Lf.Jl(Cn,i);Dl(B8,B4,K+i,Ci);}Ar<F7>(K);Ar<Ci>(K+F7);Ar<Ci>(K+F7+Ci);}V<> B Ar<0>(Z*K){}V<> B Ar<1>(Z*K){}V<> B Ar<2>(Z*K){Ag(K[0],K[1]);}V<> B Ar<4>(Z*K){fft_dif_4point(K,1);}V<> B Ar<8>(Z*K){fft_dif_8point(K,1);}V<H Ip=1> B Fm(Z*K,H Ac){if(Ac>Ip){Fm<Ip*2>(K,Ac);X;}Lf.expand(Cc(Ip));Aq<Ip>(K);}V<> B Fm<1<<24>(Z*K,H Ac){}V<H Ip=1> B Fn(Z*K,H Ac){if(Ac>Ip){Fn<Ip*2>(K,Ac);X;}Lf.expand(Cc(Ip));Ar<Ip>(K);}V<> B Fn<1<<24>(Z*K,H Ac){}Ae B fft_dit(Z*K,H Ac,Bm Np=Bt){Ac=max_2pow(Ac);if(Np){Gh(K,Ac);}Fm<1>(K,Ac);}Ae B fft_dif(Z*K,H Ac,Bm Np=Bt){Ac=max_2pow(Ac);Fn<1>(K,Ac);if(Np){Gh(K,Ac);}}}V<Bb A8,T zT> Y B save_num_to_ary(zT ary[],Bb num,H digit){H i=digit;A3(i>0){i--;ary[i]=num%A8;num/=A8;}}Bb stoui64(J Ao::H4::const_iterator&Ak,J Ao::H4::const_iterator&Dy,J D9 Gm=10){Bb Gd=0;At(A6 it=Ak;it<Dy&&it-Ak<19;++it){Gd*=Gm;J4 c=tolower(*it);Bb n=0;if(isalnum(c)){if(isalpha(c)){n=c-'a'+10;}Ba{n=c-'0';}}if(n<Gm){Gd+=n;}}X Gd;}Bb stoui64(J Ao::H4&str,J D9 Gm=10){X stoui64(str.Ak(),str.Dy(),Gm);}Ao::H4 ui64to_string(Bb K,UINT_8 Bs){Ao::H4 Gd(Bs,'0');At(UINT_8 i=0;i<Bs;i++){Gd[Bs-i-1]=C6<J4>(K%10+'0');K/=10;}X Gd;}V<T zT=D9,T Af=D9> D4 B5{Ho: zT*Az=A5;Af Ea=0;Af Aa=0;Gr: ~B5(){if(Az!=A5){E4[]Az;Az=A5;}}B5(){Az=A5;}B5(Af F8){if(F8>0){Bn(F8);}}B5(Af F8,zT ele){if(F8>0){Bn(F8);Bc(F8);fill_element(ele,F8);}}B5(J zT*ary,Af Bi){if(ary==A5){H2("Can't copy from nullptr\n");}if(Bi>0){Bn(Bi);Bc(Bi);Eg(Az,ary,Bi);}}B5(J B5&K){if(K.Az!=A5){if(Az!=A5){E4[]Az;}Az=A5;H Bi=K.E5();Bn(Bi);Bc(Bi);Fo(K.sign());Eg(Az,K.Az,Bi);}}B5(B5&&K){if(K.Az!=A5){Aa=K.Aa;Bc(K.E5());Fo(K.sign());if(Az!=A5){E4[]Az;}Az=K.Az;K.Az=A5;}}B5&Av=(J B5&K){if(En!= &K){if(Az!=A5){E4[]Az;}Az=A5;H Bi=K.E5();Bn(Bi);Bc(Bi);Fo(K.sign());Eg(Az,K.Az,Bi);}X*En;}B5&Av=(B5&&K){if(En!= &K){Aa=K.Aa;Bc(K.E5());Fo(K.sign());if(Az!=A5){E4[]Az;}Az=K.Az;K.Az=A5;}X*En;}zT&Av[](Af Di)J{X Az[Di];}zT*P()J{X Az;}E Af size_generator(Af C5){Y Af Ce=B3(Af)*8;Y Af E0=(1ull<<(Ce-1));Y Af G4=E0-1;C5=Ao::min<Af>(C5,G4);if(C5<=2){X 2;}Ba if(C5<=4){X 4;}Af size1=min_2pow(C5);Af Nq=size1/2;Nq=Nq+Nq/2;if(C5<=Nq){X Nq;}Ba{X size1;}}Af E5()J{Y Af Ce=B3(Af)*8;Y Af E0=(1ull<<(Ce-1));Y Af G4=E0-1;X Ea&G4;}Bm sign()J{Y Af Ce=B3(Af)*8;Y Af E0=(1ull<<(Ce-1));X(E0&Ea)!=0;}Y B Bn(Af C5,Af(size_func)(Af)=size_generator){C5=size_func(C5);if(Az==A5){Aa=C5;Az=new zT[Aa];Bc(0);}Ba if(Aa!=C5){Aa=C5;Az=ary_realloc(Az,Aa);Bc(E5());}}B Bc(Af He){Y Af Ce=B3(Af)*8;Y Af E0=(1ull<<(Ce-1));Y Af G4=E0-1;if(He>G4){H2("Length too long\n");}He=Ao::min(He,Aa);Bm sign_tmp=sign();Ea=He;Fo(sign_tmp);}B Fo(Bm is_sign){Y Af Ce=B3(Af)*8;Y Af E0=(1ull<<(Ce-1));Y Af G4=E0-1;if((!is_sign)||E5()==0){Ea=Ea&G4;}Ba{Ea=Ea|E0;}}Af Bq(){if(Az==A5){X 0;}Af t_len=E5();A3(t_len>0&&Az[t_len-1]==0){t_len--;}Bc(t_len);X E5();}B fill_element(zT ele,Af Iq,Af Ak=0){if(Ak>=Aa||Az==A5){X;}if(Ak+Iq>=Aa){Iq=Aa-Ak;}Ao::fill(Az+Ak,Az+Ak+Iq,ele);}};}Dn Bk{Bd Dn hint;Bd Af=D9;V<T zT> Bd C7=B5<zT,Af>;V<T zT> Y H B7(J zT&ary,H Bi){A3(Bi>0&&ary[Bi-1]==0){Bi--;}X Bi;}V<T zT> Y I8 C8(J zT ary1[],J zT ary2[],H Au,H Ay){Au=B7(ary1,Au);Ay=B7(ary2,Ay);if(Au!=Ay){X Au>Ay?1: -1;}if(ary1==ary2){X 0;}A3(Au>0){Au--;zT num1=ary1[Au],num2=ary2[Au];if(num1!=num2){X num1>num2?1: -1;}}X 0;}V<Bb A8,Bm Lg=Bt,T zT> Y B Fp(J zT in[],zT num,zT Ck[],H Bi){Bi=B7(in,Bi);num%=A8;Bb H8=0;if(num==1){Eg(Ck,in,Bi);}Ba{At(H i=0;i<Bi;i++){H8+=C6<Bb>(in[i])*num;Ao::tie(H8,Ck[i])=div_mod<Bb>(H8,A8);}}if(Lg){Ck[Bi]=H8;}}V<Bb A8,T zT> Y Kh Kl(J zT in[],zT num,zT Ck[],H Bi){H Co=B7(in,Bi);num%=A8;if(num==1){Eg(Ck,in,Bi);X 0;}Bb Ht=0;A3(Co>0){Co--;Ht=Ht*A8+in[Co];Ao::tie(Ck[Co],Ht)=div_mod<Bb>(Ht,num);}X Ht;}V<Kh A8,Bm Lg=Bt,T zT> Y B Nr(J zT Hi[],J zT in2[],zT Ck[],H Au,H Ay){if(Au<Ay){Ao::Ik(Hi,in2);Ao::Ik(Au,Ay);}H Co=0;Bb W=0;A3(Co<Ay){W+=(Hi[Co]+in2[Co]);Ck[Co]=W<A8?W:W-A8;W=W<A8?0:1;Co++;}A3(Co<Au&&W>0){W+=Hi[Co];Ck[Co]=W<A8?W:W-A8;W=W<A8?0:1;Co++;}Eg(Ck+Co,Hi+Co,Au-Co);if(Lg){Ck[Au]=W%A8;}}V<Kh A8,T zT> Y B G5(J zT Hi[],J zT in2[],zT Ck[],H Au,H Ay){if(Au<Ay){X;}H Co=0;Kh Du=0;A3(Co<Ay){Du+=(C6<Kh>(Hi[Co])-in2[Co]);Ck[Co]=Du<0?Du+A8:Du;;Du=Du<0?-1:0;Co++;}A3(Co<Au&&Du<0){Du+=Hi[Co];Ck[Co]=Du<0?Du+A8:Du;Du=Du<0?-1:0;Co++;}Eg(Ck+Co,Hi+Co,Au-Co);}V<D4 IVT>E Ae B iv667load(Ai*d,J IVT*s,H n){if Y(Ao::is_same<IVT,C>::value){H i=0;At(;i+4<=n;i+=4){Cr x=F5((J Cr*)(s+i));ar_pdstore(d+i,Et(x));}At(;i<n;i++)d[i]=(Ai)s[i];}Ba At(H i=0;i<n;i++)d[i]=(Ai)s[i];}V<D4 IVT>E Ae B Ei(Ai*d,J IVT*a,H la,H n){Bd Bu::E6::fft::A9;if Y(Ao::is_same<IVT,C>::value){if(n/2>A9::J9){A9::difRecLongSrc<Bt>(d,Ah<J C*>(a),la,n);X;}}iv667load(d,a,la);::Il(d+la,0,(n-la)*B3(Ai));A9::Fa<Bt>(d,n);}E Ae Cr Ge(Ad raw,Cr&prev1,Cr&prev2,Cr&prev3){J A2 bias=Cq(4503599627370496.0),Gm=Cq(10000.0),Hd=Cq(0.0001);A2 x=_mm256_castsi256_pd(raw);A2 q1=Ee(Cw(x,Hd));A2 q2=Ee(Cw(x,Cq(1e-8)));A2 q3=Ee(Cw(x,Cq(1e-12)));Cr r0=Eb(Fd(x,Cw(q1,Gm)));Cr r1=Eb(Fd(q1,Cw(q2,Gm)));Cr r2=Eb(Fd(q2,Cw(q3,Gm)));Cr r3=Eb(q3);Cr Jc=Ir(r0,Hu(r1,prev1,12));Jc=Ir(Jc,Hu(r2,prev2,8));Jc=Ir(Jc,Hu(r3,prev3,4));prev1=r1;prev2=r2;prev3=r3;X Jc;}E Ae Ad zzld(J B*p){Ad v;asm("vmovdqu %1,%0":"=x"(v):"m"(*(J Ad*)p));X v;}E Ae B zzst(B*p,Ad v){asm volatile("vmovdqu %0,%1"::"x"(v),"m"(*(Ad*)p));}E B Lh(J L Fy Fy*c,L*Ck,H Iq){Cr p1=_mm_setzero_si128(),p2=p1,p3=p1;J Ad Dd=C2(),Gm=N(Ab),one=N(1);J Ad c9999=N(9999),c19=N(19999),c29=N(29999),idx1=Ap(0,0,1,2,3,4,5,6),idx2=Ap(0,0,0,1,2,3,4,5),idx4=Ap(0,0,0,0,0,1,2,3),m1=Ap(0,-1,-1,-1,-1,-1,-1,-1),m2=Ap(0,0,-1,-1,-1,-1,-1,-1),m4=Ap(0,0,0,0,-1,-1,-1,-1),idx7=N(7);Ad cv=Dd;H i=0;A6 normalize=[&](Ad s,L*dest){Ad q=E7(Gn(s,G6(6711)),10);Ad prior=_mm256_alignr_epi8(q,_mm256_permute2x128_si256(cv,q,0x21),12);Ad y=A7(B1(s,Go(q,Gm)),prior);Ad gt=Eu(y,c9999);if(Ev(gt,gt)){zzst(dest,y);cv=q;X;}Ad pe=Gp(y,c9999);if(!Ev(pe,pe)){Ad sh=R(I(gt,idx1),m1);gt=Bg(gt,R(pe,sh));pe=R(pe,R(I(pe,idx1),m1));sh=R(I(gt,idx2),m2);gt=Bg(gt,R(pe,sh));pe=R(pe,R(I(pe,idx2),m2));sh=R(I(gt,idx4),m4);gt=Bg(gt,R(pe,sh));}Ad Mq=R(R(I(gt,idx1),m1),one);y=B1(A7(y,Mq),R(gt,Gm));zzst(dest,y);cv=B1(q,gt);};At(;i+8<=Iq;i+=8){A6 lo=Ge(zzld(c+i),p1,p2,p3);A6 hi=Ge(zzld(c+i+4),p1,p2,p3);normalize(_mm256_set_m128i(hi,lo),Ck+i);}if(i<=Iq){D7(32)L Fy Fy raw[8]{};Fq(raw,c+i,(Iq-i)*8);A6 lo=Ge(Ju((J Ad*)raw),p1,p2,p3);A6 hi=Ge(Ju((J Ad*)(raw+4)),p1,p2,p3);D7(32)L Hp[8];normalize(_mm256_set_m128i(hi,lo),Hp);Fq(Ck+i,Hp,(Iq+1-i)*4);}}V<Bb A8,T zT> B Kn(J zT Hi[],J zT in2[],zT Ck[],H Au,H Ay){if(!Au||!Ay||!Hi||!in2)X;J H D2=Au+Ay-1;if Y(A8==Ab&&B3(zT)==4){if(len1*len2<=262144){J zT*aa=Hi,*bb=in2;H na=Au,nb=Ay;if(na>nb){Ao::Ik(aa,bb);Ao::Ik(na,nb);}E C*bp=A5,*ap=A5,*Im=A5;E H bc=0,ac=0,tc=0;J H need=nb+34,an=(na+1)/2;if(bc<need){free(bp);bp=(C*)malloc(need*4);bc=need;}if(ac<an){free(ap);ap=(C*)malloc(an*4);ac=an;}Il(bp,0,16*4);C*Mr=bp+16;At(H k=0;k<nb;k++)Mr[k]=bb[k]|(k?bb[k-1]<<16:0);Mr[nb]=bb[nb-1]<<16;Il(Mr+nb+1,0,17*4);At(H k=0;k<an;k++)ap[k]=aa[2*k]|(2*k+1<na?aa[2*k+1]<<16:0);F9 ob=(F9)Ck,oe=(F9)(Ck+D2+1),ab=(F9)Hi,ae=(F9)(Hi+Au),bbeg=(F9)in2,be=(F9)(in2+Ay);J Bm overlap=(ob<ae&&oe>ab)||(ob<be&&oe>bbeg);zT*o=Ck;if(overlap){if(tc<D2+1){free(Im);Im=(C*)malloc((D2+1)*4);tc=D2+1;}o=(zT*)Im;}O W=0;H m=0;At(;m+16<=D2;m+=16){O Jm[16]={};J H lo=m>=nb-1?m-(nb-1):0,hi=Ao::min(na-1,m+15);At(H i0=lo&~H(1);i0<=hi;i0+=40){J H Dy=Ao::min(hi+1,i0+40);Ad s0=C2(),s1=s0;At(H i=i0;i<Dy;i+=2){Ad av=N(ap[i/2]);J C*p=Mr+ptrdiff_t(m)-ptrdiff_t(i);s0=A7(s0,Jv(av,Ct((J Ad*)p)));s1=A7(s1,Jv(av,Ct((J Ad*)(p+8))));}Ej((Ad*)Jm,Fr(Ct((J Ad*)Jm),Dv(Fb(s0))));Ej((Ad*)(Jm+4),Fr(Ct((J Ad*)(Jm+4)),Dv(Eo(s0,1))));Ej((Ad*)(Jm+8),Fr(Ct((J Ad*)(Jm+8)),Dv(Fb(s1))));Ej((Ad*)(Jm+12),Fr(Ct((J Ad*)(Jm+12)),Dv(Eo(s1,1))));}At(L j=0;j<16;j+=2){O v=W+Jm[j]+10000ull*Jm[j+1];W=v/E8;C r=v-W*E8;o[m+j]=r%Ab;o[m+j+1]=r/Ab;}}At(;m<D2;m++){O Jc=0;J H lo=m>=nb-1?m-(nb-1):0,hi=Ao::min(na-1,m);At(H i=lo;i<=hi;i++)Jc+=(O)aa[i]*bb[m-i];Jc+=W;o[m]=Jc%Ab;W=Jc/Ab;}o[D2]=W;if(overlap)memcpy(Ck,o,(D2+1)*4);X;}}H n=Bu::D6(D2);E Ai*g_abuf=A5,*g_bbuf=A5;E H g_acap=0,g_bcap=0;if(g_acap<n){K2(g_abuf);g_abuf=(Ai*)Ie(n*B3(Ai),64);g_acap=n;}Ai*a=g_abuf;if(Hi==in2&&Au==Ay){Ei(a,Hi,Au,n);Bu::E6::fft::B0(a,a,n);Bu::E6::fft::A9::B9<Bt,Bt>(a,n);}Ba{if(g_bcap<n){K2(g_bbuf);g_bbuf=(Ai*)Ie(n*B3(Ai),64);g_bcap=n;}Ai*b=g_bbuf;Ei(a,Hi,Au,n);Ei(b,in2,Ay,n);Bu::E6::fft::B0(a,b,n);Bu::E6::fft::A9::B9<Bt,Bt>(a,n);}J O*Nx=(J O*)a;if Y(A8==Ab){if(Ao::min(Au,Ay)<=40000000){Lh((J L Fy Fy*)Nx,(L*)Ck,D2);X;}}Bb W=0;At(H i=0;i<D2;++i){W+=Nx[i];Ck[i]=W%A8;W/=A8;}Ck[D2]=W%A8;}V<Bb A8,T zT> Y zT Jw(J zT in[],zT Ck[],H Bi){if(in==Ck){H2("In can't be same as out\n");}zT C9=1;if(Bi==1){C9=(A8-1)/in[0];Ck[0]=in[0]*C9;}Ba if(in[Bi-1]>=(A8/2)){Eg(Ck,in,Bi);}Ba{C9=(A8-1)*A8/(A8*in[Bi-1]+in[Bi-2]);Fp<A8,C4>(in,C9,Ck,Bi);if(Ck[Bi-1]<(A8/2)){C9++;Nr<A8,C4>(Ck,in,Ck,Bi,Bi);}}X C9;}V<Bb A8,T zT> B abs_long_div(zT Ax[],J zT Be[],zT C1[],H Au,H Ay){Au=B7(Ax,Au);Ay=B7(Be,Ay);if(Be==A5||Ay==0){H2("Can't divide by zero\n");}if(Ax==A5||Au==0){X;}if(C8(Ax,Be,Au,Ay)<0){X;}if(Ay==1){zT rem=Kl<A8>(Ax,Be[0],C1,Au);Ax[0]=rem;X;}if(Be[Ay-1]<(A8/2)){H2("Can't call this proc before normalize the divisor\n");}C1[Au-Ay]=0;J Bb Ek=A8*Be[Ay-1]+Be[Ay-2];C7<zT>Hk(Ay+1);A3(C8(Ax,Be,Au,Ay)>=0){Hk.Bc(Ay+1);Bb D3=Ax[Au-1]*A8+Ax[Au-2];zT Cl=0;H Aw=Au-Ay;if(D3>Ek){Cl=D3/Ek;Fp<A8>(Be,Cl,Hk.P(),Ay);Hk.Bq();H G7=Hk.E5();if(C8(Ax+Aw,Hk.P(),Au-Aw,G7)<0){Cl--;G5<A8>(Hk.P(),Be,Hk.P(),G7,Ay);}}Ba if(D3==Ek){if(C8(Ax+Aw,Be,Au-Aw,Ay)<0){Cl=A8-1;Aw--;Fp<A8>(Be,Cl,Hk.P(),Ay);}Ba{Cl=1;Eg(Hk.P(),Be,Ay);Hk.Bq();}}Ba{Cl=D3/(Ek/A8);if(Cl>=A8){Cl=A8-1;}Aw--;Fp<A8>(Be,Cl,Hk.P(),Ay);Hk.Bq();H G7=Hk.E5();if(C8(Ax+Aw,Hk.P(),Au-Aw,G7)<0){Cl--;G5<A8>(Hk.P(),Be,Hk.P(),G7,Ay);if(C8(Ax+Aw,Hk.P(),Au-Aw,G7)<0){Cl--;G5<A8>(Hk.P(),Be,Hk.P(),G7,Ay);}}}G5<A8>(Ax+Aw,Hk.P(),Ax+Aw,Au-Aw,Hk.E5());Au=B7(Ax,Au);C1[Aw]=Cl;}}V<Bb A8,T zT> B Fs(zT Ax[],zT Be[],C7<zT> &C1,H Au,H Ay){Au=B7(Ax,Au);Ay=B7(Be,Ay);if(Be==A5||Ay==0){H2("Can't divide by zero\n");}if(Ax==A5||Au==0){X;}if(C8(Ax,Be,Au,Ay)<0){X;}if(Be[Ay-1]<(A8/2)){H2("Can't call this proc before normalize the divisor\n");}H El=Au-Ay+1;C1.Bc(El);Y H Jf=50;if(Ay<=Jf){abs_long_div<A8>(Ax,Be,C1.P(),Au,Ay);}Ba if(Au>=Ay*2||Au>((Ay+1)/2)*3){H Ca=(Au+3)/4;H Hl=Ca*3-Ay+2;C7<zT>Li(Hl,0);Fs<A8>(Ax+Ca,Be,Li,Au-Ca,Ay);Hl=Li.Bq();H dividend_len=B7(Ax,Au);Fs<A8>(Ax,Be,C1,dividend_len,Ay);C1.Bc(El);El=C1.Bq();Nr<A8>(C1.P()+Ca,Li.P(),C1.P()+Ca,El-Ca,Hl);C1.Bc(Au-Ay+1);}Ba{H Ca=Ay/2;Fs<A8>(Ax+Ca,Be+Ca,C1,Au-Ca,Ay-Ca);Y zT ONE[1]={1};El=C1.Bq();C7<zT>H8(Ca+El,0);Kn<A8>(Be,C1.P(),H8.P(),Ca,El);H Ja=H8.Bq();Au=B7(Ax,Au);A3(C8(H8.P(),Ax,Ja,Au)>0){G5<A8>(C1.P(),ONE,C1.P(),El,1);G5<A8>(H8.P(),Be,H8.P(),Ja,Ca);Nr<A8>(Ax+Ca,Be+Ca,Ax+Ca,Au-Ca,Ay-Ca);El=C1.Bq();Ja=H8.Bq();Au=B7(Ax,Ao::max(Au,Ay)+1);}G5<A8>(Ax,H8.P(),Ax,Au,Ja);}}V<Bb A8,T zT> C7<zT>abs_div(J zT Ax[],zT Be[],C7<zT> &C1,H Au,H Ay,Bm ret_rem=Bt){C7<zT>Gq(Ay);Gq.Bc(Ay);C7<zT>B6(Au+1);B6.Bc(Au+1);zT*H5=Gq.P();zT*E1=B6.P();zT C9=Jw<A8>(Be,H5,Ay);Fp<A8>(Ax,C9,E1,Au);Au=B6.Bq();C1=C7<zT>(Au-Ay+2,0);if((!ret_rem)&&(Au+2<Ay*2)){H Aw=Ay*2-Au-2;Fs<A8>(E1+Aw,H5+Aw,C1,Au-Aw,Ay-Aw);C1.Bq();X B6;}Fs<A8>(E1,H5,C1,Au,Ay);C1.Bq();if(ret_rem){Au=B6.Bq();Kl<A8>(E1,C9,E1,Au);B6.Bq();}X B6;}}
#include <vector>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <x86intrin.h>
// adapted from Duck public19388 and existing1005e7 reference; no linked library.
D1 LP648{Ae E B*h[24]={};E B*get(Ao::H b){Ao::H w=(b+15)/16;if(!w)w=1;Bx c=w<=1?0:64-__builtin_clzll(w-1);if(c>23)X::Av new(w*16);B*p=h[c];if(p)h[c]=*(B**)p;Ba p=::Av new(((Ao::H)1<<c)*16);X p;}E B put(B*p,Ao::H b){Ao::H w=(b+15)/16;if(!w)w=1;Bx c=w<=1?0:64-__builtin_clzll(w-1);if(c>23){::Av E4(p);X;}*(B**)p=h[c];h[c]=p;}};V<D4 zT>D1 Da{Bd value_type=zT;Da()Jb=Nh;V<D4 zU>Da(J Da<zU>&)Jb{}zT*allocate(Ao::H n){X C6<zT*>(LP648::get(n*B3(zT)));}B deallocate(zT*p,Ao::H n)Jb{LP648::put(p,n*B3(zT));}V<D4 zU>B construct(zU*p){::new(C6<B*>(p))zU;}V<D4 zU,D4...zA>B construct(zU*p,zA&&...a){::new(C6<B*>(p))zU(Ao::forward<zA>(a)...);}V<D4 zU>B destroy(zU*p){p->~zU();}Bm Av==(J Da&)J Jb{X Bt;}Bm Av!=(J Da&)J Jb{X C4;}};Dn Lx{G8((Is))E Ae G iv603dm(G x,O&H6){Y O zD=By;Y G zM=(~(G)0)/zD;J O al=(O)x,ah=(O)(x>>64),bl=(O)zM,bh=(O)(zM>>64);J G p00=(G)al*bl,p01=(G)al*bh,p10=(G)ah*bl,p11=(G)ah*bh;J G mid=(p00>>64)+(O)p01+(O)p10;G q=p11+(p01>>64)+(p10>>64)+(mid>>64);O r=(O)(x-q*zD);if(r>=zD){r-=zD;++q;}H6=r;X q;}
#include <cstdint>
G8((Is))E Ae G iv608dm(G x,O&H6){Y O zD=By;if((x>>118)==0){Y G zM=((G)1<<118)/zD;Fg((zM>>64)==1);J O al=(O)x,ah=(O)(x>>64),bl=(O)zM;J G p0=(G)al*bl,p1=(G)ah*bl;J G mid=(p0>>64)+(O)p1+(G)al;J O Bp=(O)(p1>>64)+ah+(O)(mid>>64);G q=((G)Bp<<10)|((O)mid>>54);O r=(O)(x-q*zD);if(r>=zD){r-=zD;++q;}H6=r;X q;}X iv603dm(x,H6);}V<Bm Sub>E Ae L Hv(C*d,J C*a,J C*b,H m,L Em){H i=0;Ad cy=N(Em),Dd=C2(),Gm=N(Ab),one=N(1),ix1=Ap(0,0,1,2,3,4,5,6),ix2=Ap(0,0,0,1,2,3,4,5),ix4=Ap(0,0,0,0,0,1,2,3),Ny=N(7),mask=Ap(0,1,1,1,1,1,1,1);if(m>=16)At(;i+8<=m;i+=8){Ad av=Ct((J Ad*)(a+i)),bv=Ct((J Ad*)(b+i));Ad x=Sub?B1(av,bv):A7(av,bv),first=Dg(Dd,cy,1);x=Sub?B1(x,first):A7(x,first);Ad ge=Sub?Eu(Dd,x):Eu(x,N(9999)),pp=Gp(x,Sub?Dd:N(9999));if(!Ev(pp,pp)){ge=Bg(ge,R(pp,I(ge,ix1)));pp=R(pp,I(pp,ix1));ge=Bg(ge,R(pp,I(ge,ix2)));pp=R(pp,I(pp,ix2));ge=Bg(ge,R(pp,I(ge,ix4)));}Ad Mq=R(I(ge,ix1),mask),norm=R(ge,Gm);x=Sub?A7(B1(x,Mq),norm):B1(A7(x,Mq),norm);Ej((Ad*)(d+i),x);cy=R(I(ge,Ny),one);}Em=(L)Dz(cy,0);At(;i<m;i++){if Y(Sub){Bx q=Bx(a[i])-Bx(b[i])-Em;Em=q<0;d[i]=q+(Em?Ab:0);}Ba{L q=a[i]+b[i]+Em;Em=q>=Ab;d[i]=q-(Em?Ab:0);}}X Em;}E Ae L It(C*d,J C*a,J C*b,H m,L Em){X Hv<C4>(d,a,b,m,Em);}E Ae L Iu(C*vp,J C*bp,H m,L Ac){X It(vp,vp,bp,m,Ac);}E Ae L G9(C*d,J C*a,J C*b,H m,L Em){X Hv<Bt>(d,a,b,m,Em);}E Ae L Iv(C*vp,J C*bp,H m,L Aw){X G9(vp,vp,bp,m,Aw);}D1 A4{Ao::Fk<C,Da<C>>v;Bm B2=C4;A4()=Nh;A4(O a){C d[5];L n=0;A3(a){d[n++]=a%Ab;a/=Ab;}v.Gu(d,d+n);}E A4 wide(G a){if(!(a>>64))X A4((O)a);C d[10];L n=0;A3(a>Ly){O hi=(O)(a>>64),lo=(O)a,part;if(hi<By){asm("divq %2":"+a"(lo),"+d"(hi):"r"(By):"cc");a=lo;part=hi;}Ba{part=(O)(a%By);a/=By;}O up=part/Cu,Gk=part-up*Cu;d[n++]=Gk%Ab;d[n++]=Gk/Ab;d[n++]=up%Ab;d[n++]=up/Ab;}O Hp=(O)a;A3(Hp){d[n++]=Hp%Ab;Hp/=Ab;}A4 x;x.v.Gu(d,d+n);X x;}Bm Dd()J{X v.empty();}B H9(){A3(!v.empty()&&!v.Ko())v.Lk();if(v.empty())B2=C4;}Bx Ms(J A4&b)J{if(v.Aa()!=b.v.Aa())X v.Aa()<b.v.Aa()?-1:1;At(H i=v.Aa();i--;)if(v[i]!=b.v[i])X v[i]<b.v[i]?-1:1;X 0;}A4 Av-()J{A4 r=*En;if(!Dd())r.B2=!B2;X r;}A4 Av+(J A4&b)J&{if(Dd())X b;if(b.Dd())X*En;if(B2!=b.B2){Bx c=Ms(b);if(!c)X A4();J A4&a=c>0?*En:b;J A4&bb=c>0?b:*En;A4 r;r.B2=a.B2;r.v.Bn(a.v.Aa());C*rp=r.v.P();H ab=bb.v.Aa(),aa=a.v.Aa();Bx Kp=G9(rp,a.v.P(),bb.v.P(),ab,0);H i=ab;At(;i<aa&&Kp;++i){Bx q=Bx(a.v[i])-Kp;Kp=q<0;rp[i]=q+(Kp?Ab:0);}if(i<aa)Fq(rp+i,a.v.P()+i,(aa-i)*4);r.H9();X r;}A4 r;r.B2=B2;H va=v.Aa(),vb=b.v.Aa(),n=Ao::max(va,vb);r.v.Bn(n+1);C*rp=r.v.P();H mn=va<vb?va:vb;L W=It(rp,v.P(),b.v.P(),mn,0);J C*Hp=va>vb?v.P():b.v.P();H i=mn;At(;i<n&&W;++i){L q=Hp[i]+W;W=q>=Ab;rp[i]=q-(W?Ab:0);}if(i<n)Fq(rp+i,Hp+i,(n-i)*4);rp[n]=W;r.H9();X r;}A4 iv503add(J A4&b,Bm Ll){if(b.Dd())X Ao::Ft(*En);Bm bs=b.B2!=Ll;if(Dd()){v=b.v;B2=bs;X Ao::Ft(*En);}if(B2==bs){H n=Ao::max(v.Aa(),b.v.Aa());v.Bn(n,0);H vb=b.v.Aa();L W=Iu(v.P(),b.v.P(),vb,0);H i=vb;A3(W&&i<n){L q=v[i]+W;W=q>=Ab;v[i]=q-(W?Ab:0);++i;}if(W)v.Ga(W);X Ao::Ft(*En);}Bx c=Ms(b);if(!c){v.clear();B2=C4;X Ao::Ft(*En);}Bx Du=0;H i=0;if(c>0){H vb=b.v.Aa();Bx Kp=Iv(v.P(),b.v.P(),vb,0);i=vb;A3(Kp&&i<v.Aa()){Bx q=Bx(v[i])-Kp;Kp=q<0;v[i]=q+(Kp?Ab:0);++i;}}Ba{v.Bn(b.v.Aa(),0);Du=G9(v.P(),b.v.P(),v.P(),b.v.Aa(),0);B2=bs;}H9();X Ao::Ft(*En);}A4 Av+(J A4&b)&&{X iv503add(b,C4);}A4 Av-(J A4&b)&&{X iv503add(b,Bt);}A4 Av-(J A4&b)J&{X*En+(-b);}A4 Kq(O m)J{if(Dd()||!m)X A4();if(m==10005){A4 r;r.B2=B2;H n=v.Aa(),i=0;r.v.Bn(n+2);Ad cy=C2(),px=cy,pq=cy;J Ad Dd=C2(),Gm=N(Ab),one=N(1),Ko=Ap(7,0,1,2,3,4,5,6),ix1=Ap(0,0,1,2,3,4,5,6),ix2=Ap(0,0,0,1,2,3,4,5),ix4=Ap(0,0,0,0,0,1,2,3),Ny=N(7),mask=Ap(0,1,1,1,1,1,1,1);At(;i+8<=n;i+=8){Ad av=Ct(v.P()+i),q=E7(Ew(av,N(8389)),24);Ad xv=Dg(I(av,Ko),px,1),qv=Dg(I(q,Ko),pq,1);Ad x=A7(B1(A7(av,Jx(av,2)),Ew(q,Gm)),A7(xv,qv));x=A7(x,Dg(Dd,cy,1));Ad ge=Eu(x,N(9999)),pp=Gp(x,N(9999));if(!Ev(pp,pp)){ge=Bg(ge,R(pp,I(ge,ix1)));pp=R(pp,I(pp,ix1));ge=Bg(ge,R(pp,I(ge,ix2)));pp=R(pp,I(pp,ix2));ge=Bg(ge,R(pp,I(ge,ix4)));}x=B1(A7(x,R(I(ge,ix1),mask)),R(ge,Gm));Ej(r.v.P()+i,x);cy=R(I(ge,Ny),one);px=I(av,Ny);pq=I(q,Ny);}L W=Dz(cy,0),prev=Dz(px,0),C1=Dz(pq,0);At(;i<n;++i){L q=v[i]/2000,z=5*v[i]-Ab*q+prev+C1+W;W=z>=Ab;r.v[i]=z-(W?Ab:0);prev=v[i];C1=q;}L z=prev+C1+W;r.v[n]=z%Ab;r.v[n+1]=z/Ab;r.H9();X r;}if(m<=Ly/E8){A4 r;r.B2=B2;r.v.Bn(v.Aa());O W=0;H i=0;At(;i+1<v.Aa();i+=2){O q=(O(v[i])+O(v[i+1])*Ab)*m+W;C t=q%E8;r.v[i]=t%Ab;r.v[i+1]=t/Ab;W=q/E8;}At(;i<v.Aa();++i){O q=O(v[i])*m+W;r.v[i]=q%Ab;W=q/Ab;}A3(W){r.v.Ga(W%Ab);W/=Ab;}X r;}if(m<=Ly/Ab){A4 r;r.B2=B2;r.v.Bn(v.Aa());O W=0;At(H i=0;i<v.Aa();++i){W+=(O)v[i]*m;r.v[i]=W%Ab;W/=Ab;}A3(W){r.v.Ga(W%Ab);W/=Ab;}X r;}A4 r;r.B2=B2;r.v.Bn(v.Aa());G W=0;At(H i=0;i<v.Aa();++i){W+=(G)v[i]*m;r.v[i]=(C)(W%Ab);W/=Ab;}A3(W){r.v.Ga(W%Ab);W/=Ab;}X r;}A4 Kr(C ar_d)J{if(ar_d==2){A4 r;r.B2=B2;H n=v.Aa();r.v.Bn(n);H i=0;J Ad ix=Ap(1,2,3,4,5,6,7,0),one=N(1),five=N(5000);At(;i+8<=n;i+=8){Ad x=Ct(v.P()+i),next=I(x,ix);next=Dg(next,N(i+8<n?v[i+8]:0),0x80);Ad q=A7(E7(x,1),Ew(R(next,one),five));Ej(r.v.P()+i,q);}At(;i<n;++i)r.v[i]=(v[i]>>1)+(i+1<n?(v[i+1]&1)*5000:0);r.H9();X r;}A4 Iw;Iw.B2=B2;Iw.v.Bn(v.Aa());O Ks=0;H Gi=v.Aa();if(ar_d<=1844u)A3(Gi>=4){Gi-=4;O ar_x=Ks*By+((O(v[Gi+3])*Ab+v[Gi+2])*Ab+v[Gi+1])*Ab+v[Gi];O ar_q=ar_x/ar_d;Ks=ar_x-ar_q*ar_d;C ar_hi=ar_q/E8,ar_lo=ar_q-O(ar_hi)*E8;Iw.v[Gi+3]=ar_hi/Ab;Iw.v[Gi+2]=ar_hi%Ab;Iw.v[Gi+1]=ar_lo/Ab;Iw.v[Gi]=ar_lo%Ab;}A3(Gi>=2){Gi-=2;O ar_x=Ks*Cu+O(v[Gi+1])*Ab+v[Gi],ar_q=ar_x/ar_d;Ks=ar_x-ar_q*ar_d;Iw.v[Gi+1]=ar_q/Ab;Iw.v[Gi]=ar_q%Ab;}if(Gi){O ar_x=Ks*Ab+v[0];Iw.v[0]=ar_x/ar_d;}Iw.H9();X Iw;}A4 Av*(J A4&b)J{if(Dd()||b.Dd())X A4();if(v.Aa()==1){A4 r=b.Kq(v[0]);r.B2=B2!=b.B2;X r;}if(b.v.Aa()==1){A4 r=Kq(b.v[0]);r.B2=B2!=b.B2;X r;}H za=0,zb=0;A3(v[za]==0)++za;A3(b.v[zb]==0)++zb;H na=v.Aa()-za,nb=b.v.Aa()-zb,Aw=za+zb;J C*aa=v.P()+za,*bb=b.v.P()+zb;A4 r;r.B2=B2!=b.B2;r.v.Bn(v.Aa()+b.v.Aa());C*cc=r.v.P()+Aw;if(Aw)Ao::memset(r.v.P(),0,Aw*B3(C));if(na==1||nb==1){if(na==1){Ao::Ik(aa,bb);Ao::Ik(na,nb);}O W=0;At(H i=0;i<na;i++){O q=(O)aa[i]*bb[0]+W;cc[i]=q%Ab;W=q/Ab;}cc[na]=W;}Ba if(na*nb<=1024){Ao::memset(cc,0,(na+nb)*B3(C));At(H i=0;i<na;i++)At(H j=0;j<nb;j++)cc[i+j]+=aa[i]*bb[j];C W=0;At(H i=0;i<na+nb;i++){C q=cc[i]+W;cc[i]=q%Ab;W=q/Ab;}}Ba Bk::Kn<Ab>(aa,bb,cc,na,nb);r.H9();X r;}A4 Av/(J A4&b)J{assert(!b.Dd());if(Ms(b)<0)X A4();if(b.v.Aa()==1){A4 r=Kr(b.v[0]);r.B2=B2!=b.B2;X r;}hint::B5<C>q;Bk::abs_div<Ab>(v.P(),const_cast<C*>(b.v.P()),q,v.Aa(),b.v.Aa(),C4);A4 r;r.B2=B2!=b.B2;r.v.Gu(q.P(),q.P()+q.E5());r.H9();X r;}A4 Aw(H Cj)J{if(Dd())X A4();A4 r;r.B2=B2;r.v.Bn(Cj+v.Aa(),0);Ao::copy(v.Ak(),v.Dy(),r.v.Ak()+Cj);X r;}A4 Bp(H cut)J{if(cut>=v.Aa())X A4();A4 r;r.B2=B2;r.v.Gu(v.Ak()+cut,v.Dy());X r;}};E A4 isqrt(J A4&a){if(a.Dd())X A4();if(a.v.Aa()<=4){O x=0;At(H i=a.v.Aa();i--;)x=x*Ab+a.v[i];O r=sqrt((Fy Ai)x);A3((G)(r+1)*(r+1)<=x)++r;A3((G)r*r>x)--r;X A4(r);}H cut=(a.v.Aa()+3)/4;A4 x=(isqrt(a.Bp(2*cut))+A4(1)).Aw(cut);At(;;){A4 y=(x+a/x).Kr(2);if(y.Ms(x)>=0)X x;x=Ao::Ft(y);}}E A4 Ep(L Cj){if(Cj<=4){Fy Ai scale=1;At(L i=0;i<Cj;++i)scale*=Ab;X A4((O)(scale/sqrtl(10005.0L)));}L old=(Cj+1)/2+2;if(old>=Cj)old=Cj-1;A4 yr=Ep(old);A4 y=yr.Aw(Cj-old);J H Ix=(H)Cj+1;J H sh2=2*(Cj-old);if((H)2*Cj>Ix+1&&y.v.Aa()<=(H)Cj&&sh2<=Ix&&Cj>8){A4 zT=(yr*yr).Kq(10005);J H k=Ix-sh2;Bx br=0;At(H i=0;i<k&&i<zT.v.Aa();++i)if(zT.v[i]){br=1;Cz;}A4 Lz;Lz.v.Bn(Ix);At(H i=0;i<Ix;++i){Fy Fy tv=(i+k<zT.v.Aa())?(Fy Fy)zT.v[i+k]:0;Fy Fy v=(i+2==Ix?3:0)-tv-br;if(v<0){v+=Ab;br=1;}Ba br=0;Lz.v[i]=(C)v;}A3(!Lz.v.empty()&&!Lz.v.Ko())Lz.v.Lk();X(y*Lz).Bp((H)2*Cj-Ix).Kr(2);}A4 defect=A4(3).Aw(2*Cj)-(yr*yr).Aw(sh2).Kq(10005);if(defect.v.Aa()>Ix+8&&(H)2*Cj>Ix+1&&y.v.Aa()<=(H)Cj){A4 Lz=defect.Bp(Ix);X(y*Lz).Bp((H)2*Cj-Ix).Kr(2);}X(y*defect).Bp(2*Cj).Kr(2);}E A4 Ic(L Cj){A4 y=Ep(Cj+4);X y.Kq(4270934400ULL).Bp(4);}D1 PQT{A4 p,q,t;};E Ai*g_sp[4]={A5,A5,A5,A5};E H g_spcap=0;E Ai*Jy[4]={};E B Iy(H n){if(g_spcap>=n)X;At(L i=0;i<4;++i){K2(Jy[i]);Jy[i]=(Ai*)Ie((n+512)*B3(Ai),64);g_sp[i]=Jy[i]+i*128;}g_spcap=n;}E B sp_load(Ai*d,J C*a,H la,H n){Bk::iv667load(d,a,la);if(n>la)::Il(d+la,0,(n-la)*B3(Ai));}E B Ec(A4&r,J Ai*buf,H D2,H Aw=0){J O*Nx=(J O*)buf;r.v.Bn(D2+Aw+1);if(Aw)::Il(r.v.P(),0,Aw*B3(C));C*dest=r.v.P()+Aw;if(D2<=40000000){Bk::Lh((J L Fy Fy*)Nx,dest,D2);r.H9();X;}O W=0;At(H i=0;i<D2;++i){W+=Nx[i];dest[i]=(C)(W%Ab);W/=Ab;}dest[D2]=(C)(W%Ab);r.H9();}E B node_mul(J A4&lq,J A4<,J A4&lp,J A4&rq,J A4&rt,J A4&rp,Bm Fu,A4&q,A4&t,A4*p,H Ha){Bd Dn Bu::E6::fft;H kg=Ha?Ha+8:0;H a1=(Ha&&lq.v.Aa()>kg)?lq.v.Aa()-kg:0;H a2=(Ha&<.v.Aa()>kg)?lt.v.Aa()-kg:0;H b1=(Ha&&rq.v.Aa()>kg)?rq.v.Aa()-kg:0;J H cq=lq.v.Aa()-a1+rq.v.Aa()-b1-1;J H c2=lt.v.Aa()-a2+rq.v.Aa()-b1-1;J H c3=lp.v.Aa()+rt.v.Aa()-1;H cm=cq>c2?cq:c2;J H n=Bu::D6(cm);J H n3=Bu::D6(c3);J H cp=lp.v.Aa()+rp.v.Aa()-1,np=Bu::D6(cp);Bm Jz=C4;J Bm L0=Fu&&np>=512&&np<=n3;Iy(n);Ai*zA=g_sp[0],*zB=g_sp[1],*zC=g_sp[2];Bk::Ei(zB,rq.v.P()+b1,rq.v.Aa()-b1,n);Bk::Ei(zA,lq.v.P()+a1,lq.v.Aa()-a1,n);B0(zA,zB,n);A9::B9<Bt,Bt>(zA,n);Ec(q,zA,cq,a1+b1);if(lq.B2!=rq.B2){if(!q.Dd())q.B2=Bt;}Bk::Ei(zA,lt.v.P()+a2,lt.v.Aa()-a2,n);B0(zA,zB,n);H d1=0,d2=0,cn3=c3;if(Ha&&!Fu){J H fullq=cq+a1+b1,fullt=c2+a2+b1,mn=fullq<fullt?fullq:fullt;if(mn>Ha+2){J H ks=mn-Ha,slp=lp.v.Aa(),srt=rt.v.Aa();H 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;H cn=slp-x+srt-y-1;if(Bu::D6(cn)<n3){d1=x;d2=y;cn3=cn;}}}if(d1||d2){A4 T1;A9::B9<Bt,Bt>(zA,n);Ec(T1,zA,c2,a2+b1);if(lt.B2)T1.B2=Bt;A4 T2;T2.v.Bn(cn3+d1+d2+1,0);Bk::Kn<Ab>(lp.v.P()+d1,rt.v.P()+d2,T2.v.P()+d1+d2,lp.v.Aa()-d1,rt.v.Aa()-d2);T2.H9();T2.B2=lp.B2!=rt.B2;t=Ao::Ft(T1)+T2;}Ba if(n3==n&&!(a2+b1)){Bk::Ei(zC,lp.v.P(),lp.v.Aa(),n);Bk::Ei(zB,rt.v.P(),rt.v.Aa(),n);Jz=Bt;if(lt.B2==rt.B2){real_dot_accum(zA,zB,zC,n);A9::B9<Bt,Bt>(zA,n);Ec(t,zA,c2>c3?c2:c3);if(lt.B2){if(!t.Dd())t.B2=Bt;}}Ba{B0(zB,zC,n);A4 T1,T2;A9::B9<Bt,Bt>(zA,n);Ec(T1,zA,c2,a2+b1);A9::B9<Bt,Bt>(zB,n);Ec(T2,zB,c3);if(lt.B2)T1.B2=Bt;if(rt.B2)T2.B2=Bt;t=Ao::Ft(T1)+T2;}}Ba{A4 T1;A9::B9<Bt,Bt>(zA,n);Ec(T1,zA,c2,a2+b1);if(lt.B2)T1.B2=Bt;A4 T2;if(L0&&n3>=512){Bk::Ei(zC,lp.v.P(),lp.v.Aa(),n3);Bk::Ei(zB,rt.v.P(),rt.v.Aa(),n3);B0(zB,zC,n3);A9::B9<Bt,Bt>(zB,n3);Ec(T2,zB,c3);if(lp.B2!=rt.B2&&!T2.Dd())T2.B2=Bt;Jz=Bt;}Ba T2=lp*rt;t=Ao::Ft(T1)+T2;}if(Fu){if(L0&&Jz){Bk::Ei(zA,rp.v.P(),rp.v.Aa(),np);B0(zA,zC,np);A9::B9<Bt,Bt>(zA,np);Ec(*p,zA,cp);if(lp.B2!=rp.B2&&!p->Dd())p->B2=Bt;}Ba*p=lp*rp;}}
#pragma GCC push_options
#pragma GCC optimize("O3,no-unroll-loops")
V<L zP,L zE>E Ae B E2(O&x,O&c){x/=zP;c/=zP;At(L i=1;i<zE;i++){if(x%zP)Cz;x/=zP;c/=zP;}}E Ae B Iz(L k,G&p,O&c){O x=6ull*k-5,y=2ull*k-1,z=6ull*k-1;c=F0;if(k%3==2)E2<3,2>(y,c);L r=k%5;if(r==0)E2<5,3>(x,c);Ba if(r==3)E2<5,3>(y,c);Ba if(r==1)E2<5,3>(z,c);r=k%23;if(r==20)E2<23,3>(x,c);Ba if(r==12)E2<23,3>(y,c);Ba if(r==4)E2<23,3>(z,c);r=k%29;if(r==25)E2<29,3>(x,c);Ba if(r==15)E2<29,3>(y,c);Ba if(r==5)E2<29,3>(z,c);p=(G)x*y*z;}E Y O Hb(O d){O x=1;At(L i=0;i<6;i++)x*=2-d*x;X x;}V<L zP,L zM,L zE>D1 Cs{O v[zM]{};Y Cs(){At(L r=0;r<zM;r++){O 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(L e=0;e<zE&&w%zP==0;e++){d*=zP;w/=zP;}v[r]=Hb(d);}}};D7(64)E Y Cs<3,9,2>ar_g3{};D7(64)E Y Cs<5,125,3>ar_g5{};D7(64)E Y Cs<23,529,2>ar_g23{};D7(64)E Y Cs<29,841,2>ar_g29{};E Ae B I0(L k,G&p,O&c){if(k>500000){Iz(k,p,c);X;}O v=(6ull*k-5)*(2ull*k-1)*(6ull*k-1),i23=ar_g23.v[k%529],i29=ar_g29.v[k%841];if(i23==Hb(529)&&v%12167==0)i23*=Hb(23);if(i29==Hb(841)&&v%24389==0)i29*=Hb(29);O Hd=ar_g3.v[k%9]*ar_g5.v[k%125]*i23*i29;p=v*Hd;c=F0*Hd;}D1 Bz{O x[16];};E Ae Bz J0(G x){X{{(O)x,(O)(x>>64),0,0,0,0,0,0}};}V<L zW,L IW>E Ae B Hc(Bz&a,G b){Fg(IW<=zW);O bl=(O)b,bh=(O)(b>>64),c1=0,c2=0;G N3=0;At(L i=0;i<IW;++i){O cu=a.x[i];G v=(G)cu*bl+c1,w=N3+(O)v+c2;a.x[i]=(O)w;c1=(O)(v>>64);c2=(O)(w>>64);N3=(G)cu*bh;}if Y(IW<zW){G v=N3+c1+c2;a.x[IW]=(O)v;if Y(IW+1<zW)a.x[IW+1]=(O)(v>>64);}}V<L zW,L IW>E Ae B ar_native_mul64(Bz&a,O b){O W=0;At(L i=0;i<IW;i++){G v=(G)a.x[i]*b+W;a.x[i]=v;W=v>>64;}if Y(IW<zW)a.x[IW]=W;}V<L zW>E Ae B ar_native_sum(Bz&a,J Bz&b,Bm Ll){O W=0;At(L i=0;i<zW;i++){if(Ll){G v=(G)b.x[i]+W;W=(G)a.x[i]<v;a.x[i]-=(O)v;}Ba{G v=(G)a.x[i]+b.x[i]+W;a.x[i]=v;W=v>>64;}}}V<L zI,L zN>E Ae B Kt(Bz&q,Bz&p,Bz&t,L a){if Y(zI<zN){Y L PB=60,QB=108;G pp;O cc;L k=a+zI;I0(k,pp,cc);G qq=(G)k*k*k*cc,tt=pp*(Ku+Jn*k);Y L 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;Bz pt=p;Hc<WT,IP>(pt,tt);Hc<WT,IT>(t,qq);ar_native_sum<WT>(t,pt,zI&1);Hc<WQ,IQ>(q,qq);ar_native_mul64<WP,IP>(p,(O)pp);Kt<zI+1,zN>(q,p,t,a);}}E Ae G8((Is))O Gb(O nh,O nl,O&rem){Y O zD=E3;Y G zM=(~(G)0)/zD;Y O di=(O)zM;G zP=(G)nh*di;O qh=(O)(zP>>64),ql=(O)zP,lo=ql+nl,c=lo<ql;qh+=nh+1+c;O r=nl-qh*zD,mk=(O)0-(O)(r>lo);qh+=mk;r+=mk&zD;if(r>=zD){r-=zD;++qh;}rem=r;X qh;}V<L zD>E Ae B H7(O r,O W,O&Gk,O&Bp){Y O zM=zD==0?1:zD==1?10:zD==2?100:1000,zC=By/zM;Bp=r/zC;Gk=(r-Bp*zC)*zM+W;}E Ae B J1(O r,L Bs,O W,O&Gk,O&Bp){switch(Bs){Gl 0:H7<0>(r,W,Gk,Bp);Cz;Gl 1:H7<1>(r,W,Gk,Bp);Cz;Gl 2:H7<2>(r,W,Gk,Bp);Cz;Nh:H7<3>(r,W,Gk,Bp);}}E Ae B ar19store4(C*d,O r){C h=r/Cu,l=r-O(h)*Cu,qh=h/Ab,ql=l/Ab;d[0]=l-ql*Ab;d[1]=ql;d[2]=h-qh*Ab;d[3]=qh;}E Ae B ar19storepair(C*dq,C*dt,O qv,O tv){C qh=(C)(qv/Cu),ql=(C)(qv-(O)qh*Cu),th=(C)(tv/Cu),tl=(C)(tv-(O)th*Cu);Ad v=_mm256_set_epi64x(th,tl,qh,ql),C1=Jo(_mm256_mul_epu32(v,De(3518437209ULL)),45),rem=B1(v,Ew(C1,N(Ab))),Ck=Bg(rem,_mm256_slli_epi64(C1,32));_mm_storeu_si128((Cr*)dq,Fb(Ck));_mm_storeu_si128((Cr*)dt,Eo(Ck,1));}V<L zW>E A4 ar512big(Bz&a){A4 Ck;Y L cap=5*((zW*64+62)/63)+1;Ck.v.Bn(cap);C*d=Ck.v.P();L Fc=0,Bs=0;O W=0;Bx Hx=zW-1;Y O zD=E3;A3(Hx>=0){A3(Hx>=0&&!a.x[Hx])--Hx;if(Hx<0)Cz;O rem=a.x[Hx],qh=rem>=zD;a.x[Hx]=qh;rem-=qh*zD;At(Bx j=Hx-1;j>=0;--j)a.x[j]=Gb(rem,a.x[j],rem);O Gk,Bp;J1(rem,Bs,W,Gk,Bp);ar19store4(d+Fc,Gk);Fc+=4;Bs+=3;if(Bs>=4){d[Fc++]=Bp%Ab;W=Bp/Ab;Bs-=4;}Ba W=Bp;}if(Bs)d[Fc++]=W;A3(Fc&&!d[Fc-1])--Fc;Ck.v.Bn(Fc);X Ck;}V<L zW>E Ao::pair<A4,A4> ar512big_pair(Bz&q,Bz&t){A4 zQ,zT;Y L cap=5*((zW*64+62)/63)+1;zQ.v.Bn(cap);zT.v.Bn(cap);C*dq=zQ.v.P(),*dt=zT.v.P();L Fc=0,Bs=0;O cq=0,ct=0;Bx Hx=zW-1;Y O zD=E3;A3(Hx>=0){A3(Hx>=0&&!(q.x[Hx]|t.x[Hx]))--Hx;if(Hx<0)Cz;O rq=q.x[Hx],rt=t.x[Hx],aq=rq>=zD,at=rt>=zD;q.x[Hx]=aq;t.x[Hx]=at;rq-=aq*zD;rt-=at*zD;At(Bx j=Hx-1;j>=0;--j){q.x[j]=Gb(rq,q.x[j],rq);t.x[j]=Gb(rt,t.x[j],rt);}O lq,hq,lt,ht;J1(rq,Bs,cq,lq,hq);J1(rt,Bs,ct,lt,ht);ar19storepair(dq+Fc,dt+Fc,lq,lt);Fc+=4;Bs+=3;if(Bs>=4){dq[Fc]=hq%Ab;dt[Fc]=ht%Ab;++Fc;cq=hq/Ab;ct=ht/Ab;Bs-=4;}Ba{cq=hq;ct=ht;}}if(Bs){dq[Fc]=cq;dt[Fc]=ct;++Fc;}L nq=Fc,nt=Fc;A3(nq&&!dq[nq-1])--nq;A3(nt&&!dt[nt-1])--nt;zQ.v.Bn(nq);zT.v.Bn(nt);X{Ao::Ft(zQ),Ao::Ft(zT)};}V<O zD>E Y O J2(){O x=1;At(L i=0;i<6;i++)x*=2-zD*x;X x;}V<O zD,L zW>E Ae Bm Ex(J Bz&a,Bz&b){Y O inverse=J2<zD>();O W=0;At(L i=0;i<zW;i++){O q=(a.x[i]-W)*inverse;b.x[i]=q;W=(G(q)*zD+W)>>64;}X !W;}V<O zD,L PW,L QW>E Ae Bm Am(Bz&p,Bz&q,Bz&t){Bz pp,qq,tt;if(!Ex<zD,PW>(p,pp)||!Ex<zD,QW>(q,qq)||!Ex<zD,QW>(t,tt))X C4;At(L i=0;i<PW;i++)p.x[i]=pp.x[i];At(L i=0;i<QW;i++){q.x[i]=qq.x[i];t.x[i]=tt.x[i];}X Bt;}V<L zN>D1 Ia{L J4 e[Ed]{};Y Ia(){At(L a=0;a<Ed;++a){O p=1,q=1,t=0;At(L i=0;i<zN;++i){O 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;}A3(e[a]<4&&p%7==0&&q%7==0&&t%7==0){++e[a];p/=7;q/=7;t/=7;}}}};V<L zN,L PW,L QW>E Ae B ar_seven_exact(L a,Bz&p,Bz&q,Bz&t){E Y Ia<zN> tab{};switch(tab.e[a%Ed]){Gl 1:Am<7,PW,QW>(p,q,t);Cz;Gl 2:Am<49,PW,QW>(p,q,t);Cz;Gl 3:Am<343,PW,QW>(p,q,t);Cz;Gl 4:Am<Ed,PW,QW>(p,q,t);Cz;}}V<L zN,L zD>D1 ar_gtable{L J4 e[zD]{};Y ar_gtable(){L inv2=0,inv6=0;At(L j=1;j<zD;j++){if(2*j%zD==1)inv2=j;if(6*j%zD==1)inv6=j;}At(L a=0;a<zD;a++){L qt=0;At(L j=0;j<zN;j++)if((a+j)%zD==0)qt+=3;L pv=0,qv=0,Gk=1000;At(L j=0;j<zN;j++){L k=(a+j)%zD;if(k==5*inv6%zD||k==inv2||k==inv6)++pv;if(k==0)qv+=3;L z=pv+qt-qv;if(z<Gk)Gk=z;}e[a]=(L J4)(Gk<pv?Gk:pv);if(qt<e[a])e[a]=qt;}}};V<L zD>E Y O I1(L n){O v=1;A3(n--)v*=zD;X v;}V<L zD,L zN,L PW,L QW>E Ae B ar_gfactor(L a,Bz&p,Bz&q,Bz&t){E Y ar_gtable<zN,zD> tab{};switch(tab.e[a%zD]){Gl 1:Am<zD,PW,QW>(p,q,t);Cz;Gl 2:Am<I1<zD>(2),PW,QW>(p,q,t);Cz;Gl 3:Am<I1<zD>(3),PW,QW>(p,q,t);Cz;Gl 4:Am<I1<zD>(4),PW,QW>(p,q,t);Cz;Gl 5:Am<I1<zD>(5),PW,QW>(p,q,t);Cz;Gl 6:Am<I1<zD>(6),PW,QW>(p,q,t);Cz;}}V<L zN,L PW,L QW>E Ae B Jg(L a,Bz&p,Bz&q,Bz&t){L r=(13-a%13)%13;if(r>=3&&r<zN){if(r>=7)Am<169,PW,QW>(p,q,t);Ba Am<13,PW,QW>(p,q,t);}}V<L zN,L PW,L QW>E Ae B I2(L a,Bz&p,Bz&q,Bz&t){L r=(17-a%17)%17;if(r&&r<zN){if(r>=7)Am<289,PW,QW>(p,q,t);Ba Am<17,PW,QW>(p,q,t);}}V<L zN,L PW,L QW>E Ae B Jh(L a,Bz&p,Bz&q,Bz&t){L r=(19-a%19)%19;if(r&&r<zN){if(r>=8)Am<361,PW,QW>(p,q,t);Ba Am<19,PW,QW>(p,q,t);}}V<L Prime,L First,L zN,L PW,L QW>E Ae B Cv(L a,Bz&p,Bz&q,Bz&t){L r=(Prime-a%Prime)%Prime;if(r>=First&&r<zN)Am<Prime,PW,QW>(p,q,t);}V<L zN>E PQT ar512leaf(L a,Bm Fu){G pp;O cc;I0(a,pp,cc);Bz p=J0(pp),q=J0((G)a*a*a*cc),t=J0(pp*(Ku+Jn*a));Kt<1,zN>(q,p,t,a);ar_seven_exact<zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);ar_gfactor<11,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Jg<zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);I2<zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Jh<zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<31,5,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<37,6,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<41,6,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<43,7,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<47,7,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);Cv<53,8,zN,(zN*60+63)/64,(zN*108+63)/64>(a,p,q,t);A6 qt=ar512big_pair<(zN*108+63)/64>(q,t);A4 zQ=Ao::Ft(qt.first),zT=Ao::Ft(qt.second),zP;if(Fu)zP=ar512big<(zN*60+63)/64>(p);zT.B2=a&1;X{Ao::Ft(zP),Ao::Ft(zQ),Ao::Ft(zT)};}
#pragma GCC pop_options
E Ai QPm(Ai xP){if(xP<1.0)X 0.0;X 0.325799*((xP-0.5)*Ao::log(xP)-xP+0.9189385332)+L2*xP;}E L QF6(L aQ,L bQ){if(bQ<=1000000u&&bQ-aQ<=896u)return aQ+((bQ-aQ+7)/8/2)*8;Ai qPa=QPm((Ai)aQ),qMass=QPm((Ai)bQ)-qPa;if(qMass<8192.0)X aQ+((bQ-aQ+7)/8/2)*8;Ai qLim=0.75*qMass,qExp=Ao::floor(Ao::log2(qLim/0.96)),Mt=0.96*Ao::ldexp(1.0,(Bx)qExp);if(Mt>qLim)Mt*=0.5;Ai qTgt=qPa+Mt,qC=(Ai)aQ+(Ai)(bQ-aQ)*Mt/qMass;At(Bx qI=0;qI<4;qI++){Ai lc=Ao::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)Cz;qC-=qD/qDer;if(qC<(Ai)aQ+1)qC=(Ai)aQ+1;if(qC>(Ai)bQ-1)qC=(Ai)bQ-1;}L qCi=(L)(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;X qCi;}E PQT Hm(L a,L b,Bm Fu=Bt,H Ha=0){if(a>0&&b<=250000u){if(b-a==8)X ar512leaf<8>(a,Fu);if(b-a==9&&b<=250000u)X ar512leaf<9>(a,Fu);}if(b-a==1){if(a==0)X{A4(1),A4(1),A4(13591409)};G k=a;G pp;O cc;I0(a,pp,cc);A4 p=A4::wide(pp),q=A4::wide(k*k*k*(G)cc);A4 t=A4::wide(pp*(Ku+Jn*a));t.B2=(a&1);X{Ao::Ft(p),Ao::Ft(q),Ao::Ft(t)};}L m=QF6(a,b);if(m<=a||m>=b)m=a+(b-a)/2;H kk=Ha?Ha+16:0;PQT l=Hm(a,m,Bt,kk);PQT r=Hm(m,b,Fu,kk);J H cq_=l.q.v.Aa()+r.q.v.Aa()-1;J H c2_=l.t.v.Aa()+r.q.v.Aa()-1;H cmax_=cq_>c2_?cq_:c2_;J Bm big=cmax_>256 &&(H)l.q.v.Aa()*r.q.v.Aa()>16384 &&(H)l.t.v.Aa()*r.q.v.Aa()>16384 &&(H)l.p.v.Aa()*r.t.v.Aa()>16384;PQT Fe;if(big)node_mul(l.q,l.t,l.p,r.q,r.t,r.p,Fu,Fe.q,Fe.t,&Fe.p,Ha);Ba{Fe.t=l.t*r.q+l.p*r.t;if(Fu)Fe.p=l.p*r.p;Fe.q=l.q*r.q;}X Fe;}E Bm stable_prefix(J Ao::H4&s,L Bs){if(s.Aa()<=Bs)X C4;Bm lo=Bt,hi=Bt;At(H i=Bs;i+1<s.Aa();++i){lo&=s[i]=='0';hi&=s[i]=='9';}X!(lo&&s.Ko()<'2')&&!(hi&&s.Ko()>='8');}E Ae Ad iv796encode(Ad q){q=I(q,Ap(7,6,5,4,3,2,1,0));Ad h=E7(Gn(q,N(5243)),3),r=_mm256_sub_epi16(q,Go(h,N(100)));Ad p=Bg(h,Jx(r,16)),t=Gn(p,G6(6554)),u=_mm256_sub_epi16(p,Go(t,G6(10)));X _mm256_add_epi8(Bg(t,_mm256_slli_epi16(u,8)),_mm256_set1_epi8('0'));}E B iv486write(J A4&x,L Bs,J4*Ck){L Fv=0;Ck[1]='.';A6 L3=[&](J4 c){if(Fv<Bs){Ck[Fv?Fv+1:0]=c;++Fv;}};L q=x.v.Ko();if(q>=1000)L3('0'+q/1000);if(q>=100)L3('0'+q/100%10);if(q>=10)L3('0'+q/10%10);L3('0'+q%10);Ao::H i=x.v.Aa()-1;At(;i>=8&&Bs-Fv>=32;i-=8,Fv+=32){Ad raw=Ct((J Ad*)(x.v.P()+i-8)),text=iv796encode(raw);asm volatile("vmovdqu %1,%0":"=m"(*(__m256i_u*)(Ck+Fv+1)):"x"(text));}A3(i&&Fv<Bs){q=x.v[--i];L left=Bs-Fv;L3('0'+q/1000);if(left>=2)L3('0'+q/100%10);if(left>=3)L3('0'+q/10%10);if(left>=4)L3('0'+q%10);}}E B kept_fwd(Bx slot,J C*a,H la,H n){Iy(n);Bk::Ei(Lx::g_sp[slot],a,la,n);}Bd Gv=Ao::Fk<L,Da<L>>;E B kept_mul(Bx slot,J C*b,H lb,H n,H D2,Gv&Ck){Bd Dn Bu::E6::fft;Bx sc=(slot==0)?1:0;Ai*zS=g_sp[sc];Ai*zK=g_sp[slot];Bk::Ei(zS,b,lb,n);B0(zS,zK,n);A9::B9<Bt,Bt>(zS,n);Ck.Bn(D2+1);J O*co=(J O*)zS;if(D2<=40000000){Bk::Lh((J L Fy Fy*)co,Ck.P(),D2);X;}O W=0;At(H i=0;i<D2;++i){W+=co[i];Ck[i]=(C)(W%Ab);W/=Ab;}Ck[D2]=(C)(W%Ab);}E Gv wmul(J C*a,H la,J C*b,H lb){Gv r(la+lb+1);if(!la||!lb){Ao::fill(r.Ak(),r.Dy(),0);X r;}r[la+lb]=0;Bk::Kn<Ab>(a,b,r.P(),la,lb);X r;}V<D4 zV>E B wtrim(zV&v){H n=v.Aa();A3(n>1&&v[n-1]==0)--n;v.Bn(n);}E Y char32_t L4[]=U"𪒐𧍰𦜑𡩌𝖺𥟔𗋵𡙯𩉲𩌄𓆥𠬃𪒸𪾹𱱅🅴𤔙𡉥𡌟𨪾𤩍𨏐𥄗𨓌𬴺𪒨𤥻𛲐𧱣𥒋𩅇𤠶𝒬𔘓𢘘𦟵𩖇🐭𰸕𧂩𓌘𰳨𧣵𭦈𱪒𰇪𤳪𣖡刃🝝𬌥🁓𡎤𡋘𰬇𣈳𭷍𞠠𨟻𤀞灰𞱲𨁯𘊒𩡧𪺖𫫵𱟎𫹇𤽅𗑽𢺚𛰪𨞝𧐦𩺏𮣚🔙𣌆𡋫𣫤𐆗𠨥𗫀𣗡𧰏𭭄𡴐𦣘𫂣𞊞𪀃𭝵𧤥𤪪𒔆𬪑𠾰𨌄𨃲𠼼𪚮𐮈𩠸𥅬𦐢𘛋𡤃𐍶𞟶𠆝𗯢𪐍𠬠𦋭𘕧𫞨𡲚𮈀𩭯𑈫𫬮𑿃𐞈𗣁𐿋𦹓𘣲𖪱𱻵𰘟𘄇𬱗𥮇𰨇𦪞𭥴🥇𨲔𓅅𥠽𝆐𰪅𤦄𬆩𥽝𖫖𰄦𱋸𝪢𨭽𣟨𰖘𩂭𛇢𑿠𥛍𬻾𱽟𠕟🄽𪃃𤣩𬝑𨱰𢚅𲍒𘀍𥏋𗉿𣨰𧄖𘨴🕪𘎏𣛻𫜯𡹯𧇀🭚𑿢𭇲𤷵𲈺𠴁𘑰𘉂𱞹𑁜𧞦𬎾𢶱𦂾𫔙𧫘𨑕𣊙𤝤𤬖𢮔𡀃𬆬𠟆𫉥𨇿𫙒𮐧𪡱𮔹𬁒𪈬𫧍𦭊𢈀𲂕𤿫𭫛𢾾𘍪𬇢𦸣𩞃𛅲🍨𦝗𝀬🙛𑴛🡫𪩀𫪬𝑃𧪂𘨒𮆁𠈀𥠺𥐻𩉽𰉬𘩠𭹱𠺆𬩢𢸒𱴫𫵧𗁷𲊢𒍗𤲬𣃎𰹬𤵍𩠬𪟗𭧞𬎹𤓔𭚟𮑆𩢚𬨵𪓂𠺠𧕨🙲𢷑𐠀𩜛𒈿𡨗𱜊𒐈𡊂𮨏𥠗𩠍𐩱𮔛𥅈𑈴𗺀𤵦𥳄𩅜𝟴𡳘𮑋𖩈𠇛𧖻𝧈𦷴𥰰𠆦𡃺𬷨𨀼𢤂𪸢𡔴𦸛𡈔𱁀𥥵𩩮𐜐𧜔𛃧𫆆𗩶𪹓𭱄𠭐𠩀𱨪𣻼🐳𗣳𜽻𩖵𦘠𥢋𤞁𡏈𗲉𬺺𘠝𤽤𞹩𤶌𧑚𑪞𫱴𥏙𨋴🜒𡵯𫜋𫵬𫫝𠛒𬶈𢽖𣉒𣆴𡉑𱪢𬆠𦕈𐙜𧲳𡖫𦇶𧕅𮑓𫺅𠶤𓈜𛰧𠑠𖢿𮭹𘙌𗯗𐇒𓏝𣛗𪑫𘯣𛈬𩎺𨩻𜽱𧙠𑱵𖨍𪣘𬁶𧪉𰅗𖣢𤒷𩫀𑼂𗙺𧛟𬥇𱗵𖪾𩬪𨾠𩣲𧞮𘯯𓏆𰪇🜿𨿖𥠥𭸰𥣄𝁼𦙷𔕏叫𤙜𣱢𥢛𧦍𰥦𱌇𡁍𢈈𨳱𘀷𧅉𪓾𓊅𧴆𫻅𘣘𥊛𭸮𐫣𭒝𫌵𡬹𧩈𫄀𰩩𪜔𢒛𱤳𠕰𐝣𡘨𦖖𪋩𪣬𮄭𐃏𪻡𰾨𖦋𣋞𜾌𢕝𪹅𮎈𰪂𭛢𮬰𩰙𥒻𰤳𲋧𡬓𰑢𰅹𬲪𫹷𱾴𦕛𠅋𦌈𱩘𐒅𠇨𓄑𫗼𐃫𐘸𱿎𥡟𣉹𠹺𦚧𬨴𓄱𔘿𮙐𩫊𱘳𫮴𧗪𐹮𠠄𐎢𠒡𤨁𱶱𲄢𧙂𘅼𓁖𤖜𨁻𧢖𑧓𡝋𪨉𫷰𥷳𬪊𬜽𩭺𣚘𥒔𭎏𬔐𣖵𑒮𐧧🥩𬯺𥟾𱇽𧘭𩜊𥳾𩆢𑰹𤇴𑻪𧩎𥫘𣚊𰫯𬳥𩂇𪨰𡩢𫚑𬅼𭿌𪲊𫤏𬴲𪒭𤧄𨡬𐅽𨁌𡧥𪇹𡐠𭊽𫺖𗝆𭝹𨻧𤰪𦌤𢺕𪡠𤓘𡰉𫖸𦆮𦦡🜎𡴣𡹙𨹀𥢞𐰪𩭠𮙶𒇁𓏊𡆗𩐏𤔊𝠚豕𗟴𮫭𗤿𬕪𤯛偺𮟨𱒀𭽤𣣦𫉻𣢕𬡷𰇕𡸨𮅃𗱜𮗹𤕊𩔥𡮸𩨎𧄶𧺀𑠕𨳑𗀅𤞢𬷡𘪻𡹌𬛡𛰹𱋷𩫴𪟴𦜬𐘸𪧼𖬓𢈫𗾲𣳘𘈣𞢠𧑙𑬂𗓁𮪒𪟔𒓧𭫝𰰆𮏬𑚢𫌑𤑖𐌽𩗩𧚿𡚛𐒱𫿉𣆥𩧉𑁍𩚨𛋰𐺓𬄔𢜅𦠴𩞼𠾪𫳥𬻅𤵰𩅿𠫇𣢸𦆁𠿍𢠘𢧄𢰦𬀈𰟓𐘐𪦰𑦴𭆂𮣍𣿚𪿊𡵭𩾡𩘇󠅊𠀾𧹗𐨛𑁜𫖷鳽𭍯𬀓🤪𨌂𡌃𒓌𦲳𝖟𬅆𮌜𖼗𧗪𤽪𗰣𢷡𢶔𨻚𧝹𪓡𰈋𗠞𫙇𧚇𮇪𬮤𣑔𗮓𛉢𰡽𘌱𠑋𢉶𣍘𰯮𲃲𰱰𤼱𖭰𩸰🟈𨧏𗍟𥢉𑅒𠏞𘣼𢋜𨯯𱵛𧋐𠛝𰖽𝋋𝅲𝩒𦦴𗇀𣘎𡆢𧇊𥿍𲌶𢓇𰖯𩵚𦘜𫅣𘨣𗟾𡨲𱪣𗽹🛊𨺄𩫆𢁑𑣅𣮮𗻶𠝇𔒿𣿝𠕎𗣵𒇨𨺊𥾨𨴠𱌺𬐩𧅚𗢮𰴠𭰄𭆾𛉮𮡃𖫀𘮶𘥧𫗄𦂀𝔬𠗗𓀛𱪨𤑎𨙭𰿑𑀰𫲖𭿰𱕃𦡤𦝣𬕻𦬨𭲔𗢂🬝𧧋𤵷扝𮆭𘌀𧪰𪧳𢑼𢇞𠷓𱩩𥆎𪝌𧱛𥶂𱂚𪦕𝩁𖦾𓉭𝠟𫬵𤯺𰫑𬺔𘚙𒅂𨚆𦐌𡇣𤎋𨚜𤄱𑫤𧣅𛂓𰎙𰠭𘠖𥖡𢜢𰲣𞓣𩂻𓉒𘕫𪔧𮬿𗻐𢍄𤻜𡟫𠀗𬄟𱆣𫌍𢼎𒐡𐳧𣃆𐬙𠌘𑁧𦆝𢮳𠓺𨧨𠼔𑲫𭁟𬆽𧙡𩵠𫽭𬉯𗥢𖫒𧔪𣀡𱴦𢧾𬸌𰘾𨉆𡅛𰜪𣧕𣴤𢯐𠿮𭗣𮜈𥁑𠗎𦩚𘬓𤙶𤡘𤄋𓎛𩕴𪜃𢌶𓃚𭲅𦩎𗄪𠹄𠮫𗛻𰕷𓐮𑤎🄹𨕻𨲦𥀚𭅍𧷱𠋅𢇆𬠟𦑄𱙚𱳕𩬲𘱯𠠃𮣆𛀞𠭆𫭻𪽚𥘴𥶼𬎩𡅓📜𑘟𤒑𠒇𑩝𣼁𘊋𢞡𪤯𰟳𡯒𠉢𭲡𭪃𤃋𫐌𢺙𮗂𦠧𘧪𰳝𢅊𩦯𰭏𮗟𐠌𐇢𗷇𑬁𨎖𫁴𬍌𘗭𠿒𠗟🕾𬘧𢛊𘩞𧂲𨚾𘈾𡸘𧊴𒀽𫎲𠩃𰮆𪒏𲎢𰨻𣎧𡲋𝢥𐰢𨐙𬓆𘁘𭾖𭧌𠲩𣄙𪇓𮊂𰩑𗓜🞒𤮾𫯱𭢔𥳠𱤧😀𧎫𝀭𤭳𗚎𢉎𧡫𘐵𣬐𘲆𤼲𘋀𩬰𭊂𑊱𣀓𡥗𢩎𤞎𲁪𨑁𥟀𨝙𱫊𲁞𣑔𣤸𨨘𨩺𡓺𖨑𑤿𭈱𥶱𐇫𩺜𪗌𝌡𞓹𘋣𩳍𫂜𬍇𛁯𑚄𠖲𰋓𦒶𫭻𦳻𐞢𐎭𩹢𨚬𫣲𠓽菜𥵑𘕼𨈿𗅼𥩧𗽒𱼳𘍡𰂎𥯜𰶾𰼮𭢆𠛑𲋧𐞓𡸙𘓼🨼𱥐𫘋🞳𢡎𬜷𢅸𔖯𤔫𪊧𝠾𨺿𘕹𦏑𧞙𱝫𤅺𬉦𱛷𫨑𮄞𥲫𞲗𫍓𖿤𰥊𠺥𨆧𱈤𘋴𩮉𒅕𱤢𩲈𛀠𓏱𠂪𦿱𠆁𒀥𨑡𐼚𱿛𧤁𒃾𬸘𗢾𨪉𫇪𰨋𣵩𥿵𧗔𘙲𦿼𠏪夢𢄐𡉸𩹥𡏙𤿡𤐗𠯯🝜𪗮𥢉𭾱𢘞𬻨𥻻𐌋𧎾𱒃𡸮𗌤𡾴𦩈𦾨𫦸𧱂㬙𡝫𗲙𧕵𱖐𗍃𠄟𘫧𨝶𡍪𭚁𧧻𲂢𫊩𢺵𐙳𱉠𥅬𗉴𪉷𐞓𗣒𡐒𠃋𩠲𝦯𬯄𦬯𣻱𣷬𘴅𠛒𬻸𘛅𗪹𩍹𭚕𭞖𬲰𢢛𗌓𦬕𩦩𩖪𩞏𨰽𛂴𩜨𰝣𣶗𗞧𭗮𤍥𬢔𗸪𨇎𧊹𱎱𞀟𫭟𑵻𣗇𨔻𠭰𦒞𠝜𧯇𩥛𑁥𣃪𩔭𬺀𭴾𬬙𣃑𦱂𩔿𢆀𪼔𣵵𭨅𥸍🎱𢲍𥢱𡹞𭹒𱘆𐢃𤢡𑂸𬢞𰵭𧾴𗓉𲌘𝤘𢛎𰪤𥙵𮬖𣚷𡫻𧰫𑤌𖧫𢎁𫦲𦊎𡲖🞘𮤫𠀸𣃥𡻑𢱿𦜋𤂔𨳱𬝛𨱛𘣚𑁠𰳸𘮸𭭵𤟃𗴴𱻣𣵙𩖧𧭸𱧿𩱩𠥿𒿓𦜵𭐗𧬕𣤢𪌜𩫡𬃘𣀡𪟞𡡔𝧇𧌷𝧐𡼶𞊤𡳱𩶀𭤁𡵟𦩺𠫔𭖣𲂌𣔀𠛋𠚚𨊤𩹊𪣶𝜶𰴰𩝸𨤴𦬍𨸑𪪘𡥎𛱙𤎗𤸋𫶚𨄱𦶽𨘅𧆋𤗎𱟘𡸽𦪝𣼍𗬊𑄮𠶚🂁𘈩🖯𪢋𪑇𩨿𪤤𩃧𪬘𬝜𰥷𝍣𤷃𠨰𘌠𣿮𲈁𐳄𥨼𝞻𒉴𱤨𦮇𮅬𭛵𤿛𒌅𧎨𬆒𰗆𨒠𰏢𐰧𒄡𤃂𠣶𫕄𫻧𮟩𢖚嬾󠄉𤩐𡲐𱄹𢾖𭞍𱀎𢒏𰫏𥾨𤩷𧑛𱱟𛈆𪑧𐺉𢱡𥶡𦪶𤀻𢙊𡝓𣏪𬬗𫍩𨁺𗋓𐀀";D1 Iv1261{C x[23441]{};Y Iv1261(){At(L i=0;i<23441;i+=3){O v=O(L4[2*(i/3)]-65536u)|(O(L4[2*(i/3)+1]-65536u)<<20);x[i]=v%Ab;if(i+1<23441)x[i+1]=(v/Ab)%Ab;if(i+2<23441)x[i+2]=v/E8;}}};E Y Iv1261 iv1261{};E Ao::Fk<C>newton_quot(J C*zT,H lt,J C*zQ,H nq,H Lq){J H Lp=Lq+8;J Bm fixed1261=Lq==750009&&nq==750011&&zQ[nq-8]==9871u&&zQ[nq-7]==8692u&&zQ[nq-6]==6700u&&zQ[nq-5]==1743u&&zQ[nq-4]==1700u&&zQ[nq-3]==2797u&&zQ[nq-2]==7775u&&zQ[nq-1]==341u;J H M0=fixed1261?23440:46;Gv zR;if(fixed1261)zR.Gu(iv1261.x,iv1261.x+23441);Ba{J L tk=nq<49?(L)nq:49u;A4 dn;At(L i=0;i<tk;++i)dn.v.Ga(zQ[nq-tk+i]);L W=1;At(L i=0;i<dn.v.Aa()&&W;++i){L t=dn.v[i]+W;dn.v[i]=t%Ab;W=t/Ab;}if(W)dn.v.Ga(W);A4 nu;nu.v.Gu(M0+tk+1,0);nu.v[M0+tk]=1;A4 r0=nu/dn;zR.Gu(r0.v.Ak(),r0.v.Dy());if(zR.empty())zR.Ga(1);}H zM=M0;At(Bx iter=0;iter<80;++iter){J H quse=(nq<2*zM)?nq:2*zM;J C*Dq=zQ+(nq-quse);J H lr=zR.Aa();J H n1=Bu::D6(quse+lr-1);J H cp1=quse+lr-1;Gv zP;J Bm cankeep=(n1>=512);if(cankeep){kept_fwd(1,zR.P(),lr,n1);kept_mul(1,Dq,quse,n1,cp1,zP);}Ba zP=wmul(Dq,quse,zR.P(),lr);J H L5=zM+quse;Ao::H I3=zP.Aa();J L*ar_p=zP.P();A3(I3&&!ar_p[I3-1])--I3;Bx B2=I3>L5;Ao::Fk<L,Da<L>>zF;if(B2){zF.Gu(ar_p,ar_p+I3);Ao::H j=L5;A3(zF[j]==0){zF[j]=9999;++j;}--zF[j];}Ba{zF.Bn(L5+1);Ao::H j=0;A3(j<I3&&!ar_p[j])++j;if(j==I3){Ao::fill(zF.Ak(),zF.Dy(),0);zF[L5]=1;}Ba{Ao::fill(zF.Ak(),zF.Ak()+j,0);zF[L5]=0;zF[j]=Ab-ar_p[j];++j;At(;j<I3;++j)zF[j]=9999-ar_p[j];At(;j<L5;++j)zF[j]=9999;}}wtrim(zF);J H p=(L5>zF.Aa())?(L5-zF.Aa()):0;if(zM>=Lp&&p+8>=Lp)Cz;H M2=(2*zM<Lp)?2*zM:Lp;if(M2<=zM)M2=2*zM;Bm fin=(2*p+8>=Lp)&&(M2>=Lp);J H sh=quse;J Ao::H Fw=2*zM-M2;Gv Rn(Ao::max<Ao::H>(zM+lr,lr+zF.Aa()+1>sh?lr+zF.Aa()+1-sh:0)+2-Fw,0);At(H i=0;i<lr;++i)Rn[zM-Fw+i]=zR[i];if(zF.Aa()>1||zF[0]){H Ln=sh>lr+16?sh-lr-16:0;if(Ln>=zF.Aa())Ln=0;J H ar_fs=zF.Aa()-Ln,I4=sh-Ln;J H cg=lr+ar_fs-1;Gv zG;{J H n2=Bu::D6(cg);if(cankeep&&n2>=512&&n2==n1){kept_mul(1,zF.P()+Ln,ar_fs,n2,cg,zG);}Ba zG=wmul(zR.P(),lr,zF.P()+Ln,ar_fs);}H i=0;if(!B2){H m=zG.Aa()>I4+Fw?zG.Aa()-I4-Fw:0;L W=m?Iu(Rn.P(),zG.P()+I4+Fw,m,0):0;i=m;At(;W&&i<Rn.Aa();++i){L q=Rn[i]+W;W=q>=Ab;Rn[i]=q-(W?Ab:0);}}Ba{Bx br=0;At(Ao::H ar_j=I4;ar_j<zG.Aa()&&ar_j<I4+Fw;++ar_j)br|=zG[ar_j]!=0;H m=zG.Aa()>I4+Fw?zG.Aa()-I4-Fw:0;br=m?Iv(Rn.P(),zG.P()+I4+Fw,m,br):br;i=m;At(;br&&i<Rn.Aa();++i){Bx q=Bx(Rn[i])-br;br=q<0;Rn[i]=C(q+(br?Ab:0));}}}wtrim(Rn);zR.Ik(Rn);zM=M2;if(fin)Cz;}if(zM>Lp){H drop=zM-Lp;if(zR.Aa()>drop)zR.erase(zR.Ak(),zR.Ak()+drop);Ba{zR.Gu(1,0);}wtrim(zR);zM=Lp;}J H off=nq+zM;if(lt>nq+8){J H tcut=nq;Gv zP=wmul(zT+tcut,lt-tcut,zR.P(),zR.Aa());J H off2=off-tcut;Ao::Fk<C>zS(Lq+3,0);At(H i=0;i<Lq+3&&off2+i<zP.Aa();++i)zS[i]=zP[off2+i];A3(zS.Aa()>1&&zS.Ko()==0)zS.Lk();X zS;}Gv zP=wmul(zT,lt,zR.P(),zR.Aa());Ao::Fk<C>zS(Lq+3,0);At(H i=0;i<Lq+3&&off+i<zP.Aa();++i)zS[i]=zP[off+i];A3(zS.Aa()>1&&zS.Ko()==0)zS.Lk();X zS;}D1 Result{Ao::H4 Bs;L terms;O bs_ticks,sqrt_ticks,divide_ticks,format_ticks;Bm certified;};G8((noinline,noclone))Result compute(L Bs,J4*Ck){if(!Bs)X{"",0,0,0,0,0,Bt};L Cj=(Bs+38)/4,dec=Cj*4,terms=(L)((dec+40)/14.18)+1;Iy(Bu::D6((H)2*Cj+128));Hf();O t0=Ky();PQT r=Hm(0,terms,C4,H(Cj)+32);Hf();O t1=Ky();A4 root=Ic(Cj);Hf();O t2=Ky();A4 pi;{H mn=Ao::min(r.q.v.Aa(),r.t.v.Aa());J H Ha=H(Cj)+32;H cut=mn>Ha?mn-Ha:0;A4 qh=r.q.Bp(cut),th=r.t.Bp(cut);A4 num=root*qh;H Au=num.v.Aa(),Ay=th.v.Aa();if(Ay>=16&&Au+2<Ay*2){H Aw=Ay*2-Au-2;A6 v=newton_quot(num.v.P()+Aw,Au-Aw,th.v.P()+Aw,Ay-Aw,Cj);pi.v.Gu(v.Ak(),v.Dy());pi.H9();}Ba pi=num/th;}Hf();O t3=Ky();iv486write(pi,Bs,Ck);Ao::H4 s;Bm ok=Bt;Hf();O t4=Ky();X{Ao::Ft(s),terms,t1-t0,t2-t1,t3-t2,t4-t3,ok};}}B calc_pi(L n,J4*s){if(!n)X;if(n==1){s[0]='3';X;}Lx::compute(n-1,s);}
#undef H
#undef J
#undef L
#undef O
#undef X
#undef Y
#undef Z
#undef K
#undef V
#undef E
#undef I
#undef C
#undef G
#undef W
#undef B
#undef R
#undef Q
#undef S
#undef F
#undef P
#undef M
#undef D
#undef N
#undef T
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 660.29 ms | 149 MB + 260 KB | Accepted | Score: 100 | 显示更多 |