/* saffah_codex62a_agg6 https://duck.ac/submission/180359 提供固定因子族及分组记录的狄利克雷卷积。保留原作者、网址和许可说明。 */
/* saffah_codex62a_agg6 https://duck.ac/submission/180116 supplies the measured paired eight- and sixteen-stride input synthesis. Its counterpart https://duck.ac/submission/179938 supplies the specialized six-row families. */
/* saffah_codex62a_agg6 https://duck.ac/submission/179704 supplies the six-factor product families. This account https://duck.ac/submission/179339 explored producing sixteen stride-three terms per initialized span. All upstream sources and license notes follow. */
/* saffah_codex62a_agg6 https://duck.ac/submission/179704 supplies the fixed small-family traversal. Its original code references and license notices follow. */
/* saffah_codex62a_agg6 https://duck.ac/submission/179671 supplies the accepted six-row grouped multiplication. All upstream code, sources and licenses follow. */
/* saffah_v41f1017_agg4 https://duck.ac/submission/178960 supplies the adjusted blocked Dirichlet evaluator, downstream of saffah_codex62a_agg6 https://duck.ac/submission/176396. All original sources and license notices follow. */
/* References / 引用: derived from our own accepted saffah_v41f1017_agg4 https://duck.ac/submission/177248 (complete body below, every inherited notice, author, URL and licence term retained verbatim above the code), which is the adoption of saffah_codex62a_agg6 https://duck.ac/submission/176396 plus the FOLD arm.
Idea / 思路 (2D tiling of the destination c): the adopted body tiles c on ONE axis only - the block (32768 u32 = 128 KiB = half the 256 KiB L2) - and then sweeps every leader row i over the whole block with destination stride i. For i >= 16 that is one read-modify-write per 64 B cache line, so every such row re-fetches the block's entire 2048-line c footprint; the 66 leaders with stride in [16,128) alone own 28.1% of the 428M destination RMWs at n=1e8. This arm adds the second tile axis: inside each block, the leaders with stride in [16,128) are swept window by window (WIN=8192 u32 = 32 KiB) so a window's c lines are fetched once and reused by all 66 band rows before eviction, while the rows outside the band keep the original whole-block sweep. All row cursors are already monotone and stored in the row record (record[1],record[2] for the row, record[7],record[10] for the folded 2i/4i child streams), so the sweep is a pure reordering: every (i,j) product is still evaluated exactly once, in the same order within each row, and every add is integer addition mod 2^32, which is associative and commutative - the output is bit-identical. The band edges and window length are the only new constants. Purpose: measure whether collapsing the redundant c-line re-fetches of the stride band on the active rank-1 chassis is worth more than the added per-(row,window) bookkeeping.
Value gate: FNV-1a over the whole c[] vector byte-identical to accepted 177248 on 1313 n (exhaustive 1..400, every candidate window/block boundary +-1, i*i+-1 for i<320, 1e6+-1, 4194304+1, 1e7, 2e7) and n=1e8 exact a0b2bc4baedf2e53. Judge-side in-process A/B (lfence+rdtscp, order-rotated, 3 rounds): n=1e7 -2.52%, n=6e6 -2.90% against the identical-binary base arm. */
/* Arm note: FOLD - in the fourfold row class the 4i child values land on lanes 0,1 of the 128-bit 2i vector, so they are summed into `more` and zero-extended once instead of twice. All adds are epi32 (no carry crosses a 32-bit lane) so every partial sum is unchanged mod 2^32. Deletes one vpmovzxdq and one vpaddd per eight outputs. Purpose: measure the fold on the adopted rank-1 chassis. */
/* ADOPTION NOTICE. Adopted from account saffah_codex62a_agg6, https://duck.ac/submission/176396 (Accepted, 766707.167 us): the complete body below is used verbatim with every inherited notice, author, URL and licence term intact, and that body's own citation of saffah_v41f1017_agg4 https://duck.ac/submission/174978 is retained on line 2 as its first line records. No arithmetic, no order, no constant and no value is changed; this notice is the only addition. Purpose: re-price the rank-1 body on our own seat and measure it against 0.99*T+1 before any edit. */
/* 引用 saffah_v41f1017_agg4 https://duck.ac/submission/174978 完整算法和数学表,保留原引用与许可。*/
/* References / 引用: duck.ac/submission/172873 (saffah_codex_6a_agg3, the live rank-1
body) and our accepted 173203 replicate of it, both retained with all inherited
notices above. Idea / 思路: the rank-1 body already routes the generic-row source
loads through inline-asm vmovups (root_ld256), but the fused root panel still uses
the _mm256_loadu_si256 / _mm256_storeu_si256 intrinsics, which gcc 9.3.0 emits as
16-byte op + vinserti128 / vextracti128 -- two uops per logical 32-byte access,
30 redundant instructions in every 48-output panel iteration. Purpose: route those
24 loads and 6 stores through the same inline-asm form, changing no arithmetic,
no order and no value. */
/* References / 引用: saffah_codex_6a_agg3
https://duck.ac/submission/170571: complete Accepted sorted parent-row
list, monotone active prefix, fourfold SSE partner fusion/cursors/tails.
saffah_v41f1017_agg4 https://duck.ac/submission/170554: row-invariant flag
specialization idea, extended independently from twofold to fourfold rows.
All inherited authors, exact URLs, used content and notices are retained.
Own saffah_codex61s_agg5 https://duck.ac/submission/170650:
previous generic-lambda row specialization, officially Accepted but slow.
Approach / 思路: Emit the three specialized vector regions lexically in
multiply itself so the owning function directly sees all row scalars,
pointers and cursor variables, without a separate generic-lambda operator
or its capture-object accesses. Each local child helper has literal bool
flags and the original loop arithmetic. Additionally, Instantiate the entire32-wide/eight-wide vector phase
for the three possible row-flag pairs: no child,2i only, or2i plus4i.
Dispatch once per row and make both fusion flags compile-time constants
inside each specialization. Preserve the original SSE partner products,
masked crossing/steady-state arithmetic, scatter order, deferred cursor
updates and every pair. Physical target block=49152.
Experiment purpose:129 quadratic sizes and full10^8 independent divisor
pairs with an explicit specialized-path hit/input/64guards, then official
measurement; local speed never rejects the candidate.
*/
/* References / 引用: Each ID denotes https://duck.ac/submission/{ID}; verified official authors override historical misattributions.
saffah_cc_v41_agg1:100000.
saffah_codex61s_agg5:164808,164972,166022,166311,166337,166395,170141,170182.
saffah_codex_6a_agg3:165981,167080,167081,167082.
saffah_v41f1017_agg4:164782,164866,166996,167233,167897,170438.
170438: copied complete fourfold/odd-part-three folded engine, aligned generic starts, cursor boundaries and masked fringes.170182: incremental integer-square-root window bound idea.170141: doubled-row fusion;167897/167233/167082/167080/167081: first-writer48 stream, generic32 unroll and deferred tails/diagonals.166996/166395/166337/166311/166022/165981: inherited fused low rows and cursor methods;164972/164866/164808/164782: full-width load/store methods. No separate source license is attached.
Idea / 思路: Build the sorted list of actual generic parent divisors once, removing folded child rows from traversal itself. Advance the integer-square-root bound monotonically once per physical window and grow the active prefix of this list. Each window then visits only relevant parent cursors, without repeated64-bit i*i bounds or per-row child/modulus tests. Keep170438 original scalar/SSE child products because the wider partner experiment did not improve official timing. All row order, product coverage and cursor/tail behavior remain unchanged. Purpose: reduce the per-window scheduler overhead with full100M and boundary/arbitrary correctness checks before official measurement. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170669: complete lexical three-region multiply implementation, with all inherited notices above retained. saffah_codex_6a_agg3 https://duck.ac/submission/170611: idea of separating initial masked partner folds from steady unconditional folds; that earlier generic-lambda implementation was slow. Duck sources have no additional license notice.
Idea / 思路: In the two partner-enabled lexical regions, test once whether the starting aligned cursor is past every child cursor. If so, use a full lexical copy of the body whose partner additions are unconditional; otherwise retain the original masked boundary body. All later product indices increase, so the single row test suffices. This combines the observed efficient lexical layout with removing repeated child-start comparisons inside each32-product iteration. Purpose: reduce folded-row bookkeeping, with full100M and fallback verification before online measurement. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170707: complete lexical steady-fold engine; https://duck.ac/submission/170526: first-writer low-row fusion idea. All inherited authors and notices above retained.
Idea / 思路: Fuse row8 into the existing row4 SSE vector before the48-output first-writer stores. Each16-output section computes two row8 products and interleaves them into the four row4 products. Mask the initial diagonal/crossing section, handle window fringes with a row8 cursor, and delete row8 from generic traversal and final tails. Purpose: eliminate row8's separate destination read-modify-write stream. Validate all100M outputs plus boundaries and fallback cases before official timing. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170728: complete first-writer row8 fusion and lexical engine. All inherited sources above retained.
Idea / 思路: Extend the row8 first-writer vector with one row16 scalar product in its low lane for each16 output positions. Use its exact diagonal cutoff and cursor fringes, then remove row16 from generic traversal and final tails. Purpose: eliminate another sparse destination read-modify-write pass while reusing row8-to-row4 interleaving. Full100M, random, boundaries and small cases verified before official timing. */
/* References / 引用:
* saffah_v41f1017_agg4 https://duck.ac/submission/171744: complete accepted engine with row-constant caching, large-input specialization, first-writer16 and all inherited notices above.
Idea / 思路: Cache coefficients only for actual generic parent rows, in their traversal order, using exactly six32-bit words per parent instead of eight words for every divisor. Index by the current parent-row ordinal. This removes unused folded-row entries and padding from repeated coefficient traffic, while preserving all six constants, specialization, cursors, pair coverage and arithmetic order.
Experiment purpose: independent divisor-pair outputs for two full100M arrays, boundaries, hashes and guards, then official timing of the compact physical coefficient stream.
*/
/* References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/171798: actual-parent coefficient cache and complete accepted multiplication engine, retaining all inherited author URLs and notices above.
Idea / 思路: Partition independent parent rows by zero, one or two folded children. Each sorted group has its own monotone active prefix and exactly two, four or six coefficient words per row. Instantiate each group with compile-time child flags, eliminating runtime shape branches and unused coefficient traffic. Outputs are modulo-2^32 additive, and each child cursor has exactly one parent, so group traversal preserves coverage and results.
Experiment purpose: full independent100M divisor-pair correctness, varied boundaries/alignment/input hashes and output guards, then official timing of reduced coefficient footprint and compile-time row shapes.
*/
/* References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/171847: compile-time child-count groups and compact coefficients; all original engine references and notices remain above.
Idea / 思路: Store each generic parent's divisor, two advancing cursors and used coefficients in one contiguous record. Folded child cursors retain their separate array because no folded child is a generic parent. Each hot iteration now reads and writes the parent's sequential record, avoiding the dependent position[i] lookup and separate row-index stream. Reconcile parent cursors once after all windows for the final scalar tails.
Experiment purpose: verify two full100M independent divisor-pair arrays plus boundaries, alignments, guards and input hashes, then measure the official cost of unifying hot parent state.
*/
/* 对奇数部分至少5的行,按二进因子指数每三层一组,令原来独立的8i、16i、32i再次进入同一融合散射行。*/
/* Approach and experiment: For each selected odd divisor 5,7,11,13,17,19,23,25,29,31, fuse its rows at multipliers 1, 2, 3, 4, 6 and 12 into one output traversal. Each aligned span of 24 computes three parent vectors and one independent stride-three vector; inject its eight contributions at their exact positions before each scalar scatter. Handle short squares and incomplete tile spans with the exact divisor condition. Test destination traffic and arithmetic costs. */
/* Approach and experiment: Extend the six-factor destination traversal to odd roots coprime to 3 through 127. Evaluate 24-value spans separately at the exact activation squares of multipliers 2, 3, 4, 6 and 12. Each span contains only the child factors whose symmetric partners have already started. Keep incomplete SIMD tails pending for the next initialized destination tile and complete the final one exactly. Allow partly populated factor groups near the square root; each activated term itself proves the corresponding factor exists. Measure full-product throughput. */
/* Approach and experiment: Specialize the numerical phases for divisors 5,7,11,13 so their addresses, lane offsets and square thresholds fold at compilation. Retain ordinary exact grouped evaluation up to divisor 13. Measure the destination update cost with tiles of 32768 coefficients. */
/* Approach and experiment: Separate initialization below the last small-divisor square from steady 48-output blocks. In the steady region every multiplier through sixteen is active, so omit per-pair activation masks and late-start branches. Compute exactly sixteen stride-three products in two vectors per full block, then permute each into the three output vectors it serves. Evaluate three stride-sixteen coefficients together and extract their low scalar slots. Form all six stride-eight terms from one neighboring eight-wide multiply pair. Measure the first write of every output and its subsequent true Dirichlet sum. */
/* 结束最末输出块后,直接从五字、八字、十一字的因子记录取出游标和已保存的系数,就地处理每一行的余项。按逆因子顺序处理。由同一记录同时计算平方项。不再把全部成组游标拷回独立的稀疏位置表,实验大规模乘法卷积尾端的访存变化。 */
#include <type_traits>
#include<type_traits>
#include <immintrin.h>
#include <algorithm>
#include <cstdint>
#include <vector>
#include <cstring>
static __attribute__((always_inline))inline __m256i root_ld256(const void*p){__m256i v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const __m256i*)p));return v;}
static __attribute__((always_inline,target("avx")))inline __m256i root_single256_li(const __m256i*p){__m256i v;__asm__("vmovdqu %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_si(__m256i*p,__m256i v){__asm__("vmovdqu %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256d root_single256_ld(const double*p){__m256d v;__asm__("vmovupd %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sd(double*p,__m256d v){__asm__("vmovupd %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256 root_single256_lf(const float*p){__m256 v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sf(float*p,__m256 v){__asm__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline void root_st256(void*p,__m256i v){__asm__ __volatile__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v):"memory");}
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace root_fast {
using u32=unsigned;using u64=unsigned long long;
inline u32 reduce(__m256i x){__m128i y=_mm_add_epi32(_mm256_castsi256_si128(x),_mm256_extracti128_si256(x,1));y=_mm_add_epi32(y,_mm_srli_si128(y,8));y=_mm_add_epi32(y,_mm_srli_si128(y,4));return _mm_cvtsi128_si32(y);}
inline void divide(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;u32 sb=0;for(unsigned j=1;j<n;++j)sb+=b[j];c[0]=a[0]*sb;
constexpr unsigned block=65536;
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);
for(unsigned i=1;u64(i)*i<hi;++i){
unsigned j=std::max(i,(lo+i-1)/i),last=(hi-1)/i,k=i*j;u32 sum=0,bi=b[i];
if(j==i){sum+=a[k]*bi;++j;k+=i;}
__m256i vs=_mm256_setzero_si256(),vb=_mm256_set1_epi32(bi),ix=_mm256_setr_epi32(0,i,2*i,3*i,4*i,5*i,6*i,7*i);
for(;j+7<=last;j+=8,k+=8*i){
__m256i x=_mm256_i32gather_epi32((const int*)(a+k),ix,4);
vs=_mm256_add_epi32(vs,_mm256_mullo_epi32(x,root_ld256(b+j)));
__m256i old=_mm256_loadu_si256((const __m256i*)(c+j));
_mm256_storeu_si256((__m256i*)(c+j),_mm256_add_epi32(old,_mm256_mullo_epi32(x,vb)));
}
sum+=reduce(vs);
for(;j<=last;++j,k+=i){u32 x=a[k];sum+=x*b[j];c[j]+=x*bi;}c[i]+=sum;
}
}
}
inline void floor_conv(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
if(!n)return;std::vector<u32>prefix(n);u32 total=0;
for(unsigned i=0;i<n;++i){prefix[i]=total;total+=a[i];}
divide(n,prefix.data(),b,c);
u32 tail=0,previous=0;unsigned bound=n;
for(unsigned k=1;k<n;++k){unsigned need=(n-1)/k+1;while(bound>need)tail+=b[--bound];u32 current=c[k]+total*tail;c[k-1]=current-previous;previous=current;}
while(bound>1)tail+=b[--bound];c[n-1]=total*tail-previous;
}
inline std::vector<unsigned> primes(unsigned n){
std::vector<unsigned char> comp((n+1)/2);std::vector<unsigned> ps;
if(n>2)ps.push_back(2);
for(unsigned i=3;u64(i)*i<n;i+=2)if(!comp[i/2])for(unsigned j=i*i;j<n;j+=i*2)comp[j/2]=1;
for(unsigned i=3;i<n;i+=2)if(!comp[i/2])ps.push_back(i);return ps;
}
inline void gcd_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned> f(b,b+n);std::memcpy(c,a,size_t(n)*4);
for(unsigned p:ps){
unsigned i=(n-1)/p;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i>=15;i-=8){unsigned l=i-7;
auto x=_mm256_i32gather_epi32((const int*)(c+l*p),ix,4),y=_mm256_i32gather_epi32((const int*)(f.data()+l*p),ix,4);
_mm256_storeu_si256((__m256i*)(c+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(c+l)),x));
_mm256_storeu_si256((__m256i*)(f.data()+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(f.data()+l)),y));
}
for(;i;--i){c[i]+=c[i*p];f[i]+=f[i*p];}
}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){
unsigned last=(n-1)/p,i=1;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i+7<=last;i+=8){auto x=_mm256_i32gather_epi32((const int*)(c+i*p),ix,4);_mm256_storeu_si256((__m256i*)(c+i),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(c+i)),x));}
for(;i<=last;++i)c[i]-=c[i*p];
}
c[0]=a[0]*b[0];for(unsigned i=1;i<n;++i)c[i]+=a[0]*b[i]+b[0]*a[i];
}
}
namespace root_fast {
inline void lcm_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned>f(b,b+n);std::memcpy(c,a,size_t(n)*4);
u32 sa=0,sb=0;for(unsigned i=0;i<n;++i){sa+=a[i];sb+=b[i];}
for(unsigned p:ps){unsigned last=(n-1)/p;for(unsigned i=1,k=p;i<=last;++i,k+=p){c[k]+=c[i];f[k]+=f[i];}}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){for(unsigned i=(n-1)/p,k=i*p;i;--i,k-=p)c[k]-=c[i];}
c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
#ifdef ROOT_PAIR_CHECK
static uint64_t root_pair_hits=0;
#endif
#ifdef ROOT_ROW_FLAGS_CHECK
static uint64_t root_row_flags_hits=0;
#endif
template<bool root_BIG> inline void multiply_t(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;if(n==1){c[0]=a[0]*b[0];return;}
__m256i vsa=_mm256_setzero_si256(),vsb=_mm256_setzero_si256();
u32 sa=a[0]+a[1],sb=b[0]+b[1];
const unsigned block=32768;
unsigned bound=1;while(u64(bound)*bound<n)++bound;
struct Position{unsigned j,k;};std::vector<Position>position(bound+1);
for(unsigned i=1;i<bound;++i)position[i]={i+1,i*i+i};c[1]=0;std::vector<unsigned> rowgroups[3];std::vector<u32> coeffgroups[3];
std::vector<unsigned char> grouped3(bound);std::vector<unsigned> family3;for(unsigned f=5;f<=13&&3*f<bound;f+=2)if(f%3){family3.push_back(f);for(unsigned d:{1u,2u,3u,4u,6u,12u})if(d*f<bound)grouped3[d*f]=1;}for(unsigned i=5;i<bound;++i){if(grouped3[i])continue;unsigned exponent=__builtin_ctz(i),odd=i>>exponent;bool pair;if(odd>=5){if(exponent%3)continue;pair=2*i<bound;}else{if(i==8||i==16)continue;if(i>=10&&(i&3)==2)continue;if(i>=20&&(i&7)==4)continue;if(i==12||i==24)continue;
pair=(i>=5&&((i&1)||i==6)&&2*i<bound);}unsigned g=pair?(4*i<bound?2:1):0;rowgroups[g].push_back(i);auto &v=coeffgroups[g];v.push_back(i);v.push_back(position[i].j);v.push_back(position[i].k);v.push_back(a[i]);v.push_back(b[i]);if(g>=1){v.push_back(a[2*i]);v.push_back(b[2*i]);v.push_back(position[2*i].j);}if(g>=2){v.push_back(a[4*i]);v.push_back(b[4*i]);v.push_back(position[4*i].j);}}
unsigned bands[3][2];for(unsigned g=0;g<3;++g){auto&bv=rowgroups[g];unsigned bn=bv.size(),q=0;while(q<bn&&bv[q]<16u)++q;bands[g][0]=q;while(q<bn&&bv[q]<128u)++q;bands[g][1]=q;}unsigned imax=3,activegroups[3]={};
position[2]={3,6};
const u32 a1=a[1],b1=b[1],a2=n>2?a[2]:0,b2=n>2?b[2]:0;
const bool root_sixteen=root_BIG||(bound>16);const unsigned a16=n>16?a[16]:0,b16=n>16?b[16]:0;const bool root_eight=root_BIG||(bound>8);const unsigned a8=n>8?a[8]:0,b8=n>8?b[8]:0;const __m128i va8=_mm_set1_epi32(a8),vb8=_mm_set1_epi32(b8);const bool root_four=root_BIG||(bound>4);const u32 root_a4=n>4?a[4]:0,root_b4=n>4?b[4]:0;
const __m128i root_va4=_mm_set1_epi32(root_a4),root_vb4=_mm_set1_epi32(root_b4),root_zero128=_mm_setzero_si128();
const bool root_three=root_BIG||(bound>3);const u32 a3r=n>3?a[3]:0,b3r=n>3?b[3]:0;
const __m256i va3=_mm256_set1_epi32((int)a3r),vb3=_mm256_set1_epi32((int)b3r);
const __m256i g0i=_mm256_setr_epi32(0,0,0,1,0,0,2,0),g1i=_mm256_setr_epi32(0,3,0,0,4,0,0,5);
const __m256i h0i=_mm256_setr_epi32(0,0,0,0,0,1,0,0),h1i=_mm256_setr_epi32(2,0,0,3,0,0,4,0);
const __m256i k0i=_mm256_setr_epi32(0,0,0,0,1,0,0,2),k1i=_mm256_setr_epi32(0,0,3,0,0,4,0,0);
const auto va1=_mm256_set1_epi32(a1),vb1=_mm256_set1_epi32(b1),va2=_mm256_set1_epi32(a2),vb2=_mm256_set1_epi32(b2),zero=_mm256_setzero_si256();
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);while(u64(imax)*imax<hi)++imax;for(unsigned g=0;g<3;++g)while(activegroups[g]<rowgroups[g].size()&&rowgroups[g][activegroups[g]]<imax)++activegroups[g];
unsigned k=position[1].k,j2=position[2].j,k2=position[2].k;
unsigned root_j4=root_four?position[4].j:0,root_k4=root_four?position[4].k:hi;unsigned root_j8=root_eight?position[8].j:0,root_k8=root_eight?position[8].k:hi;unsigned root_j16=root_sixteen?position[16].j:0,root_k16=root_sixteen?position[16].k:hi;
unsigned j3=root_three?position[3].j:0,k3=root_three?position[3].k:hi;
for(;k<hi&&(k%48);++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<k&&k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<k&&root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<k&&root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<k&&root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<k&&k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
auto unit48=[&](auto tag,unsigned limit) __attribute__((always_inline)){constexpr bool steady=decltype(tag)::value;for(;k+47<limit;k+=48,j2+=24,k2+=48){
unsigned q=k/3;__m256i three[2];if constexpr(steady){
#pragma GCC unroll 2
for(int j=0;j<2;j++)three[j]=_mm256_add_epi32(_mm256_mullo_epi32(va3,root_ld256(b+q+8*j)),_mm256_mullo_epi32(vb3,root_ld256(a+q+8*j)));}
__m128i sixteen{};if constexpr(steady)sixteen=_mm_add_epi32(_mm_mullo_epi32(_mm_set1_epi32(a16),_mm_loadu_si128((const __m128i*)(b+k/16))),_mm_mullo_epi32(_mm_set1_epi32(b16),_mm_loadu_si128((const __m128i*)(a+k/16))));
__m256i eights{};if constexpr(steady)eights=_mm256_add_epi32(_mm256_mullo_epi32(_mm256_set1_epi32(a8),root_ld256(b+k/8)),_mm256_mullo_epi32(_mm256_set1_epi32(b8),root_ld256(a+k/8)));
{
auto av0=root_ld256(a+k),av1=root_ld256(a+k+8);
auto bv0=root_ld256(b+k),bv1=root_ld256(b+k+8);
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,root_ld256(b+j2)),_mm256_mullo_epi32(vb2,root_ld256(a+j2)));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(steady||(root_four)){unsigned w=k/4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(steady||(root_eight)){unsigned q=w/2;__m128i more=(steady?_mm256_castsi256_si128(eights):_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q)))));if constexpr(!steady)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(steady||(root_sixteen&&q>=34)){unsigned r=q/2;more=_mm_add_epi32(more,(steady?_mm_cvtsi32_si128(_mm_extract_epi32(sixteen,0)):_mm_cvtsi32_si128(a16*b[r]+b16*a[r])));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if constexpr(steady){x0=_mm256_add_epi32(x0,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[0],_mm256_setr_epi32(0,0,0,1,0,0,2,0)),73));x1=_mm256_add_epi32(x1,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[0],_mm256_setr_epi32(0,3,0,0,4,0,0,5)),146));}else if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,root_ld256(b+q)),_mm256_mullo_epi32(vb3,root_ld256(a+q)));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g0i),zero,0xB6));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g1i),zero,0x6D));}
root_st256(c+k,_mm256_add_epi32(u0,x0));
root_st256(c+k+8,_mm256_add_epi32(u1,x1));
}
{
auto av0=root_ld256(a+k+16),av1=root_ld256(a+k+24);
auto bv0=root_ld256(b+k+16),bv1=root_ld256(b+k+24);
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,root_ld256(b+j2+8)),_mm256_mullo_epi32(vb2,root_ld256(a+j2+8)));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(steady||(root_four)){unsigned w=k/4+4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(steady||(root_eight)){unsigned q=w/2;__m128i more=(steady?_mm_srli_si128(_mm256_castsi256_si128(eights),8):_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q)))));if constexpr(!steady)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(steady||(root_sixteen&&q>=34)){unsigned r=q/2;more=_mm_add_epi32(more,(steady?_mm_cvtsi32_si128(_mm_extract_epi32(sixteen,1)):_mm_cvtsi32_si128(a16*b[r]+b16*a[r])));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if constexpr(steady){x0=_mm256_add_epi32(x0,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[0],_mm256_setr_epi32(0,0,6,0,0,7,0,0)),36));x1=_mm256_add_epi32(x1,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[1],_mm256_setr_epi32(0,0,0,1,0,0,2,0)),73));}else if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,root_ld256(b+q+6)),_mm256_mullo_epi32(vb3,root_ld256(a+q+6)));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h0i),zero,0xDB));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h1i),zero,0xB6));}
root_st256(c+k+16,_mm256_add_epi32(u0,x0));
root_st256(c+k+24,_mm256_add_epi32(u1,x1));
}
{
auto av0=root_ld256(a+k+32),av1=root_ld256(a+k+40);
auto bv0=root_ld256(b+k+32),bv1=root_ld256(b+k+40);
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,root_ld256(b+j2+16)),_mm256_mullo_epi32(vb2,root_ld256(a+j2+16)));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(steady||(root_four)){unsigned w=k/4+8;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(steady||(root_eight)){unsigned q=w/2;__m128i more=(steady?_mm256_extracti128_si256(eights,1):_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q)))));if constexpr(!steady)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(steady||(root_sixteen&&q>=34)){unsigned r=q/2;more=_mm_add_epi32(more,(steady?_mm_cvtsi32_si128(_mm_extract_epi32(sixteen,2)):_mm_cvtsi32_si128(a16*b[r]+b16*a[r])));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if constexpr(steady){x0=_mm256_add_epi32(x0,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[1],_mm256_setr_epi32(0,3,0,0,4,0,0,5)),146));x1=_mm256_add_epi32(x1,_mm256_blend_epi32(zero,_mm256_permutevar8x32_epi32(three[1],_mm256_setr_epi32(0,0,6,0,0,7,0,0)),36));}else if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,root_ld256(b+q+11)),_mm256_mullo_epi32(vb3,root_ld256(a+q+11)));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k0i),zero,0x6D));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k1i),zero,0xDB));}
root_st256(c+k+32,_mm256_add_epi32(u0,x0));
root_st256(c+k+40,_mm256_add_epi32(u1,x1));
}
if(steady||(root_four)){root_j4=k/4+12;root_k4=k+48;}if(steady||(root_eight)){root_j8=k/8+6;root_k8=k+48;}if(steady||(root_sixteen&&k+48>272)){root_j16=k/16+3;root_k16=k+48;}
j3=q+16;k3=k+48;
}
};unit48(std::false_type{},std::min(hi,288u));unit48(std::true_type{},hi);
for(;k<hi;++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
position[1]={k,k};position[2]={j2,k2};if(root_four)position[4]={root_j4,root_k4};if(root_eight)position[8]={root_j8,root_k8};if(root_sixteen)position[16]={root_j16,root_k16};if(root_three)position[3]={j3,k3};
auto family=[&](auto tag,unsigned input) __attribute__((always_inline)){constexpr unsigned fixed=decltype(tag)::value;unsigned f=fixed?fixed:input;
unsigned j=position[f].j,k=position[f].k;
auto scalar=[&](){c[k]+=a[f]*b[j]+b[f]*a[j];for(unsigned d:{2u,3u,4u,6u,12u})if(j%d==0&&j/d>d*f)c[k]+=a[d*f]*b[j/d]+b[d*f]*a[j/d];j++;k+=f;};
auto three=[&](auto layers,unsigned ff,unsigned x) __attribute__((always_inline)){constexpr unsigned depth=decltype(layers)::value;auto parent=_mm256_add_epi32(_mm256_mullo_epi32(_mm256_set1_epi32(a[ff]),root_ld256(b+x)),_mm256_mullo_epi32(_mm256_set1_epi32(b[ff]),root_ld256(a+x)));
if constexpr(depth==0)return parent;else{auto child=_mm_add_epi32(_mm_mullo_epi32(_mm_set1_epi32(a[2*ff]),_mm_loadu_si128((const __m128i*)(b+x/2))),_mm_mullo_epi32(_mm_set1_epi32(b[2*ff]),_mm_loadu_si128((const __m128i*)(a+x/2))));if constexpr(depth==1)return _mm256_add_epi32(parent,_mm256_cvtepu32_epi64(child));else{auto grand=_mm_add_epi32(_mm_mullo_epi32(_mm_set1_epi32(a[4*ff]),_mm_loadl_epi64((const __m128i*)(b+x/4))),_mm_mullo_epi32(_mm_set1_epi32(b[4*ff]),_mm_loadl_epi64((const __m128i*)(a+x/4))));return _mm256_add_epi32(parent,_mm256_cvtepu32_epi64(_mm_add_epi32(child,_mm_unpacklo_epi32(grand,root_zero128))));}}};
auto phase=[&](auto kind,unsigned from,unsigned limit) __attribute__((always_inline)){constexpr unsigned stage=decltype(kind)::value;if(j<from||j>=limit)return;while(k<hi&&j<limit&&j%24)scalar(); for(;k+23*f<hi&&j+23<limit;k+=24*f,j+=24){__m256i donor{};if constexpr(stage>=2)donor=three(std::integral_constant<unsigned,(stage>=5?2:stage>=4?1:0)>{},3*f,j/3);{auto sub=_mm256_permutevar8x32_epi32(donor,_mm256_setr_epi32(0,0,0,1,0,0,2,0));auto total=_mm256_add_epi32(three(std::integral_constant<unsigned,(stage>=3?2:stage>=1?1:0)>{},f,j+0),_mm256_blend_epi32(zero,sub,73));alignas(32) unsigned lanes[8];volatile unsigned*v=lanes;_mm256_store_si256((__m256i*)lanes,total);c[k+0*f]+=v[0];c[k+1*f]+=v[1];c[k+2*f]+=v[2];c[k+3*f]+=v[3];c[k+4*f]+=v[4];c[k+5*f]+=v[5];c[k+6*f]+=v[6];c[k+7*f]+=v[7];}{auto sub=_mm256_permutevar8x32_epi32(donor,_mm256_setr_epi32(0,3,0,0,4,0,0,5));auto total=_mm256_add_epi32(three(std::integral_constant<unsigned,(stage>=3?2:stage>=1?1:0)>{},f,j+8),_mm256_blend_epi32(zero,sub,146));alignas(32) unsigned lanes[8];volatile unsigned*v=lanes;_mm256_store_si256((__m256i*)lanes,total);c[k+8*f]+=v[0];c[k+9*f]+=v[1];c[k+10*f]+=v[2];c[k+11*f]+=v[3];c[k+12*f]+=v[4];c[k+13*f]+=v[5];c[k+14*f]+=v[6];c[k+15*f]+=v[7];}{auto sub=_mm256_permutevar8x32_epi32(donor,_mm256_setr_epi32(0,0,6,0,0,7,0,0));auto total=_mm256_add_epi32(three(std::integral_constant<unsigned,(stage>=3?2:stage>=1?1:0)>{},f,j+16),_mm256_blend_epi32(zero,sub,36));alignas(32) unsigned lanes[8];volatile unsigned*v=lanes;_mm256_store_si256((__m256i*)lanes,total);c[k+16*f]+=v[0];c[k+17*f]+=v[1];c[k+18*f]+=v[2];c[k+19*f]+=v[3];c[k+20*f]+=v[4];c[k+21*f]+=v[5];c[k+22*f]+=v[6];c[k+23*f]+=v[7];}}if(hi==n||j+23>=limit)while(k<hi&&j<limit)scalar();};
phase(std::integral_constant<unsigned,0>{},f+1,4*f+1);phase(std::integral_constant<unsigned,1>{},4*f+1,9*f+1);phase(std::integral_constant<unsigned,2>{},9*f+1,16*f+1);phase(std::integral_constant<unsigned,3>{},16*f+1,36*f+1);phase(std::integral_constant<unsigned,4>{},36*f+1,144*f+1);phase(std::integral_constant<unsigned,5>{},144*f+1,~0u);position[f]={j,k};};if(15<bound)family(std::integral_constant<unsigned,5>{},5);if(21<bound)family(std::integral_constant<unsigned,7>{},7);if(33<bound)family(std::integral_constant<unsigned,11>{},11);if(39<bound)family(std::integral_constant<unsigned,13>{},13);auto runrows=[&](auto kind,unsigned r0,unsigned r1,unsigned w1v) __attribute__((always_inline)) {constexpr unsigned g=decltype(kind)::value;constexpr unsigned stride=(g==0?5:(g==1?8:11));auto &rowsc=coeffgroups[g];unsigned active=activegroups[g];if(r1>active)r1=active;const unsigned wk=(w1v<hi)?w1v:hi;
{u32*record=rowsc.data()+(size_t)r0*stride;for(unsigned row=r0;row<r1;++row,record+=stride){unsigned i=record[0];
unsigned j=record[1],k=record[2];
unsigned kend=(7u*i<wk)?wk-7u*i:0u;
if(k>=kend)continue;
u32 ai=record[3],bi=record[4];
auto va=_mm256_set1_epi32((int)ai),vb=_mm256_set1_epi32((int)bi);
constexpr bool root_pair=(g>=1);
const unsigned root_start=root_pair?record[7]:0;
const __m128i root_av2=_mm_set1_epi32(root_pair?record[5]:0),root_bv2=_mm_set1_epi32(root_pair?record[6]:0);
constexpr bool root_deep=(g>=2);
constexpr bool root_pair4=(g>=2);
const unsigned root_start4=root_pair4?record[10]:0;
const __m128i root_av4=_mm_set1_epi32(root_pair4?record[8]:0),root_bv4=_mm_set1_epi32(root_pair4?record[9]:0);
{if(root_pair){while(j&7){c[k]+=ai*b[j]+bi*a[j];++j;k+=i;}}}
#ifdef ROOT_ROW_FLAGS_CHECK
++root_row_flags_hits;
#endif
if(!root_pair){auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!false)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=k;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}else if(root_pair4){if(j/2>=root_start&&j/4>=root_start4){auto root_double=[&](__m256i value,unsigned jj){unsigned half=jj/2;
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
unsigned h4=jj/4;__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
more=_mm_add_epi32(more,_mm_unpacklo_epi32(m4,root_zero128));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));
return value;};
{unsigned kend32=k;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}else{auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(true){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=k;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}}else{if(j/2>=root_start){auto root_double=[&](__m256i value,unsigned jj){unsigned half=jj/2;
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));
return value;};
{unsigned kend32=k;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}}else{auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=k;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}}}
record[1]=j;record[2]=k;
if(root_pair&&j/2>root_start)record[7]=j/2;if(root_pair4&&j/4>root_start4)record[10]=j/4;
}}
};
for(unsigned w0=lo;w0<hi;w0+=8192u){unsigned w1=w0+8192u;
runrows(std::integral_constant<unsigned,0>{},bands[0][0],bands[0][1],w1);
runrows(std::integral_constant<unsigned,1>{},bands[1][0],bands[1][1],w1);
runrows(std::integral_constant<unsigned,2>{},bands[2][0],bands[2][1],w1);}
runrows(std::integral_constant<unsigned,0>{},0,bands[0][0],hi);
runrows(std::integral_constant<unsigned,0>{},bands[0][1],~0u,hi);
runrows(std::integral_constant<unsigned,1>{},0,bands[1][0],hi);
runrows(std::integral_constant<unsigned,1>{},bands[1][1],~0u,hi);
runrows(std::integral_constant<unsigned,2>{},0,bands[2][0],hi);
runrows(std::integral_constant<unsigned,2>{},bands[2][1],~0u,hi);
}
auto remain=[&](unsigned i,unsigned j,unsigned k,unsigned av,unsigned bv){for(;k<n;++j,k+=i)c[k]+=av*b[j]+bv*a[j];};
auto endgroup=[&](auto tag){constexpr unsigned g=decltype(tag)::value,step=5+3*g;auto &v=coeffgroups[g];for(size_t z=0;z<v.size();z+=step){size_t q=v.size()-step-z;unsigned i=v[q];remain(i,v[q+1],v[q+2],v[q+3],v[q+4]);c[u64(i)*i]+=v[q+3]*v[q+4];
if constexpr(g>=1){remain(2*i,v[q+7],2*i*v[q+7],v[q+5],v[q+6]);c[u64(2*i)*(2*i)]+=v[q+5]*v[q+6];}
if constexpr(g>=2){remain(4*i,v[q+10],4*i*v[q+10],v[q+8],v[q+9]);c[u64(4*i)*(4*i)]+=v[q+8]*v[q+9];}
}};endgroup(std::integral_constant<unsigned,0>{});endgroup(std::integral_constant<unsigned,1>{});endgroup(std::integral_constant<unsigned,2>{});for(unsigned g=0;g<3;g++)for(unsigned i:rowgroups[g]){grouped3[i]=2;if(g>=1)grouped3[i*2]=2;if(g>=2)grouped3[i*4]=2;}for(unsigned i=1;i<bound;++i)if(grouped3[i]!=2)c[u64(i)*i]+=a[i]*b[i];for(unsigned i=3;i<bound;++i)if(!grouped3[i]&&i!=4&&i!=8&&i!=16&&i!=3){auto q=position[i];remain(i,q.j,q.k,a[i],b[i]);}
sa+=reduce(vsa);sb+=reduce(vsb);c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){unsigned long long bd=1;while(bd*bd<n)++bd;if(bd>16)root_fast::multiply_t<true>(n,a,b,c);else root_fast::multiply_t<false>(n,a,b,c);}