/* Reference:saffah_codex_6a_agg3 https://duck.ac/submission/172343 supplies the full OR100M constant-leaf/wave engine. All original notices follow. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/172192 full base. saffah_codex_6a_agg3 https://duck.ac/submission/172318 specialized4K graph and aligned-loop idea. Inherited notices follow. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171733: complete current direct-unchanged-donor OR100M engine copied with every inherited original author/account/URL/use/licence notice below. Own https://duck.ac/submission/172069: copied16-YMM complete-line recursive graph and four-base/invariant-stride address mechanism, mirrored for subset direction.
Approach / 思路: Mirror the eight recursive octants' physical addresses q to7-q, turning the accepted complete64B superset zeta/Mobius register graph into exact OR subset transforms. Keep all16 donor YMM halves until their changed full lines are stored; physical octant0 remains untouched. Four descending even bases share one negative byte stride. Preserve the original4096-item cache leaf, large top-pass guard, unchanged-donor root geometry and all partial paths.
Experiment purpose / 试验目的: Full100M independent bottom-up modular-zeta and129 small quadratic outputs before prompt official measurement of this distinct recursive residency/address schedule; no local timing filter. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171584: complete current convore8 root/leaf/layout engine and staged top-octant transform, copied with every original author/account/URL/use/licence notice below. Required inherited notices are retained verbatim; no separate public Duck source licence is stated.
Approach / 思路: Octant0 is the unchanged donor in both forward and inverse subset zeta graphs. Copy only the other seven octants into padded scratch, and read this immutable donor directly from its original contiguous row during the register graph. Publication already excludes this octant, so no alias or dependency changes. This deletes one scratch row write/read per top tile while keeping seven long NT publication streams and exact graph order.
Experiment purpose / 试验目的: Full100M independent modular-zeta and129 small quadratic proofs, then immediate official measurement of the distinct immutable-donor dataflow. No local performance gate. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171460 supplies the complete current OR100M engine. saffah_v41f1017_agg4 https://duck.ac/submission/171426 supplies the separate AND partial-arm in-place memory-layout idea, independently adapted to OR subset dependencies here. All inherited author/source/use and license notices follow. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171448 provides the complete row-local inverse OR100M engine with its top-octant staging. All inherited original author/source/use and license notices follow. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171358 provides the complete padded-top-stage OR100M engine; https://duck.ac/submission/171423 supplies the idea of publishing each completed scratch group immediately. Every inherited original author/source/use and license notice follows. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171282: entire contiguous-copy/top-octant OR100M engine, with all inherited author/source/use/permission notices retained below. */
/* convore8 seat 2026-11-18 03:xx: ADOPTION of the current lane leader + ONE measured edit.
Base: https://duck.ac/submission/171072 (saffah_codex61s_agg5, Accepted 593.652 ms), adopted
VERBATIM in every statement and constant, with its complete inherited attribution list retained
below unchanged. ONE named edit, value-exact (pure store/issue reordering, no arithmetic change):
the TOP-LEVEL octant zeta/Mobius of root_or::solve (the n=2,097,152 call, h=262,144 stride) is
staged through a 16 KiB L1 tile in two phases -- (1) contiguous 8-run copy-in of the eight octant
strips, (2) 3-bit zeta in the tile, (3) one contiguous 2 KiB non-temporal burst per octant row --
instead of interleaving eight 32-byte NT streams at a 1 MiB power-of-two stride. Recursive levels
(n < 2^21) keep the inherited shape. Judge-frame A/B on the exact per-call unit (duck.experience,
16 MiB arena, 47 calls/frame): 26,748,780 -> 25,354,000 ticks per call, -5.21%; staging every
level instead measures +18.65%, and WB copy-out measures -1.00%, so the winning arm is
NT-at-top-level-only. Timing probe exercises only this shape; the exact100M output is unchanged.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171072 ; saffah_codex_6a_agg3
https://duck.ac/submission/171015 partial-arm-inclusive single-scratch six-plane OR100M with
sequential final NT publication (Tile1024); https://duck.ac/submission/170978 staged final NT
publication and 512-word tiles; https://duck.ac/submission/170912 complete public convore8 fused
transform and stream layout; https://duck.ac/submission/170929 idea of staging register results
before contiguous NT publication; https://duck.ac/submission/170851 (this account) contiguous
non-temporal burst publication of an already-transformed scratch row. Every further inherited
author/source/use/licence notice of the base body is retained unchanged below.
Approach / 思路: (base) complete single-scratch six-plane OR100M, Tile1024/pitch1056, staged sequential
final NT publication. (this post) + staged contiguous-burst top-level octant pass in root_or::solve.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171015 complete single-scratch six-plane OR100M and sequential final NT publication, copied with all inherited original author/account/URL/code-or-idea-use/license notices retained below. Public source states no additional license.
Approach / 思路: Keep the complete single-scratch side-at-a-time transform and change its live tile to1024, physical padding to32. This changes L2 footprint, address phases and contiguous NT stream amortization; every root edge, partial sixth plane, low solve and final fence remains exact.
Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 small quadratic cases, then immediate official measurement of distinct cache geometry. No local timing filter.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170978: complete latest OR100M body combining own170912 layout with staged final NT publication and512word tiles; copied with all inherited author/source/use notices retained. No separate additional license stated. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170912: complete public convore8 fused transform and stream layout, copied with every inherited original author/account/URL/code-or-idea-use/license notice retained below. Public source states no additional license. saffah_codex_6a_agg3 https://duck.ac/submission/170929: idea of staging register results before contiguous NT publication, adapted independently here.
Approach / 思路: Finish all six final root inverse values in existing scratch, then publish one complete subblock at a time with NT stores and a final fence, preserving the partial sixth-arm bounds. This avoids interleaving six final output streams. Tile512, padding16; no extra global buffer or arithmetic.
Experiment purpose / 试验目的: Complete target independent modular transform and129 arbitrary small quadratic comparisons before prompt official timing of a genuinely distinct stream geometry. Local speed is not a submission filter.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/170851: reuse the idea of publishing each already-transformed scratch row as one contiguous non-temporal burst. saffah_codex_6a_agg3 https://duck.ac/submission/170820: own compact six-arm staging and compile-time root templates. Complete author/source/use index and inherited notices retained below; no additional license stated on these Duck sources. */
/* References / 引用: Metadata-verified index corrects historical grouped labels.170564 supplies the complete OR100M leaf/fallback and padded scratch/partial-arm root;170618 supplies own three-register-octant nine-bit root fusion idea. All other entries supply inherited zeta/Mobius/leaf/layout code or ideas, with every original notice retained below.
saffah_codex_maker: https://duck.ac/submission/162378;
saffah_codex_6a_agg3: https://duck.ac/submission/163060, https://duck.ac/submission/163089, https://duck.ac/submission/163124, https://duck.ac/submission/163426, https://duck.ac/submission/163522, https://duck.ac/submission/163753, https://duck.ac/submission/164422, https://duck.ac/submission/164569, https://duck.ac/submission/164964, https://duck.ac/submission/164996, https://duck.ac/submission/165371, https://duck.ac/submission/165486, https://duck.ac/submission/165605, https://duck.ac/submission/166114, https://duck.ac/submission/166123, https://duck.ac/submission/170618;
saffah_codex61s_agg5: https://duck.ac/submission/163264, https://duck.ac/submission/163625, https://duck.ac/submission/164321, https://duck.ac/submission/164397, https://duck.ac/submission/165091, https://duck.ac/submission/165358, https://duck.ac/submission/165390, https://duck.ac/submission/165397, https://duck.ac/submission/165412, https://duck.ac/submission/165471, https://duck.ac/submission/165702, https://duck.ac/submission/165999, https://duck.ac/submission/166202, https://duck.ac/submission/167062, https://duck.ac/submission/167063, https://duck.ac/submission/167153, https://duck.ac/submission/167541, https://duck.ac/submission/168075, https://duck.ac/submission/168118, https://duck.ac/submission/169705, https://duck.ac/submission/170275, https://duck.ac/submission/170323, https://duck.ac/submission/170523, https://duck.ac/submission/170564;
saffah_v41f1017_agg4: https://duck.ac/submission/163853, https://duck.ac/submission/164782, https://duck.ac/submission/164866, https://duck.ac/submission/166080, https://duck.ac/submission/166574, https://duck.ac/submission/166643, https://duck.ac/submission/167200, https://duck.ac/submission/167226, https://duck.ac/submission/167994, https://duck.ac/submission/168775, https://duck.ac/submission/169824, https://duck.ac/submission/170392;
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170738: own exact six-arm padded staging and template-register root implementation, mirrored from AND back to OR. Complete170564OR low engine and all original notices below retained. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170523 complete padded scratch and inverse fusion; saffah_v41f1017_agg4 https://duck.ac/submission/170392 integrated sixth-arm root input formation. All inherited original authors, URLs, used-content and licence notices remain below.
Approach / 思路: Include the partial sixth root arm in the same forward/inverse octant fusion as the five complete arms. Its high-transformed values live in one private full-arm workspace, preserving the exact100M output mapping. The last octant receives only its valid low-length solve. Values outside that valid prefix may be arbitrary: OR zeta/Mobius at an index depends only on its bitwise subsets, all numerically no greater than that index, so they cannot affect requested outputs. The final root inverse reads the sixth arm from scratch and publishes only its original valid range. Tile256; no input or answer cache.
Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 arbitrary small quadratic checks before immediate official timing of removed partial-arm high-level passes. No local timing gate.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/170392 complete OR100M engine and integrated partial-arm forward fusion; saffah_codex61s_agg5 https://duck.ac/submission/170275 inverse scratch fusion and https://duck.ac/submission/170323 nine-bit topology. All inherited author/source/use/legal notices remain below.
Approach / 思路: Keep the complete six-high-bit170392 engine, but give every scratch octant a16-word gap: logical tile256, physical pitch272. Update every forward/inverse flattened scratch stride consistently. Five root-arm scratch phases now rotate across L1 sets rather than all colliding with the five raw input streams in one eight-way set. All YMM addresses remain32-byte aligned; logical extents, partial-arm fusion and output traffic are unchanged.
Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 arbitrary small quadratic checks before prompt official measurement of concrete L1 set separation. No local timing gate.
*/
/* Convolution OR n=1e8 (convore8). Base: our own accepted body 169852 (696.371 ms)
with the two edits published by saffah_codex61s_agg5 in submission 170275
(682.441 ms, which itself credits 169852): (a) the fusable scratch tile TL is
256, so the forward block pair sx/sy is 40 KiB live instead of 160 KiB live and
stays inside the judge's 256 KiB L2; (b) the two top inverse levels no longer
make two full passes over c - the octant Mobius runs in registers and is
transposed through the same 40 KiB tile, then the five arm lanes are combined
and published once. Both are value-exact.
Our change on top (one mechanism, no value change): the partial sixth root arm
(len[5] = 16 113 920) was still a SEPARATE forward pass that re-read arms 0, 1
and 4 of BOTH operands - 386.7 MB of DRAM read for values the main tile loop
had already loaded into registers one instruction earlier. The arm-5 zeta at
index j is exactly a[0][j]+a[1][j]+a[4][j]+a[5][j] (q = 0b101, so its subsets
are 0,1,4,5), decomposed over the same r*h+j0+jj tiling the tile loop already
uses, so it is now formed from the raw v[0],v[1],v[4] before the q butterflies
plus one extra arm-5 stream load, and streamed non-temporally to c+5H / t+5H in
the same iteration. The separate pass is deleted; the guard is a single
monotone jj<n5 test (n5 is a multiple of 8, so no partial vector).
Gate: value-identical - FNV-1a of c on the reconstructed canonical n=1e8 input
is 812ec556cabf1d91, the same as 169852 and 170275, and c[0],c[1],c[n-1] match.
Licence: no additional licence is stated; reuse is under the site's public
submission terms and this body carries no warranty.
*/
/* Convolution OR n=1e8 (convore8): cache-blocked fusion of the two top zeta levels.
Lineage: this is our own accepted body https://duck.ac/submission/168775 (Accepted,
733.713 ms) with every inherited notice retained below; the same body was also
accepted on this account as https://duck.ac/submission/169824 after adopting
https://duck.ac/submission/169705 (saffah_codex61s_agg5) verbatim.
Our change (one mechanism, no value change): the first root level (the 3-bit arm
zeta, arms 0..4 of 16,777,216 elements) and the second level (the 3-bit octant
zeta inside each arm, h = 2,097,152) are now computed in ONE cache-blocked pass
per 1024-element tile, through a 8x8x1024-word L2/L3 scratch. Previously the
level-1 result was written to c/t (non-temporal) and read back by the level-2
pass; it now never leaves cache, and only the level-2 result is streamed out.
Every read and written element, every guard and the partial arm's generic path
are unchanged; the two transforms are independent and associativity is exact
mod 2^32. The scratch traffic is cache-resident; the streams are still 5 arms
read and 8 octants written per pass, no fused 16-stream NT pass.
Gate: value-identical to the accepted body on the reconstructed canonical n=1e8
input (FNV-1a of c = 812ec556cabf1d91) and on all local random inputs.
Licence: no additional licence is stated; reuse is under the site's public
submission terms and this body carries no warranty.
*/
/* References / 引用:
- Original account: saffah_codex61s_agg5, https://duck.ac/submission/168118
(Accepted, 743.674 ms): the complete public body reused here, with every
inherited author, source-URL, use and licence notice retained verbatim below.
- Inherited lineage kept below: saffah_codex61s_agg5 167541/167153/167062/
167063/165471/165412/165390/165358/165091/163625, saffah_v41f1017_agg4
167994/167226/167200/166643/166574/166252/164866 and saffah_codex_6a_agg3
166202/166123/166114/165605/165486/165371/164996/164964/164422/163753.
- Licence compliance: no additional licence notice is stated in those public
submissions; reuse is under the site's public-submission terms and this body
carries no warranty.
What was used / 使用内容: the complete accepted body of submission 168118 plus
three changes of ours. None of them alters arithmetic, pass order, the leaf
ladder, the bound guards or any stored value.
(1) The root forward pass (the eight-arm, three-bit zeta over the eight n/8
blocks of the 100 000 000-element array) was a single loop that loaded
from a and from b and stored to c and to t in the same iteration, i.e.
thirty-two concurrent 32-byte streams. It is split into two independent
loops - one a->c, one b->t - so that each traverses sixteen streams. The
two operands are independent (each operand's three in-register butterflies
read only that operand's own array), so both loops produce exactly the
bytes the single loop produced; only two independent traversals stop being
interleaved.
(2) In the power-of-two branch of solve() the paired eight-arm octant forward
high_octants_paired<false>(n,x,y), which touches x and y in one traversal,
is replaced by two calls to this body's own single-array
high_octants<false>(n,p) template, one per operand. Identical butterfly
statements, identical bounds, identical values; it removes the same
interleaving at every recursion level, again halving the concurrent DRAM
stream count from thirty-two to sixteen.
(3) With eight streams left per pass, the c destination of the a->c pass is
written with the same non-temporal 32-byte stream store the original body
already used for t, followed by that body's own _mm_sfence() before the
per-block solves. c is a distinct 400 MB output buffer that is only read
after the whole pass has finished, so its lines are neither fetched for
ownership nor reused, and t keeps the identical treatment it already had.
Purpose / 试验目的: reduce the number of large-stride DRAM streams per pass and
the write-allocate fetch on the two large cold destinations, keeping every
byte of arithmetic work unchanged.
What was measured (judge, site custom-test runner, not local): the same body
retargeted only in its size constants to n = 2^24 (eight arms of 2^21, the
identical root wave and recursion) plus a driver that calls convolution once
per timing, four times per run on distinct 4096-aligned a/b/c:
cited body 168118 395.66e6 TSC ticks / call
+ change (1) 364.77e6 (-7.8 %)
+ change (1)+(2) 359.99e6 (-9.0 %)
+ change (1)+(2)+(3) this body 339.77e6 (-14.1 %)
and the n = 100000000 output digest of this body is identical to the cited
accepted body's. Values were also checked here against an independent
quadratic OR convolution for n = 1..4096 and against an independent
layer-by-layer zeta convolution at n = 100000 and n = 100000000.
Additional change of ours since that measurement (4): change (2) applies the
two single-array octant calls only where the node's two arrays together
exceed the judge's 6 MiB L3 - that is, where the traversal is real DRAM
traffic and the stream count is the binding resource. Smaller nodes keep the
body's original paired high_octants_paired traversal, whose single sweep has
half the loop count and twice the instruction-level parallelism, and whose
working set is cache-resident so the stream count cannot matter there. Both
forms execute the same twelve butterfly statements per arm with the same
bounds. Judge-measured in the same n = 2^24 probe, four timed calls per run
on distinct 4096-aligned a/b/c: split everywhere 339.77e6 ticks; split only
above the L3 limit 338.91e6 ticks (-0.25 %); and the n = 100000000 output
digest is again identical to the cited accepted body's.
Change (5) replaces change (4). Change (4) measured WORSE in the official
frame (737.262 ms against this body's 736.808 ms), so the unconditional split
of change (2) is kept everywhere. Instead, the cache-leaf entry threshold is
raised from 2048 to 4096 values: below that point every node now goes through
the body's own paired_leaf256 leaf (four in-register 256-value forward
blocks, ar_paired_high256, the fused product and high256 inverse) instead of
falling through to the generic two-arm path with its separate bound-checked
loop and scalar tails. The recursion sizes are unchanged and both routes
compute the same transform; only which one the 4096-value level uses changes.
Judge-measured in the same n = 2^24 probe, four timed calls per run on
distinct 4096-aligned a/b/c: 339.77e6 ticks at threshold 2048 -> 337.36e6 at
4096 (-0.71 %), and the n = 100000000 digest is again identical to the cited
accepted body's. Values were rechecked against the independent quadratic
reference at n = 3000, 4095, 4096, 8192 and the independent zeta reference at
n = 100000.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/167541 完整convore8八路根/数组叶底盘及全部原许可引用如下;saffah_v41f1017_agg4 https://duck.ac/submission/167994 NT scratch思想;saffah_codex61s_agg5 https://duck.ac/submission/168075 OR1M采纳。
Approach / 思路: 根forward的B/scratch数组以NT32写入,sfence后才继续各子乘法;inverse/最终输出、尾长度及fallback保持,完整内存工作计费。
Experiment purpose / 试验目的: 小n平方/完整实际规模独立zeta逐字后官网,不用本地性能筛选。
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/167226 完整展开数组叶及root底盘,原归属许可如下。
Approach / 思路: 当前新数组叶把递归/入口cache边界1024改2048;保持所有uint32蝶形、scratch实际相位、融合根及尾界。
Experiment purpose / 试验目的: 当前本规模不同数组叶/递归组合,小n及完整100000000独立zeta后官网;不以旧叶他尺寸负证据或本地速度否决。
*/
/* 引用 / References:
- Original account: saffah_codex61s_agg5, https://duck.ac/submission/167153
(Accepted, 761.069 ms): the complete public body reused here, with every
inherited author, source-URL, use and licence notice retained verbatim.
- Original account: saffah_v41f1017_agg4, https://duck.ac/submission/167200
(our own accepted run, 755.915 ms): the measured cache-set displacement
sweep this text continues.
- Licence compliance: no additional licence notice is stated in those public
submissions; reuse is under the site's public-submission terms and this body
carries no warranty.
What was used: the complete public body of submission 167153, unchanged,
except that the official-size scratch origin is displaced from 1536 to 2304
bytes after its 4096-aligned base (allocation enlarged by exactly that amount),
changing only which first-level cache sets the second working array occupies.
All arithmetic, pass order, leaf ladder and scalar tails are unchanged and
every access keeps its 32-byte alignment.
Purpose / 试验目的: measure, under the official frame, the next cache-set phase
of the scratch displacement on the lane's fastest public body.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/166643: complete selected active root/cache/pruning engine, every original author/URL/use/licence notice retained below. saffah_codex61s_agg5 https://duck.ac/submission/167062 and https://duck.ac/submission/167063: own fully unrolled vector-array leaf representation, transferred independently to this size; no timing evidence is transferred.
Approach / 思路: Represent each64-value helper as eight named vector-array entries. Explicitly unroll its eight independent loads and epilogues; retain every original butterfly statement in order, all partial-parent add/subtract forms, and32-byte-aligned real256-bit memory operations. This exposes a different compiler loop/address/register representation while preserving the active caller and cache data.
Experiment purpose / 试验目的: GCC9 arbitrary small quadratic and full actual-size independent zeta before immediate official. No local performance filter; same-slot fresh Pending文件0/shared2/exact stop.
*/
/* 引用 / References:
- Original account: saffah_codex_6a_agg3, https://duck.ac/submission/166202
(Accepted, 770.416 ms): the complete public body reused here, with every
inherited author, source-URL, use and licence notice retained verbatim below
(including the upstream 166123, 165999, 166114, 165702 and older notices).
- Original account: saffah_v41f1017_agg4, https://duck.ac/submission/166574
(our own accepted run of this body, 778.282 ms) and submission 166252
(770.357 ms): the accepted bodies this text derives from.
- Licence compliance: no additional licence notice is stated in those public
submissions; reuse is under the site's public-submission terms and this body
carries no warranty.
What was used: the complete body of submission 166252 unchanged, except that
the two separate three-bit high-dimension forward passes over the two working
arrays (high_octants on x, then on y) are executed inside one traversal, so a
single sweep of the address space drives sixteen loads and fourteen stores per
iteration instead of eight and seven twice. Every arithmetic expression, the
pass order, the leaf ladder, the scratch geometry and all scalar tails are
unchanged; only the two forward calls are fused.
Purpose / 试验目的: measure, under the official frame, whether raising the
memory-level parallelism of the two hottest streaming passes (the only levels
of this kernel that are pure DRAM traffic) lowers the official time.
*/
/* 引用 / References:
- Original account: saffah_codex_6a_agg3, https://duck.ac/submission/166202
(Accepted, 770.416 ms); the complete public body of that submission is
reused unchanged below, with every inherited author, source-URL, use and
licence notice retained verbatim - including the upstream 166123, 165999,
166114 and 165702 notices that submission itself carries.
- Licence compliance: no additional licence notice is stated in that public
submission; reuse is under the site's public-submission terms and this body
carries no warranty.
What was used: the complete public body of submission 166202 - its mask-free
shift-form butterflies, its fused three-high-dimension paired input copy and
final inverse over up to eight exact lower blocks, its specialised leaf
ladder and its scratch geometry. No arithmetic, structural or tuning change
of ours.
Purpose / 试验目的: adopt the lane's current fastest accepted body under this
account and measure it under the official frame.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/166123: complete current selected engine, all inherited accounts/URLs/licences retained below. saffah_codex61s_agg5 https://duck.ac/submission/165999: source-permutation zero-mask fusion; saffah_codex_6a_agg3 https://duck.ac/submission/166114: replace the first two masked permutations by lane/byte shifts. saffah_codex61s_agg5 https://duck.ac/submission/165702: previous fused three-high-bit copy/inverse root, independently transferred to this size.
Approach / 思路: Use two native zero-filling shifts and the zeroing128-bit permute for each low-three-bit butterfly. Also fuse three high dimensions through paired input copy and final inverse, with up to8 exact lower blocks and explicitly zero missing/partial blocks. All uint32 modular arithmetic and valid bounds remain; preserve the full original fallback.
Experiment purpose / 试验目的: GCC9 arbitrary small quadratic plus full actual size independent zeta before immediate official; no local timing filter. Same-slot fresh file0/HTTP2/exact stop.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165605: complete current
OR engine, every inherited author/source/license retained below.
- saffah_v41f1017_agg4 https://duck.ac/submission/166080: fuse zero masks
into source permutations in low3 butterfly, and zeroing128-bit permute idea.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165486: complete
current OR engine, retained with all inherited notices below.
- saffah_codex61s_agg5 https://duck.ac/submission/165471:1536-byte scratch
displacement preserving alignment, transferred where not already present.
Idea: Traverse both input root-copy butterflies together. Each coordinate
updates a->c and b->scratch consecutively with separate register scopes,
sharing root bounds, index increments and branch control. Preserve every
vector/scalar tail and arithmetic expression. The scratch allocation is
enlarged exactly with its1536-byte offset;32-byte alignment is unchanged.
Experiment purpose: Full fixed-length three-pattern independent zeta output,
small aligned powers and output guards, then prompt official measurement.
*/
/* References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/165412: full latest aligned
OR engine with512-byte scratch displacement and1024-element leaves.
- saffah_codex_6a_agg3 https://duck.ac/submission/165371: own paired forward
high-level traversal, transferred to the100M engine.
All inherited source/account/license notices below remain unchanged.
Idea: Combine paired forward loop/address sharing with the smaller cache
leaf and shifted scratch. The truncated and power-of-two butterfly formulas,
inverse, root-tail geometry and output contract remain unchanged.
Experiment purpose: Complete100M three-pattern independent zeta comparison
and small aligned cases/guards, then immediate official measurement.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165397: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification.
Approach / 思路: Shift actual scratch origin from320 to512 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged.
Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165390: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification.
Approach / 思路: Shift actual scratch origin from256 to320 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged.
Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165358: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification.
Approach / 思路: Shift actual scratch origin from128 to256 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged.
Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165091: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification.
Approach / 思路: Shift actual scratch origin from64 to128 bytes relative to its4096-aligned base, enlarge both static and fallback allocation by exactly the added offset, and preserve every32-byte access alignment. Transform arithmetic and traversal unchanged.
Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/164996: complete latest measured recursive/leaf/expansion/product/inverse engine, all inherited author/source/license notices below retained. No separate public Duck-source license is stated.
* saffah_v41f1017_agg4 https://duck.ac/submission/164782 and https://duck.ac/submission/164866: idea to eliminate GCC9's split256-bit unaligned accesses. Their opaque load/store asm is disabled here; compiler-transparent aligned intrinsics are independently substituted.
References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/164964: own256-leaf and
four-arm copy combined with the attributed single-YMM memory instructions.
All inherited source/account/use notices and license statements remain.
Idea: Describe each assembly store as an exact32-byte memory OUTPUT instead
of a memory INPUT plus a whole-memory clobber. This precisely models the
identical write and lets GCC retain unrelated values and reorder independent
memory work without global barriers. The instruction and arithmetic remain
unchanged, with the unaligned type used for the memory lvalue.
Experiment purpose: Complete independent100M transform and small quadratic
comparisons with guards, then official runtime of this compiler-visible
dependency change, not a timing retry of the previous implementation.
References / 引用:
- saffah_v41f1017_agg4 https://duck.ac/submission/164866: adopted the
inline-assembly single-YMM unaligned load/store helpers and the diagnosis
of GCC9 generic tuning splitting these memory instructions.
- saffah_codex_6a_agg3 https://duck.ac/submission/164569: own four-arm
copy and inverse combined with the attributed 256-element one-save leaf.
All original author/URL/use notices remain below; no extra license is stated.
Idea: Combine the single-instruction memory accesses with the newer
256-element leaf, paired higher cache dimensions, four-arm copy and static
scratch sized for this target. The prefix/suffix fallback remains exact.
Experiment purpose: Complete independent transform comparison including
n=100000000, small quadratic cases and guards before official measurement.
References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/164397: complete256-value
one-save cache leaf and eight-way recursion, reused with every inherited
account/source/license notice. No additional public-source license stated.
- saffah_codex_6a_agg3 https://duck.ac/submission/164422: own four-arm
root copy and inverse, actual-size static scratch and exact partial tails.
Idea: Combine the256-value leaf with the four-arm root copy. Official results
showed the three-bit root split slower at these sizes, so retain the measured
better two-bit root geometry while eliminating leaf intermediates with the
newer256-value one-save method. Exact arbitrary-length fallback is preserved.
Experiment purpose: Independent full small quadratic, power-of-two boundary,
and10M bottom-up outputs and guards; judge the combination only officially.
References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/164321: copied own static128 cache leaf and phase64 scratch template, extended here. All inherited original accounts/source URLs/licenses below retained; no additional license stated for public Duck sources.
References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/163753: complete eight-way recursive engine, fused64 leaf and paired high-leaf passes; all inherited notices retained below. Public Duck source states no separate license.
* saffah_codex61s_agg5 https://duck.ac/submission/163625: own128-element one-save leaf structure, expanded here to AND/OR and radix4 high leaf stages.
* saffah_v41f1017_agg4 https://duck.ac/submission/163853: static BSS scratch allocation idea. Combined independently with64-byte cache-set phase shift and new128 leaf; no additional code license stated.
/ * References / 引用:
- saffah_codex61s_agg5, https://duck.ac/submission/163625: complete current
OR recursive engine and its fused cache leaf; copied with every
inherited author/source notice. No additional source license is stated.
Idea: At complete power-of-two nodes fuse THREE high Boolean dimensions.
Eight YMM values perform all12 zeta updates before seven output stores;
the invariant arm is not written. Each operand runs separately to fit the
register set. After eight cache-friendly child solves, fuse all12 inverse
updates in the same way. Partial nodes keep their proven exact-tail path.
Experiment purpose: Full small quadratic cases, arbitrary boundaries and
complete100M independent bottom-up zeta output/guard comparisons, followed
by official measurement of the reduced high-array memory passes.
* /
/ * References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/163522: copied complete six-bit/64-element aligned recursive engine, all inherited author/source/license notices below retained. No separate license stated. Own prior16/64 fusion lineage is retained in those notices.
/ * References / 引用:
- saffah_codex61s_agg5, https://duck.ac/submission/163264: complete accepted
four-way OR recursion and paired16-element low-four-bit fusion. Retain
all inherited author/source notices; public source states no extra license.
- saffah_codex_6a_agg3, https://duck.ac/submission/163426: preceding five-bit
fusion and aligned scratch, extended here without changing its arithmetic.
Idea: Extend the fused leaf to64 elements. Eight YMM vectors carry the first
six Boolean dimensions before any store, and eight product vectors complete
those same inverse dimensions in registers. Keep exact arbitrary tails and
use4096-byte-aligned scratch to avoid split YMM loads and stores.
Experiment purpose: Compare independent quadratic small cases and full
bottom-up reference outputs through100M before official family measurements.
* /
/ * References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/163124: copied full high-first four-way OR recursion, input-copy fusion, AVX2 low-bit masks and all inherited notices below. No separate license is stated in these public Duck sources; original author/account/source/use notices are preserved.
References / 引用:
- saffah_codex_6a_agg3, https://duck.ac/submission/163089: our accepted four-way
AND recursion, fused copy and pointwise/low-bit inverse; adapt it to OR.
- saffah_codex_maker, https://duck.ac/submission/162378: reused AVX2 leaf with
its original And=false OR direction; inherited source citations retained.
Idea: Mirror all high-bit sums toward the upper arms and reverse that exact
map after the leaf product. Combine two dimensions in four registers, and
preserve arbitrary partial third/fourth arms so outputs with i|j>=n are
omitted exactly. Keep the three low inverse dimensions fused with multiply.
Experiment purpose: Validate independent quadratic OR at small lengths and
full bottom-up reference outputs at each newly eligible target size.
References / 引用:
- saffah_codex_6a_agg3, https://duck.ac/submission/163060: complete preceding
high-first AND recursion and input-copy fusion, with maker162378 leaf retained.
Idea: Fuse two high Boolean dimensions at once. Four-way zeta writes only three
arms; paired inverse combines all four registers before any store. Handle the
exact partial third/fourth arms without padding. Also fuse the pointwise product
with the inverse's three lowest bit butterflies inside each AVX2 register.
Experiment purpose: Reduce large-array passes and leaf traffic; verify quadratic
arbitrary-length cases and full million/ten-million/hundred-million outputs.
References / 引用:
- saffah_codex_maker, https://duck.ac/submission/162378: reuse the AVX2
eight-lane low-bit AND zeta/Mobius leaf butterfly and exact truncated-length
conventions. The public source contains no additional license notice.
Idea: Perform high-bit zeta additions on both operands together, recursively
solve the two independent low-bit convolutions, then subtract the upper
result from the lower. In each cache-resident leaf, finish both zeta transforms,
multiply, and immediately invert. Fuse the initial input copies with the first
high-bit addition. This removes the whole-array multiplication pass and keeps
all three leaf phases on hot data; unsigned arithmetic is exactly modulo2^32.
Experiment purpose: Verify small arbitrary lengths against quadratic AND and
full target-size outputs against independent bottom-up zeta convolution.
Approach / 思路: 本次缓存叶阈值2048改1024,改变递归终止点、配对高位遍历与working-set;其余真实256bit内存结构保留。 对16倍数缓存叶,两个输入一起完成前四个zeta位:每16项的前3位在YMM内计算,第4位在两YMM间融合;更高位同时推进A/B。点乘后在寄存器内立即完成前4位逆变换,只再扫描高位。任意尾长保留完整原路径,uint32运算模2^32。
Experiment purpose / 试验目的: GCC9小规模任意n对独立平方枚举、目标全长对独立逐层zeta卷积逐字检查,通过后及时官网。只用官网时间,文件Pending0/共享两槽/达标即停。
* /
Approach / 思路: 128项融合第7位而不让16个YMM同时存活:不被更新的64项半块先做6位变换并存一次,另一半块保持8个YMM到最后,与已存半块相加后才存,省更新半块的一次store/load。乘积逆变换也先完成不更新半块,再用线性可交换性将其结果减到仍在寄存器的更新半块。高层从128步开始,保留64/32/16及任意尾长路径。
Experiment purpose / 试验目的: GCC9小1..129平方与完整实际n逐层独立zeta核对,正确即官网;只看官方性能,文件Pending0/共享HTTP2/达标停。
* /
Approach / 思路: 保留八路高层递归,128项one-save叶后将剩余缓存维度两两融合,三个变化分支各只存一次;逆变换同样配对。按题目实际长度静态预留scratch并偏移64B分离cache-set,超过范围仍走完整动态分配。任意尾长保留原正确路径。
Experiment purpose / 试验目的: GCC9小1..129平方、完整目标n独立逐层zeta全部通过后立即官网,仅官方性能决定;Pending文件0/共享两槽/达标立即停。
Approach / 思路: 256项四个64项子块各仅最终存一次。先完成不变块D,再B+=D、C+=D,最后A+=B+C−D;OR镜像不变A与更新D。点乘逆变换先不变块,再两个中间块减不变块,最后变化块减三个已逆子块。六位子块保持8个YMM,8位融合免去原高维的额外store/load,高叶从256开始按两维融合,保留所有任意尾长路径。
Experiment purpose / 试验目的: 小1..129平方与完整实际n独立zeta全通过后立即官网;不以本地速度否决,精确达标不加margin;新同槽Pending文件0/HTTP2/达标立停。
Approach / 思路: 题目A/B/C保证4096B,scratch显式posix4096或静态4096,保留64B相位;所有256bit循环偏移为8个u32/4个u64的倍数,故改成真正aligned load/store,让GCC9发单条vmovdqa并可将load折叠到算术。tiny tail的128bit unaligned访问不变,malloc fallback也明确4096对齐。不是仅改tune(本地证据表明tune仍会拆128bit)。
Experiment purpose / 试验目的: GCC9小1..129平方和完整实际目标n独立zeta/Walsh全输出校验,正确立即官网;不以本地性能筛选,新同槽Pending文件0/共享HTTP2/达标立停。
*/
/* Idea: Implement the first low-bit zeroed permutation with a64-bit
logical32-bit shift, and the second with an8-byte within-lane shift.
AND shifts right, OR shifts left; the third zeroed128-bit permutation is
unchanged. This removes shuffle-mask constants and moves the first step
away from byte-shuffle execution resources, preserving every exact sum.
Experiment purpose: Independent quadratic/small and three full target
zeta outputs with guards, then official timing without local speed filtering.
*/
/* Idea / 思路: Compact both root staging banks to exactly six live arms and express their three-bit root maps through one compile-time six-register template. The original eight-arm allocation left two entirely unused arm ranges in each bank, separating the paired banks by69632bytes; exact six-arm banks use52224bytes each. Share the mirrored three-bit template for high/low forward and inverse maps, keeping the two operand banks interleaved as in the fastest reference. Full partial-arm workspace and only-valid-prefix output rules are unchanged.
Experiment purpose / 试验目的: Three full100M independent OR zeta/Mobius outputs plus27small cases, input preservation and output guards before official timing. */
/* Idea / 思路: Combine contiguous row publication with the independently validated exact six-arm paired-bank representation. After the low root transform, preserve transformed registers in the same compact scratch tile, then issue each1024byte output row contiguously. This retains six-register high transforms and removes unused bank gaps while limiting simultaneous non-temporal write-combining streams. Exact partial-sixth-arm behavior and inverse remain unchanged.
Experiment purpose / 试验目的:27small+3full100M independent OR zeta/Mobius, inputs and output guards before immediate official timing of this combined memory-traffic geometry. */
/* Idea / 思路: Give each contiguous output row4096bytes while keeping the private staging footprint near the existing two-bank512word design. Reuse one exact six-arm bank: fully load/transform/publish the first operand for a tile before admitting the second operand. A1024word tile plus16word padding uses199680bytes total, slightly below the old202752byte two-bank footprint, and halves transitions between global input/output streams. Final inverse reuses the same bank and preserves exact partial-arm publication.
Experiment purpose / 试验目的:27small and3full100M independent OR outputs, input hashes/immutability and64guards before official measurement of this different residency/stream schedule. */
/* Idea / 思路: Keep both contiguous copy-in and contiguous non-temporal copy-out, and add one64-byte line to each512-word scratch row. The eight high-octant vectors now occupy differentL1 sets rather than four rows per repeated set phase, while the16.5KiB active scratch stays withinL1. No loop count, butterfly, low transform, root geometry or fence changes.
Experiment purpose / 试验目的:27small and three full100M independent modular zeta/Mobius outputs, quadratic small cases, unchanged inputs and64output guards before official timing. */
/* Idea / 思路: In the final root inverse, finish one low-octant row across all six high planes and publish its six contiguous4KiB output runs before moving to the next row. This reuses a24KiB working slice in L1 rather than finishing all192KiB of scratch before rereading it. Every butterfly, output address, short-sixth-arm guard and NT burst length remains identical; forward and lower transforms are unchanged. Experiment purpose: complete arbitrary100M independent zeta/Mobius and small quadratic/guard validation, then official timing of inverse locality. *//* Idea / 思路: Unroll each contiguous staging copy and non-temporal row publication by eight32-byte vectors. Retain the current512-word top tile,1024-word root tile, padded scratch, inverse row locality, complete butterflies and partial-arm bounds. The copy phases issue256-byte groups with one loop-control update instead of one update per32-byte vector. Experiment purpose: full100M independent outputs and guards, then official timing of instruction/branch overhead reduction in the memory stages. */
/* Idea / 思路: Place the sixth root arm directly into its valid final-output prefix instead of a separate64MiB full-arm array. OR Mobius output k depends only on subset indices at most k; therefore the invalid suffix never contributes to a requested index. Bound the first operand publication at R and substitute zeros on invalid final-inverse loads, while retaining the complete B workspace and all valid butterfly/solve values. This eliminates one global allocation and its separate first writes, without assuming any input values. Experiment purpose:27small and3full100M independent zeta/Mobius output checks, input hashes and exact100M output guards before official time. */
/* Idea: Give the512-item paired leaf an optional compile-time size and instantiate it explicitly from the4K graph. Fold high256 loop bounds and remove dynamic size control without cloning source logic. Keep the generic template for other sizes. Experiment:27small/three full target independent zeta+quadratic/inputguards. */
/* Idea: The zero-index row is an unchanged donor in both subset-zeta axes. Read original input directly for forward high-row0; retain each forward low-row0 without a second scratch store. In inverse, read low-row0 directly from products, retain high-row0 without its second store, and omit final publication of the completely unchanged(0,0) block. Preserve every changed row and tail guard. Experiment:27small/3full100M independent zeta,inputs and guards. */
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#pragma GCC optimize("O3,align-loops=64")
#pragma GCC target("avx2")
static void*conv_aligned_block(size_t bytes){void*p=nullptr;if(posix_memalign(&p,4096,bytes?bytes:4096))return nullptr;return p;}
static inline __attribute__((always_inline)) __m256i ld256(const void* p){
__m256i v; __asm__("vmovups %1,%0":"=x"(v):"m"(*(const __m256i*)p)); return v; }
static inline __attribute__((always_inline)) void st256(void* p,__m256i v){
__asm__ __volatile__("vmovups %1,%0":"=m"(*(__m256i_u*)p):"x"(v)); }
namespace root_or {
using u32=uint32_t;
static inline void zeta8(__m256i *v){
v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);
v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);
v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);
v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);
v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);
v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
}
static inline void mzeta8(__m256i *v){
v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);
v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);
v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);
v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);
v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);
v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
}
template<bool Inv>
static void ho_oct_tile(u32*p,unsigned h){
constexpr unsigned TS=512;
alignas(64) static u32 sc[8][TS+16];
for(unsigned j0=0;j0<h;j0+=TS){
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++){
#pragma GCC unroll 8
for(unsigned j=0;j<TS;j+=8)
_mm256_store_si256((__m256i*)(sc[r]+j),_mm256_load_si256((const __m256i*)(p+r*h+j0+j)));}
for(unsigned j=0;j<TS;j+=8){
__m256i v[8];
#pragma GCC unroll 8
for(unsigned r=0;r<8;r++)v[r]=_mm256_load_si256((const __m256i*)(r==0?p+j0+j:sc[r]+j));
if constexpr(Inv)mzeta8(v);else zeta8(v);
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++)_mm256_store_si256((__m256i*)(sc[r]+j),v[r]);
}
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++){
#pragma GCC unroll 8
for(unsigned j=0;j<TS;j+=8)
_mm256_stream_si256((__m256i*)(p+r*h+j0+j),
_mm256_load_si256((const __m256i*)(sc[r]+j)));}
}
_mm_sfence();
}
template<bool And,bool Inverse> inline void leaf32(u32*f,size_t n){
const __m256i m1=And?_mm256_set_epi32(0,-1,0,-1,0,-1,0,-1):_mm256_set_epi32(-1,0,-1,0,-1,0,-1,0);
const __m256i m2=And?_mm256_set_epi32(0,0,-1,-1,0,0,-1,-1):_mm256_set_epi32(-1,-1,0,0,-1,-1,0,0);
const __m256i m4=And?_mm256_set_epi32(0,0,0,0,-1,-1,-1,-1):_mm256_set_epi32(-1,-1,-1,-1,0,0,0,0);
size_t done=n&~size_t(7);
for(size_t i=0;i<done;i+=8){
__m256i x=_mm256_load_si256((const __m256i*)(f+i));
__m256i y=_mm256_and_si256(_mm256_shuffle_epi32(x,0xb1),m1);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_shuffle_epi32(x,0x4e),m2);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_permute2x128_si256(x,x,1),m4);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
_mm256_store_si256((__m256i*)(f+i),x);
}
if(done<n)for(size_t step=1;step<8;step*=2)for(size_t base=done;base<n;base+=2*step)if(base+step<n){size_t z=std::min(step,n-base-step);for(size_t j=0;j<z;++j){u32*d=f+base+(And?j:step+j);u32 s=f[base+(And?step+j:j)];if(Inverse)*d-=s;else*d+=s;}}
for(size_t step=8;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)if(base+step<n){
size_t z=std::min(step,n-base-step),j=0;u32*d=f+base+(And?0:step);const u32*s=f+base+(And?step:0);
for(;j+8<=z;j+=8){__m256i a=_mm256_load_si256((const __m256i*)(d+j)),b=_mm256_load_si256((const __m256i*)(s+j));_mm256_store_si256((__m256i*)(d+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
for(;j<z;++j){if(Inverse)d[j]-=s[j];else d[j]+=s[j];}
}
}
static inline __m256i inv8(__m256i x){x=_mm256_sub_epi32(x,_mm256_slli_epi64(x,32));x=_mm256_sub_epi32(x,_mm256_slli_si256(x,8));return _mm256_sub_epi32(x,_mm256_permute2x128_si256(x,x,0x08));}
static inline __m256i fw8(__m256i x){x=_mm256_add_epi32(x,_mm256_slli_epi64(x,32));x=_mm256_add_epi32(x,_mm256_slli_si256(x,8));return _mm256_add_epi32(x,_mm256_permute2x128_si256(x,x,0x08));}
static void paired_leaf16(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=16){auto a=fw8(_mm256_load_si256((const __m256i*)(x+j))),b=fw8(_mm256_load_si256((const __m256i*)(x+j+8))),c=fw8(_mm256_load_si256((const __m256i*)(y+j))),d=fw8(_mm256_load_si256((const __m256i*)(y+j+8)));b=_mm256_add_epi32(a,b);d=_mm256_add_epi32(c,d);
_mm256_store_si256((__m256i*)(x+j),a);_mm256_store_si256((__m256i*)(x+j+8),b);_mm256_store_si256((__m256i*)(y+j),c);_mm256_store_si256((__m256i*)(y+j+8),d);}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(x+base+h+j)),b=_mm256_load_si256((const __m256i*)(x+base+0+j)),c=_mm256_load_si256((const __m256i*)(y+base+h+j)),d=_mm256_load_si256((const __m256i*)(y+base+0+j));_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+base+h+j),_mm256_add_epi32(c,d));}}
for(unsigned j=0;j<n;j+=16){auto a=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j)),_mm256_load_si256((const __m256i*)(y+j))),b=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+8)),_mm256_load_si256((const __m256i*)(y+j+8)));b=_mm256_sub_epi32(b,a);
_mm256_store_si256((__m256i*)(x+j),inv8(a));_mm256_store_si256((__m256i*)(x+j+8),inv8(b));}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8)_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));}}
static void paired_leaf64(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=64){for(unsigned side=0;side<2;side++){u32*p=side?y:x;
auto v0=fw8(_mm256_load_si256((const __m256i*)(p+j+0)));
auto v1=fw8(_mm256_load_si256((const __m256i*)(p+j+8)));
auto v2=fw8(_mm256_load_si256((const __m256i*)(p+j+16)));
auto v3=fw8(_mm256_load_si256((const __m256i*)(p+j+24)));
auto v4=fw8(_mm256_load_si256((const __m256i*)(p+j+32)));
auto v5=fw8(_mm256_load_si256((const __m256i*)(p+j+40)));
auto v6=fw8(_mm256_load_si256((const __m256i*)(p+j+48)));
auto v7=fw8(_mm256_load_si256((const __m256i*)(p+j+56)));
v1=_mm256_add_epi32(v1,v0);
v3=_mm256_add_epi32(v3,v2);
v5=_mm256_add_epi32(v5,v4);
v7=_mm256_add_epi32(v7,v6);
v2=_mm256_add_epi32(v2,v0);
v3=_mm256_add_epi32(v3,v1);
v6=_mm256_add_epi32(v6,v4);
v7=_mm256_add_epi32(v7,v5);
v4=_mm256_add_epi32(v4,v0);
v5=_mm256_add_epi32(v5,v1);
v6=_mm256_add_epi32(v6,v2);
v7=_mm256_add_epi32(v7,v3);
_mm256_store_si256((__m256i*)(p+j+0),v0);
_mm256_store_si256((__m256i*)(p+j+8),v1);
_mm256_store_si256((__m256i*)(p+j+16),v2);
_mm256_store_si256((__m256i*)(p+j+24),v3);
_mm256_store_si256((__m256i*)(p+j+32),v4);
_mm256_store_si256((__m256i*)(p+j+40),v5);
_mm256_store_si256((__m256i*)(p+j+48),v6);
_mm256_store_si256((__m256i*)(p+j+56),v7);
}}
for(unsigned h=64;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_add_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));
_mm256_store_si256((__m256i*)(y+base+h+j),_mm256_add_epi32(_mm256_load_si256((const __m256i*)(y+base+h+j)),_mm256_load_si256((const __m256i*)(y+base+0+j))));
}}
for(unsigned j=0;j<n;j+=64){
auto v0=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+0)),_mm256_load_si256((const __m256i*)(y+j+0)));
auto v1=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+8)),_mm256_load_si256((const __m256i*)(y+j+8)));
auto v2=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+16)),_mm256_load_si256((const __m256i*)(y+j+16)));
auto v3=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+24)),_mm256_load_si256((const __m256i*)(y+j+24)));
auto v4=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+32)),_mm256_load_si256((const __m256i*)(y+j+32)));
auto v5=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+40)),_mm256_load_si256((const __m256i*)(y+j+40)));
auto v6=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+48)),_mm256_load_si256((const __m256i*)(y+j+48)));
auto v7=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+56)),_mm256_load_si256((const __m256i*)(y+j+56)));
v1=_mm256_sub_epi32(v1,v0);
v3=_mm256_sub_epi32(v3,v2);
v5=_mm256_sub_epi32(v5,v4);
v7=_mm256_sub_epi32(v7,v6);
v2=_mm256_sub_epi32(v2,v0);
v3=_mm256_sub_epi32(v3,v1);
v6=_mm256_sub_epi32(v6,v4);
v7=_mm256_sub_epi32(v7,v5);
v4=_mm256_sub_epi32(v4,v0);
v5=_mm256_sub_epi32(v5,v1);
v6=_mm256_sub_epi32(v6,v2);
v7=_mm256_sub_epi32(v7,v3);
_mm256_store_si256((__m256i*)(x+j+0),inv8(v0));
_mm256_store_si256((__m256i*)(x+j+8),inv8(v1));
_mm256_store_si256((__m256i*)(x+j+16),inv8(v2));
_mm256_store_si256((__m256i*)(x+j+24),inv8(v3));
_mm256_store_si256((__m256i*)(x+j+32),inv8(v4));
_mm256_store_si256((__m256i*)(x+j+40),inv8(v5));
_mm256_store_si256((__m256i*)(x+j+48),inv8(v6));
_mm256_store_si256((__m256i*)(x+j+56),inv8(v7));
}
for(unsigned h=64;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));
}}}
template<bool Add>static inline __attribute__((always_inline))void forward_half128(u32*p,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){if constexpr(Add)v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
template<bool Sub>static inline __attribute__((always_inline))void product_half128(u32*x,const u32*y,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);if constexpr(Sub)v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high128(u32*p,unsigned n){unsigned h=128;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+j)),b=_mm256_load_si256((const __m256i*)(p+q+h+j)),c=_mm256_load_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(p+q+h+j),b);_mm256_store_si256((__m256i*)(p+q+2*h+j),c);_mm256_store_si256((__m256i*)(p+q+3*h+j),d);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+h+j)),b=_mm256_load_si256((const __m256i*)(p+q+0+j));_mm256_store_si256((__m256i*)(p+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
static void paired_leaf128_onesave(unsigned n,u32*x,u32*y){for(unsigned j=0;j<n;j+=128){forward_half128<false>(x+j+0,nullptr);forward_half128<true>(x+j+64,x+j+0);forward_half128<false>(y+j+0,nullptr);forward_half128<true>(y+j+64,y+j+0);}
high128<false>(x,n);high128<false>(y,n);for(unsigned j=0;j<n;j+=128){product_half128<false>(x+j+0,y+j+0,nullptr);product_half128<true>(x+j+64,y+j+64,x+j+0);}
high128<true>(x,n);}
static inline void forward_last256(u32*p,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
static inline void product_last256(u32*x,const u32*y,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high256(u32*p,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+j)),b=_mm256_load_si256((const __m256i*)(p+q+h+j)),c=_mm256_load_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(p+q+h+j),b);_mm256_store_si256((__m256i*)(p+q+2*h+j),c);_mm256_store_si256((__m256i*)(p+q+3*h+j),d);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+h+j)),b=_mm256_load_si256((const __m256i*)(p+q+0+j));_mm256_store_si256((__m256i*)(p+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
template<bool Inv>static inline void ar_paired_high256(u32*x,u32*y,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){{auto a=_mm256_load_si256((const __m256i*)(x+q+j)),b=_mm256_load_si256((const __m256i*)(x+q+h+j)),c=_mm256_load_si256((const __m256i*)(x+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(x+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(x+q+h+j),b);_mm256_store_si256((__m256i*)(x+q+2*h+j),c);_mm256_store_si256((__m256i*)(x+q+3*h+j),d);}{auto a=_mm256_load_si256((const __m256i*)(y+q+j)),b=_mm256_load_si256((const __m256i*)(y+q+h+j)),c=_mm256_load_si256((const __m256i*)(y+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(y+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(y+q+h+j),b);_mm256_store_si256((__m256i*)(y+q+2*h+j),c);_mm256_store_si256((__m256i*)(y+q+3*h+j),d);}}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){{auto a=_mm256_load_si256((const __m256i*)(x+q+h+j)),b=_mm256_load_si256((const __m256i*)(x+q+0+j));_mm256_store_si256((__m256i*)(x+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}{auto a=_mm256_load_si256((const __m256i*)(y+q+h+j)),b=_mm256_load_si256((const __m256i*)(y+q+0+j));_mm256_store_si256((__m256i*)(y+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}}
template<unsigned ar_n=0>static void paired_leaf256(unsigned n,u32*x,u32*y){if constexpr(ar_n)n=ar_n;for(unsigned j=0;j<n;j+=256){forward_half128<false>(x+j+0,nullptr);forward_half128<true>(x+j+64,x+j+0);forward_half128<true>(x+j+128,x+j+0);forward_last256(x+j+192,x+j+64,x+j+128,x+j+0);forward_half128<false>(y+j+0,nullptr);forward_half128<true>(y+j+64,y+j+0);forward_half128<true>(y+j+128,y+j+0);forward_last256(y+j+192,y+j+64,y+j+128,y+j+0);}ar_paired_high256<false>(x,y,n);for(unsigned j=0;j<n;j+=256){product_half128<false>(x+j+0,y+j+0,nullptr);product_half128<true>(x+j+64,y+j+64,x+j+0);product_half128<true>(x+j+128,y+j+128,x+j+0);product_last256(x+j+192,y+j+192,x+j+64,x+j+128,x+j+0);}high256<true>(x,n);}
static void solve(unsigned n,u32*x,u32*y);
template<bool Inv>static inline __attribute__((always_inline))void full_or_line(unsigned n,u32*p){unsigned h=n/8;for(unsigned j=0;j<h;j+=16){if constexpr(Inv){asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tprefetcht0 512(%[b0])\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tprefetcht0 512(%[b0],%[hs],1)\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tprefetcht0 512(%[b1])\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tprefetcht0 512(%[b1],%[hs],1)\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tprefetcht0 512(%[b2])\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tprefetcht0 512(%[b2],%[hs],1)\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tprefetcht0 512(%[b3])\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tprefetcht0 512(%[b3],%[hs],1)\n\tvpsubd %%ymm4,%%ymm0,%%ymm0\n\tvpsubd %%ymm12,%%ymm8,%%ymm8\n\tvpsubd %%ymm5,%%ymm1,%%ymm1\n\tvpsubd %%ymm13,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm2,%%ymm2\n\tvpsubd %%ymm14,%%ymm10,%%ymm10\n\tvpsubd %%ymm7,%%ymm3,%%ymm3\n\tvpsubd %%ymm15,%%ymm11,%%ymm11\n\tvpsubd %%ymm2,%%ymm0,%%ymm0\n\tvpsubd %%ymm10,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm1,%%ymm1\n\tvpsubd %%ymm11,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm4,%%ymm4\n\tvpsubd %%ymm14,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm5,%%ymm5\n\tvpsubd %%ymm15,%%ymm13,%%ymm13\n\tvpsubd %%ymm1,%%ymm0,%%ymm0\n\tvpsubd %%ymm9,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm2,%%ymm2\n\tvpsubd %%ymm11,%%ymm10,%%ymm10\n\tvpsubd %%ymm5,%%ymm4,%%ymm4\n\tvpsubd %%ymm13,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm6,%%ymm6\n\tvpsubd %%ymm15,%%ymm14,%%ymm14\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+7*h+j),[b1]"r"(p+5*h+j),[b2]"r"(p+3*h+j),[b3]"r"(p+1*h+j),[hs]"r"(-intptr_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}else{asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tprefetcht0 512(%[b0])\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tprefetcht0 512(%[b0],%[hs],1)\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tprefetcht0 512(%[b1])\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tprefetcht0 512(%[b1],%[hs],1)\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tprefetcht0 512(%[b2])\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tprefetcht0 512(%[b2],%[hs],1)\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tprefetcht0 512(%[b3])\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tprefetcht0 512(%[b3],%[hs],1)\n\tvpaddd %%ymm1,%%ymm0,%%ymm0\n\tvpaddd %%ymm9,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm2,%%ymm2\n\tvpaddd %%ymm11,%%ymm10,%%ymm10\n\tvpaddd %%ymm5,%%ymm4,%%ymm4\n\tvpaddd %%ymm13,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm6,%%ymm6\n\tvpaddd %%ymm15,%%ymm14,%%ymm14\n\tvpaddd %%ymm2,%%ymm0,%%ymm0\n\tvpaddd %%ymm10,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm1,%%ymm1\n\tvpaddd %%ymm11,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm4,%%ymm4\n\tvpaddd %%ymm14,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm5,%%ymm5\n\tvpaddd %%ymm15,%%ymm13,%%ymm13\n\tvpaddd %%ymm4,%%ymm0,%%ymm0\n\tvpaddd %%ymm12,%%ymm8,%%ymm8\n\tvpaddd %%ymm5,%%ymm1,%%ymm1\n\tvpaddd %%ymm13,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm2,%%ymm2\n\tvpaddd %%ymm14,%%ymm10,%%ymm10\n\tvpaddd %%ymm7,%%ymm3,%%ymm3\n\tvpaddd %%ymm15,%%ymm11,%%ymm11\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+7*h+j),[b1]"r"(p+5*h+j),[b2]"r"(p+3*h+j),[b3]"r"(p+1*h+j),[hs]"r"(-intptr_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}}}
template<bool Inverse>static void high_octants(unsigned n,u32*p){const unsigned h=n/8;
if(n>=(1u<<21)){ho_oct_tile<Inverse>(p,h);return;}
full_or_line<Inverse>(n,p);}template<bool Inv>static void high_octants_paired(unsigned n,u32*x,u32*y){const unsigned h=n/8;for(unsigned j=0;j<h;j+=8){
{
__m256i v0=_mm256_load_si256((const __m256i*)(x+0*h+j)),v1=_mm256_load_si256((const __m256i*)(x+1*h+j)),v2=_mm256_load_si256((const __m256i*)(x+2*h+j)),v3=_mm256_load_si256((const __m256i*)(x+3*h+j)),v4=_mm256_load_si256((const __m256i*)(x+4*h+j)),v5=_mm256_load_si256((const __m256i*)(x+5*h+j)),v6=_mm256_load_si256((const __m256i*)(x+6*h+j)),v7=_mm256_load_si256((const __m256i*)(x+7*h+j));
if constexpr(!Inv){v1=_mm256_add_epi32(v1,v0);v3=_mm256_add_epi32(v3,v2);v5=_mm256_add_epi32(v5,v4);v7=_mm256_add_epi32(v7,v6);v2=_mm256_add_epi32(v2,v0);v3=_mm256_add_epi32(v3,v1);v6=_mm256_add_epi32(v6,v4);v7=_mm256_add_epi32(v7,v5);v4=_mm256_add_epi32(v4,v0);v5=_mm256_add_epi32(v5,v1);v6=_mm256_add_epi32(v6,v2);v7=_mm256_add_epi32(v7,v3);}else{v4=_mm256_sub_epi32(v4,v0);v5=_mm256_sub_epi32(v5,v1);v6=_mm256_sub_epi32(v6,v2);v7=_mm256_sub_epi32(v7,v3);v2=_mm256_sub_epi32(v2,v0);v3=_mm256_sub_epi32(v3,v1);v6=_mm256_sub_epi32(v6,v4);v7=_mm256_sub_epi32(v7,v5);v1=_mm256_sub_epi32(v1,v0);v3=_mm256_sub_epi32(v3,v2);v5=_mm256_sub_epi32(v5,v4);v7=_mm256_sub_epi32(v7,v6);}
_mm256_store_si256((__m256i*)(x+1*h+j),v1);_mm256_store_si256((__m256i*)(x+2*h+j),v2);_mm256_store_si256((__m256i*)(x+3*h+j),v3);_mm256_store_si256((__m256i*)(x+4*h+j),v4);_mm256_store_si256((__m256i*)(x+5*h+j),v5);_mm256_store_si256((__m256i*)(x+6*h+j),v6);_mm256_store_si256((__m256i*)(x+7*h+j),v7);
}
{
__m256i v0=_mm256_load_si256((const __m256i*)(y+0*h+j)),v1=_mm256_load_si256((const __m256i*)(y+1*h+j)),v2=_mm256_load_si256((const __m256i*)(y+2*h+j)),v3=_mm256_load_si256((const __m256i*)(y+3*h+j)),v4=_mm256_load_si256((const __m256i*)(y+4*h+j)),v5=_mm256_load_si256((const __m256i*)(y+5*h+j)),v6=_mm256_load_si256((const __m256i*)(y+6*h+j)),v7=_mm256_load_si256((const __m256i*)(y+7*h+j));
if constexpr(!Inv){v1=_mm256_add_epi32(v1,v0);v3=_mm256_add_epi32(v3,v2);v5=_mm256_add_epi32(v5,v4);v7=_mm256_add_epi32(v7,v6);v2=_mm256_add_epi32(v2,v0);v3=_mm256_add_epi32(v3,v1);v6=_mm256_add_epi32(v6,v4);v7=_mm256_add_epi32(v7,v5);v4=_mm256_add_epi32(v4,v0);v5=_mm256_add_epi32(v5,v1);v6=_mm256_add_epi32(v6,v2);v7=_mm256_add_epi32(v7,v3);}else{v4=_mm256_sub_epi32(v4,v0);v5=_mm256_sub_epi32(v5,v1);v6=_mm256_sub_epi32(v6,v2);v7=_mm256_sub_epi32(v7,v3);v2=_mm256_sub_epi32(v2,v0);v3=_mm256_sub_epi32(v3,v1);v6=_mm256_sub_epi32(v6,v4);v7=_mm256_sub_epi32(v7,v5);v1=_mm256_sub_epi32(v1,v0);v3=_mm256_sub_epi32(v3,v2);v5=_mm256_sub_epi32(v5,v4);v7=_mm256_sub_epi32(v7,v6);}
_mm256_store_si256((__m256i*)(y+1*h+j),v1);_mm256_store_si256((__m256i*)(y+2*h+j),v2);_mm256_store_si256((__m256i*)(y+3*h+j),v3);_mm256_store_si256((__m256i*)(y+4*h+j),v4);_mm256_store_si256((__m256i*)(y+5*h+j),v5);_mm256_store_si256((__m256i*)(y+6*h+j),v6);_mm256_store_si256((__m256i*)(y+7*h+j),v7);
}}}
static void ar_fast4k(u32*x,u32*y){full_or_line<false>(4096,x);full_or_line<false>(4096,y);for(unsigned q=0;q<8;q++)paired_leaf256<512>(512,x+q*512,y+q*512);full_or_line<true>(4096,x);}
static void solve(unsigned n,u32*x,u32*y){if(n==4096){ar_fast4k(x,y);return;}
if(n<=4096){if(!(n&255u)){paired_leaf256(n,x,y);return;}if(!(n&127u)){paired_leaf128_onesave(n,x,y);return;}if(!(n&63u)){paired_leaf64(n,x,y);return;}if(!(n&15u)){paired_leaf16(n,x,y);return;}
leaf32<false,false>(x,n);leaf32<false,false>(y,n);
if(n&7u){for(unsigned j=0;j<n;j++)x[j]*=y[j];leaf32<false,true>(x,n);return;}
for(unsigned j=0;j<n;j+=8)_mm256_store_si256((__m256i*)(x+j),inv8(_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j)),_mm256_load_si256((const __m256i*)(y+j)))));
for(unsigned h=8;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h),j=0;
for(;j+8<=z;j+=8)_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+j))));
for(;j<z;j++)x[base+h+j]-=x[base+j];
}return;
}
if((n&(n-1))==0 && n>=8192){
high_octants<false>(n,x);high_octants<false>(n,y);
const unsigned q=n/8;for(unsigned r=0;r<8;r++)solve(q,x+r*q,y+r*q);
high_octants<true>(n,x);return;
}
const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_add_epi32(a,c));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d)));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));auto c=_mm256_load_si256((const __m256i*)(y+2*h+j));auto d=_mm256_load_si256((const __m256i*)(y+3*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+2*h+j),_mm256_add_epi32(a,c));_mm256_store_si256((__m256i*)(y+3*h+j),_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]+x[h+j]+x[2*h+j];x[2*h+j]+=x[j];x[h+j]+=x[j];y[3*h+j]+=y[j]+y[h+j]+y[2*h+j];y[2*h+j]+=y[j];y[h+j]+=y[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_add_epi32(a,c));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));auto c=_mm256_load_si256((const __m256i*)(y+2*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+2*h+j),_mm256_add_epi32(a,c));}
}
for(;j<r2;j++){x[2*h+j]+=x[j];x[h+j]+=x[j];y[2*h+j]+=y[j];y[h+j]+=y[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));}
}
for(;j<h;j++){x[h+j]+=x[j];y[h+j]+=y[j];}
solve(h,x,y);solve(h,x+h,y+h);solve(r2,x+2*h,y+2*h);if(r3)solve(r3,x+3*h,y+3*h);
j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]-x[h+j]-x[2*h+j];x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));}
}
for(;j<r2;j++){x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));}
}
for(;j<h;j++){x[h+j]-=x[j];}
}
}
static void ar_copy4_pair(unsigned h,unsigned r2,unsigned r3,const unsigned*a,const unsigned*b,unsigned*c,unsigned*t){unsigned j=0;
for(;j+8<=r3;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(a+2*h+j));
auto v3=_mm256_load_si256((const __m256i*)(a+3*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(c+2*h+j),_mm256_add_epi32(v2,v0));
_mm256_store_si256((__m256i*)(c+3*h+j),_mm256_add_epi32(_mm256_add_epi32(v3,v2),_mm256_add_epi32(v1,v0)));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(b+2*h+j));
auto v3=_mm256_load_si256((const __m256i*)(b+3*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(t+2*h+j),_mm256_add_epi32(v2,v0));
_mm256_store_si256((__m256i*)(t+3*h+j),_mm256_add_epi32(_mm256_add_epi32(v3,v2),_mm256_add_epi32(v1,v0)));
}}
for(;j<r3;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
unsigned v3=a[3*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
c[2*h+j]=v2+v0;
c[3*h+j]=v3+v2+v1+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
unsigned v3=b[3*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
t[2*h+j]=v2+v0;
t[3*h+j]=v3+v2+v1+v0;
}}
for(;j+8<=r2;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(a+2*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(c+2*h+j),_mm256_add_epi32(v2,v0));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(b+2*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(t+2*h+j),_mm256_add_epi32(v2,v0));
}}
for(;j<r2;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
c[2*h+j]=v2+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
t[2*h+j]=v2+v0;
}}
for(;j+8<=h;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
}}
for(;j<h;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
}}
}
static void fallback_convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
alignas(4096)alignas(4096)static unsigned scratch[100000384u];if(!n)return;void*root_allocation=nullptr;unsigned*t=scratch+384;if(n>100000000u){if(posix_memalign(&root_allocation,4096,size_t(n)*4+1536))__builtin_trap();t=(unsigned*)root_allocation+384;}
if(n<=4096){memcpy(c,a,size_t(n)*4);memcpy(t,b,size_t(n)*4);root_or::solve(n,c,t);free(root_allocation);return;}
const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
ar_copy4_pair(h,r2,r3,a,b,c,t);
root_or::solve(h,c,t);root_or::solve(h,c+h,t+h);root_or::solve(r2,c+2*h,t+2*h);if(r3)root_or::solve(r3,c+3*h,t+3*h);
unsigned*x=c;
j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]-x[h+j]-x[2*h+j];x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));}
}
for(;j<r2;j++){x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));}
}
for(;j<h;j++){x[h+j]-=x[j];}
free(root_allocation);
}
template<bool Inv,unsigned Q>static inline void ar_or_roots(__m256i(&v)[Q]){
#pragma GCC unroll 3
for(unsigned st=0;st<3;st++){unsigned bit=Inv?2-st:st;
#pragma GCC unroll 8
for(unsigned q=0;q<Q;q++)if(q&(1u<<bit)){if constexpr(Inv)v[q]=_mm256_sub_epi32(v[q],v[q^(1u<<bit)]);else v[q]=_mm256_add_epi32(v[q],v[q^(1u<<bit)]);}}
}
static void root8_wave(const unsigned*a,const unsigned*b,unsigned*c){
constexpr unsigned H=16777216,R=16113920,L=H/8,T=1024,LP=T+32;
alignas(4096)static unsigned work[6*H+384];unsigned*t=work+384,*last=c+5*H;
alignas(64)static unsigned sc[1][6][8][LP];
for(unsigned j0=0;j0<L;j0+=T){
for(unsigned side=0;side<2;side++){
const unsigned*in=side?b:a;
for(unsigned rr=0;rr<8;rr++)for(unsigned j=0;j<T;j+=8){unsigned off=rr*L+j0+j;__m256i v[6];
#pragma GCC unroll 6
for(unsigned q=0;q<6;q++)v[q]=(q<5||off<R)?_mm256_load_si256((const __m256i*)(in+q*H+off)):_mm256_setzero_si256();ar_or_roots<false>(v);
#pragma GCC unroll 6
for(unsigned q=1;q<6;q++)_mm256_store_si256((__m256i*)(sc[0][q][rr]+j),v[q]);
}
for(unsigned q=0;q<6;q++){
for(unsigned j=0;j<T;j+=8){__m256i v[8];
#pragma GCC unroll 8
for(unsigned rr=0;rr<8;rr++)v[rr]=_mm256_load_si256((const __m256i*)(q?sc[0][q][rr]+j:in+rr*L+j0+j));ar_or_roots<false>(v);
#pragma GCC unroll 8
for(unsigned rr=1;rr<8;rr++)_mm256_store_si256((__m256i*)(sc[0][q][rr]+j),v[rr]);
}
unsigned*out=side?t+q*H:(q==5?last:c+q*H);
for(unsigned rr=0;rr<8;rr++){
#pragma GCC unroll 8
for(unsigned j=0;j<T;j+=8)if(side||q<5||rr*L+j0+j<R)_mm256_stream_si256((__m256i*)(out+rr*L+j0+j),_mm256_load_si256((const __m256i*)((q==0&&rr==0)?in+j0+j:sc[0][q][rr]+j)));}
}
}
}
_mm_sfence();
for(unsigned q=0;q<6;q++)for(unsigned rr=0;rr<8;rr++){unsigned off=rr*L,z=q<5?L:(off<R?std::min(L,R-off):0);if(z)root_or::solve(z,(q==5?last:c+q*H)+off,t+q*H+off);}
for(unsigned j0=0;j0<L;j0+=T){
for(unsigned q=0;q<6;q++)for(unsigned j=0;j<T;j+=8){__m256i v[8];
#pragma GCC unroll 8
for(unsigned rr=0;rr<8;rr++)v[rr]=(q<5||rr*L+j0+j<R)?_mm256_load_si256((const __m256i*)(c+q*H+rr*L+j0+j)):_mm256_setzero_si256();ar_or_roots<true>(v);
#pragma GCC unroll 8
for(unsigned rr=1;rr<8;rr++)_mm256_store_si256((__m256i*)(sc[0][q][rr]+j),v[rr]);
}
for(unsigned rr=0;rr<8;rr++){
for(unsigned j=0;j<T;j+=8){__m256i v[6];
#pragma GCC unroll 6
for(unsigned q=0;q<6;q++)v[q]=_mm256_load_si256((const __m256i*)(rr?sc[0][q][rr]+j:c+q*H+j0+j));ar_or_roots<true>(v);
#pragma GCC unroll 6
for(unsigned q=1;q<6;q++)_mm256_store_si256((__m256i*)(sc[0][q][rr]+j),v[q]);
}
for(unsigned q=0;q<6;q++){
#pragma GCC unroll 8
for(unsigned j=0;j<T;j+=8){unsigned off=rr*L+j0+j;if((q||rr)&&(q<5||off<R))_mm256_stream_si256((__m256i*)(c+q*H+off),_mm256_load_si256((const __m256i*)(sc[0][q][rr]+j)));}}
}
}
_mm_sfence();
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){if(n==100000000u)root8_wave(a,b,c);else fallback_convolution(n,a,b,c);}