// DUCK_PUBLIC_SURROGATE_BENCHMARK
// Adapted from Duck public submissions141230 and141068, with their inherited techniques.
// Sources: https://duck.ac/submission/141230 https://duck.ac/submission/141068
// FFT originally by TSKY (WithSky), https://github.com/With-Sky/HintFFT.
// Full inherited source/author notices are retained in the distributed headers.
/* MIT License -- HintFFT by TSKY (WithSky)
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. */
#define AA __m256i
#define AB _mm256_set1_epi32
#define AC unsigned
#define AD __m128i
#define AE _mm_loadu_si128
#define AF _mm256_add_epi32
#define AG const
#define AH _mm256_permute2x128_si256
#define AI ldu256
#define AJ static
#define AK return
#define AL _mm256_shuffle_epi32
#define AM __builtin_prefetch
#define AN size_t
#define AO _mm256_sub_epi32
#define AP constexpr
#define AQ float_len
#define AR reinterpret_cast
#define AS _mm256_min_epu32
#define AT _mm256_blend_epi32
#define AU _mm256_mul_epu32
#define AV _mm256_castsi256_si128
#define AW stu256
#define AX _mm256_bsrli_epi128
#define AY template
#define AZ stride
#define BA _mm_storeu_si128
#define BB _mm256_permute2f128_pd
#define BC fft_len
#define BD fast_e7_field
#define BE _mm256_set1_epi64x
#define BF in_out
#define BG C64X4
#define BH __attribute__
#define BI _mm256_permutevar8x32_epi32
#define BJ _mm256_mullo_epi32
#define BK transform2
#define BL _mm256_castpd_si256
#define BM typename
#define BN inline
#define BO getBegin
#define BP transpose64_4X4
#define BQ _mm256_add_epi64
#define BR _mm_prefetch
#define BS multi_table_2
#define BU FROM_RIRI_PERM
#define BV vaddm
#define BW _mm_bsrli_si128
#define BX Float64
#define BY uint32_t
#define BZ __m256d
#define CA _MM_HINT_T0
#define CB merge4_dit_h
#define CC LazyOutput
#define CD integral_constant
#define CE uint64_t
#define CF operator
#define CG double
#define CH _mm_mul_epu32
#define CI _mm256_sub_epi64
#define CJ small_product
#define CK _mm256_loadu_si256
#define CL Complex64X4
#define CM mulConj
#define CN FFTSqrtTableC64X4
#define CO _mm256_setzero_si256
#define CP static_cast
#define CQ _mm256_storeu_si256
#define CR NoInitTag
#define CS multi_table_mid2
#define CT multi_table_mid3
#define CU Float
#define CW padpos
#define CX swap_context
#define CY check_divisibility
#define CZ _mm256_unpacklo_pd
#define DA _mm256_unpackhi_pd
#define DB sqrt_table_1
#define DC namespace
#define DD F64X4
#define DE _mm_sub_epi32
#define DF merge4_h1v
#define DG paddedA
#define DH CACHE_LOG_LEN
#define DI multi_table_3
#define DJ vsubm
#define DK begin
#define DL FFTAVX
#define DM Float64X4
#define DN _mm256_set1_pd
#define DO powmod
#define DP full_product
#define DQ TO_RIRI_PERM
#define DR _mm_add_epi32
#define DS __builtin_ctz
#define DT _mm256_add_pd
#define DU store
#define DV TableFixMulti
#define DW multi_table_1
#define DX _mm256_or_si256
#define DY _mm256_cmpeq_epi32
#define DZ stage4_dif_h
#define EA g_pmdelta
#define EB using
#define EC _mm256_load_pd
#define ED hint_log2
#define EE LOG_BEGIN
#define EF ntst256
#define EG _mm256_setr_epi32
#define EH inverse
#define EI scratch
#define EJ mulmod
#define EK _mm256_inserti128_si256
#define EL false
#define EM g_cisI
#define EN _mm_min_epu32
#define EO _mm256_castsi128_si256
#define EP always_inline
#define EQ ntt_inv_batch
#define ER AlignedBuffer
#define ES binary_layout
#define ET AlignMem
#define EU transToI64
#define EV certifiedRoot
#define EW omega1
#define EX g_generator
#define EY _mm256_unpacklo_epi32
#define EZ _mm256_unpackhi_epi32
#define FA _mm256_unpacklo_epi64
#define FB _mm256_unpackhi_epi64
#define FC shoup_c
#define FD merge4_h1v_lazy
#define FE _mm256_fmadd_pd
#define FF log_len
#define FG butterflyCommon
#define FH store_padded
#define FI SavedContext
#define FJ immintrin
#define FK g_shmagic
#define FL transpose4
#define FM primitive_root
#define FN initialize
#define FO tiny_transform
#define FP normalize
#define FQ prefix_context
#define FR ThreeField
#define FS Storage
#define FT factor
#define FU SHORT_LEN
#define FW LOG_SHORT
#define FX MID_LEN
#define FY difRecLong
#define FZ MiddlePlan
#define GA _MM_SHUFFLE
#define GB capacity
#define GC active_p
#define GD load_padded
#define GE offset
#define GF rotate
#define GG paired_leaf
#define GH table1
#define GI iditRecLong
#define GJ other
#define GK _mm256_mul_pd
#define GL static_assert
#define GM trans2MulNegI
#define GN bc128
#define GO e7z3_minn
#define GP idit_func
#define GQ struct
#define GR gen_geo
#define GS nullptr
#define GT reserve
#define GU active_n
#define GV explicit
#define GW FFTTableSqrt
#define GX omega2
#define GY TO_INT64
#define GZ g_cisF
#define HA public
#define HB gen_geo_val
#define HC count
#define HD cyclic_impl
#define HE ntt_forward
#define HF ntt_inverse
#define HG block
#define HH int64_t
#define HI initOmegaX4
#define HJ getBeginLog
#define HK TableMulti1
#define HL TableMulti2
#define HM TableMulti3
#define HN duck_sha256
#define HO sub_lazy4
#define HP e7z3_pmn
#define HQ cross
#define HR table_len
#define HS CACHE_LEN
#define HT TableLong
#define HU iditSplit
#define HV dif_func
#define HW difRecMid
#define HX vector
#define HY g_ciI
#define HZ wanted
#define IA in_data
#define IB reverse
#define IC LOG_MAX
#define ID g_pinv
#define IE store_nt
#define IF TableFix
#define IG table
#define IH log_rank
#define II difSplit
#define IJ FromRIRI
#define IK result
#define IL compress
#define IM paddedB
#define IN class
#define IO LOG_MID
#define IP value
#define IQ der_ws
#define IR assert
#define IS sizeof
#define IT middle
#define IU scale
#define IV while
#define IW vmulhi
#define IX blocks
#define IY tableF
#define IZ tableI
#define JA delete
#define JB table2
#define JC table3
#define JD ToRIRI
#define JE g_ciF
#define JF g_odd
#define JG apply
#define JH index
#define JI shift
#define JJ magic
#define JK g_mod
#define JL idit4
#define JM omega
#define JN gamma
#define JO void
#define JP g_Sb
#define JQ g_nb
#define JR g_TF
#define JS g_TI
#define JT long
#define JU high
#define JV nsub
#define JW else
#define JX char
#define JY bool
#define JZ true
#define KA root
#define KB base
#define KC imag
#define KD mask
#define KE swap
#define KF data
#define KG size
#define KH bits
#define KI next
#define KJ rank
#define KK auto
#define KL row0
#define KM row1
#define KN load
#define KO tail
#define KP real
#define KQ dif4
#define KR indx
#define KS YMM
#define KT sum
#define KU end
#define KV it3
#define KW mpa
#define KX pv4
#define KY dst
#define KZ off
#define LA it2
#define LB cis
#define LC it0
#define LD it1
#define LE F64
#define LF len
#define LG u64
#define LH mpb
#define LI out
#define LJ cIs
#define LK mul
#define LL std
#define LM int
#define LN for
#define LO u32
#pragma once
#include <array>
#pragma once
#include <immintrin.h>
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <algorithm>
#pragma GCC push_options
DC BD{
AJ BY JK=2013265921u,EX=31u,FK=572662301u,g_shint=2u;
#define NTT_MAXN (1u<<25)
#pragma GCC optimize("O3,rename-registers")
#include <immintrin.h>
#include <cstdint>
#include <cstring>
#include <cstdlib>
BH((target("avx2")))AJ BN AA AI(AG JO*p){
AA r;
__asm__("vmovdqu %1, %0":"=x"(r):"m"(*(AG AA*)p));
AK r;
}
BH((target("avx2")))AJ BN JO AW(JO*p,AA v){
__asm__("vmovdqu %1, %0":"=m"(*(AA*)p):"x"(v));
}
typedef BY LO;
typedef CE LG;
#define PF_DIST 192
#define NTP JK
#define TPAD 704u
#define TOPPAD 128u
AJ BN LO CW(LO i){
AK i+TOPPAD*((i>>20)+(i>>18)+(i>>16)+(i>>14));
}
#define PADJUMP() if (j >= nxt) { if (j >= nxt0) { bp += TOPPAD; nxt0 += (1u << 20); } \
if (j >= nxt1) { bp += TOPPAD; nxt1 += (1u << 18); } \
if (j >= nxt2) { bp += TOPPAD; nxt2 += (1u << 16); } \
if (j >= nxt3) { bp += TOPPAD; nxt3 += (1u << 14); } \
nxt = nxt0; if (nxt1 < nxt) nxt = nxt1; if (nxt2 < nxt) nxt = nxt2; if (nxt3 < nxt) nxt = nxt3; }
#define PADJUMP_S() if (s >= nxt) { if (s >= nxt0) { bp += TOPPAD; nxt0 += (1u << 20); } \
if (s >= nxt1) { bp += TOPPAD; nxt1 += (1u << 18); } \
if (s >= nxt2) { bp += TOPPAD; nxt2 += (1u << 16); } \
if (s >= nxt3) { bp += TOPPAD; nxt3 += (1u << 14); } \
nxt = nxt0; if (nxt1 < nxt) nxt = nxt1; if (nxt2 < nxt) nxt = nxt2; if (nxt3 < nxt) nxt = nxt3; }
#define TGT BH((target("avx2")))
AJ LO g_scale_digit[10];
AJ LO g_scale_lo[8]BH((aligned(32)));
AJ LO g_scale_hi[8]BH((aligned(32)));
#ifndef NTT_MAXN
#define NTT_MAXN (1u << 25)
#endif
AJ LO g_n,JP;
AJ LO ID;
AJ LM g_log2n,g_L,JF,JQ,g_BT=13;
AJ LO JE,GZ,HY,EM;
AJ LO*g_tabF;
#define Q_T5OFF (5 * NTT_MAXN / 2 + 4096 - 4 * (1u << 22))
#define Q_SCF (g_tabF + 2*g_n + 131072u)
#define Q_SCI (g_tabI + 2*g_n + 131072u)
AJ LO*g_tabI;
GQ Tabs{
AG LO*l1[40],*l2[40],*l3[40],*m1[40],*m2[40],*m3[40];
AG LO*b2,*b2s;
AG LO*h1[40],*h2[40],*h3[40],*q1[40],*q2[40],*q3[40];
}
;
AJ Tabs JR,JS;
AJ BN LO EJ(LO a,LO b){
AK(LO)((LG)a*b%NTP);
}
AJ LO DO(LO a,LO e){
LO r=1;
IV(e){
if(e&1)r=EJ(r,a);
a=EJ(a,a);
e>>=1;
}
AK r;
}
#define RRW ((LO)((1ull<<32)%NTP))
AJ LO g_wf,g_wif;
AJ BN LO FC(LO w){
AK(LO)(((LG)w<<32)/NTP);
}
TGT AJ BN AA IW(AA a,AA b){
AA e=AU(a,b);
AA o=AU(AX(a,4),AX(b,4));
e=AX(e,4);
AK AT(e,o,0xAA);
}
TGT AJ BN AA vmont(AA a,AA b,AA pv){
AG AA pinv=AB((LM)ID);
AA tlo=BJ(a,b);
AA thi=IW(a,b);
AA m=BJ(tlo,pinv);
AA mhi=IW(m,pv);
AA nz=_mm256_andnot_si256(DY(tlo,CO()),AB(1));
AA u=AF(AF(thi,mhi),nz);
AK AS(u,AO(u,pv));
}
TGT AJ BN AA KW(AA a,AA b,AA pv){
AG AA np=BE((JT JT)ID);
AG AA p64=BE((JT JT)NTP);
AA ae=AU(a,b);
AA ao=AU(AX(a,4),AX(b,4));
AA me=AU(ae,np),mo=AU(ao,np);
ae=BQ(ae,AU(me,p64));
ao=BQ(ao,AU(mo,p64));
AA IP=DX(AX(ae,4),ao);
AK AS(IP,AO(IP,pv));
}
TGT AJ BN AA LH(AA a,AA b,AA bpi,AA pv){
AG AA p64=BE((JT JT)NTP);
AA ae=AU(a,b);
AA ao=AU(AX(a,4),AX(b,4));
AA me=AU(a,bpi),mo=AU(AX(a,4),AX(bpi,4));
ae=BQ(ae,AU(me,p64));
ao=BQ(ao,AU(mo,p64));
AA IP=DX(AX(ae,4),ao);
AK AS(IP,AO(IP,pv));
}
TGT AJ BN AD mpc(AD a,AD b,AD bpi,AD pv){
AG AD p64=_mm_set1_epi64x((JT JT)NTP);
AD ae=CH(a,b);
AD ao=CH(BW(a,4),BW(b,4));
AD me=CH(a,bpi),mo=CH(BW(a,4),BW(bpi,4));
ae=_mm_add_epi64(ae,CH(me,p64));
ao=_mm_add_epi64(ao,CH(mo,p64));
AD IP=_mm_or_si128(BW(ae,4),ao);
AK EN(IP,DE(IP,pv));
}
#define MLO_V FK
TGT AJ BN AA IQ(AA w){
AA q=AF(BJ(w,AB(g_shint)),IW(w,AB((LM)FK)));
AA q1=AF(q,AB(1)),p=AB((LM)NTP);
AA JU=IW(q1,p),low=BJ(q1,p),zero=CO();
AA correction=DX(_mm256_xor_si256(DY(JU,w),AB(-1)),DY(low,zero));
AK AF(q,_mm256_and_si256(correction,AB(1)));
}
TGT AJ BN AA vS(AA a,AA w,AA ws,AA pv){
AA t=BJ(a,w);
AA q=IW(a,ws);
AA r=AO(t,BJ(q,pv));
AK AS(r,AO(r,pv));
}
TGT AJ BN AA BV(AA a,AA b,AA pv){
AA s=AF(a,b);
AK AS(s,AO(s,pv));
}
TGT AJ BN AA DJ(AA a,AA b,AA pv){
AA d=AO(a,b);
AK AS(d,AF(d,pv));
}
TGT AJ BN AD vmulhi4(AD a,AD b){
AD e=CH(a,b);
AD o=CH(BW(a,4),BW(b,4));
e=BW(e,4);
AK _mm_blend_epi32(e,o,0xAA);
}
TGT AJ BN AD sh4(AD a,AD w,AD ws,AD pv){
AD t=_mm_mullo_epi32(a,w);
AD q=vmulhi4(a,ws);
AD r=DE(t,_mm_mullo_epi32(q,pv));
AK EN(r,DE(r,pv));
}
TGT AJ BN AD add4(AD a,AD b,AD pv){
AD s=DR(a,b);
AK EN(s,DE(s,pv));
}
TGT AJ BN AD sub4(AD a,AD b,AD pv){
AD d=DE(a,b);
AK EN(d,DR(d,pv));
}
TGT AJ BN AA ld2(AG AD*lo,AG AD*hi){
AK EK(EO(AE(lo)),AE(hi),1);
}
TGT AJ BN JO st2(AD*lo,AD*hi,AA v){
BA(lo,AV(v));
BA(hi,_mm256_extracti128_si256(v,1));
}
TGT AJ BN AA GN(AD v){
AK EK(EO(v),v,1);
}
TGT AJ BN AA vL(AA a,AA b,AA pv){
AK AF(AO(a,b),pv);
}
TGT AJ BN AD HO(AD a,AD b,AD pv){
AK DR(DE(a,b),pv);
}
TGT AJ JO stage4_dif_t(LO*a,LO blk,LO h,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<blk;
i+=4*h){
LO*p=a+i;
LO j=0;
LN(;
j+16<=h;
j+=16){
AA x0=AI((p+j));
AA x1=AI((p+j+h));
AA x2=AI((p+j+2*h));
AA x3=AI((p+j+3*h));
AA y0=AI((p+j+8));
AA y1=AI((p+j+h+8));
AA y2=AI((p+j+2*h+8));
AA y3=AI((p+j+3*h+8));
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA A2=BV(y0,y2,pv),B2=DJ(y0,y2,pv);
AA C2=BV(y1,y3,pv),D2=vL(y1,y3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA v0=BV(A2,C2,pv),v2=vL(A2,C2,pv);
AA E=vS(D,cI,LJ,pv);
AA F=vS(D2,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
AA v1=AF(B2,F),v3=vL(B2,F,pv);
{
u1=KW(u1,AI((t1+j)),pv);
}
{
u2=KW(u2,AI((t2+j)),pv);
}
{
u3=KW(u3,AI((t3+j)),pv);
}
{
v1=KW(v1,AI((t1+j+8)),pv);
}
{
v2=KW(v2,AI((t2+j+8)),pv);
}
{
v3=KW(v3,AI((t3+j+8)),pv);
}
AW((p+j),u0);
AW((p+j+h),u1);
AW((p+j+2*h),u2);
AW((p+j+3*h),u3);
AW((p+j+8),v0);
AW((p+j+h+8),v1);
AW((p+j+2*h+8),v2);
AW((p+j+3*h+8),v3);
}
LN(;
j+8<=h;
j+=8){
AM(p+j+192);
AM(p+j+h+192);
AM(p+j+2*h+192);
AM(p+j+3*h+192);
AA x0=AI((p+j));
AA x1=AI((p+j+h));
AA x2=AI((p+j+2*h));
AA x3=AI((p+j+3*h));
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA E=vS(D,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
{
u1=KW(u1,AI((t1+j)),pv);
}
{
u2=KW(u2,AI((t2+j)),pv);
}
{
u3=KW(u3,AI((t3+j)),pv);
}
AW((p+j),u0);
AW((p+j+h),u1);
AW((p+j+2*h),u2);
AW((p+j+3*h),u3);
}
}
}
AY<LM H>TGT AJ JO DZ(LO*a,LO blk,LO _h,AG LO*tb,LO ci,LO LB){
AG LO MP=H+TPAD;
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<blk;
i+=4*H){
LO*q0=a+i;
AG LO*w=tb;
LO j=0;
LN(;
j+16<=H;
j+=16,q0+=16,w+=16){
AM(q0+192);
AM(q0+H+192);
AM(q0+2*H+192);
AM(q0+3*H+192);
AA x0=AI(q0),x1=AI(q0+H),x2=AI(q0+2*H),x3=AI(q0+3*H);
AA y0=AI(q0+8),y1=AI(q0+H+8),y2=AI(q0+2*H+8),y3=AI(q0+3*H+8);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA A2=BV(y0,y2,pv),B2=DJ(y0,y2,pv);
AA C2=BV(y1,y3,pv),D2=vL(y1,y3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA v0=BV(A2,C2,pv),v2=vL(A2,C2,pv);
AA E=vS(D,cI,LJ,pv),F=vS(D2,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
AA v1=AF(B2,F),v3=vL(B2,F,pv);
u1=LH(u1,AI(w),AI(w+3*MP),pv);
u2=LH(u2,AI(w+MP),AI(w+4*MP),pv);
u3=LH(u3,AI(w+2*MP),AI(w+5*MP),pv);
v1=LH(v1,AI(w+8),AI(w+3*MP+8),pv);
v2=LH(v2,AI(w+MP+8),AI(w+4*MP+8),pv);
v3=LH(v3,AI(w+2*MP+8),AI(w+5*MP+8),pv);
AW(q0,u0);
AW(q0+H,u1);
AW(q0+2*H,u2);
AW(q0+3*H,u3);
AW(q0+8,v0);
AW(q0+H+8,v1);
AW(q0+2*H+8,v2);
AW(q0+3*H+8,v3);
}
LN(;
j+8<=H;
j+=8,q0+=8,w+=8){
AM(q0+192);
AM(q0+H+192);
AM(q0+2*H+192);
AM(q0+3*H+192);
AA x0=AI(q0),x1=AI(q0+H),x2=AI(q0+2*H),x3=AI(q0+3*H);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA E=vS(D,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
u1=LH(u1,AI(w),AI(w+3*MP),pv);
u2=LH(u2,AI(w+MP),AI(w+4*MP),pv);
u3=LH(u3,AI(w+2*MP),AI(w+5*MP),pv);
AW(q0,u0);
AW(q0+H,u1);
AW(q0+2*H,u2);
AW(q0+3*H,u3);
}
}
}
TGT AJ BN JO FL(AA&a,AA&b,AA&c,AA&d){
AA t0=EY(a,b),t1=EZ(a,b),t2=EY(c,d),t3=EZ(c,d);
a=FA(t0,t2);
b=FB(t0,t2);
c=FA(t1,t3);
d=FB(t1,t3);
}
TGT AJ JO dh1(LO*a,LO blk,LO ci,LO LB);
AJ JT EA=0;
#define E7Z3_PM_ON() (EA != 0)
TGT AJ BN AA GO(AA u,AA pv){
AK AS(u,AO(u,pv));
}
TGT AJ BN AA HP(AA u,AG LO*p,AA pv){
AK KW(ld2((AG AD*)(p),(AG AD*)(p+16)),u,pv);
}
TGT BH((EP))AJ BN JO dh4(LO*a,LO JV,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
if(JV<32){
AG AD KX=AV(pv),cI4=AV(cI),cIs4=AV(LJ);
AD W1=AE((AG AD*)t1);
AD WS1=AE((AG AD*)s1);
AD W2=AE((AG AD*)t2);
AD WS2=AE((AG AD*)s2);
AD W3=AE((AG AD*)t3);
AD WS3=AE((AG AD*)s3);
LN(LO i=0;
i<JV;
i+=16){
LO*p=a+i;
AD x0=AE((AG AD*)(p));
AD x1=AE((AG AD*)(p+4));
AD x2=AE((AG AD*)(p+8));
AD x3=AE((AG AD*)(p+12));
AD A=add4(x0,x2,KX),B=sub4(x0,x2,KX);
AD C=add4(x1,x3,KX),D=HO(x1,x3,KX);
AD u0=add4(A,C,KX),u2=HO(A,C,KX);
AD E=sh4(D,cI4,cIs4,KX);
AD u1=DR(B,E),u3=HO(B,E,KX);
u1=mpc(u1,W1,WS1,KX);
u2=mpc(u2,W2,WS2,KX);
u3=mpc(u3,W3,WS3,KX);
BA((AD*)(p),u0);
BA((AD*)(p+4),u1);
BA((AD*)(p+8),u2);
BA((AD*)(p+12),u3);
}
dh1(a,JV,ci,LB);
AK;
}
AA W1=GN(AE((AG AD*)t1));
AA WS1=GN(AE((AG AD*)s1));
AA W2=GN(AE((AG AD*)t2));
AA WS2=GN(AE((AG AD*)s2));
AA W3=GN(AE((AG AD*)t3));
AA WS3=GN(AE((AG AD*)s3));
if(EA==0){
#pragma GCC unroll 2
LN(LO i=0,*p=a;
i<JV;
i+=32,p+=32){
AA x0=ld2((AG AD*)(p),(AG AD*)(p+16));
AA x1=ld2((AG AD*)(p+4),(AG AD*)(p+20));
AA x2=ld2((AG AD*)(p+8),(AG AD*)(p+24));
AA x3=ld2((AG AD*)(p+12),(AG AD*)(p+28));
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA E=vS(D,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
u1=LH(u1,W1,WS1,pv);
u2=LH(u2,W2,WS2,pv);
u3=LH(u3,W3,WS3,pv);
FL(u0,u1,u2,u3);
{
AA A4=BV(u0,u2,pv),B4=DJ(u0,u2,pv),C4=BV(u1,u3,pv),D4=vL(u1,u3,pv),E4=vS(D4,cI,LJ,pv);
u0=BV(A4,C4,pv);
u2=vL(A4,C4,pv);
u1=AF(B4,E4);
u3=vL(B4,E4,pv);
FL(u0,u1,u2,u3);
}
u0=GO(u0,pv);
u1=GO(u1,pv);
u2=GO(u2,pv);
u3=GO(u3,pv);
st2((AD*)(p),(AD*)(p+16),u0);
st2((AD*)(p+4),(AD*)(p+20),u1);
st2((AD*)(p+8),(AD*)(p+24),u2);
st2((AD*)(p+12),(AD*)(p+28),u3);
}
}
JW{
#pragma GCC unroll 2
LN(LO i=0,*p=a,*pd=(LO*)((JX*)a+EA);
i<JV;
i+=32,p+=32,pd+=32){
AA x0=ld2((AG AD*)(p),(AG AD*)(p+16));
AA x1=ld2((AG AD*)(p+4),(AG AD*)(p+20));
AA x2=ld2((AG AD*)(p+8),(AG AD*)(p+24));
AA x3=ld2((AG AD*)(p+12),(AG AD*)(p+28));
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA E=vS(D,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
u1=LH(u1,W1,WS1,pv);
u2=LH(u2,W2,WS2,pv);
u3=LH(u3,W3,WS3,pv);
FL(u0,u1,u2,u3);
{
AA A4=BV(u0,u2,pv),B4=DJ(u0,u2,pv),C4=BV(u1,u3,pv),D4=vL(u1,u3,pv),E4=vS(D4,cI,LJ,pv);
u0=BV(A4,C4,pv);
u2=vL(A4,C4,pv);
u1=AF(B4,E4);
u3=vL(B4,E4,pv);
FL(u0,u1,u2,u3);
}
u0=HP(u0,pd,pv);
u1=HP(u1,pd+4,pv);
u2=HP(u2,pd+8,pv);
u3=HP(u3,pd+12,pv);
st2((AD*)(pd),(AD*)(pd+16),u0);
st2((AD*)(pd+4),(AD*)(pd+20),u1);
st2((AD*)(pd+8),(AD*)(pd+24),u2);
st2((AD*)(pd+12),(AD*)(pd+28),u3);
}
}
}
TGT AJ JO dh1(LO*a,LO blk,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<blk;
i+=8){
LO*p=a+i;
AA x=AI(p);
AA t=AL(x,GA(1,0,3,2));
AA s=BV(x,t,pv);
AA d=DJ(x,t,pv);
AA Z=AL(d,0x00);
AA P=AT(s,Z,0xAA);
AA E=vS(d,cI,LJ,pv);
AA E2=AL(E,0x55);
AA W=AL(s,0x55);
AA Q=AT(W,E2,0xAA);
AA KT=BV(P,Q,pv);
AA dif=DJ(P,Q,pv);
AW(p,AT(KT,dif,0xCC));
}
}
TGT AJ JO stage2_dif(LO*a,LO blk,AG LO*t,AG LO*s){
AG AA pv=AB((LM)NTP);
LO h=blk>>1;
LN(LO j=0;
j<h;
j+=8){
AA x0=AI((a+j));
AA x1=AI((a+j+h));
AA u0=BV(x0,x1,pv);
AA u1=KW(DJ(x0,x1,pv),AI((t+j)),pv);
AW((a+j),u0);
AW((a+j+h),u1);
}
}
TGT AJ JO merge4_dit_t(LO*a,LO blk,LO h,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<blk;
i+=4*h){
LO*p=a+i;
LN(LO j=0;
j<h;
j+=8){
AA x0=AI((p+j));
AA x1=AI((p+j+h));
AA x2=AI((p+j+2*h));
AA x3=AI((p+j+3*h));
{
x1=KW(x1,AI((t1+j)),pv);
}
{
x2=KW(x2,AI((t2+j)),pv);
}
{
x3=KW(x3,AI((t3+j)),pv);
}
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA E=vS(D,cI,LJ,pv);
AW((p+j),BV(A,C,pv));
AW((p+j+h),BV(B,E,pv));
AW((p+j+2*h),DJ(A,C,pv));
AW((p+j+3*h),DJ(B,E,pv));
}
}
}
AY<LM H,JY CC=EL>TGT AJ JO CB(LO*a,LO blk,LO _h,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG LO MP=H+TPAD;
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
(JO)t2;
(JO)t3;
(JO)s1;
(JO)s2;
(JO)s3;
LN(LO i=0;
i<blk;
i+=4*H){
LO*q0=a+i;
AG LO*w=t1;
LO j=0;
LN(;
j<H;
j+=16,q0+=16,w+=16){
AM(q0+192);
AM(q0+H+192);
AM(q0+2*H+192);
AM(q0+3*H+192);
AA x0=AI(q0),y0=AI(q0+8);
AA x1=AI(q0+H),y1=AI(q0+H+8);
AA x2=AI(q0+2*H),y2=AI(q0+2*H+8);
AA x3=AI(q0+3*H),y3=AI(q0+3*H+8);
x1=LH(x1,AI(w),AI(w+3*MP),pv);
y1=LH(y1,AI(w+8),AI(w+3*MP+8),pv);
x2=LH(x2,AI(w+MP),AI(w+4*MP),pv);
y2=LH(y2,AI(w+MP+8),AI(w+4*MP+8),pv);
x3=LH(x3,AI(w+2*MP),AI(w+5*MP),pv);
y3=LH(y3,AI(w+2*MP+8),AI(w+5*MP+8),pv);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA A2=BV(y0,y2,pv),B2=DJ(y0,y2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA C2=BV(y1,y3,pv),D2=vL(y1,y3,pv);
AA E=vS(D,cI,LJ,pv),F=vS(D2,cI,LJ,pv);
AW(q0,(CC?AF(A,C):BV(A,C,pv)));
AW(q0+8,(CC?AF(A2,C2):BV(A2,C2,pv)));
AW(q0+H,(CC?AF(B,E):BV(B,E,pv)));
AW(q0+H+8,(CC?AF(B2,F):BV(B2,F,pv)));
AW(q0+2*H,(CC?vL(A,C,pv):DJ(A,C,pv)));
AW(q0+2*H+8,(CC?vL(A2,C2,pv):DJ(A2,C2,pv)));
AW(q0+3*H,(CC?vL(B,E,pv):DJ(B,E,pv)));
AW(q0+3*H+8,(CC?vL(B2,F,pv):DJ(B2,F,pv)));
}
LN(;
j<H;
j+=8,q0+=8,w+=8){
AA x0=AI(q0),x1=AI(q0+H),x2=AI(q0+2*H),x3=AI(q0+3*H);
x1=LH(x1,AI(w),AI(w+3*MP),pv);
x2=LH(x2,AI(w+MP),AI(w+4*MP),pv);
x3=LH(x3,AI(w+2*MP),AI(w+5*MP),pv);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA E=vS(D,cI,LJ,pv);
AW(q0,(CC?AF(A,C):BV(A,C,pv)));
AW(q0+H,(CC?AF(B,E):BV(B,E,pv)));
AW(q0+2*H,(CC?vL(A,C,pv):DJ(A,C,pv)));
AW(q0+3*H,(CC?vL(B,E,pv):DJ(B,E,pv)));
}
}
}
TGT AJ JO merge4_dit_h4(LO*a,LO JV,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
if(JV<32){
AG AD KX=AV(pv),cI4=AV(cI),cIs4=AV(LJ);
AD W1=AE((AG AD*)t1);
AD WS1=AE((AG AD*)s1);
AD W2=AE((AG AD*)t2);
AD WS2=AE((AG AD*)s2);
AD W3=AE((AG AD*)t3);
AD WS3=AE((AG AD*)s3);
LN(LO i=0;
i<JV;
i+=16){
LO*p=a+i;
AD x0=AE((AG AD*)(p));
AD x1=mpc(AE((AG AD*)(p+4)),W1,WS1,KX);
AD x2=mpc(AE((AG AD*)(p+8)),W2,WS2,KX);
AD x3=mpc(AE((AG AD*)(p+12)),W3,WS3,KX);
AD A=add4(x0,x2,KX),B=sub4(x0,x2,KX);
AD C=add4(x1,x3,KX),D=sub4(x1,x3,KX);
AD E=sh4(D,cI4,cIs4,KX);
BA((AD*)(p),add4(A,C,KX));
BA((AD*)(p+4),add4(B,E,KX));
BA((AD*)(p+8),sub4(A,C,KX));
BA((AD*)(p+12),sub4(B,E,KX));
}
AK;
}
AA W1=GN(AE((AG AD*)t1));
AA WS1=GN(AE((AG AD*)s1));
AA W2=GN(AE((AG AD*)t2));
AA WS2=GN(AE((AG AD*)s2));
AA W3=GN(AE((AG AD*)t3));
AA WS3=GN(AE((AG AD*)s3));
LN(LO i=0;
i<JV;
i+=32){
LO*p=a+i;
AA x0=ld2((AG AD*)(p),(AG AD*)(p+16));
AA x1=ld2((AG AD*)(p+4),(AG AD*)(p+20));
AA x2=ld2((AG AD*)(p+8),(AG AD*)(p+24));
AA x3=ld2((AG AD*)(p+12),(AG AD*)(p+28));
x1=LH(x1,W1,WS1,pv);
x2=LH(x2,W2,WS2,pv);
x3=LH(x3,W3,WS3,pv);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA E=vS(D,cI,LJ,pv);
st2((AD*)(p),(AD*)(p+16),BV(A,C,pv));
st2((AD*)(p+4),(AD*)(p+20),BV(B,E,pv));
st2((AD*)(p+8),(AD*)(p+24),DJ(A,C,pv));
st2((AD*)(p+12),(AD*)(p+28),DJ(B,E,pv));
}
}
TGT AJ BN AA DF(AA x,AA pv,AA cI,AA LJ){
AA t=AL(x,GA(1,0,3,2)),sv=BV(x,t,pv),d=DJ(x,t,pv),Z=AL(d,0x00),P=AT(sv,Z,0xAA),E=vS(d,cI,LJ,pv),E2=AL(E,0x55),W=AL(sv,0x55),Q=AT(W,E2,0xAA),KT=BV(P,Q,pv),dif=DJ(P,Q,pv);
AK AT(KT,dif,0xCC);
}
TGT AJ BN AA FD(AA x,AA pv,AA cI,AA LJ){
AA t=AL(x,GA(1,0,3,2)),sv=BV(x,t,pv),d=DJ(x,t,pv),Z=AL(d,0x00),P=AT(sv,Z,0xAA),E=vS(d,cI,LJ,pv),E2=AL(E,0x55),W=AL(sv,0x55),Q=AT(W,E2,0xAA),KT=AF(P,Q),dif=vL(P,Q,pv);
AK AT(KT,dif,0xCC);
}
TGT AJ JO mhh(LO*a,LO JV,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB){
AG AA pv=AB((LM)NTP),cI=AB((LM)ci),LJ=AB((LM)LB);
AA W1=GN(AE((AG AD*)t1)),WS1=GN(AE((AG AD*)s1)),W2=GN(AE((AG AD*)t2)),WS2=GN(AE((AG AD*)s2)),W3=GN(AE((AG AD*)t3)),WS3=GN(AE((AG AD*)s3));
LN(LO i=0;
i+32<=JV;
i+=32){
LO*p=a+i;
AA g0=DF(AI((AG JO*)(p)),pv,cI,LJ),g1=DF(AI((AG JO*)(p+8)),pv,cI,LJ),g2=DF(AI((AG JO*)(p+16)),pv,cI,LJ),g3=DF(AI((AG JO*)(p+24)),pv,cI,LJ);
AA x0=AH(g0,g2,0x20),x1=AH(g0,g2,0x31),x2=AH(g1,g3,0x20),x3=AH(g1,g3,0x31);
x1=LH(x1,W1,WS1,pv);
x2=LH(x2,W2,WS2,pv);
x3=LH(x3,W3,WS3,pv);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv),C=BV(x1,x3,pv),D=vL(x1,x3,pv),E=vS(D,cI,LJ,pv);
st2((AD*)(p),(AD*)(p+16),BV(A,C,pv));
st2((AD*)(p+4),(AD*)(p+20),BV(B,E,pv));
st2((AD*)(p+8),(AD*)(p+24),DJ(A,C,pv));
st2((AD*)(p+12),(AD*)(p+28),DJ(B,E,pv));
}
LN(LO i=(JV&~31u);
i<JV;
i+=8){
LO*p=a+i;
AW((JO*)p,DF(AI((AG JO*)p),pv,cI,LJ));
}
}
#define H4B32(Q,R1,R2,R3,R4,LAZY) {AG LO*q=(Q);AA g0=DF(AI((AG JO*)(q)),pv,cI,LJ),g1=FD(AI((AG JO*)(q+8)),pv,cI,LJ),g2=DF(AI((AG JO*)(q+16)),pv,cI,LJ),g3=FD(AI((AG JO*)(q+24)),pv,cI,LJ);AA e0=AH(g0,g2,0x20),e1=AH(g0,g2,0x31),e2=AH(g1,g3,0x20),e3=AH(g1,g3,0x31);e1=LH(e1,W1,WS1,pv);e2=LH(e2,W2,WS2,pv);e3=LH(e3,W3,WS3,pv);AA a1=BV(e0,e2,pv),b1=DJ(e0,e2,pv),c1=BV(e1,e3,pv),d1=vL(e1,e3,pv),f1=vS(d1,cI,LJ,pv);if AP(LAZY){R1=AF(a1,c1);R2=AF(b1,f1);R3=vL(a1,c1,pv);R4=vL(b1,f1,pv);}JW{R1=BV(a1,c1,pv);R2=BV(b1,f1,pv);R3=DJ(a1,c1,pv);R4=DJ(b1,f1,pv);}}
TGT BH((EP))AJ BN JO mhh64(LO*a,LO JV,AG LO*t1,AG LO*t2,AG LO*t3,AG LO*s1,AG LO*s2,AG LO*s3,LO ci,LO LB,AG LO*u1,AG LO*u2,AG LO*u3,AG LO*v1,AG LO*v2,AG LO*v3){
AG AA pv=AB((LM)NTP),cI=AB((LM)ci),LJ=AB((LM)LB);
AG AA W1=GN(AE((AG AD*)t1)),WS1=GN(AE((AG AD*)s1)),W2=GN(AE((AG AD*)t2)),WS2=GN(AE((AG AD*)s2)),W3=GN(AE((AG AD*)t3)),WS3=GN(AE((AG AD*)s3));
LN(LO i=0,*p=a;
i+64<=JV;
i+=64,p+=64){
AA R1,R2,R3,R4,R1b,R2b,R3b,R4b;
H4B32(p,R1,R2,R3,R4,EL)H4B32(p+32,R1b,R2b,R3b,R4b,JZ)AA x0=AH(R1,R2,0x20),y0=AH(R3,R4,0x20),x1=AH(R1,R2,0x31),y1=AH(R3,R4,0x31),x2=AH(R1b,R2b,0x20),y2=AH(R3b,R4b,0x20),x3=AH(R1b,R2b,0x31),y3=AH(R3b,R4b,0x31);
x1=LH(x1,AI((AG JO*)(u1)),AI((AG JO*)(v1)),pv);
y1=LH(y1,AI((AG JO*)(u1+8)),AI((AG JO*)(v1+8)),pv);
x2=LH(x2,AI((AG JO*)(u2)),AI((AG JO*)(v2)),pv);
y2=LH(y2,AI((AG JO*)(u2+8)),AI((AG JO*)(v2+8)),pv);
x3=LH(x3,AI((AG JO*)(u3)),AI((AG JO*)(v3)),pv);
y3=LH(y3,AI((AG JO*)(u3+8)),AI((AG JO*)(v3+8)),pv);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv),A2=BV(y0,y2,pv),B2=DJ(y0,y2,pv),C=BV(x1,x3,pv),D=vL(x1,x3,pv),C2=BV(y1,y3,pv),D2=vL(y1,y3,pv),E=vS(D,cI,LJ,pv),F=vS(D2,cI,LJ,pv);
if(JV>=256u&&(JV&255u)==0u&&(i&192u)!=0u){
AW((JO*)(p),AF(A,C));
AW((JO*)(p+8),AF(A2,C2));
AW((JO*)(p+16),AF(B,E));
AW((JO*)(p+24),AF(B2,F));
AW((JO*)(p+32),vL(A,C,pv));
AW((JO*)(p+40),vL(A2,C2,pv));
AW((JO*)(p+48),vL(B,E,pv));
AW((JO*)(p+56),vL(B2,F,pv));
}
JW{
AW((JO*)(p),BV(A,C,pv));
AW((JO*)(p+8),BV(A2,C2,pv));
AW((JO*)(p+16),BV(B,E,pv));
AW((JO*)(p+24),BV(B2,F,pv));
AW((JO*)(p+32),DJ(A,C,pv));
AW((JO*)(p+40),DJ(A2,C2,pv));
AW((JO*)(p+48),DJ(B,E,pv));
AW((JO*)(p+56),DJ(B2,F,pv));
}
}
LN(LO i=(JV&~63u);
i<JV;
i+=8){
LO*p=a+i;
AW((JO*)p,DF(AI((AG JO*)p),pv,cI,LJ));
}
}
TGT AJ JO mh1(LO*a,LO blk,LO ci,LO LB){
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<blk;
i+=8){
LO*p=a+i;
AA x=AI(p);
AA t=AL(x,GA(1,0,3,2));
AA s=BV(x,t,pv);
AA d=DJ(x,t,pv);
AA Z=AL(d,0x00);
AA P=AT(s,Z,0xAA);
AA E=vS(d,cI,LJ,pv);
AA E2=AL(E,0x55);
AA W=AL(s,0x55);
AA Q=AT(W,E2,0xAA);
AA KT=BV(P,Q,pv);
AA dif=DJ(P,Q,pv);
AW(p,AT(KT,dif,0xCC));
}
}
TGT AJ JO merge2_dit(LO*a,LO blk,AG LO*t,AG LO*s){
AG AA pv=AB((LM)NTP);
LO h=blk>>1;
LN(LO j=0;
j<h;
j+=8){
AA x0=AI((a+j));
AA x1=KW(AI((a+j+h)),AI((t+j)),pv);
AW((a+j),BV(x0,x1,pv));
AW((a+j+h),DJ(x0,x1,pv));
}
}
TGT AJ BN JO EF(JO*p,AA v){
if(((uintptr_t)p&31u)==0)_mm256_stream_si256((AA*)p,v);
JW AW(p,v);
}
TGT AJ JO HB(LO*KY,LO cnt,LO v0,LO r);
TGT AJ JO GR(LO*KY,LO*sc,LO cnt,LO v0,LO r){
if(!sc){
HB(KY,cnt,v0,r);
AK;
}
if(!cnt)AK;
if(cnt<32){
LO x=v0%NTP;
LN(LO i=0;
i<cnt;
i++){
KY[i]=x;
sc[i]=FC(x);
x=EJ(x,r);
}
AK;
}
AG AA pv=AB((LM)NTP);
AG AA mlo=AB((LM)FK);
LO seq[32],cur=v0%NTP;
LN(LM i=0;
i<32;
i++){
seq[i]=cur;
cur=EJ(cur,r);
}
if(v0!=1u)cur=DO(r,32);
LO rs=FC(cur);
AG AA rv=AB((LM)cur);
AG AA rsv=AB((LM)rs);
AA a=AI(seq),b=AI(seq+8),c=AI(seq+16),d=AI(seq+24);
LO i=0;
LN(;
i+32<=cnt;
i+=32){
EF(KY+i,a);
EF(KY+i+8,b);
EF(KY+i+16,c);
EF(KY+i+24,d);
EF(sc+i,IQ(a));
EF(sc+i+8,IQ(b));
EF(sc+i+16,IQ(c));
EF(sc+i+24,IQ(d));
a=vS(a,rv,rsv,pv);
b=vS(b,rv,rsv,pv);
c=vS(c,rv,rsv,pv);
d=vS(d,rv,rsv,pv);
}
if(i<cnt){
LO x=EJ(v0,DO(r,i));
LN(;
i<cnt;
i++){
KY[i]=x;
sc[i]=FC(x);
x=EJ(x,r);
}
}
}
TGT AJ JO HB(LO*KY,LO cnt,LO v0,LO r){
if(!cnt)AK;
if(cnt<32){
LO x=v0%NTP;
LN(LO i=0;
i<cnt;
i++){
KY[i]=x;
x=EJ(x,r);
}
AK;
}
AG AA pv=AB((LM)NTP);
LO seq[32],cur=v0%NTP;
LN(LM i=0;
i<32;
i++){
seq[i]=cur;
cur=EJ(cur,r);
}
if(v0!=1u)cur=DO(r,32);
if(v0!=1u)cur=DO(r,32);
LO rs=FC(cur);
AG AA rv=AB((LM)cur);
AG AA rsv=AB((LM)rs);
AA a=AI(seq),b=AI(seq+8),c=AI(seq+16),d=AI(seq+24);
LO i=0;
LN(;
i+32<=cnt;
i+=32){
EF(KY+i,a);
EF(KY+i+8,b);
EF(KY+i+16,c);
EF(KY+i+24,d);
a=vS(a,rv,rsv,pv);
b=vS(b,rv,rsv,pv);
c=vS(c,rv,rsv,pv);
d=vS(d,rv,rsv,pv);
}
if(i<cnt){
LO x=EJ(v0,DO(r,i));
LN(;
i<cnt;
i++){
KY[i]=x;
x=EJ(x,r);
}
}
}
AJ JO build_tabs(Tabs&T,LO*tab,LO n,LO Sb,LM L,LM odd,LO KA,LO*scbase,LO skipsc){
LO*p=tab;
LO*sp=scbase;
LO S=n;
LN(LM l=0;
l<L;
l++){
LO M=S>>2;
AG LO MPr=M+TPAD;
T.l1[l]=p;
T.l2[l]=p+MPr;
T.l3[l]=p+2*MPr;
T.m1[l]=sp;
T.m2[l]=sp+MPr;
T.m3[l]=sp+2*MPr;
LO KB=DO(KA,n/S);
LO b1=KB,b2=EJ(KB,KB),b3=EJ(b2,KB);
{
AG JY nosc=((skipsc>>l)&1u)!=0;
AG LO unit=(LO)((1ull<<32)%NTP);
GR(p,nosc?0:sp,M,unit,b1);
GR(p+MPr,nosc?0:sp+MPr,M,unit,b2);
GR(p+2*MPr,nosc?0:sp+2*MPr,M,unit,b3);
}
p+=3*MPr;
sp+=3*MPr;
S>>=2;
}
T.b2=0;
T.b2s=0;
if(odd){
LO M=Sb>>1;
T.b2=p;
T.b2s=p+M;
GR(p,0,M,(LO)((1ull<<32)%NTP),DO(KA,n/Sb));
p+=2*M;
}
LM s=0;
LO S2v=4;
IV(s<JQ){
LO M=S2v>>2;
if(M>=32)p=(LO*)(((uintptr_t)p+31u)&~(uintptr_t)31u);
AG LO MP=M+TPAD;
T.h1[s]=p;
T.h2[s]=p+MP;
T.h3[s]=p+2*MP;
T.q1[s]=p+3*MP;
T.q2[s]=p+4*MP;
T.q3[s]=p+5*MP;
LO KB=DO(KA,n/S2v);
LO b1=KB,b2=EJ(KB,KB),b3=EJ(b2,KB);
GR(p,0,M,(LO)((1ull<<32)%NTP),b1);
GR(p+MP,0,M,(LO)((1ull<<32)%NTP),b2);
GR(p+2*MP,0,M,(LO)((1ull<<32)%NTP),b3);
LN(LO i2=0;
i2<M;
i2++){
p[3*MP+i2]=(LO)((LG)p[i2]*(LG)ID);
p[4*MP+i2]=(LO)((LG)p[MP+i2]*(LG)ID);
p[5*MP+i2]=(LO)((LG)p[2*MP+i2]*(LG)ID);
}
p+=6*MP;
S2v<<=2;
s++;
}
}
AJ JO ntt_init(LO n){
{
LO iv=1;
LN(LM q=0;
q<5;
q++)iv*=2u-NTP*iv;
ID=0u-iv;
}
g_n=n;
LM lg=0;
IV((1u<<lg)<n)lg++;
g_log2n=lg;
AG LM BT=g_BT;
LM L=0;
IV(lg-2*(L+1)>=BT)L++;
g_L=L;
JP=n>>(2*L);
JF=((lg-2*L)&1)?1:0;
LO S2=JP;
if(JF)S2>>=1;
JQ=0;
IV(S2>=4){
S2>>=2;
JQ++;
}
LO w=DO(EX,(NTP-1)/n);
LO wi=DO(w,NTP-2);
LO iF=DO(w,n>>2),iI=DO(wi,n>>2);
JE=iF;
GZ=FC(iF);
HY=iI;
EM=FC(iI);
build_tabs(JR,g_tabF,n,JP,L,JF,w,Q_SCF,~0u);
build_tabs(JS,g_tabI,n,JP,L,JF,wi,Q_SCI,~0u);
}
LM g_fuse16=1;
#define E7_TILE 512u
AJ LO g_scrA[16*E7_TILE]BH((aligned(64)));
#ifndef E7Z_SBFUSE
#define E7Z_SBFUSE 1
#endif
#ifndef E7Z_IVFUSE
#define E7Z_IVFUSE 1
#endif
TGT BH((EP))AJ BN JO stage4_h16_loop(LO*a,LO total,AG LO*tb,LO ci,LO LB){
AG LO MP=16+TPAD;
AG AA pv=AB((LM)NTP);
AG AA cI=AB((LM)ci),LJ=AB((LM)LB);
LN(LO i=0;
i<total;
i+=64){
LO*q0=a+i;
AG LO*w=tb;
LO j=0;
LN(;
j+16<=16;
j+=16,q0+=16,w+=16){
AA x0=AI(q0),x1=AI(q0+16),x2=AI(q0+32),x3=AI(q0+48);
AA y0=AI(q0+8),y1=AI(q0+24),y2=AI(q0+40),y3=AI(q0+56);
AA A=BV(x0,x2,pv),B=DJ(x0,x2,pv);
AA C=BV(x1,x3,pv),D=vL(x1,x3,pv);
AA A2=BV(y0,y2,pv),B2=DJ(y0,y2,pv);
AA C2=BV(y1,y3,pv),D2=vL(y1,y3,pv);
AA u0=BV(A,C,pv),u2=vL(A,C,pv);
AA v0=BV(A2,C2,pv),v2=vL(A2,C2,pv);
AA E=vS(D,cI,LJ,pv),F=vS(D2,cI,LJ,pv);
AA u1=AF(B,E),u3=vL(B,E,pv);
AA v1=AF(B2,F),v3=vL(B2,F,pv);
u1=LH(u1,AI(w),AI(w+3*MP),pv);
u2=LH(u2,AI(w+MP),AI(w+4*MP),pv);
u3=LH(u3,AI(w+2*MP),AI(w+5*MP),pv);
v1=LH(v1,AI(w+8),AI(w+3*MP+8),pv);
v2=LH(v2,AI(w+MP+8),AI(w+4*MP+8),pv);
v3=LH(v3,AI(w+2*MP+8),AI(w+5*MP+8),pv);
AW(q0,u0);
AW(q0+16,u1);
AW(q0+32,u2);
AW(q0+48,u3);
AW(q0+8,v0);
AW(q0+24,v1);
AW(q0+40,v2);
AW(q0+56,v3);
}
}
}
TGT AJ JO fwd_sb_ring(LO*a,LO b){
LO*p=a+CW(b);
if(JF)stage2_dif(p,JP,JR.b2,JR.b2s);
LN(LM s=JQ-1;
s>=0;
s--){
LO S2=4u<<(2*s);
if(S2>=32){
if(S2==16384){
LN(LO i=0;
i<JP;
i+=S2)DZ<4096>(p+i,16384,4096,JR.h1[s],JE,GZ);
}
JW if(S2==4096){
LN(LO i=0;
i<JP;
i+=S2)DZ<1024>(p+i,4096,1024,JR.h1[s],JE,GZ);
}
JW if(S2==1024){
LN(LO i=0;
i<JP;
i+=S2)DZ<256>(p+i,1024,256,JR.h1[s],JE,GZ);
}
JW if(S2==256){
LN(LO i=0;
i<JP;
i+=S2)DZ<64>(p+i,256,64,JR.h1[s],JE,GZ);
}
JW if(S2==64){
stage4_h16_loop(p,JP,JR.h1[s],JE,GZ);
}
JW{
LN(LO i=0;
i<JP;
i+=S2)stage4_dif_t(p+i,S2,S2>>2,JR.h1[s],JR.h2[s],JR.h3[s],JR.q1[s],JR.q2[s],JR.q3[s],JE,GZ);
}
}
JW if(S2==16){
dh4(p,JP,JR.h1[s],JR.h2[s],JR.h3[s],JR.q1[s],JR.q2[s],JR.q3[s],JE,GZ);
}
JW{
}
}
}
TGT AJ JO outer_dif(LO*a,LO h,AG LO*t1,AG LO*t2,AG LO*t3,LO ci,LO LB){
AG AA p=AB((LM)NTP),KC=AB(ci),imags=AB(LB);
LN(LO j=0;j<h;j+=8){LO KZ=CW(j),s=CW(h);AA x0=AI(a+KZ),x1=AI(a+s+KZ),x2=AI(a+CW(2*h)+KZ),x3=AI(a+CW(3*h)+KZ);
AA A=BV(x0,x2,p),B=DJ(x0,x2,p),C=BV(x1,x3,p),D=vL(x1,x3,p),E=vS(D,KC,imags,p);
AW(a+KZ,BV(A,C,p));AW(a+s+KZ,KW(AF(B,E),AI(t1+j),p));AW(a+CW(2*h)+KZ,KW(vL(A,C,p),AI(t2+j),p));AW(a+CW(3*h)+KZ,KW(vL(B,E,p),AI(t3+j),p));
}
}
TGT AJ JO outer_dit(LO*a,LO h,AG LO*t1,AG LO*t2,AG LO*t3,LO ci,LO LB){
AG AA p=AB((LM)NTP),KC=AB(ci),imags=AB(LB);
LN(LO j=0;j<h;j+=8){LO KZ=CW(j),s=CW(h);AA x0=AI(a+KZ),x1=AI(a+s+KZ),x2=AI(a+CW(2*h)+KZ),x3=AI(a+CW(3*h)+KZ);
x0=AS(x0,AO(x0,p));x1=AS(x1,AO(x1,p));x2=AS(x2,AO(x2,p));x3=AS(x3,AO(x3,p));
x1=KW(x1,AI(t1+j),p);x2=KW(x2,AI(t2+j),p);x3=KW(x3,AI(t3+j),p);
AA A=BV(x0,x2,p),B=DJ(x0,x2,p),C=BV(x1,x3,p),D=vL(x1,x3,p),E=vS(D,KC,imags,p);
AW(a+KZ,BV(A,C,p));AW(a+s+KZ,BV(B,E,p));AW(a+CW(2*h)+KZ,DJ(A,C,p));AW(a+CW(3*h)+KZ,DJ(B,E,p));
}
}
TGT AJ JO ntt_fwd_tail(LO*a,LO S,LM lstart,LM l0);
TGT AJ JO ntt_fwd(LO*a,AG LO*src=0,LO LF=0){
(JO)src;(JO)LF;LN(LM l=0;l<g_L;++l){LO S=g_n>>(2*l),h=S/4;LN(LO b=0;b<g_n;b+=S)outer_dif(a+CW(b),h,JR.l1[l],JR.l2[l],JR.l3[l],JE,GZ);}
LN(LO b=0;b<g_n;b+=JP)fwd_sb_ring(a,b);
}
TGT AJ JO ntt_fwd_pair_batch(LO**aa,LO**bb,LM nb,AG JT*deltas){(JO)deltas;EA=0;LN(LM i=0;i<nb;++i){ntt_fwd(aa[i]);ntt_fwd(bb[i]);}}
#define I44 512u
TGT AJ JO ntt_inv_tail(LO*a,AG LO*Bmul){
LN(LO b=0;
b<g_n;
b+=JP){
LO*p=a+CW(b);
if(Bmul&&!E7Z3_PM_ON()){
AG AA pv=AB((LM)NTP);
AG LO*q=Bmul+CW(b);
LN(LO i=0;
i<JP;
i+=8){
AA x=AI((p+i));
AA y=AI((q+i));
AW((p+i),vS(x,y,IQ(y),pv));
}
}
AG LM h1fused=(JQ>=2&&JP>=32u&&(JP%32u)==0u);
AG LM s64fused=(h1fused&&JQ>=3&&JP>=64u&&(JP%64u)==0u);
LN(LM s=0;
s<JQ;
s++){
LO S=4u<<(2*s);
if(S>=32){
if(S==16384){
LN(LO i=0;
i<JP;
i+=S){
if(JP==16384&&!JF&&g_L==4&&(b&(3*JP)))CB<4096,JZ>(p+i,16384,4096,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
JW CB<4096>(p+i,16384,4096,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW if(S==4096){
LN(LO i=0;
i<JP;
i+=S){
if(JP>=4*S&&(i&(3*S))!=0)CB<1024,JZ>(p+i,4096,1024,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
JW CB<1024>(p+i,4096,1024,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW if(S==1024){
LN(LO i=0;
i<JP;
i+=S){
if(JP>=4*S&&(i&(3*S))!=0)CB<256,JZ>(p+i,1024,256,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
JW CB<256>(p+i,1024,256,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW if(S==256){
LN(LO i=0;
i<JP;
i+=S){
if(JP>=4*S&&(i&(3*S))!=0)CB<64,JZ>(p+i,256,64,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
JW CB<64>(p+i,256,64,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW if(S==64){
if(!s64fused){
LN(LO i=0;
i<JP;
i+=S)CB<16>(p+i,64,16,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW{
LN(LO i=0;
i<JP;
i+=S)merge4_dit_t(p+i,S,S>>2,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
}
JW if(S==16){
if(s64fused)mhh64(p,JP,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM,JS.h1[s+1],JS.h2[s+1],JS.h3[s+1],JS.q1[s+1],JS.q2[s+1],JS.q3[s+1]);
JW if(h1fused)mhh(p,JP,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
JW merge4_dit_h4(p,JP,JS.h1[s],JS.h2[s],JS.h3[s],JS.q1[s],JS.q2[s],JS.q3[s],HY,EM);
}
JW{
if(!h1fused)mh1(p,JP,HY,EM);
}
}
if(JF)merge2_dit(p,JP,JS.b2,JS.b2s);
}
LN(LM l=g_L-1;l>=0;--l){LO S=g_n>>(2*l),h=S/4;LN(LO b=0;b<g_n;b+=S)outer_dit(a+CW(b),h,JS.l1[l],JS.l2[l],JS.l3[l],HY,EM);}
}
TGT AJ JO EQ(LO**IX,LM HC){EA=0;LN(LM i=0;i<HC;++i)ntt_inv_tail(IX[i],0);}
GQ ER{LO*p=GS;AN GB=0;~ER(){free(p);}JO GT(AN words){if(words<=GB)AK;free(p);p=GS;if(posix_memalign((JO**)&p,64,words*4))LL::abort();GB=words;}};
AJ ER IY,IZ,DG,IM;
AJ LO GU=0,GC=0;
AJ LO FM(LO p){LO x=p-1;LL::HX<LO>f;LN(LO d=2;LG(d)*d<=x;++d)if(x%d==0){f.push_back(d);IV(x%d==0)x/=d;}if(x>1)f.push_back(x);LN(LO g=2;;++g){JY ok=JZ;LN(LO q:f)if(DO(g,(p-1)/q)==1){ok=EL;break;}if(ok)AK g;}}
AJ JO FN(LO n,LO p){IR(n>=64&&(n&(n-1))==0&&p<(1u<<31)&&(p-1)%n==0);JK=p;if(GU==n&&GC==p)AK;FK=LO(~0ull/LG(p));g_shint=LO((~0ull/LG(p))>>32);if(GC!=p)EX=FM(p);IY.GT(3ull*n+262144);IZ.GT(3ull*n+262144);g_tabF=IY.p;g_tabI=IZ.p;ntt_init(n);EA=0;_mm_sfence();GU=n;GC=p;}
AJ JO GD(LO*KY,AG LO*src,LO n){LN(LO i=0;i<n;i+=16384u)LL::memcpy(KY+CW(i),src+i,AN(LL::min(16384u,n-i))*4);}
TGT AJ JO FH(LO*KY,AG LO*src,LO n,LO IU){AG AA p=AB((LM)NTP),s=AB(IU),ss=AB(FC(IU));LN(LO KB=0;KB<n;KB+=16384u){AG LO*x=src+CW(KB);LO HC=LL::min(16384u,n-KB);LN(LO i=0;i<HC;i+=8)AW(KY+KB+i,vS(AI(x+i),s,ss,p));}}
TGT AJ JY HD(LO*a,LO*b,LO n,LO p,JY mont){
if(!n||(n&(n-1))||p>=(1u<<31)||(p-1)%n)AK EL;
if(n<64){LL::HX<LO>c(n);LO inv=1;LN(LM i=0;i<5;++i)inv*=2-p*inv;LO small_pinv=0-inv;LN(LO i=0;i<n;++i)LN(LO j=0;j<n;++j){LG z=LG(a[i])*b[j],m=LO(z)*LG(small_pinv);LO v=mont?LO((z+LG(LO(m))*p)>>32):LO(z%p);if(v>=p)v-=p;LO&vout=c[(i+j)&(n-1)];vout+=v;if(vout>=p)vout-=p;}LL::copy(c.DK(),c.KU(),a);AK JZ;}
FN(n,p);DG.GT(CW(n)+64);IM.GT(CW(n)+64);GD(DG.p,a,n);GD(IM.p,b,n);LO*aa[1]={DG.p},*bb[1]={IM.p};ntt_fwd_pair_batch(aa,bb,1,GS);
AG AA pv=AB(p);LN(LO KB=0;KB<n;KB+=16384u){LO*x=DG.p+CW(KB),*y=IM.p+CW(KB);LO HC=LL::min(16384u,n-KB);LN(LO i=0;i<HC;i+=8){AA ax=AI(x+i),by=AI(y+i);ax=AS(ax,AO(ax,pv));by=AS(by,AO(by,pv));AW(x+i,vmont(ax,by,pv));}}
EQ(aa,1);LO IU=DO(n,p-2);if(!mont)IU=EJ(IU,RRW);FH(a,DG.p,n,IU);AK JZ;
}
TGT AJ JY cyclic_mont(LO*a,LO*b,LO n,LO p){AK HD(a,b,n,p,JZ);}
TGT AJ JY cyclic_normal(LO*a,LO*b,LO n,LO p){AK HD(a,b,n,p,EL);}
AJ LO pair_mask(){LO KD=0;LN(LM k=0;k<JQ;++k)KD|=1u<<(2*k);LN(LM k=0;k<g_L;++k)KD|=1u<<(g_log2n-2-2*k);AK KD;}
AJ LO reorder_index(LO i,LO lo){LO hi=lo<<1;AK((i&lo)<<1)|((i&hi)>>1)|(i&~(lo|hi));}
TGT AJ JO ES(LO*KY,AG LO*src,LO n,JY to_padded){
AG AA p=AB(NTP),perm=EG(0,2,1,3,4,6,5,7);LO KD=pair_mask();
LN(LO i=0;i<n;i+=16){LO GE=CW(reorder_index(i,KD));AG LO*in=to_padded?src+i:src+GE;AA a=AI(in),b=AI(in+8);a=AS(a,AO(a,p));b=AS(b,AO(b,p));a=BI(a,perm);b=BI(b,perm);LO*LI=to_padded?KY+GE:KY+i;AW(LI,AH(a,b,0x20));AW(LI+8,AH(a,b,0x31));}
}
AJ LO bitreverse(LO x,AC log){LO y=0;LN(AC i=0;i<log;++i){y=y*2+(x&1);x>>=1;}AK y;}
AJ JO FO(LO*a,LO n,LO p,JY EH,JY normal){LO oldmod=JK;JK=p;LO KA=DO(FM(p),(p-1)/n);if(EH)KA=DO(KA,p-2);LL::HX<LO>LI(n);AC log=DS(n);LN(LO k=0;k<n;++k){LO step=DO(KA,k),w=1,KT=0;LN(LO j=0;j<n;++j){LO IP=a[EH?bitreverse(j,log):j];KT=(KT+LG(IP)*w)%p;w=EJ(w,step);}if(EH&&normal)KT=EJ(KT,DO(n,p-2));LI[EH?k:bitreverse(k,log)]=KT;}LL::copy(LI.DK(),LI.KU(),a);JK=oldmod;}
TGT AJ JY HE(LO*a,LO n,LO p){if(!n||(n&(n-1))||p>=1u<<31||(p-1)%n)AK EL;if(n<64){FO(a,n,p,EL,EL);AK JZ;}FN(n,p);DG.GT(CW(n)+64);GD(DG.p,a,n);ntt_fwd(DG.p);ES(a,DG.p,n,EL);AK JZ;}
TGT AJ JY HF(LO*a,LO n,LO p,JY FP=JZ){if(!n||(n&(n-1))||p>=1u<<31||(p-1)%n)AK EL;if(n<64){FO(a,n,p,JZ,FP);AK JZ;}FN(n,p);DG.GT(CW(n)+64);ES(DG.p,a,n,JZ);LO*IX[1]={DG.p};EQ(IX,1);FH(a,DG.p,n,FP?DO(n,p-2):1);AK JZ;}
GQ FI{LO mod=0,generator=0,shmagic=0,shint=0,n=0,Sb=0,pinv=0,ciF=0,cisF=0,ciI=0,cisI=0,wf=0,wif=0,GU=0,GC=0;LM log2n=0,L=0,odd=0,nb=0,BT=13;JT pmdelta=0;Tabs TF{},TI{};ER F,I;};
AJ FI FQ;
AJ JO CX(FI&s){
LL::KE(s.mod,JK);LL::KE(s.generator,EX);LL::KE(s.shmagic,FK);LL::KE(s.shint,g_shint);LL::KE(s.n,g_n);LL::KE(s.Sb,JP);LL::KE(s.pinv,ID);LL::KE(s.ciF,JE);LL::KE(s.cisF,GZ);LL::KE(s.ciI,HY);LL::KE(s.cisI,EM);LL::KE(s.wf,g_wf);LL::KE(s.wif,g_wif);LL::KE(s.GU,GU);LL::KE(s.GC,GC);LL::KE(s.log2n,g_log2n);LL::KE(s.L,g_L);LL::KE(s.odd,JF);LL::KE(s.nb,JQ);LL::KE(s.BT,g_BT);LL::KE(s.pmdelta,EA);LL::KE(s.TF,JR);LL::KE(s.TI,JS);LL::KE(s.F.p,IY.p);LL::KE(s.F.GB,IY.GB);LL::KE(s.I.p,IZ.p);LL::KE(s.I.GB,IZ.GB);g_tabF=IY.p;g_tabI=IZ.p;
}
TGT AJ JY ntt_inverse_prefix(LO*a,LO n,LO HZ,LO p,JY FP=JZ){
if(!n||(n&(n-1))||!HZ||HZ>n||p>=1u<<31||(p-1)%n)AK EL;
LO KB=1;IV(KB<HZ)KB*=2;KB=LL::min(n,LL::max(KB,64u));
if(KB==n)AK HF(a,n,p,FP);
CX(FQ);FN(KB,p);DG.GT(CW(KB)+64);LO*IX[1]={DG.p};
LN(LO GE=0;GE<n;GE+=KB){ES(DG.p,a+GE,KB,JZ);EQ(IX,1);FH(a+GE,DG.p,KB,1);}
LO HC=(HZ+7)&~7u;LL::HX<LO>tw(HC),ts(HC);AG AA pv=AB(p);
LN(LO step=KB;step<n;step*=2){LO KA=DO(EX,(p-1)/(step*2));KA=DO(KA,p-2);LO v=1;LN(LO i=0;i<HC;++i){tw[i]=v;ts[i]=FC(v);v=EJ(v,KA);}
LN(LO GE=0;GE<n;GE+=step*2){LO*x=a+GE,*y=x+step;LN(LO i=0;i<HC;i+=8){AA left=AI(x+i),right=vS(AI(y+i),AI(tw.KF()+i),AI(ts.KF()+i),pv);AA KT=AF(left,right);AW(x+i,AS(KT,AO(KT,pv)));}}
}
if(FP){LO IU=DO(n,p-2);AG AA sv=AB(IU),ss=AB(FC(IU));LN(LO i=0;i<HC;i+=8)AW(a+i,vS(AI(a+i),sv,ss,pv));}
CX(FQ);AK JZ;
}
}
#pragma GCC pop_options
#undef NTT_MAXN
#undef PF_DIST
#undef NTP
#undef TPAD
#undef TOPPAD
#undef PADJUMP
#undef PADJUMP_S
#undef TGT
#undef Q_T5OFF
#undef Q_SCF
#undef Q_SCI
#undef RRW
#undef MLO_V
#undef E7Z3_PM_ON
#undef H4B32
#undef E7_TILE
#undef E7Z_SBFUSE
#undef E7Z_IVFUSE
#undef I44
#pragma GCC push_options
#pragma GCC target("avx2,fma")
#pragma GCC optimize("O3")
DC nuss_baseline{
EB LO=BY;EB LG=CE;
AP LG powm(LG a,LG e,LG p){LG r=1;LN(;e;e>>=1,a=a*a%p)if(e&1)r=r*a%p;AK r;}
IN FR{
AC h,n;LL::array<BD::FI,3>ctx;LL::HX<LO>bh[3],bs[3],res[3],x;
AY<LO P>JO prepare(AC f,AG LO*b){BD::CX(ctx[f]);bh[f].resize(n);bs[f].resize(n);LN(AC i=0;i<h;++i){LO v=b[h-1-i];if(v>=P)v-=P;if(v>=P)v-=P;bh[f][i]=v;}JY ok=BD::HE(bh[f].KF(),n,P);IR(ok);LO iv=BD::DO(n,P-2);AA pp=AB(P),vv=AB(iv),ss=AB(BD::FC(iv));LN(AC i=0;i<n;i+=8){AA z=BD::vS(CK((AG AA*)(bh[f].KF()+i)),vv,ss,pp);CQ((AA*)(bh[f].KF()+i),z);CQ((AA*)(bs[f].KF()+i),BD::IQ(z));}res[f].resize(8*h);BD::CX(ctx[f]);}
AY<LO P>JO field(AC f,AG LO*a){BD::CX(ctx[f]);AG AA pp=AB(P);LN(AC rho=0;rho<8;++rho){LN(AC i=0;i<n;++i){LO v=a[8*i+rho];if(v>=P)v-=P;if(v>=P)v-=P;x[i]=v;}JY ok=BD::HE(x.KF(),n,P);IR(ok);LN(AC i=0;i<n;i+=8){AA z=BD::vS(CK((AG AA*)(x.KF()+i)),CK((AG AA*)(bh[f].KF()+i)),CK((AG AA*)(bs[f].KF()+i)),pp);CQ((AA*)(x.KF()+i),z);}ok=BD::HF(x.KF(),n,P,EL);IR(ok);LN(AC t=0;t<h;++t)res[f][8*t+rho]=x[h-1+t];}BD::CX(ctx[f]);}
HA:
FR(AG LO*b,AC KG):h(KG),n(2*KG),x(n){prepare<2013265921u>(0,b);prepare<1811939329u>(1,b);prepare<2113929217u>(2,b);}FR(AG FR&)=JA;
JO JG(AG LO*a,LO*LI){field<2013265921u>(0,a);field<1811939329u>(1,a);field<2113929217u>(2,a);AP LG P0=2013265921,P1=1811939329,P2=2113929217,P01=P0*P1,I0=powm(P0,P1-2,P1),I01=powm(P01%P2,P2-2,P2);LN(AC i=0;i<8*h;++i){LG t=(res[1][i]+P1-res[0][i]%P1)%P1*I0%P1,v=res[0][i]+P0*t,t2=(res[2][i]+P2-v%P2)%P2*I01%P2;LI[i]=LO(v)+LO(P01)*LO(t2);}}
};
}
#pragma GCC pop_options
#pragma once
#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
DC nuss{
EB LO=BY;EB LG=CE;
AY<IN T>GQ FS{T*p;AC n;GV FS(AC HC):p(GS),n(HC){JO*q=GS;if(posix_memalign(&q,64,AN(n)*IS(T)))LL::abort();p=(T*)q;LN(AC i=0;i<n;++i)new(p+i)T{};}~FS(){free(p);}FS(AG FS&)=JA;T&CF[](AC i){AK p[i];}AG T&CF[](AC i)AG{AK p[i];}};
GQ V4{AA v;V4():v(CO()){}GV V4(AA z):v(z){}friend V4 CF+(V4 a,V4 b){AK V4(BQ(a.v,b.v));}friend V4 CF-(V4 a,V4 b){AK V4(CI(a.v,b.v));}};
BN LG LK(LG a,LG b){AK a*b;}
BN V4 LK(V4 a,LG b){AG AA bv=BE(b),sw=BE((b>>32)|(b<<32));AA low=AU(a.v,bv),HQ=BJ(a.v,sw);HQ=BQ(HQ,_mm256_srli_epi64(HQ,32));AK V4(BQ(low,_mm256_slli_epi64(HQ,32)));}
AY<AC N,IN V>BH((EP))BN JO CJ(AG V*a,AG LG*b,V*LI){if AP(N==1){LI[0]=LK(a[0],b[0]);LI[1]=V{};}JW{AP AC S=N/2;V sa[S],HQ[2*S];LG sb[S];LN(AC i=0;i<S;++i){sa[i]=a[i]+a[S+i];sb[i]=b[i]+b[S+i];}CJ<S>(a,b,LI);CJ<S>(a+S,b+S,LI+2*S);CJ<S>(sa,sb,HQ);LN(AC i=0;i<2*S;++i)HQ[i]=HQ[i]-LI[i]-LI[2*S+i];LN(AC i=0;i<2*S;++i)LI[i+S]=LI[i+S]+HQ[i];}}
AY<IN V>JO DP(AG V*a,AG LG*b,V*LI,AC n,V*EI,LG*bs){
if(n<=8){if(n==1)CJ<1>(a,b,LI);JW if(n==2)CJ<2>(a,b,LI);JW if(n==4)CJ<4>(a,b,LI);JW CJ<8>(a,b,LI);AK;}
AC s=n/2;V*sumA=EI,*HQ=sumA+s,*KI=HQ+2*s;LG*sumB=bs,*nextB=bs+s;
LN(AC i=0;i<s;++i){sumA[i]=a[i]+a[s+i];sumB[i]=b[i]+b[s+i];}
DP(a,b,LI,s,KI,nextB);DP(a+s,b+s,LI+2*s,s,KI,nextB);DP(sumA,sumB,HQ,s,KI,nextB);
LN(AC i=0;i<2*s;++i)HQ[i]=HQ[i]-LI[i]-LI[i+2*s];LN(AC i=0;i<2*s;++i)LI[i+s]=LI[i+s]+HQ[i];
}
AY<IN V>JO GF(AG V*src,V*KY,AC LF,AC JI){JI%=2*LF;JY neg=JI>=LF;if(neg)JI-=LF;LN(AC i=0;i<LF-JI;++i)KY[i+JI]=neg?V{}-src[i]:src[i];LN(AC i=LF-JI;i<LF;++i)KY[i+JI-LF]=neg?src[i]:V{}-src[i];}
AY<IN V>JO fft(V*a,AC HC,AC LF,JY EH){FS<V>tmp(LF);if(!EH){LN(AC KJ=HC;KJ>=2;KJ/=2){AC half=KJ/2,unit=2*LF/KJ;LN(AC HG=0;HG<HC;HG+=KJ)LN(AC j=0;j<half;++j){V*x=a+(HG+j)*LF,*y=a+(HG+j+half)*LF;LN(AC t=0;t<LF;++t){tmp[t]=x[t]-y[t];x[t]=x[t]+y[t];}GF(tmp.p,y,LF,unit*j);}}}JW LN(AC KJ=2;KJ<=HC;KJ*=2){AC half=KJ/2,unit=2*LF/KJ;LN(AC HG=0;HG<HC;HG+=KJ)LN(AC j=0;j<half;++j){V*x=a+(HG+j)*LF,*y=a+(HG+j+half)*LF;GF(y,tmp.p,LF,(2*LF-unit*j)%(2*LF));LN(AC t=0;t<LF;++t){V old=x[t];x[t]=old+tmp[t];y[t]=old-tmp[t];}}}}
GQ Shape{AC h,K,M,N,L,logN,logM;GV Shape(AC KG):h(KG){IR(h>=4&&(h&(h-1))==0);AC lg=DS(h);K=1u<<((lg+1)/2);M=h/K;N=2*K;L=2*M;logN=DS(N);logM=DS(M);IR(2*L%N==0);}};
IN Plan64{
HA:
Shape s;FS<LG>bhat;GV Plan64(AG LO*b,AC h):s(h),bhat(s.N*s.L){LN(AC j=0;j<s.K;++j)LN(AC t=0;t<s.M;++t)bhat[j*s.L+t]=b[s.h-1-j*s.M-t];fft(bhat.p,s.N,s.L,EL);}
JY JG(AG LO*a,LO*LI,JY CY=EL)AG{FS<LG>x(s.N*s.L),prod(2*s.L),EI(4*s.L),bs(2*s.L);LN(AC j=0;j<s.N;++j)LN(AC t=0;t<s.M;++t)x[j*s.L+t]=a[j*s.M+t];fft(x.p,s.N,s.L,EL);LN(AC j=0;j<s.N;++j){DP(x.p+j*s.L,bhat.p+j*s.L,prod.p,s.L,EI.p,bs.p);LN(AC t=0;t<s.L;++t)x[j*s.L+t]=prod[t]-prod[t+s.L];}fft(x.p,s.N,s.L,JZ);if(CY)LN(AC i=0;i<s.N*s.L;++i)if(x[i]&(s.N-1))AK EL;LN(AC t=0;t<s.h;++t){AC k=s.h-1+t,j=k>>s.logM,r=k&(s.M-1),prev=(j+s.N-1)&(s.N-1);LI[t]=LO(x[j*s.L+r]>>s.logN)+LO(x[prev*s.L+r+s.M]>>s.logN);}AK JZ;}
};
IN Plan4{
AG Plan64&plan;FS<V4>x,prod,EI;FS<LG>bs;
HA:
GV Plan4(AG Plan64&p):plan(p),x(p.s.N*p.s.L),prod(2*p.s.L),EI(4*p.s.L),bs(2*p.s.L){}
JY JG(AG LO*a,LO*LI,AC AZ=4,JY CY=EL){AG KK&s=plan.s;LN(AC i=0;i<s.N*s.L;++i)x[i]=V4{};LN(AC j=0;j<s.N;++j)LN(AC t=0;t<s.M;++t)x[j*s.L+t]=V4(_mm256_cvtepu32_epi64(AE((AG AD*)(a+AZ*(j*s.M+t)))));fft(x.p,s.N,s.L,EL);LN(AC j=0;j<s.N;++j){DP(x.p+j*s.L,plan.bhat.p+j*s.L,prod.p,s.L,EI.p,bs.p);LN(AC t=0;t<s.L;++t)x[j*s.L+t]=prod[t]-prod[t+s.L];}fft(x.p,s.N,s.L,JZ);if(CY){AA KD=BE(s.N-1);LN(AC i=0;i<s.N*s.L;++i)if(!_mm256_testz_si256(x[i].v,KD))AK EL;}AG AD sh=_mm_cvtsi32_si128(s.logN);AG AA perm=EG(0,2,4,6,1,3,5,7);LN(AC t=0;t<s.h;++t){AC k=s.h-1+t,j=k>>s.logM,r=k&(s.M-1),prev=(j+s.N-1)&(s.N-1);AA v=_mm256_srl_epi64(BQ(x[j*s.L+r].v,x[prev*s.L+r+s.M].v),sh);BA((AD*)(LI+AZ*t),AV(BI(v,perm)));}AK JZ;}
};
}
#pragma GCC pop_options
#pragma once
#pragma once
#include <bits/stdc++.h>
#include <immintrin.h>
AP KK 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>
#define NI64 BG(hint::CR{})
#pragma GCC target("avx2,fma,tune=skylake")
#pragma GCC optimize("O3,tree-vectorize")
#pragma GCC optimize("align-functions=32")
#pragma GCC optimize("ira-loop-pressure")
#pragma GCC optimize("sched-pressure")
DC hint
{
AY<BM T,AN ALIGN=64>
IN ET{
HA:
EB Ptr=T*;
EB ConstPtr=AG T*;
~ET(){
if(ptr){
_mm_free(ptr);}};
ET():ptr(GS),LF(0){}
ET(AN n):ptr(AR<Ptr>(_mm_malloc(n*IS(T),ALIGN))),LF(n){}
ET(AG ET&)=JA;
ET&CF=(AG ET&)=JA;
T&CF[](AN i){
AK ptr[i];}
AG T&CF[](AN i)AG{
AK ptr[i];}
Ptr DK(){
AK ptr;}
Ptr KU(){
AK ptr+LF;}
ConstPtr DK()AG{
AK ptr;}
ConstPtr KU()AG{
AK ptr+LF;}
AN KG()AG{
AK LF;}
private:
T*ptr;
AN LF;};
AY<BM KS>
BN JO transpose64_2X4(KS&KL,KS&KM){
KK t0=CZ(BZ(KL),BZ(KM));
KK t1=DA(BZ(KL),BZ(KM));
KL=KS(BB(t0,t1,0x20));
KM=KS(BB(t0,t1,0x31));}
AY<BM KS>
BN JO transpose64_4X2(KS&KL,KS&KM){
KK t0=BB(BZ(KL),BZ(KM),0x20);
KK t1=BB(BZ(KL),BZ(KM),0x31);
KL=KS(CZ(t0,t1));
KM=KS(DA(t0,t1));}
AY<BM KS>
BN JO BP(KS&KL,KS&KM,KS&row2,KS&row3){
KK t0=CZ(BZ(KL),BZ(KM));
KK t1=DA(BZ(KL),BZ(KM));
KK t2=CZ(BZ(row2),BZ(row3));
KK t3=DA(BZ(row2),BZ(row3));
KL=KS(BB(t0,t2,0x20));
KM=KS(BB(t1,t3,0x20));
row2=KS(BB(t0,t2,0x31));
row3=KS(BB(t1,t3,0x31));}
GQ CR{};
IN DM{
HA:
EB LE=CG;
EB DD=DM;
DM():KF(_mm256_setzero_pd()){}
DM(CR){}
DM(BZ IA):KF(IA){}
DM(LE IA):KF(DN(IA)){}
DM(AG LE*IA):KF(EC(IA)){}
DD CF+(AG DD&GJ)AG{
AK DT(KF,GJ.KF);}
DD CF-(AG DD&GJ)AG{
AK _mm256_sub_pd(KF,GJ.KF);}
DD CF*(AG DD&GJ)AG{
AK GK(KF,GJ.KF);}
DD CF/(AG DD&GJ)AG{
AK _mm256_div_pd(KF,GJ.KF);}
AJ DD fmadd(AG DD&a,AG DD&b,AG DD&c){
AK FE(a.KF,b.KF,c.KF);}
AJ DD fmsub(AG DD&a,AG DD&b,AG DD&c){
AK _mm256_fmsub_pd(a.KF,b.KF,c.KF);}
AY<LM N>
DD permute4x64()AG{
AK _mm256_permute4x64_pd(KF,N);}
DD IB()AG{
AK permute4x64<0b00011011>();}
JO KN(AG LE*p){
KF=EC(p);}
JO load1(AG LE*p){
KF=_mm256_broadcast_sd(p);}
JO DU(LE*p)AG{
_mm256_store_pd(p,KF);}
JO IE(LE*p)AG{
_mm256_stream_pd(p,KF);}
CF BZ()AG{
AK KF;}
AA toI64X4()AG{
AP CE KD=(CE(1)<<52)-1;
AP CE GE=(CE(1)<<10)-1;
AG AA f64bits=BL(KF);
AA KO=_mm256_and_si256(f64bits,BE(KD));
KO=DX(KO,BE(KD+1));
AA exp=_mm256_srli_epi64(f64bits,52);
exp=CI(BE(GE+52),exp);
AK _mm256_srlv_epi64(KO,exp);}
private:
BZ KF;};
GQ CL{
EB BG=CL;
EB DD=DM;
EB LE=CG;
CL(){}
CL(CR):KP(CR{}),KC(CR{}){}
CL(DD KP,DD KC):KP(KP),KC(KC){}
CL(AG LE*p):KP(p),KC(p+4){}
CL(AG LE*p_real,AG LE*p_imag):KP(p_real),KC(p_imag){}
BG CF+(AG BG&GJ)AG{
AK BG(KP+GJ.KP,KC+GJ.KC);}
BG CF-(AG BG&GJ)AG{
AK BG(KP-GJ.KP,KC-GJ.KC);}
BG CF*(AG DD&GJ)AG{
AK BG(KP*GJ,KC*GJ);}
BG LK(AG BG&GJ)AG{
AG DD ii=KC*GJ.KC;
AG DD ri=KP*GJ.KC;
AG DD r=DD::fmsub(KP,GJ.KP,ii);
AG DD i=DD::fmadd(KC,GJ.KP,ri);
AK BG(r,i);}
BG CM(AG BG&GJ)AG{
AG DD ii=KC*GJ.KC;
AG DD ri=KP*GJ.KC;
AG DD r=DD::fmadd(KP,GJ.KP,ii);
AG DD i=DD::fmsub(KC,GJ.KP,ri);
AK BG(r,i);}
BG IB()AG{
AK BG(KP.IB(),KC.IB());}
JO set1(LE real_in,LE imag_in){
KP=DD(real_in);
KC=DD(imag_in);}
AY<BM T>
JO KN(AG T*p,LL::false_type){
this->KN(p);}
AY<BM T>
JO KN(AG T*p,LL::true_type){
this->KN(p);
*this=this->toRRIIPermu();}
AY<BM T>
JO KN(AG T*p){
KP.KN(AR<AG LE*>(p));
KC.KN(AR<AG LE*>(p)+4);}
JO load1(AG LE*real_p,AG LE*imag_p){
KP.load1(real_p);
KC.load1(imag_p);}
AY<BM T>
JO DU(T*p,LL::false_type)AG{
this->DU(p);}
AY<BM T>
JO DU(T*p,LL::true_type)AG{
this->toRIRIPermu().DU(p);}
AY<BM T>
JO DU(T*p)AG{
KP.DU(AR<LE*>(p));
KC.DU(AR<LE*>(p)+4);}
AY<BM T>
JO IE(T*p)AG{
KP.IE(AR<LE*>(p));
KC.IE(AR<LE*>(p)+4);}
BG toRIRIPermu()AG{
BG res=*this;
transpose64_2X4(res.KP,res.KC);
AK res;}
BG toRRIIPermu()AG{
BG res=*this;
transpose64_4X2(res.KP,res.KC);
AK res;}
BG EU(LL::false_type)AG{
AK*this;}
BG EU(LL::true_type)AG{
AG BZ JJ=DN(6755399441055744.0);
AG AA KH=BL(JJ);AK BG(_mm256_castsi256_pd(CI(BL(DT(KP,JJ)),KH)),_mm256_castsi256_pd(CI(BL(DT(KC,JJ)),KH)));}
DD KP,KC;};
EB Float32=float;
EB BX=CG;
AP BX HINT_PI=3.141592653589793238462643;
AP BX HINT_2PI=HINT_PI*2;
AP BX COS_PI_8=0.707106781186547524400844;
AY<BM T>
AP T int_floor2(T n){
AP LM KH=IS(n)*8;
LN(LM i=1;i<KH;i*=2){
n|=(n>>i);}
AK(n>>1)+1;}
AY<BM T>
AP T int_ceil2(T n){
AP LM KH=IS(n)*8;
n--;
LN(LM i=1;i<KH;i*=2){
n|=(n>>i);}
AK n+1;}
AY<BM IntTy>
AP JY is_2pow(IntTy n){
AK n!=0&&(n&(n-1))==0;}
AY<BM T>
AP LM ED(T n){
AP LM KH=IS(n)*8;
LM l=-1,r=KH;
IV((l+1)!=r){
LM mid=(l+r)/2;
if((T(1)<<mid)>n){
r=mid;}
JW{
l=mid;}}
AK l;}
AP BY crc32(AG JX*str){
BY crc=0xFFFFFFFF;
IV(*str!='\0'){
crc^=*str;
LN(LM i=0;i<8;++i){
crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}
str++;}
AK~crc;}
DC transform{
AY<BM T>
BN JO BK(T&KT,T&diff){
T temp0=KT,temp1=diff;
KT=temp0+temp1;
diff=temp0-temp1;}
DC fft{
EB LE=BX;
EB C64=LL::complex<LE>;
EB DD=DM;
EB BG=CL;
BN C64 EV(AN n,AN JH){
JH%=n;
AG AN q=(4*JH+n/2)/n;
AG HH d=HH(4*JH)-HH(q*n);
AP JT CG pi=3.141592653589793238462643383279502884L;
AG JT CG x=(CP<JT CG>(d)/CP<JT CG>(n))*(pi/2);
AG JT CG xx=x*x;
JT CG sn=x,cs=1,st=x,ct=1;
LN(AC k=1;k<=18;++k){
st*=(-xx)/CP<JT CG>((2*k)*(2*k+1));
ct*=(-xx)/CP<JT CG>((2*k-1)*(2*k));
sn+=st;cs+=ct;
}
JT CG re,im;
switch(q&3){case 0:re=cs;im=sn;break;case 1:re=-sn;im=cs;break;case 2:re=-cs;im=-sn;break;default:re=sn;im=-cs;break;}
AK C64(CP<CG>(re),-CP<CG>(im));
}
AY<BM CU,AN OMEGA_LEN>
IN IF{
alignas(64)CU IG[OMEGA_LEN*2];
HA:
IF(AN theta_divider,AN FT,AN AZ){
LN(AN DK=0,JH=0;DK<OMEGA_LEN*2;DK+=AZ*2)
LN(AN j=0;j<AZ;++j,++JH){C64 z=EV(theta_divider,JH*FT);IG[DK+j]=CU(z.KP());IG[DK+j+AZ]=CU(z.KC());}
}
AP AG CU&CF[](AN JH)AG{
AK IG[JH];}};
JO HI(LE*arr,AN BC,LM HR,LM FT){
LN(LM j=0;j<HR;++j){C64 z=EV(BC,AN(j)*FT);AN p=AN(j/4)*8+j%4;arr[p]=z.KP();arr[p+4]=z.KC();}
}
AY<BM CU,LM EE,LM LOG_END,LM DIV>
IN DV{
GL(LOG_END>=EE);
GL(is_2pow(DIV));
AJ AP AN TABLE_CPX_LEN=(AN(1)<<(LOG_END+1))/DIV;
alignas(64)CU IG[TABLE_CPX_LEN*2];
HA:
DV(AN FT,AN AZ=4){
initBottomUp(FT,AZ);}
JO initBottomUp(AN FT,AN AZ){
(JO)AZ;GL(LL::is_same<CU,BX>::IP);
LN(LM FF=EE;FF<=LOG_END;++FF){AN LF=AN(1)<<FF;HI(HJ(FF),LF,LF/DIV,FT);}
}
AP AG CU*HJ(LM IH)AG{
AK BO(AN(1)<<IH);}
AP CU*HJ(LM IH){
AK BO(AN(1)<<IH);}
AP AG CU*BO(AN KJ)AG{
AK&IG[KJ*2/DIV];}
AP CU*BO(AN KJ){
AK&IG[KJ*2/DIV];}};
AY<LM DH>
IN CN{
HA:
EB LE=CG;
EB C64=LL::complex<CG>;
EB BG=hint::CL;
AJ AP AN HS=AN(1)<<DH;
AJ AP AN MASK=HS-1;
AJ AP AN C4_COUNT=IS(BG)/IS(C64);
~CN(){
if(JU)
{
JA[]JU;}}
CN(){}
CN(AN BC,LM len_div,LM FT){
init(BC,len_div,FT);}
JO init(AN BC,LM len_div,LM FT){
AN HR=BC/len_div,low_len=HS*C4_COUNT,high_len=HR/low_len;
if(JU!=GS)JA[]JU;JU=new C64[high_len];
HI(AR<LE*>(&low[0]),BC,low_len,FT);
LN(AN i=0;i<high_len;++i)JU[i]=EV(BC,i*low_len*FT);
}
AJ AP AN LOGV=DH,MASKV=MASK;
AG BG*lowPtr()AG{AK low;}
AG C64*highPtr()AG{AK JU;}
BG CF[](AN i)AG{
BG hi(CR{});
KK p=AR<AG LE*>(&JU[i>>DH]);
hi.load1(p,p+1);
AK low[i&MASK].LK(hi);}
private:
alignas(64)BG low[HS];
C64*JU=GS;};
AY<LM DIV,LM EE,LM IC,LM DH>
IN GW{
EB HT=CN<DH>;
AJ AP AN FU=AN(1)<<EE;
AJ AP AN TABLE_LEN=IC-EE+1;
HA:
GW(LM FT){
LN(LM i=0;i<TABLE_LEN;i++)
{
AN BC=FU<<i;
IG[i].init(BC,DIV,FT);}}
AG HT&CF[](LM FF)AG{
FF-=EE;
AK IG[FF];}
HT&CF[](LM FF){
FF-=EE;
AK IG[FF];}
private:
HT IG[TABLE_LEN];};
GQ FFT{
AY<BM CU>
AJ JO trans2MulI(CU&r0,CU&i0,CU&r1,CU&i1){
KK temp=r1;
r1=r0+i1;
r0=r0-i1;
i1=i0-temp;
i0=i0+temp;}
AY<BM CU>
AJ JO GM(CU&r0,CU&i0,CU&r1,CU&i1){
KK temp=r1;
r1=r0-i1;
r0=r0+i1;
i1=i0+temp;
i0=i0-temp;}
AY<BM CU>
AJ JO KQ(CU&r0,CU&i0,CU&r1,CU&i1,CU&r2,CU&i2,CU&r3,CU&i3){
II(r0,i0,r1,i1,r2,i2,r3,i3);
BK(r0,r1);
BK(i0,i1);}
AY<BM CU>
AJ JO JL(CU&r0,CU&i0,CU&r1,CU&i1,CU&r2,CU&i2,CU&r3,CU&i3){
BK(r0,r1);
BK(i0,i1);
HU(r0,i0,r1,i1,r2,i2,r3,i3);}
AY<BM CU>
AJ JO II(CU&r0,CU&i0,CU&r1,CU&i1,CU&r2,CU&i2,CU&r3,CU&i3){
BK(r0,r2);
BK(i0,i2);
BK(r1,r3);
BK(i1,i3);
GM(r2,i2,r3,i3);}
AY<BM CU>
AJ JO HU(CU&r0,CU&i0,CU&r1,CU&i1,CU&r2,CU&i2,CU&r3,CU&i3){
BK(r2,r3);
BK(i2,i3);
BK(r0,r2);
BK(i0,i2);
trans2MulI(r1,i1,r3,i3);}};
DC GG{extern JY enabled;JO run(LE*,AN);}
AJ JY g_skip_leaf=EL;
GQ DL:HA FFT{
AJ AP LM FW=11,IO=17,IC=23,LOG_CACHE=8;
AJ AP AN FU=AN(1)<<FW,FX=AN(1)<<IO,MAX_LEN=AN(1)<<IC;
EB TableFix4=AG IF<BX,4>;
EB TableFix8=AG IF<BX,8>;
EB HK=AG DV<BX,FW+1,IO,4>;
EB HL=AG DV<BX,6,FW+1,4>;
EB HM=AG DV<BX,6,FW,4>;
EB TableSqrt=AG GW<4,IO+1,IC,LOG_CACHE>;
AJ TableFix4 table_8,table_16_1,table_16_3;
AJ TableFix8 table_32_1,table_32_3;
AJ HL BS;
AJ HM DI;
AJ HK DW,CS,CT;
AJ TableSqrt DB;
AJ AP AG BX*it8=&table_8[0],*it16_1=&table_16_1[0],*it16_3=&table_16_3[0],*it32_1=&table_32_1[0],*it32_3=&table_32_3[0];
AJ JO dif4x4(DD&r0,DD&i0,DD&r1,DD&i1,DD&r2,DD&i2,DD&r3,DD&i3){
BP(r0,r1,r2,r3);
BP(i0,i1,i2,i3);
KQ(r0,i0,r1,i1,r2,i2,r3,i3);
BP(r0,r1,r2,r3);
BP(i0,i1,i2,i3);}
AJ JO idit4x4(DD&r0,DD&i0,DD&r1,DD&i1,DD&r2,DD&i2,DD&r3,DD&i3){
BP(r0,r1,r2,r3);
BP(i0,i1,i2,i3);
JL(r0,i0,r1,i1,r2,i2,r3,i3);
BP(r0,r1,r2,r3);
BP(i0,i1,i2,i3);}
AJ JO dif8x2(BG&c0,BG&c1,BG&c2,BG&c3){
BG JM(it8);
BK(c0,c1);
BK(c2,c3);
c1=c1 .LK(JM),c3=c3 .LK(JM);
dif4x4(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);}
AJ JO idit8x2(BG&c0,BG&c1,BG&c2,BG&c3){
BG JM(it8);
idit4x4(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .CM(JM),c3=c3 .CM(JM);
BK(c0,c1);
BK(c2,c3);}
AJ JO dif16(BX BF[]){
KK p=AR<BG*>(BF);
BG c0=p[0],c1=p[1],c2=p[2],c3=p[3];
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(BG(it8)),c2=c2 .LK(BG(it16_1)),c3=c3 .LK(BG(it16_3));
dif4x4(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
AJ JO idit16(BX BF[]){
KK p=AR<BG*>(BF);
BG c0=p[0],c1=p[1],c2=p[2],c3=p[3],JM;
idit4x4(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .CM(BG(it8)),c2=c2 .CM(BG(it16_1)),c3=c3 .CM(BG(it16_3));
JL(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
AJ JO dif32(BX BF[]){
KK p=AR<BG*>(BF);
BG c0=p[0],c1=p[2],c2=p[4],c3=p[6];
II(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c2=c2 .LK(BG(it32_1)),c3=c3 .LK(BG(it32_3));
p[0]=c0,p[2]=c1,p[4]=c2,p[6]=c3;
c0=p[1],c1=p[3],c2=p[5],c3=p[7];
II(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c2=c2 .LK(BG(it32_1+8)),c3=c3 .LK(BG(it32_3+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(BF);}
AJ JO idit32(BX BF[]){
idit16(BF);
KK p=AR<BG*>(BF);
BG 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 .CM(BG(it32_1)),c2=c2 .CM(BG(it32_3));
HU(c1 .KP,c1 .KC,c3 .KP,c3 .KC,c0 .KP,c0 .KC,c2 .KP,c2 .KC);
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 .CM(BG(it32_1+8)),c3=c3 .CM(BG(it32_3+8));
HU(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
p[1]=c0,p[3]=c1,p[5]=c2,p[7]=c3;}
AY<BM F32,BM F16>
AJ JO fftTiny(BX BF[],AN AQ,F32&&func32,F16&&func16){
if(ED(AQ/2)%2==0)
{
LN(KK KU=BF+AQ;BF<KU;BF+=32)
{
func16(BF);}}
JW
{
LN(KK KU=BF+AQ;BF<KU;BF+=64)
{
func32(BF);}}}
#define E8Z3_FUSE_MINRANK 256u
AJ JO difTop2(BX*BF,AN AQ,AN R){
AG AN S1=R/2,S2=R/8;
LN(BX*DK=BF,*bend=BF+AQ;DK<bend;DK+=R*2){
AG BX*t1a=BS.BO(R*2),*t2a=BS.BO(R),*t3a=DI.BO(R);
AG BX*t1b=BS.BO(R/2),*t2b=BS.BO(R/4),*t3b=DI.BO(R/4);
LN(AN j2=0;j2<S2;j2+=8){
BG v[4][4]={NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64};
LN(LM q=0;q<4;q++){
AG AN KZ=(AN)q*S2+j2;
BG c0(DK+KZ),c1(DK+S1+KZ),c2(DK+2*S1+KZ),c3(DK+3*S1+KZ);
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(BG(t2a+KZ));c2=c2 .LK(BG(t1a+KZ));c3=c3 .LK(BG(t3a+KZ));
v[0][q]=c0;v[1][q]=c1;v[2][q]=c2;v[3][q]=c3;
}
LN(LM s=0;s<4;s++){
BG c0=v[s][0],c1=v[s][1],c2=v[s][2],c3=v[s][3];
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(BG(t2b+j2));c2=c2 .LK(BG(t1b+j2));c3=c3 .LK(BG(t3b+j2));
c0 .DU(DK+(AN)s*S1+j2);
c1 .DU(DK+(AN)s*S1+S2+j2);
c2 .DU(DK+(AN)s*S1+2*S2+j2);
c3 .DU(DK+(AN)s*S1+3*S2+j2);
}
}
}
}
AJ JO difIter(BX BF[],AN AQ){
AN BC=AQ/2;
BG c0(CR{}),c1(CR{}),c2(CR{}),c3(CR{});
AN AZ=BC/2;
KK LC=BF,LD=LC+AZ,LA=LD+AZ,KV=LA+AZ;
if(BC>=E8Z3_FUSE_MINRANK){difTop2(BF,AQ,BC);}
LN(AN KJ=BC>=E8Z3_FUSE_MINRANK?BC/16:BC;KJ>=64;KJ/=4)
{
AZ=KJ/2;
LN(KK DK=BF,KU=BF+AQ;DK<KU;DK+=KJ*2)
{
KK GH=BS.BO(KJ*2),JB=BS.BO(KJ),JC=DI.BO(KJ);
LC=DK,LD=LC+AZ,LA=LD+AZ,KV=LA+AZ;
LN(;LC<DK+AZ;LC+=8,LD+=8,LA+=8,KV+=8,GH+=8,JB+=8,JC+=8)
{
c0=LC,c1=LD,c2=LA,c3=KV;
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(BG(JB)),c2=c2 .LK(BG(GH)),c3=c3 .LK(BG(JC));
c0 .DU(LC),c1 .DU(LD),c2 .DU(LA),c3 .DU(KV);
}}}
fftTiny(BF,AQ,dif32,dif16);}
AJ JO iditIter(BX BF[],AN AQ){
if(GG::enabled)GG::run(BF,AQ);
AN BC=AQ/2;
AN KJ=ED(BC)%2==0?64:128;
fftTiny(BF,AQ,idit32,idit16);
LN(;KJ<=BC;KJ*=4)
{
AG AN AZ=KJ/2;
LN(KK DK=BF,KU=BF+AQ;DK<KU;DK+=KJ*2)
{
KK GH=BS.BO(KJ*2),JB=BS.BO(KJ),JC=DI.BO(KJ);
KK LC=DK,LD=LC+AZ,LA=LD+AZ,KV=LA+AZ;
LN(;LC<DK+AZ;LC+=8,LD+=8,LA+=8,KV+=8,GH+=8,JB+=8,JC+=8)
{
BG c0=LC,c1=LD,c2=LA,c3=KV;
c1=c1 .CM(BG(JB)),c2=c2 .CM(BG(GH)),c3=c3 .CM(BG(JC));
JL(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c0 .DU(LC),c1 .DU(LD),c2 .DU(LA),c3 .DU(KV);
}}}}
#define difLayer(HV, BF, AZ, IG) \
do \
{ \
KK LC = BF, LD = BF + AZ, LA = LD + AZ, KV = LA + AZ; \
AN KR = 0; \
LN (KK KU = LD; BU && LC < KU; LC += 8, LD += 8, LA += 8, KV += 8, KR++) \
{ \
BG c0, c1, c2, c3, EW, GX; \
c0.KN(LC, IJ{}), c1.KN(LD, IJ{}), c2 = c0,c3 = c1; \
BK(c0,c1); \
GM(c2.KP,c2.KC,c3.KP,c3.KC); \
EW = IG[KR], c2 = c2.LK(EW); \
GX = BC<=FX?BG(CS.BO(BC)+8*KR):EW.LK(EW), c1 = c1.LK(GX); \
c3 = c3.LK(BC<=FX?BG(CT.BO(BC)+8*KR):GX.LK(EW)); \
c0.DU(LC), c1.DU(LD), c2.DU(LA), c3.DU(KV); \
} \
LN (KK KU = LD; (!BU) && LC < KU; LC += 8, LD += 8, LA += 8, KV += 8, KR++) \
{ \
BR((AG JX*)(LC+64),CA); \
BR((AG JX*)(LD+64),CA); \
BR((AG JX*)(LA+64),CA); \
BR((AG JX*)(KV+64),CA); \
BG c0 = LC, c1 = LD, c2 = LA, c3 = KV, EW, GX; \
KQ(c0.KP, c0.KC, c1.KP, c1.KC, c2.KP, c2.KC, c3.KP, c3.KC); \
EW = IG[KR], c2 = c2.LK(EW); \
GX = BC<=FX?BG(CS.BO(BC)+8*KR):EW.LK(EW), c1 = c1.LK(GX); \
c3 = c3.LK(BC<=FX?BG(CT.BO(BC)+8*KR):GX.LK(EW)); \
c0.DU(LC), c1.DU(LD), c2.DU(LA), c3.DU(KV); \
} \
HV(BF, AZ); \
HV(BF + AZ, AZ); \
HV(BF + AZ * 2, AZ); \
HV(BF + AZ * 3, AZ); \
} IV (0)
#define iditLayer(GP, BF, AZ, IG) \
do \
{ \
GP(BF, AZ); \
GP(BF + AZ, AZ); \
GP(BF + AZ * 2, AZ); \
GP(BF + AZ * 3, AZ); \
KK LC = BF, LD = BF + AZ, LA = LD + AZ, KV = LA + AZ; \
AN KR = 0; \
_Pragma("GCC unroll 4") \
LN (KK KU = LD; LC < KU; LC += 8, LD += 8, LA += 8, KV += 8, KR++) \
{ \
BR((AG JX*)(LC+64),CA); \
BR((AG JX*)(LD+64),CA); \
BR((AG JX*)(LA+64),CA); \
BR((AG JX*)(KV+64),CA); \
BG c0 = LC, c1 = LD, c2 = LA, c3 = KV, EW, GX; \
EW = IG[KR], c2 = c2.CM(EW); \
GX = BC<=FX?BG(CS.BO(BC)+8*KR):EW.LK(EW), c1 = c1.CM(GX); \
c3 = c3.CM(BC<=FX?BG(CT.BO(BC)+8*KR):GX.LK(EW)); \
JL(c0.KP, c0.KC, c1.KP, c1.KC, c2.KP, c2.KC, c3.KP, c3.KC); \
c0 = c0.EU(ToI64{}), c1 = c1.EU(ToI64{}), c2 = c2.EU(ToI64{}), c3 = c3.EU(ToI64{}); \
c0.DU(LC, JD{}), c1.DU(LD, JD{}), c2.DU(LA, JD{}), c3.DU(KV, JD{}); \
} \
} IV (0)
AY<JY BU=EL>
AJ JO HW(BX BF[],AN AQ){
AG AN BC=AQ/2;
if(BC<=FU)
{
difIter(BF,AQ);
AK;}
EB IJ=LL::CD<JY,BU>;
KK GH=AR<AG BG*>(DW.BO(BC));
AG AN AZ=AQ/4;
difLayer(HW,BF,AZ,GH);}
AY<JY DQ=EL,JY GY=EL>
AJ JO iditRecMid(BX BF[],AN AQ){
AG AN BC=AQ/2;
if(BC<=FU)
{
if(!g_skip_leaf)iditIter(BF,AQ);
AK;}
EB JD=LL::CD<JY,DQ>;
EB ToI64=LL::CD<JY,GY>;
AG AN AZ=AQ/4;
KK GH=AR<AG BG*>(DW.BO(BC));
iditLayer(iditRecMid,BF,AZ,GH);}
AJ JO fusedLong(BX*a,AN LF,JY EH){
AN AZ=LF/16;
AG KK&t0=DB[ED(LF/2)];
AG KK&t1=DB[ED(LF/8)];
if(EH)LN(LM k=0;k<16;k++)GI<EL,EL>(a+k*AZ,AZ);
LN(AN j=0;j<AZ;j+=8){
if(j>=64&&j+416<AZ){
LN(LM k=0;k<16;k++)BR((AG JX*)(a+(AN)k*AZ+j-64+32*k),CA);
}
BG v[16];
KK butterfly=[&](BG&c0,BG&c1,BG&c2,BG&c3,AG BG&w){
BG w2=w.LK(w),w3=w2 .LK(w);
if(EH){
c1=c1 .CM(w2);c2=c2 .CM(w);c3=c3 .CM(w3);
JL(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
}JW{
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(w2);c2=c2 .LK(w);c3=c3 .LK(w3);
}
};
AG BG w=t1[j/8],w2=w.LK(w),w3=w2 .LK(w);
KK FG=[&](BG&c0,BG&c1,BG&c2,BG&c3){
if(EH){
c1=c1 .CM(w2);c2=c2 .CM(w);c3=c3 .CM(w3);
JL(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
}JW{
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c1=c1 .LK(w2);c2=c2 .LK(w);c3=c3 .LK(w3);
}
};
if(EH){
#pragma GCC unroll 4
LN(LM q=0;q<4;q++){
v[4*q]=BG(a+(4*q)*AZ+j);
v[4*q+1]=BG(a+(4*q+1)*AZ+j);
v[4*q+2]=BG(a+(4*q+2)*AZ+j);
v[4*q+3]=BG(a+(4*q+3)*AZ+j);
FG(v[4*q],v[4*q+1],v[4*q+2],v[4*q+3]);
}
#pragma GCC unroll 4
LN(LM k=0;k<4;k++){
butterfly(v[k],v[k+4],v[k+8],v[k+12],t0[(k*AZ+j)/8]);
v[k].DU(a+k*AZ+j);
v[k+4].DU(a+(k+4)*AZ+j);
v[k+8].DU(a+(k+8)*AZ+j);
v[k+12].DU(a+(k+12)*AZ+j);
}
}JW{
#pragma GCC unroll 4
LN(LM k=0;k<4;k++){
v[k]=BG(a+k*AZ+j);
v[k+4]=BG(a+(k+4)*AZ+j);
v[k+8]=BG(a+(k+8)*AZ+j);
v[k+12]=BG(a+(k+12)*AZ+j);
butterfly(v[k],v[k+4],v[k+8],v[k+12],t0[(k*AZ+j)/8]);
}
#pragma GCC unroll 4
LN(LM q=0;q<4;q++){
FG(v[4*q],v[4*q+1],v[4*q+2],v[4*q+3]);
v[4*q].DU(a+(4*q)*AZ+j);
v[4*q+1].DU(a+(4*q+1)*AZ+j);
v[4*q+2].DU(a+(4*q+2)*AZ+j);
v[4*q+3].DU(a+(4*q+3)*AZ+j);
}
}
}
if(!EH)LN(LM k=0;k<16;k++)FY<EL>(a+k*AZ,AZ);
}
AJ JO difFuseAB(BX*a,AN AQ){
AG AN BC=AQ/2;
AG AN sa=AQ/4;
AG AN sb=sa/4;
AG KK&TA=DB[ED(BC)];
AG BG*TB=AR<AG BG*>(DW.BO(sa/2));
LN(AN j0=0;j0<sb;j0+=8){
BG A[4][4]={NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64,NI64};
AG AN jb=j0>>3;
AG BG*talp=TA.lowPtr()+(jb&TA.MASKV);
AG BG talv=*talp;
AG AN tahbase=(jb>>TA.LOGV),tahstep=(sb>>3)>>TA.LOGV;
LN(LM k2=0;k2<4;k2++){
LE*pj=a+(AN)k2*sb+j0;
BR((AG JX*)(pj+sa+128+8*k2),CA);
BR((AG JX*)(pj+2*sa+136+8*k2),CA);
BR((AG JX*)(pj+3*sa+144+8*k2),CA);
BG c0(pj),c1(pj+sa),c2(pj+2*sa),c3(pj+3*sa);
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
AG C64*tahp=TA.highPtr()+tahbase+(AN)k2*tahstep;
BG tah(CR{});{AG LE*hq=AR<AG LE*>(tahp);tah.load1(hq,hq+1);}
BG w=talv.LK(tah),w2=w.LK(w);
c2=c2 .LK(w);c1=c1 .LK(w2);c3=c3 .LK(w2 .LK(w));
A[k2][0]=c0;A[k2][1]=c1;A[k2][2]=c2;A[k2][3]=c3;
}
AG BG wB=TB[j0>>3],wB2=wB.LK(wB),wB3=wB2 .LK(wB);
LN(LM k1=0;k1<4;k1++){
BG c0=A[0][k1],c1=A[1][k1],c2=A[2][k1],c3=A[3][k1];
KQ(c0 .KP,c0 .KC,c1 .KP,c1 .KC,c2 .KP,c2 .KC,c3 .KP,c3 .KC);
c2=c2 .LK(wB);c1=c1 .LK(wB2);c3=c3 .LK(wB3);
LE*q=a+(AN)k1*sa+j0;
c0 .DU(q);c1 .DU(q+sb);c2 .DU(q+2*sb);c3 .DU(q+3*sb);
}
}
LN(LM k1=0;k1<4;k1++)LN(LM k2=0;k2<4;k2++)
HW<EL>(a+(AN)k1*sa+(AN)k2*sb,sb);
}
AY<JY BU=EL>
AJ JO FY(BX BF[],AN AQ){
if AP(!BU)if(AQ/2>=(1ULL<<22)){fusedLong(BF,AQ,EL);AK;}
AG AN BC=AQ/2;
if(BC<=FX)
{
HW<BU>(BF,AQ);
AK;}
if AP(!BU)
if(AQ>(1ULL<<18)&&AQ<=(1ULL<<20)){difFuseAB(BF,AQ);AK;}
EB IJ=LL::CD<JY,BU>;
AG KK&GH=DB[ED(BC)];
AG AN AZ=AQ/4;
difLayer(FY,BF,AZ,GH);}
AY<JY DQ=EL,JY GY=EL>
AJ JO GI(BX BF[],AN AQ){
if AP(!DQ&&!GY)if(AQ/2>=(1ULL<<22)){fusedLong(BF,AQ,JZ);AK;}
AG AN BC=AQ/2;
if(BC<=FX)
{
iditRecMid<DQ,GY>(BF,AQ);
AK;}
EB JD=LL::CD<JY,DQ>;
EB ToI64=LL::CD<JY,GY>;
AG AN AZ=AQ/4;
AG KK&GH=DB[ED(BC)];
iditLayer(GI,BF,AZ,GH);}};
#undef difLayer
#undef iditLayer
AP LM DL::FW,DL::IO,DL::IC,DL::LOG_CACHE;
AP AN DL::FU,DL::FX,DL::MAX_LEN;
DL::TableFix4 DL::table_8(8,1,4),DL::table_16_1(16,1,4),DL::table_16_3(16,3,4);
DL::TableFix8 DL::table_32_1(32,1,4),DL::table_32_3(32,3,4);
DL::HL DL::BS(2);
DL::HM DL::DI(3);
DL::HK DL::DW(1),DL::CS(2),DL::CT(3);
DL::TableSqrt DL::DB(1);
DC GG{JY enabled=EL;BN JO run(LE*,AN){LL::abort();}}
}}}
#pragma GCC push_options
#pragma GCC target("avx2,fma")
#pragma GCC optimize("O3")
DC packed_fft{
EB LO=BY;EB C=LL::complex<CG>;EB FFT=hint::transform::fft::DL;
BN AC at(AC i){AK 8*(i/4)+i%4;}
BN C get(AG CG*a,AC i){AC k=at(i);AK{a[k],a[k+4]};}
BN JO put(CG*a,AC i,C v){AC k=at(i);a[k]=v.KP();a[k+4]=v.KC();}
BN AC negslot(AC i){AK i?i^((1u<<(31-__builtin_clz(i)))-1):0;}
GQ Result{JY certified=EL;JT CG bound=0;CG observed_max_fraction=0;};
IN FZ{
AC h,n;hint::ET<CG>x,y,z;CE normB=0;
EB CV=hint::CL;EB FV=hint::DM;
AJ CV conjugate(CV v){v.KC=FV(_mm256_xor_pd(BZ(v.KC),DN(-0.)));AK v;}
AJ CV product(CV X,CV Xc,CV Y,CV Yc){AK(X+Xc).LK(Y+Yc)*FV(.25)+(X.LK(Y)-Xc.LK(Yc))*FV(.5);}
HA:
GV FZ(AG LO*b,AC KG):h(KG),n(2*KG),x(4*KG),y(4*KG),z(4*KG){
IR(h>=8&&h<=(1u<<20)&&(h&(h-1))==0);LL::fill(y.DK(),y.DK()+2*n,0.);
LN(AC i=0;i<h;++i){LM lo=int16_t(b[i]),hi=int16_t((b[i]+32768u)>>16);put(y.DK(),h-1-i,{CG(lo),CG(hi)});normB+=HH(lo)*lo+HH(hi)*hi;}
FFT::FY<EL>(y.DK(),2*n);
}
Result JG(AG LO*a,LO*LI){
CE normA=0;LN(AC i=0;i<n;++i){LM lo=int16_t(a[i]),hi=int16_t((a[i]+32768u)>>16);put(x.DK(),i,{CG(lo),CG(hi)});normA+=HH(lo)*lo+HH(hi)*hi;}
FFT::FY<EL>(x.DK(),2*n);JT CG normZ2=0;
LN(AC i=0;i<4;++i){AC j=negslot(i);C X=get(x.DK(),i),Xc=LL::conj(get(x.DK(),j)),Y=get(y.DK(),i),Yc=LL::conj(get(y.DK(),j));C Z=.25*(X+Xc)*(Y+Yc)+.5*(X*Y-Xc*Yc);put(z.DK(),i,Z);normZ2+=CP<JT CG>(Z.KP())*Z.KP()+CP<JT CG>(Z.KC())*Z.KC();}
BZ norms=_mm256_setzero_pd();LN(AC HG=4;HG<n;HG*=2)LN(AC i=HG;i<HG*2;i+=4){AC j=3*HG-4-i;CV X(x.DK()+2*i),Xc=conjugate(CV(x.DK()+2*j).IB()),Y(y.DK()+2*i),Yc=conjugate(CV(y.DK()+2*j).IB());CV Z=product(X,Xc,Y,Yc);Z.DU(z.DK()+2*i);norms=FE(BZ(Z.KP),BZ(Z.KP),norms);norms=FE(BZ(Z.KC),BZ(Z.KC),norms);}
alignas(32)CG sums[4];_mm256_store_pd(sums,norms);LN(CG IP:sums)normZ2+=IP;
AP JT CG u=0x1p-53L;JT CG op=(n<=(1u<<17)?5:64)*(AC(DS(n))+1),JN=op*u/(1-op*u),normprod=sqrtl(CP<JT CG>(normA)*normB);JT CG normZ=sqrtl(normZ2)*(1+32*n*u);
JT CG error=(4*JN+2*JN*JN+128*u*(1+JN)*(1+JN))*normprod+JN*normZ/sqrtl(n);Result IK;IK.bound=error;if(!(error<.49L))AK IK;
if(_MM_GET_ROUNDING_MODE()!=_MM_ROUND_NEAREST)AK IK;
FFT::GI<EL,EL>(z.DK(),2*n);AG BZ IU=DN(1./n),JJ=DN(0x1.8p52);AG AA mb=BL(JJ),perm=EG(0,2,4,6,1,3,5,7);AC t=0;
KK scalar=[&](AC atout){C v=get(z.DK(),h-1+atout)/CG(n);LI[atout]=LO(llround(v.KP()))+(LO(llround(v.KC()))<<16);};scalar(t++);
LN(;t+4<=h;t+=4){AC pos=2*(h-1+t);BZ re=GK(EC(z.DK()+pos),IU),im=GK(EC(z.DK()+pos+4),IU);AA ri=CI(BL(DT(re,JJ)),mb),ii=CI(BL(DT(im,JJ)),mb);AD low=AV(BI(ri,perm)),HQ=AV(BI(ii,perm));BA((AD*)(LI+t),DR(low,_mm_slli_epi32(HQ,16)));}
LN(;t<h;++t)scalar(t);IK.certified=JZ;AK IK;
}
};
BN Result IT(AG LO*a,AG LO*b,LO*LI,AC h){FZ plan(b,h);AK plan.JG(a,LI);}
}
#pragma GCC pop_options
#pragma once
#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
DC mod_karatsuba{
EB LO=BY;EB LG=CE;
BH((noinline))BN JO IT(AG LO*__restrict a,AG LO*__restrict b,LO*__restrict LI,AC h,LO*EI){
if(h<=32){
if(h<8){LN(AC t=0;t<h;++t){LO z=0;LN(AC i=0;i<h;++i)z+=a[i+t]*b[i];LI[t]=z;}AK;}
LN(AC t=0;t<h;t+=8){AA z=CO();LN(AC i=0;i<h;++i)z=AF(z,BJ(CK((AG AA*)(a+i+t)),AB(b[i])));CQ((AA*)(LI+t),z);}AK;
}
AG AC s=h/2;LO*x=EI,*y=x+h,*bs=y+h,*tmp=bs+s,*KI=tmp+s;
LN(AC i=0;i<h;++i){x[i]=a[i]-a[s+i];y[i]=a[h+i]-a[s+i];}
LN(AC i=0;i<s;++i)bs[i]=b[i]+b[s+i];
IT(x,b,LI,s,KI);IT(y,b+s,LI+s,s,KI);IT(a+s,bs,tmp,s,KI);
LN(AC i=0;i<s;++i){LI[i]+=tmp[i];LI[s+i]+=tmp[i];}
}
BH((noinline))BN JO HQ(AC n,AG LO*a,AG LO*b,LO*c,AC l,AC r,AC qlo=1,AC qhi=~0u){
AG AC w=(r-l)/2,m=l+w,jend=LL::min(r,n);if(!w||m>=jend||l+m>=n)AK;
qhi=LL::min(qhi,(n-1-l)/m);
LN(AC q=qlo;q<=qhi;++q){AC HZ=LL::min(w,n-q*m-l),h=1;IV(h<(HZ+q-1)/q)h*=2;
LL::HX<LO>bb(h),aa(2*h+8),z(h),EI(6*h+32);
LN(AC jb=m;jb<jend;jb+=h){AC HC=LL::min(h,jend-jb);LL::fill(bb.DK(),bb.KU(),0);LL::copy(b+jb,b+jb+HC,bb.KF());
LN(AC rho=0;rho<LL::min(q,HZ);++rho){AC LF=(HZ-1-rho)/q+1;LG start=LG(q)*jb+l+rho;
LN(AC i=0;i<2*h;++i){LG at=start+LG(q)*i;aa[i]=at<n?a[at]:0;}
IT(aa.KF(),bb.KF(),z.KF(),h,EI.KF());
LN(AC t=0;t<LF;++t)c[l+rho+q*t]+=z[t];
}
}
}
}
BH((noinline))BN JO triangle(AC n,AG LO*a,AG LO*b,LO*c,AC l,AC r){
if(r-l<=32){LN(AC j=l+1;j<LL::min(r,n-l);++j)LN(AC st=j;st+l<n;st+=j)LN(AC k=l;k<LL::min(r,LL::min(j,n-st));++k)c[k]+=a[st+k]*b[j];AK;}
if(2ull*l+1>=n)AK;AC m=l+(r-l)/2;triangle(n,a,b,c,l,m);triangle(n,a,b,c,m,r);HQ(n,a,b,c,l,r);
}
}
#ifndef DUCK_SHA256_HPP
#define DUCK_SHA256_HPP
#include <stddef.h>
#include <stdint.h>
#include <string.h>
DC HN{
AJ BN BY GF(BY x,AC n){AK(x>>n)|(x<<(32-n));}
AJ JO IL(BY h[8],AG AC JX HG[64]){
AJ AG BY k[64]={
0x428a2f98u,0x71374491u,0xb5c0fbcfu,0xe9b5dba5u,0x3956c25bu,0x59f111f1u,0x923f82a4u,0xab1c5ed5u,
0xd807aa98u,0x12835b01u,0x243185beu,0x550c7dc3u,0x72be5d74u,0x80deb1feu,0x9bdc06a7u,0xc19bf174u,
0xe49b69c1u,0xefbe4786u,0x0fc19dc6u,0x240ca1ccu,0x2de92c6fu,0x4a7484aau,0x5cb0a9dcu,0x76f988dau,
0x983e5152u,0xa831c66du,0xb00327c8u,0xbf597fc7u,0xc6e00bf3u,0xd5a79147u,0x06ca6351u,0x14292967u,
0x27b70a85u,0x2e1b2138u,0x4d2c6dfcu,0x53380d13u,0x650a7354u,0x766a0abbu,0x81c2c92eu,0x92722c85u,
0xa2bfe8a1u,0xa81a664bu,0xc24b8b70u,0xc76c51a3u,0xd192e819u,0xd6990624u,0xf40e3585u,0x106aa070u,
0x19a4c116u,0x1e376c08u,0x2748774cu,0x34b0bcb5u,0x391c0cb3u,0x4ed8aa4au,0x5b9cca4fu,0x682e6ff3u,
0x748f82eeu,0x78a5636fu,0x84c87814u,0x8cc70208u,0x90befffau,0xa4506cebu,0xbef9a3f7u,0xc67178f2u};
BY w[64];
LN(AC i=0;i<16;++i)w[i]=(BY(HG[4*i])<<24)|(BY(HG[4*i+1])<<16)|(BY(HG[4*i+2])<<8)|HG[4*i+3];
LN(AC i=16;i<64;++i){BY a=w[i-15],b=w[i-2];w[i]=w[i-16]+(GF(a,7)^GF(a,18)^(a>>3))+w[i-7]+(GF(b,17)^GF(b,19)^(b>>10));}
BY a=h[0],b=h[1],c=h[2],d=h[3],e=h[4],f=h[5],g=h[6],v=h[7];
LN(AC i=0;i<64;++i){
BY t1=v+(GF(e,6)^GF(e,11)^GF(e,25))+((e&f)^(~e&g))+k[i]+w[i];
BY t2=(GF(a,2)^GF(a,13)^GF(a,22))+((a&b)^(a&c)^(b&c));
v=g;g=f;f=e;e=d+t1;d=c;c=b;b=a;a=t1+t2;
}
h[0]+=a;h[1]+=b;h[2]+=c;h[3]+=d;h[4]+=e;h[5]+=f;h[6]+=g;h[7]+=v;
}
BN JO digest(AG JO*KF,AN length,AC JX LI[32]){
BY h[8]={0x6a09e667u,0xbb67ae85u,0x3c6ef372u,0xa54ff53au,0x510e527fu,0x9b05688cu,0x1f83d9abu,0x5be0cd19u};
AG AC JX*p=(AG AC JX*)KF;
AN whole=length/64;
LN(AN i=0;i<whole;++i)IL(h,p+64*i);
AC JX KO[128]={};AN remain=length%64;
if(remain)memcpy(KO,p+64*whole,remain);
KO[remain]=0x80;AN padded=remain<56?64:128;
CE KH=CE(length)*8;
LN(AC i=0;i<8;++i)KO[padded-1-i]=(AC JX)(KH>>(8*i));
IL(h,KO);if(padded==128)IL(h,KO+64);
LN(AC i=0;i<8;++i)LN(AC j=0;j<4;++j)LI[4*i+j]=(AC JX)(h[i]>>(24-8*j));
}
}
#endif
#include <x86intrin.h>
AJ CE ticks(){_mm_lfence();AK __rdtsc();}
GQ PublicRng{CE s;AC KI(){CE z=(s+=0x9e3779b97f4a7c15ULL);z=(z^(z>>30))*0xbf58476d1ce4e5b9ULL;z=(z^(z>>27))*0x94d049bb133111ebULL;AK AC(z^(z>>31));}};
LM main(){AC JX hashes[64];AC at=0;PublicRng rg{0x4433998866112255ULL};LN(AC H:{16384u,32768u}){AP AC R=2,T=8192;LL::HX<AC>a(16*H),b(H),cn(8*H),ct(cn.KG()),cp(cn.KG()),aa(2*T),zz(T),EI(6*T+32);LN(KK&v:a)v=rg.KI();LN(KK&v:b)v=rg.KI();nuss::Plan64 bp(b.KF(),H);nuss::Plan4 np(bp);nuss_baseline::FR tp(b.KF(),H);LL::HX<LL::unique_ptr<packed_fft::FZ>>pp;LN(AC j=0;j<H;j+=T)pp.push_back(LL::make_unique<packed_fft::FZ>(b.KF()+j,T));CE t0=ticks();LN(AC r=0;r<R;++r){np.JG(a.KF(),cn.KF(),8);np.JG(a.KF()+4,cn.KF()+4,8);}CE t1=ticks();LN(AC r=0;r<R;++r)tp.JG(a.KF(),ct.KF());CE t2=ticks();AC accepted=0,refused=0;LN(AC r=0;r<R;++r){LL::fill(cp.DK(),cp.KU(),0);LN(AC jb=0;jb<H;jb+=T)LN(AC tb=0;tb<H;tb+=T)LN(AC rho=0;rho<8;++rho){LN(AC i=0;i<2*T;++i)aa[i]=a[8*(jb+tb+i)+rho];KK IK=pp[jb/T]->JG(aa.KF(),zz.KF());if(IK.certified)++accepted;JW{++refused;mod_karatsuba::IT(aa.KF(),b.KF()+jb,zz.KF(),T,EI.KF());}LN(AC t=0;t<T;++t)cp[8*(tb+t)+rho]+=zz[t];}}CE t3=ticks();if(cn!=ct||cn!=cp){puts("FAIL full output");AK 2;}HN::digest(cn.KF(),cn.KG()*4,hashes+32*at++);printf("H%u R%u N%llu T%llu P%llu ok%u no%u\n",H,R,(AC JT JT)(t1-t0),(AC JT JT)(t2-t1),(AC JT JT)(t3-t2),accepted,refused);}AC JX hash[32];HN::digest(hashes,64,hash);LN(KK v:hash)printf("%02x",v);puts(" PASS");}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 251.341 ms | 25 MB + 736 KB | Accepted | Score: 100 | 显示更多 |