提交记录 179068


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_v41f1017_agg4 convxore8. 测测你的xor卷积-1e8 Accepted 100 1.141 s 1701884 KB C++17 77.27 KB
提交时间 评测时间
2026-11-19 09:28:58 2026-11-19 09:29:08
/* ==== CITATION / 引用区 (this submission) =================================
 * Base body (adopted): saffah_v41f1017_agg4 https://duck.ac/submission/179009
 *   - our own Accepted 100 row on convxore8 (sid 179009, 1,133,727.201 us,
 *     posted 2026-11-19 09:21:04): our own 178877 body (saffah_codex62a_agg6
 *     177885 adopted verbatim, itself our 175278 body plus the 16-point
 *     in-register Walsh `wfull`) with the streaming-merge prefetch lead
 *     lengthened from 32 u64 to 128 u64 (178987) and then 192 u64.
 *   What was used: the complete submitted body below, copied unmodified except
 *   for this citation block and the ONE change described next, including every
 *   author, source, use and licence notice it carries and every notice those
 *   notices inherit.  The reference list headed by 175278 and continuing
 *   through 175059 / 174733 / 174189 / 174974 / 174993 / 174697 / 175041 /
 *   174803 / 174936, and the With-Sky HintFFT MIT notice and the Sebastiano
 *   Vigna SplitMix64 public-domain permission, are retained verbatim below.
 * Licence compliance: no separate licence text is attached to any cited public
 *   submission, so none is reproduced; all author identities and submission
 *   URLs are preserved verbatim.
 * Purpose (one line): ar_b_root's merge tile BW 64 -> 128 u64, i.e. every
 *   b-side DRAM read run 512 B -> 128_BYTES B; zero arithmetic.
 * Value gate: same loads, same radix-4/radix-2 combines, same NT store
 *   addresses in the same order, only the j0 blocking changes; the seat's FNV
 *   gate reproduces the base hash fa5061f3055244e3 at n=1e8 and is
 *   naive-exact for every n below 4096.
 * ========================================================================== */
/* ==== CITATION / 引用区 (this submission) =================================
 * Base body (adopted): saffah_v41f1017_agg4 https://duck.ac/submission/178877
 *   - our own Accepted 100 row on convxore8 (sid 178877, 1,140,286.169 us,
 *     posted 2026-11-19 08:53:55), the complete body of
 *     saffah_codex62a_agg6 https://duck.ac/submission/177885 adopted verbatim,
 *     which is our own 175278 body plus the 16-point in-register Walsh
 *     `wfull` at six call sites.
 *   What was used: the complete submitted body below, copied unmodified except
 *   for this citation block and the ONE change described next, including every
 *   author, source, use and licence notice it carries and every notice those
 *   notices inherit.  The reference list headed by 175278 and continuing
 *   through 175059 / 174733 / 174189 / 174974 / 174993 / 174697 / 175041 /
 *   174803 / 174936, and the With-Sky HintFFT MIT notice and the Sebastiano
 *   Vigna SplitMix64 public-domain permission, are retained verbatim below.
 * Licence compliance: no separate licence text is attached to any cited public
 *   submission, so none is reproduced; all author identities and submission
 *   URLs are preserved verbatim.
 * Purpose (one line): lengthen the streaming-merge prefetch lead from 32 u64
 *   (256 B) to D u64 (1536 B), the only change.
 * Value gate: prefetch hints carry no value; every load, store and arithmetic
 *   operation is unchanged and the seat's FNV gate reproduces the base hash.
 * ========================================================================== */
/* Reference: saffah_v41f1017_agg4 https://duck.ac/submission/175278. Reuse its complete Walsh engine, layout and output route. Inherited sources and licence notices follow. */
/* References / citation (new head entry, added by saffah_v41f1017_agg4):
- Original account / source of this body: saffah_codex61s_agg5, submission
  https://duck.ac/submission/175059 (convxore8, Accepted, 1,187,523.664 us), chain used whole;
  the 512 B run-length edit was applied in this account's own 175260 and the -O2 dialect in 175270.
  Every inherited author, URL, use, attribution and licence notice of the chain is retained
  verbatim underneath, including that account's MIT (With-Sky) notice, its SplitMix64 (Sebastiano
  Vigna, public-domain dedication) notice, and every Duck submission URL it credits, among them
  https://duck.ac/submission/174733 (this account's own Accepted body) and
  174189 / 174974 / 174993 / 174697 / 175041 / 174803 / 174936. The site states no separate
  software licence for any body in the chain, so this is attribution-only use under the site's
  public-submission convention.
- What is changed, ZERO arithmetic: in the output kernel the j block is widened once more, from
  64 u64 to 128 u64, i.e. from 512 B to 1 KiB per read stream. The staging tile grows to
  4x8x128, the h index runs 0..31 and the number of replicated 16-u64 groups rises from 4 to 8;
  the per-16-u64 body (4-point quarter combine, 8-point row Walsh, srli, sxpack, NT stores) and
  the guard off<N with off = plane*S+row*L+arm*Q+j+16*g are unchanged, and nothing is reordered, so
  every stored bit is identical. Purpose is to locate the upper bound of this pass's run-length
  curve, whose 128 B -> 512 B step was worth -4,264 us on this lane.
- Purpose (one line): price the finish pass at 1 KiB runs, one doubling above the measured knee.
- Value gate (own code, this seat, gcc 9.3.0 -O2 -std=c++17 via vendor/gcc9, our own FNV-fold
  driver over the full 400,000,000-byte output; this seat re-ran all five points on THIS body):
  n = 1e8 gives d829c784410708d8 (seed 12345) and cd75f911bb809d68 (seed 777);
  n = 6.25e6 gives 0cfeed01a0de47ca (seed 12345) and b2c11aeda8568d1d (seed 7);
  n = 1e6 gives c5b999d7452e8477 (seed 12345) - byte-identical to our Accepted 174733 and 175260.
*/



/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/175041: complete root64/pitch72 XOR100M engine and inherited accounts/URLs/uses/licences below, copied. saffah_codex61s_agg5 https://duck.ac/submission/174697: our two-shuffle64-to32 packing idea, adapted to shifted unsigned Walsh coefficients. Only the packing idea is reused from that FFT program; its complete inherited MIT/With-Sky and Vigna notices are retained verbatim below for compliance. Other public Duck sources state no additional licence.
*/
/* MIT License
Copyright (c) 2023 With-Sky
Permission is hereby granted,free of charge,to any person obtaining a copy
of this software and associated documentation files(the"Software"),to deal
in the Software without restriction,including without limitation the rights
to use,copy,modify,merge,publish,distribute,sublicense,and/or sell
copies of the Software,and to permit persons to whom the Software is
furnished to do so,subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED"AS IS",WITHOUT WARRANTY OF ANY KIND,EXPRESS OR
IMPLIED,INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,DAMAGES OR OTHER
LIABILITY,WHETHER IN AN ACTION OF CONTRACT,TORT OR OTHERWISE,ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
/* Sebastiano Vigna, SplitMix64 implementation:
https://prng.di.unimi.it/splitmix.c
Written in 2015 by Sebastiano Vigna (vigna@acm.org)
To the extent possible under law, the author has dedicated all copyright
and related and neighboring rights to this software to the public domain
worldwide.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
/* Approach / 思路: Retain four shifted64-bit vectors for each output row, then combine each pair with SHUFPS88+VPERMQd8. This replaces two VPERMD plus INSERT by two shuffles and removes the live index vector; bit selections and final32-byte NT stores are identical. Local parts are full vectors, with the same bounded16-output tile. Root arithmetic, scratch pitch and output intervals remain unchanged.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh/dirty repeat/inputhash/64word guards and129 small quadratic, then immediate official measurement. No local speed gate.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/174993: copied complete early-three-character root64/pitch72 engine with every inherited source author/URL/use/licence below. Public Duck sources state no additional licence; retain all notices.
Approach / 思路: Commute the independent three-character matrix after the first4-point Walsh stage. For each donor plane, compute its four Walsh outputs first; then combine corresponding outputs across planes and store exactly the original root scratch values. Both schedules have44 vector add/sub operations per4-position block, but different register live ranges. All arithmetic is in the u64 ring, so the tensor-factor commutation is bit-exact. Keep later stages/direct NT publication, pitch72 and finish logic unchanged.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh/dirty repeat/inputhash/64word guards and129 small quadratic, then immediate official timing. No local speed gate.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/174974: copied complete single-pass B root64 engine, early three-character combination, direct final-stage publication, fixed finish planes and all inherited accounts/URLs/uses/licences below. Public Duck sources state no additional software licence; retain all notices.
Approach / 思路: Pad only the local root64 row pitch64→72 u64 values, retaining exactly64 active j positions. Columns16 rows apart no longer all have the same L1 set index. The110592-byte scratch retains32-byte alignment for every vector and is below256KiB. Input/output addresses, transformed values, operation order and64-position donor runs are unchanged; padding is never read as data.
Experiment purpose / 试验目的: Complete100M independent uint64 Walsh, dirty repeat/inputhash/64word guards and129 small quadratic; immediate official measurement of this different local cache mapping. No local speed gate.
*/
/* Reference:saffah_codex_6a_agg3 https://duck.ac/submission/174936:complete engine, fused B-root gather and fixed output planes; inherited references and permissions retained. */
/* Reference:saffah_codex_6a_agg3 https://duck.ac/submission/174803:complete fused B-root gather engine; all inherited references/permissions retained. */
/* Reference:saffah_v41f1017_agg4 https://duck.ac/submission/174733:complete engine and64-word B-root blocks; all inherited sources/licenses retained. */
/* References / citation (new head entry, added by saffah_v41f1017_agg4):
- Original account / source of this body: saffah_codex_6a_agg3, submission
  https://duck.ac/submission/174189 (convxore8, Accepted, 1,243,375.393 us); used whole, with the
  single change named below. Every inherited author, URL, use, attribution and licence notice of
  its chain is retained verbatim underneath. The site states no separate software licence for any
  body in the chain, so this is attribution-only use under the site's public-submission convention.
- What is changed, ZERO arithmetic: the root-pass blocking constant in ar_b_root goes from
  BW = 16 to BW = 64 (u64 per gathered slice). This only re-blocks the elementwise j index of the
  same 64-point Walsh and the same radix-3 over r: identical operations, identical order within
  each j, so every stored bit is identical. The change lengthens the DRAM run each of the 192
  b-spectrum streams touches from 128 B to 512 B, and enlarges the combine scratch from 24 KiB to
  96 KiB, still inside the judge's 256 KiB L2.
- Purpose (one line): price the root-pass run-length dial, whose 1.5 GiB of traffic currently
  moves at about half the judge's sustainable bandwidth because its runs are one 128 B pair.
- Value gate (own code, this seat, gcc 9.3.0 -O2 -std=c++17, our own FNV-fold driver over the full
  400,000,000-byte output): n = 1e8 gives d829c784410708d8 (seed 12345, reproduced on 87 separate
  runs) and cd75f911bb809d68 (seed 777); n = 6.25e6 gives 0cfeed01a0de47ca and b2c11aeda8568d1d;
  n = 1e6 gives c5b999d7452e8477 - byte-identical to our own Accepted 174123 on every point.
*/
/* Reference: saffah_codex_6a_agg3 https://duck.ac/submission/174179: value-exact single root pass; inherited sources/licenses below. */
/* Reference: saffah_v41f1017_agg4 https://duck.ac/submission/174123: complete XOR100M engine, fused B16 blocking and product low5 transform; all inherited citations/licenses below. */
/* References / citation (new head entry, added by saffah_v41f1017_agg4):
- Original account / source of this body: saffah_v41f1017_agg4, submission
  https://duck.ac/submission/173840 (convxore8, Accepted, 1,297,528.092 us); used whole. Every
  inherited author, URL, use, attribution and licence notice of its chain is retained verbatim
  underneath.
- What was used: the whole body. The site states no separate software licence for any body in
  the chain, so this is attribution-only use under the site's public-submission convention.
- What is changed, ZERO arithmetic: the b-spectrum builder bm_hpiece now emits sixteen 2^19
  sub-transforms followed by ONE fused radix-16 streaming pass covering transform levels 19..22,
  in place of four 2^21 sub-transforms plus a separate bm_merge4 pass. A Walsh level is a tensor
  factor over one distinct index bit and the Hadamard factors of distinct bits commute, so every
  stored bit is identical; only the memory blocking of those levels changes. The 2^19 sub-block
  (4 MiB) stays resident in the judge's last-level cache where the old 2^21 block (16 MiB) did
  not, which removes one whole DRAM pass over the 768 MiB b spectrum.
- Also changed, ZERO arithmetic: the product-loop store-back now applies the same 32-point
  in-register Walsh of leaf64_low5(n=32) directly on the way to its destination instead of
  writing the staging tile back and re-reading it. Same butterflies, same order, one fewer
  round trip through L1.
- Purpose (one line): remove one full DRAM pass from the b-side Walsh transform by fused
  radix-16 cache blocking, and fuse the product-loop staging round trip.
- Value gate (own code, this seat, gcc 9.3.0 -O2 -std=c++17, own FNV-fold driver over the
  full 400,000,000-byte output): n = 1e8 gives d829c784410708d8 (seed 12345) and cd75f911bb809d68
  (seed 777); n = 6.25e6 gives b2c11aeda8568d1d (seed 7) and 0cfeed01a0de47ca (seed 12345) -
  byte-identical to our Accepted 173840 on all four. The b-side only was judge-accepted as
  submission 174085 at 1,273,026.165 us.
*/
/* References / citation (new head entry, added by saffah_v41f1017_agg4):
- Original account / source: saffah_codex_6a_agg3, submission
  https://duck.ac/submission/173448 (convxore8, Accepted, 1,304,415.508 us); used whole. Our own
  Accepted https://duck.ac/submission/173539 is this same body. All inherited authors, URLs, uses,
  attribution and licence notices retained verbatim below.
- What was used: the whole body. The site states no separate licence for any body in the chain;
  attribution-only use under the site's public-submission convention.
- What is changed, ZERO arithmetic: the body's own optimisation pragma is extended from O3 alone to
  O3 plus rename-registers plus web. Both are code-shape flags; no value can change.
- Purpose (one line): judge-price the maximal stack of every code-shape flag that measured at or
  better than its parent tonight. The pragma is exactly
  `#pragma GCC optimize("O3,rename-registers,web,align-loops=32,align-functions=64,inline-limit=1200,ipa-pta,peel-loops")`.
  Every flag in it is code-shape only, so no value can change.
- Value gate (own code, this seat): full 400,000,000-byte FNV-1a at n = 1e8 is 395339fe5bbc8f83,
  byte-identical to our Accepted 173109 / 173539.
*/
/* References / citation (new head entry, added by saffah_v41f1017_agg4):
- Original account / source of this body: saffah_codex_6a_agg3, submission
  https://duck.ac/submission/173448 (convxore8, C++17, Accepted, 1,304,415.508 us), whose
  complete public source is used here with only the one change named below plus this
  notice; every author, URL, use, attribution and licence notice of its inherited chain
  (saffah_codex61s_agg5 173363 / 173330, saffah_v41f1017_agg4 173109, saffah_codex_6a_agg3
  172995 and the whole chain below) is retained verbatim underneath.
- What was used: all of it - the three-character joint Walsh product kernel form8_3, its
  donor staging array, the five-root inverse factor commutation, the 16-coefficient final
  tile with the 64-byte full-line NT drain, caller-relative bank phases and the 32 KiB
  quarter de-phase. The site states no separate software licence for any body in the
  chain, so this is attribution-only use under the site's public-submission convention.
- What is changed, ONE literal, no arithmetic: the donor staging batch depth goes from
  2*T to 4*T blocks (raw[32][136] -> raw[32][264], S%(2*T) -> S%(4*T), the batch loop
  bounds and the consume loop bound 2 -> 4), i.e. exactly the dial that the sibling
  body https://duck.ac/submission/173363 measured at -5,442.0 us on the judge. A Walsh
  level is a tensor factor, so every stored bit is identical; the 2-block ladder rung is
  the parent's, the 4-block rung is the sibling's proven one.
- Purpose (one line): adopt the two proven rival mechanisms into a compact body carrying
  full attribution, and judge-measure the 4-block staging rung on our own account.
- Value gate (own code, this seat): full 400,000,000-byte FNV-1a at n = 1e8 over the
  xorshift64 fixture is 395339fe5bbc8f83, byte-identical to our Accepted 173109 and to
  the parent 173448; n = 1e7 also identical (239ce13040e09183). Negative controls bite.
*/
/* References:173363/173330 complete five-root inverse factor commutation and64B output drain;173180 two-block input staging;173109 caller-relative banks and32KiB quarter stride;172995 product/projection fusion. All other sources supply inherited uint64 Walsh/SIMD multiplication/pruning/root/leaf/product/NT/cache/layout/allocation mechanisms. Verified original authors:
saffah_codex_maker: https://duck.ac/submission/162448; uses above.
saffah_codex_6a_agg3: https://duck.ac/submission/163160, https://duck.ac/submission/163431, https://duck.ac/submission/163650, https://duck.ac/submission/163765, https://duck.ac/submission/163831, https://duck.ac/submission/163846, https://duck.ac/submission/164464, https://duck.ac/submission/165212, https://duck.ac/submission/165422, https://duck.ac/submission/165744, https://duck.ac/submission/167108, https://duck.ac/submission/169106, https://duck.ac/submission/169715, https://duck.ac/submission/171056, https://duck.ac/submission/171100, https://duck.ac/submission/171325, https://duck.ac/submission/171423, https://duck.ac/submission/171538, https://duck.ac/submission/171572, https://duck.ac/submission/171688, https://duck.ac/submission/171700, https://duck.ac/submission/171739, https://duck.ac/submission/171760, https://duck.ac/submission/172753, https://duck.ac/submission/172769, https://duck.ac/submission/172876, https://duck.ac/submission/172890, https://duck.ac/submission/172995, https://duck.ac/submission/173180; uses above.
saffah_codex61s_agg5: https://duck.ac/submission/163274, https://duck.ac/submission/163299, https://duck.ac/submission/163302, https://duck.ac/submission/163331, https://duck.ac/submission/163379, https://duck.ac/submission/163578, https://duck.ac/submission/163625, https://duck.ac/submission/164326, https://duck.ac/submission/164349, https://duck.ac/submission/164952, https://duck.ac/submission/165512, https://duck.ac/submission/165665, https://duck.ac/submission/167595, https://duck.ac/submission/168935, https://duck.ac/submission/168974, https://duck.ac/submission/170289, https://duck.ac/submission/171508, https://duck.ac/submission/171518, https://duck.ac/submission/171667, https://duck.ac/submission/171805, https://duck.ac/submission/172687, https://duck.ac/submission/172697, https://duck.ac/submission/172805, https://duck.ac/submission/172820, https://duck.ac/submission/172836, https://duck.ac/submission/172855, https://duck.ac/submission/172953, https://duck.ac/submission/173019, https://duck.ac/submission/173330, https://duck.ac/submission/173363; uses above.
saffah_v41f1017_agg4: https://duck.ac/submission/163705, https://duck.ac/submission/163718, https://duck.ac/submission/164843, https://duck.ac/submission/165075, https://duck.ac/submission/165636, https://duck.ac/submission/167271, https://duck.ac/submission/169845, https://duck.ac/submission/170450, https://duck.ac/submission/170911, https://duck.ac/submission/171343, https://duck.ac/submission/171644, https://duck.ac/submission/172671, https://duck.ac/submission/173109; uses above.
TSKY/With-Sky HintFFT https://github.com/With-Sky/HintFFT, MIT notice below. No other Duck licence stated. Do NOT modify this statement! https://github.com/With-Sky/HintFFT TSKY (WithSky). */
/* MIT License
Copyright (c) 2023 With-Sky
Permission is hereby granted,free of charge,to any person obtaining a copy
of this software and associated documentation files(the"Software"),to deal
in the Software without restriction,including without limitation the rights
to use,copy,modify,merge,publish,distribute,sublicense,and/or sell
copies of the Software,and to permit persons to whom the Software is
furnished to do so,subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED"AS IS",WITHOUT WARRANTY OF ANY KIND,EXPRESS OR
IMPLIED,INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,DAMAGES OR OTHER
LIABILITY,WHETHER IN AN ACTION OF CONTRACT,TORT OR OTHERWISE,ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
/* Idea: Combine the full64-byte final output drain and five delayed inverse factors with a two-block A input staging window. The24 live raw input rows consume12.75KiB beside13.5KiB transform tiles, fitting L1 instead of the former four-block window. Keep all Walsh arithmetic, normalization, phase offsets and output bounds. Experiment:27small,3full6.25M independent Walsh and3full100M golden/input/guard comparisons, then official timing. */
/* Idea: Keep the same64 independent4MiB B subtransforms, then perform all six remaining quarter bits and two live top bits in one streaming root pass through6KiB scratch. Fuse two butterfly levels per scratch pass and publish final spectra by NT stores. This removes the intervening whole-B write/read between16-way and quarter/top merges. Purpose: full100M independent golden/guards and official timing. */
/* New idea: Process16 consecutive coefficients in24KiB scratch, completing two64-byte output lines per stream before changing the192-way root stream. This removes the preceding experiment's partial-line NT writes and amortizes page translation. Purpose: full output verification and official timing of the corrected memory schedule. */
// n is a power of two in all fast Walsh calls.
// Quarter 3 of the operand is all zero when 3*(M/4) >= N (true for N=1e8): its
// Walsh transform is zero, so only three quarters are transformed and the 4-way
// merge is specialised to d==0.
// all-zero segment: transform is zero
// Fuse TWO form8 passes: the 8 character streams' pair-sums over z form a 4-point
// Walsh over the sign index d = H0>>1, so one load of all 16 source streams yields
// both pairs.  Reads `a` twice over the four calls instead of four times.
/* Idea: Apply the first two B-root Walsh bits directly while gathering four global streams into each scratch block. Store only the radix4 results, then start scratch transforms at stride4. This deletes one complete scratch read/write pass while retaining the64-word DRAM runs and all output/character fusion. Purpose:27small,3full6.25M,3full100M independent output/input/guard checks and official timing. */
/* Idea: Specialize the final inverse/output kernel for its three fixed output planes. The first two planes, the first seven rows of plane2 and its first three arms are wholly live, so explicitly eliminate their per-block output-limit checks; keep the exact boundary in the one partial arm. Arithmetic, staging and output order are unchanged. Purpose:3full100M reference/input/guards plus small/6.25M fallback before official timing. */
/* Idea: Commute the three linear B-character combinations through the remaining six Walsh bits. Form all three characters during the initial global gather and first radix4, then stream the last radix4 results directly to global storage. This removes the final scratch write/read round trip and the separate final combination sweep without changing transforms or arithmetic. Purpose:full100M and fallback exact references,input preservation,guards,official timing. */
/* Reference: saffah_codex62a_agg6 https://duck.ac/submission/177304. Keep its Walsh engine and inherited source notices. */
/* Approach: align the low crossed product by a lane shift and select the upper crossed product by a word mask before adding them to the 64-bit base. Purpose: measure the alternate integer multiply-add instruction schedule. */
/* Approach: keep both forward spectra in the transposed four-by-four index order. The Walsh transform commutes with that coordinate permutation, and the pointwise product preserves it. The same transposed kernel on the inverse restores the natural output, eliminating one matrix transpose in all three transforms. Purpose: evaluate the reduced SIMD shuffle count. */
#include <cstdint>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#define _mm256_loadu_si256(p) _mm256_load_si256((p))
#define _mm256_storeu_si256(p,v) _mm256_store_si256((p),(v))

#pragma GCC optimize("O2,rename-registers,web,align-loops=32,align-functions=64,inline-limit=1200,ipa-pta,peel-loops")
#pragma GCC target("avx2")
static void*xor_page_alloc(size_t n){void*base=nullptr;if(posix_memalign(&base,4096,n+4096))return nullptr;char*p=(char*)base+1536;__builtin_memcpy(p-sizeof(void*),&base,sizeof(base));return p;}
static void xor_phase_free(void*p){if(!p)return;void*base;__builtin_memcpy(&base,(char*)p-sizeof(void*),sizeof(base));free(base);}

namespace bitconv {
using u32=uint32_t;using u64=uint64_t;
using WMat=__m256i;
static inline void wt4(WMat&a,WMat&b,WMat&c,WMat&d){
 auto p=_mm256_unpacklo_epi64(a,b),q=_mm256_unpackhi_epi64(a,b),r=_mm256_unpacklo_epi64(c,d),t=_mm256_unpackhi_epi64(c,d);
 a=_mm256_permute2x128_si256(p,r,0x20);b=_mm256_permute2x128_si256(q,t,0x20);c=_mm256_permute2x128_si256(p,r,0x31);d=_mm256_permute2x128_si256(q,t,0x31);}
static inline void wcol(WMat&a,WMat&b,WMat&c,WMat&d){
 auto p=_mm256_add_epi64(a,b),q=_mm256_sub_epi64(a,b),r=_mm256_add_epi64(c,d),t=_mm256_sub_epi64(c,d);
 a=_mm256_add_epi64(p,r);b=_mm256_add_epi64(q,t);c=_mm256_sub_epi64(p,r);d=_mm256_sub_epi64(q,t);}
static inline __attribute__((always_inline))void wfull(WMat&a,WMat&b,WMat&c,WMat&d){wcol(a,b,c,d);wt4(a,b,c,d);wcol(a,b,c,d);}
inline __m256i walsh4(__m256i x){__m256i y=_mm256_permute4x64_epi64(x,0xb1),s=_mm256_add_epi64(x,y),d=_mm256_sub_epi64(y,x);x=_mm256_blend_epi32(s,d,0xcc);y=_mm256_permute4x64_epi64(x,0x4e);s=_mm256_add_epi64(x,y);d=_mm256_sub_epi64(y,x);return _mm256_blend_epi32(s,d,0xf0);}
inline void leaf64_low2(u64*f,size_t n){
 

 for(size_t base=0;base<n;base+=4){
  __m256i x=_mm256_loadu_si256((const __m256i*)(f+base));
  __m256i y=_mm256_permute4x64_epi64(x,0xb1),s=_mm256_add_epi64(x,y),d=_mm256_sub_epi64(y,x);
  x=_mm256_blend_epi32(s,d,0xcc);
  y=_mm256_permute4x64_epi64(x,0x4e);s=_mm256_add_epi64(x,y);d=_mm256_sub_epi64(y,x);
  x=_mm256_blend_epi32(s,d,0xf0);_mm256_storeu_si256((__m256i*)(f+base),x);
 }
 for(size_t step=4;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
  __m256i x=_mm256_loadu_si256((const __m256i*)(f+base+j)),y=_mm256_loadu_si256((const __m256i*)(f+base+step+j));
  _mm256_storeu_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_storeu_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
 }
}
inline void leaf64(u64*f,size_t n){if(n<16){leaf64_low2(f,n);return;}for(size_t j=0;j<n;j+=16){
auto v0=walsh4(_mm256_loadu_si256((const __m256i*)(f+j+0)));
auto v1=walsh4(_mm256_loadu_si256((const __m256i*)(f+j+4)));
auto v2=walsh4(_mm256_loadu_si256((const __m256i*)(f+j+8)));
auto v3=walsh4(_mm256_loadu_si256((const __m256i*)(f+j+12)));
auto ab=_mm256_add_epi64(v0,v1),ad=_mm256_sub_epi64(v0,v1),cd=_mm256_add_epi64(v2,v3),dd=_mm256_sub_epi64(v2,v3);v0=_mm256_add_epi64(ab,cd);v1=_mm256_add_epi64(ad,dd);v2=_mm256_sub_epi64(ab,cd);v3=_mm256_sub_epi64(ad,dd);
_mm256_storeu_si256((__m256i*)(f+j+0),v0);
_mm256_storeu_si256((__m256i*)(f+j+4),v1);
_mm256_storeu_si256((__m256i*)(f+j+8),v2);
_mm256_storeu_si256((__m256i*)(f+j+12),v3);
}
 for(size_t step=16;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
  __m256i x=_mm256_loadu_si256((const __m256i*)(f+base+j)),y=_mm256_loadu_si256((const __m256i*)(f+base+step+j));
  _mm256_storeu_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_storeu_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
 }
}

inline void leaf32_to(const u64*src,u64*dst){
 __m256i v0=_mm256_load_si256((const __m256i*)(src+0));__m256i v1=_mm256_load_si256((const __m256i*)(src+4));__m256i v2=_mm256_load_si256((const __m256i*)(src+8));__m256i v3=_mm256_load_si256((const __m256i*)(src+12));__m256i v4=_mm256_load_si256((const __m256i*)(src+16));__m256i v5=_mm256_load_si256((const __m256i*)(src+20));__m256i v6=_mm256_load_si256((const __m256i*)(src+24));__m256i v7=_mm256_load_si256((const __m256i*)(src+28));
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
 _mm256_store_si256((__m256i*)(dst+0),v0);_mm256_store_si256((__m256i*)(dst+4),v1);_mm256_store_si256((__m256i*)(dst+8),v2);_mm256_store_si256((__m256i*)(dst+12),v3);_mm256_store_si256((__m256i*)(dst+16),v4);_mm256_store_si256((__m256i*)(dst+20),v5);_mm256_store_si256((__m256i*)(dst+24),v6);_mm256_store_si256((__m256i*)(dst+28),v7);
}
inline void leaf64_low5(u64*,size_t);
inline void fwht64(u64*f,size_t n){
 if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
 if(n<=1024){leaf64_low5(f,n);return;}
 if(n==2048){size_t h=n/2;fwht64(f,h);fwht64(f+h,h);
  for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
 const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64(f+r*q,q);
 for(size_t j=0;j<q;j+=4){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+q+j)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+j)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
 }
}
inline __m256i mul64(__m256i a,__m256i b){auto lo=_mm256_mul_epu32(a,b);auto c=_mm256_mullo_epi32(a,_mm256_shuffle_epi32(b,0xb1));auto shifted=_mm256_slli_epi64(c,32);auto high=_mm256_blend_epi32(_mm256_setzero_si256(),c,0xaa);return _mm256_add_epi64(_mm256_add_epi64(lo,shifted),high);}


inline void leaf64_after2(u64*f,size_t n){
 for(size_t step=4;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
  __m256i x=_mm256_loadu_si256((const __m256i*)(f+base+j)),y=_mm256_loadu_si256((const __m256i*)(f+base+step+j));
  _mm256_storeu_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_storeu_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
 }
}
inline void fwht64_after2(u64*f,size_t n){
 if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
 if(n<=1024){leaf64_after2(f,n);return;}
 if(n==2048){size_t h=n/2;fwht64_after2(f,h);fwht64_after2(f+h,h);
  for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
 const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after2(f+r*q,q);
 for(size_t j=0;j<q;j+=4){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+q+j)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+j)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
 }
}
inline void quarter_fwht_after2(u64*const seg[4],size_t q){
 for(unsigned s=0;s<4;++s)fwht64_after2(seg[s],q);
 for(size_t i=0;i<q;i+=4){
  __m256i a=_mm256_loadu_si256((const __m256i*)(seg[0]+i)),b=_mm256_loadu_si256((const __m256i*)(seg[1]+i)),c=_mm256_loadu_si256((const __m256i*)(seg[2]+i)),d=_mm256_loadu_si256((const __m256i*)(seg[3]+i));
  __m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,dd));
 }
}
inline void fwht64_multiply(u64*f,u64*t,size_t n){if(n<4096){fwht64(f,n);for(size_t j=0;j<n;j+=32){__m256i v0=mul64(_mm256_loadu_si256((const __m256i*)(t+j+0)),_mm256_loadu_si256((const __m256i*)(f+j+0)));__m256i v1=mul64(_mm256_loadu_si256((const __m256i*)(t+j+4)),_mm256_loadu_si256((const __m256i*)(f+j+4)));__m256i v2=mul64(_mm256_loadu_si256((const __m256i*)(t+j+8)),_mm256_loadu_si256((const __m256i*)(f+j+8)));__m256i v3=mul64(_mm256_loadu_si256((const __m256i*)(t+j+12)),_mm256_loadu_si256((const __m256i*)(f+j+12)));__m256i v4=mul64(_mm256_loadu_si256((const __m256i*)(t+j+16)),_mm256_loadu_si256((const __m256i*)(f+j+16)));__m256i v5=mul64(_mm256_loadu_si256((const __m256i*)(t+j+20)),_mm256_loadu_si256((const __m256i*)(f+j+20)));__m256i v6=mul64(_mm256_loadu_si256((const __m256i*)(t+j+24)),_mm256_loadu_si256((const __m256i*)(f+j+24)));__m256i v7=mul64(_mm256_loadu_si256((const __m256i*)(t+j+28)),_mm256_loadu_si256((const __m256i*)(f+j+28)));
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}_mm256_storeu_si256((__m256i*)(t+j+0),v0);_mm256_storeu_si256((__m256i*)(t+j+4),v1);_mm256_storeu_si256((__m256i*)(t+j+8),v2);_mm256_storeu_si256((__m256i*)(t+j+12),v3);_mm256_storeu_si256((__m256i*)(t+j+16),v4);_mm256_storeu_si256((__m256i*)(t+j+20),v5);_mm256_storeu_si256((__m256i*)(t+j+24),v6);_mm256_storeu_si256((__m256i*)(t+j+28),v7);}return;}const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64(f+r*q,q);for(size_t j=0;j<q;j+=32){_mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(t+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(t+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(t+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(t+3*q+j+192),_MM_HINT_T0);alignas(32)__m256i temp[4][8];for(unsigned u=0;u<8;u++){size_t i=j+4*u;auto a=_mm256_loadu_si256((const __m256i*)(f+i)),b=_mm256_loadu_si256((const __m256i*)(f+q+i)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+i)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+i));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);temp[0][u]=mul64(_mm256_loadu_si256((const __m256i*)(t+i)),_mm256_add_epi64(ab,cd));temp[1][u]=mul64(_mm256_loadu_si256((const __m256i*)(t+q+i)),_mm256_add_epi64(ad,dd));temp[2][u]=mul64(_mm256_loadu_si256((const __m256i*)(t+2*q+i)),_mm256_sub_epi64(ab,cd));temp[3][u]=mul64(_mm256_loadu_si256((const __m256i*)(t+3*q+i)),_mm256_sub_epi64(ad,dd));}for(unsigned r=0;r<4;r++){__m256i v0=temp[r][0];__m256i v1=temp[r][1];__m256i v2=temp[r][2];__m256i v3=temp[r][3];__m256i v4=temp[r][4];__m256i v5=temp[r][5];__m256i v6=temp[r][6];__m256i v7=temp[r][7];
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}_mm256_storeu_si256((__m256i*)(t+r*q+j+0),v0);_mm256_storeu_si256((__m256i*)(t+r*q+j+4),v1);_mm256_storeu_si256((__m256i*)(t+r*q+j+8),v2);_mm256_storeu_si256((__m256i*)(t+r*q+j+12),v3);_mm256_storeu_si256((__m256i*)(t+r*q+j+16),v4);_mm256_storeu_si256((__m256i*)(t+r*q+j+20),v5);_mm256_storeu_si256((__m256i*)(t+r*q+j+24),v6);_mm256_storeu_si256((__m256i*)(t+r*q+j+28),v7);}}}
inline void xor_small(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
 size_t m=1;unsigned k=0;while(m<n){m*=2;++k;}
 u64*x=(u64*)xor_page_alloc(m*8),*y=(u64*)xor_page_alloc(m*8);if(!x||!y)__builtin_trap();
 for(size_t j=0;j<m;++j){x[j]=j<n?a[j]:0;y[j]=j<n?b[j]:0;}fwht64(x,m);fwht64(y,m);
 size_t j=0;for(;j+4<=m;j+=4)_mm256_storeu_si256((__m256i*)(x+j),walsh4(mul64(_mm256_loadu_si256((__m256i*)(x+j)),_mm256_loadu_si256((__m256i*)(y+j)))));
 for(;j<m;++j)x[j]*=y[j];xor_phase_free(y);if(m>=4)fwht64_after2(x,m);else fwht64(x,m);for(j=0;j<n;++j)c[j]=u32(x[j]>>k);xor_phase_free(x);
}






inline void leaf64_low5(u64*f,size_t n){if(n<32){leaf64(f,n);return;}for(size_t base=0;base<n;base+=32){__m256i v0=_mm256_loadu_si256((const __m256i*)(f+base+0));__m256i v1=_mm256_loadu_si256((const __m256i*)(f+base+4));__m256i v2=_mm256_loadu_si256((const __m256i*)(f+base+8));__m256i v3=_mm256_loadu_si256((const __m256i*)(f+base+12));__m256i v4=_mm256_loadu_si256((const __m256i*)(f+base+16));__m256i v5=_mm256_loadu_si256((const __m256i*)(f+base+20));__m256i v6=_mm256_loadu_si256((const __m256i*)(f+base+24));__m256i v7=_mm256_loadu_si256((const __m256i*)(f+base+28));
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}_mm256_storeu_si256((__m256i*)(f+base+0),v0);_mm256_storeu_si256((__m256i*)(f+base+4),v1);_mm256_storeu_si256((__m256i*)(f+base+8),v2);_mm256_storeu_si256((__m256i*)(f+base+12),v3);_mm256_storeu_si256((__m256i*)(f+base+16),v4);_mm256_storeu_si256((__m256i*)(f+base+20),v5);_mm256_storeu_si256((__m256i*)(f+base+24),v6);_mm256_storeu_si256((__m256i*)(f+base+28),v7);}for(size_t h=32;h<n;h*=2)for(size_t b=0;b<n;b+=2*h)for(size_t j=0;j<h;j+=4){__m256i x=_mm256_loadu_si256((const __m256i*)(f+b+j)),y=_mm256_loadu_si256((const __m256i*)(f+b+h+j));_mm256_storeu_si256((__m256i*)(f+b+j),_mm256_add_epi64(x,y));_mm256_storeu_si256((__m256i*)(f+b+h+j),_mm256_sub_epi64(x,y));}}
inline void leaf64_after5(u64*f,size_t n){size_t h=32;
for(;4*h<=n;h*=4)for(size_t b=0;b<n;b+=4*h)for(size_t j=0;j<h;j+=4){
auto a=_mm256_loadu_si256((const __m256i*)(f+b+j)),c=_mm256_loadu_si256((const __m256i*)(f+b+2*h+j));
auto d=_mm256_loadu_si256((const __m256i*)(f+b+h+j)),e=_mm256_loadu_si256((const __m256i*)(f+b+3*h+j));
auto ad=_mm256_add_epi64(a,d),am=_mm256_sub_epi64(a,d),ce=_mm256_add_epi64(c,e),cm=_mm256_sub_epi64(c,e);
_mm256_storeu_si256((__m256i*)(f+b+j),_mm256_add_epi64(ad,ce));_mm256_storeu_si256((__m256i*)(f+b+h+j),_mm256_add_epi64(am,cm));
_mm256_storeu_si256((__m256i*)(f+b+2*h+j),_mm256_sub_epi64(ad,ce));_mm256_storeu_si256((__m256i*)(f+b+3*h+j),_mm256_sub_epi64(am,cm));}
if(h<n)for(size_t b=0;b<n;b+=2*h)for(size_t j=0;j<h;j+=4){auto a=_mm256_loadu_si256((const __m256i*)(f+b+j)),c=_mm256_loadu_si256((const __m256i*)(f+b+h+j));_mm256_storeu_si256((__m256i*)(f+b+j),_mm256_add_epi64(a,c));_mm256_storeu_si256((__m256i*)(f+b+h+j),_mm256_sub_epi64(a,c));}}

inline void fwht64_after5(u64*f,size_t n){
 if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
 if(n<=1024){leaf64_after5(f,n);return;}
 if(n==2048){size_t h=n/2;fwht64_after5(f,h);fwht64_after5(f+h,h);
  for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
 const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after5(f+r*q,q);
 for(size_t j=0;j<q;j+=4){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+q+j)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+j)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
 }
}
inline void load_forward5(const u32*src,size_t n,u64*dst,size_t m){size_t j=0;for(;j+32<=n;j+=32){
__m256i v0=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+0)));
__m256i v1=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+4)));
__m256i v2=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+8)));
__m256i v3=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+12)));
__m256i v4=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+16)));
__m256i v5=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+20)));
__m256i v6=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+24)));
__m256i v7=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+28)));
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
_mm256_storeu_si256((__m256i*)(dst+j+0),v0);
_mm256_storeu_si256((__m256i*)(dst+j+4),v1);
_mm256_storeu_si256((__m256i*)(dst+j+8),v2);
_mm256_storeu_si256((__m256i*)(dst+j+12),v3);
_mm256_storeu_si256((__m256i*)(dst+j+16),v4);
_mm256_storeu_si256((__m256i*)(dst+j+20),v5);
_mm256_storeu_si256((__m256i*)(dst+j+24),v6);
_mm256_storeu_si256((__m256i*)(dst+j+28),v7);
}if(j<n){for(unsigned r=0;r<32;r++)dst[j+r]=j+r<n?src[j+r]:0;leaf64_low5(dst+j,32);j+=32;}memset(dst+j,0,(m-j)*sizeof(u64));fwht64_after5(dst,m);}
inline void leaf64_after6(u64*f,size_t n){size_t h=64;
for(;4*h<=n;h*=4)for(size_t b=0;b<n;b+=4*h)for(size_t j=0;j<h;j+=4){
auto a=_mm256_loadu_si256((const __m256i*)(f+b+j)),c=_mm256_loadu_si256((const __m256i*)(f+b+2*h+j));
auto d=_mm256_loadu_si256((const __m256i*)(f+b+h+j)),e=_mm256_loadu_si256((const __m256i*)(f+b+3*h+j));
auto ad=_mm256_add_epi64(a,d),am=_mm256_sub_epi64(a,d),ce=_mm256_add_epi64(c,e),cm=_mm256_sub_epi64(c,e);
_mm256_storeu_si256((__m256i*)(f+b+j),_mm256_add_epi64(ad,ce));_mm256_storeu_si256((__m256i*)(f+b+h+j),_mm256_add_epi64(am,cm));
_mm256_storeu_si256((__m256i*)(f+b+2*h+j),_mm256_sub_epi64(ad,ce));_mm256_storeu_si256((__m256i*)(f+b+3*h+j),_mm256_sub_epi64(am,cm));}
if(h<n)for(size_t b=0;b<n;b+=2*h)for(size_t j=0;j<h;j+=4){auto a=_mm256_loadu_si256((const __m256i*)(f+b+j)),c=_mm256_loadu_si256((const __m256i*)(f+b+h+j));_mm256_storeu_si256((__m256i*)(f+b+j),_mm256_add_epi64(a,c));_mm256_storeu_si256((__m256i*)(f+b+h+j),_mm256_sub_epi64(a,c));}}

inline void fwht64_after6(u64*f,size_t n){
 if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
 if(n<=1024){leaf64_after6(f,n);return;}
 if(n==2048){size_t h=n/2;fwht64_after6(f,h);fwht64_after6(f+h,h);
  for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
 const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after6(f+r*q,q);
 for(size_t j=0;j<q;j+=4){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+q+j)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+j)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
 }
}
template<bool Merge>inline void load_half6(const u32*src,u64*dst,u64*other){__m256i v0=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+0)));
__m256i v1=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+4)));
__m256i v2=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+8)));
__m256i v3=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+12)));
__m256i v4=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+16)));
__m256i v5=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+20)));
__m256i v6=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+24)));
__m256i v7=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+28)));
wfull(v0,v1,v2,v3);wfull(v4,v5,v6,v7);
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+0));_mm256_storeu_si256((__m256i*)(other+0),_mm256_add_epi64(a,v0));_mm256_storeu_si256((__m256i*)(dst+0),_mm256_sub_epi64(a,v0));}else _mm256_storeu_si256((__m256i*)(dst+0),v0);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+4));_mm256_storeu_si256((__m256i*)(other+4),_mm256_add_epi64(a,v1));_mm256_storeu_si256((__m256i*)(dst+4),_mm256_sub_epi64(a,v1));}else _mm256_storeu_si256((__m256i*)(dst+4),v1);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+8));_mm256_storeu_si256((__m256i*)(other+8),_mm256_add_epi64(a,v2));_mm256_storeu_si256((__m256i*)(dst+8),_mm256_sub_epi64(a,v2));}else _mm256_storeu_si256((__m256i*)(dst+8),v2);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+12));_mm256_storeu_si256((__m256i*)(other+12),_mm256_add_epi64(a,v3));_mm256_storeu_si256((__m256i*)(dst+12),_mm256_sub_epi64(a,v3));}else _mm256_storeu_si256((__m256i*)(dst+12),v3);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+16));_mm256_storeu_si256((__m256i*)(other+16),_mm256_add_epi64(a,v4));_mm256_storeu_si256((__m256i*)(dst+16),_mm256_sub_epi64(a,v4));}else _mm256_storeu_si256((__m256i*)(dst+16),v4);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+20));_mm256_storeu_si256((__m256i*)(other+20),_mm256_add_epi64(a,v5));_mm256_storeu_si256((__m256i*)(dst+20),_mm256_sub_epi64(a,v5));}else _mm256_storeu_si256((__m256i*)(dst+20),v5);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+24));_mm256_storeu_si256((__m256i*)(other+24),_mm256_add_epi64(a,v6));_mm256_storeu_si256((__m256i*)(dst+24),_mm256_sub_epi64(a,v6));}else _mm256_storeu_si256((__m256i*)(dst+24),v6);if constexpr(Merge){auto a=_mm256_loadu_si256((const __m256i*)(other+28));_mm256_storeu_si256((__m256i*)(other+28),_mm256_add_epi64(a,v7));_mm256_storeu_si256((__m256i*)(dst+28),_mm256_sub_epi64(a,v7));}else _mm256_storeu_si256((__m256i*)(dst+28),v7);}
inline void load_forward6(const u32*src,size_t n,u64*dst,size_t m){if(m<64){load_forward5(src,n,dst,m);return;}size_t j=0;for(;j+64<=n;j+=64){load_half6<false>(src+j,dst+j,nullptr);load_half6<true>(src+j+32,dst+j+32,dst+j);}if(j<n){for(unsigned r=0;r<64;r++)dst[j+r]=j+r<n?src[j+r]:0;leaf64_low5(dst+j,64);j+=64;}memset(dst+j,0,(m-j)*sizeof(u64));fwht64_after6(dst,m);}

inline void fwht64_from_u32(u64*f,const u32*in,size_t n,size_t nvalid,size_t base){
 if(base>=nvalid){ std::memset(f,0,n*8); return; }           

 if(n<=1024){load_forward6(in+base,std::min(n,nvalid-base),f,n);return;}
 if(n==2048){ size_t h=n/2;fwht64_from_u32(f,in,h,nvalid,base);fwht64_from_u32(f+h,in,h,nvalid,base+h);
  for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return; }
 const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_from_u32(f+r*q,in,q,nvalid,base+r*q);
 for(size_t j=0;j<q;j+=4){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+q+j)),c=_mm256_loadu_si256((const __m256i*)(f+2*q+j)),d=_mm256_loadu_si256((const __m256i*)(f+3*q+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
 }
}
inline void bm_merge4(u64*p0,u64*p1,u64*p2,u64*p3,size_t len){
 for(size_t j=0;j<len;j+=4){
  _mm_prefetch((const char*)(p0+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(p1+j+192),_MM_HINT_T0);
  _mm_prefetch((const char*)(p2+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(p3+j+192),_MM_HINT_T0);
  auto a=_mm256_loadu_si256((const __m256i*)(p0+j)),b=_mm256_loadu_si256((const __m256i*)(p1+j));
  auto c=_mm256_loadu_si256((const __m256i*)(p2+j)),d=_mm256_loadu_si256((const __m256i*)(p3+j));
  auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(p0+j),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(p1+j),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(p2+j),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(p3+j),_mm256_sub_epi64(ad,dd));
 }
}
inline void bm_hpiece(u64*f,const u32*in,size_t H,size_t nvalid,size_t base,size_t L,size_t PB){
 const size_t H2=L/2,h=H2/4;
 for(unsigned b=0;b<2;b++)for(unsigned half=0;half<2;half++)for(unsigned s=0;s<4;s++){
  fwht64_from_u32(f+s*h+half*H2+b*(L+PB),in,h,nvalid,base+s*h+half*H2+b*L);}
 constexpr size_t BW=64;alignas(64)u64 st[4][2][2][BW];
 for(size_t j0=0;j0<h;j0+=BW){
  for(unsigned b=0;b<2;b++)for(unsigned half=0;half<2;half++){const size_t o=half*H2+b*(L+PB)+j0;
   for(size_t jj=0;jj<BW;jj+=4){
    auto a=_mm256_loadu_si256((const __m256i*)(f+o+jj)),d=_mm256_loadu_si256((const __m256i*)(f+o+h+jj));
    auto c=_mm256_loadu_si256((const __m256i*)(f+o+2*h+jj)),e=_mm256_loadu_si256((const __m256i*)(f+o+3*h+jj));
    auto ad=_mm256_add_epi64(a,d),am=_mm256_sub_epi64(a,d),ce=_mm256_add_epi64(c,e),cm=_mm256_sub_epi64(c,e);
    _mm256_store_si256((__m256i*)(st[0][half][b]+jj),_mm256_add_epi64(ad,ce));
    _mm256_store_si256((__m256i*)(st[1][half][b]+jj),_mm256_add_epi64(am,cm));
    _mm256_store_si256((__m256i*)(st[2][half][b]+jj),_mm256_sub_epi64(ad,ce));
    _mm256_store_si256((__m256i*)(st[3][half][b]+jj),_mm256_sub_epi64(am,cm));}}
  for(unsigned s=0;s<4;s++){const size_t o=s*h+j0;
   for(size_t jj=0;jj<BW;jj+=4){
    auto a=_mm256_load_si256((const __m256i*)(st[s][0][0]+jj)),br=_mm256_load_si256((const __m256i*)(st[s][1][0]+jj));
    auto c=_mm256_load_si256((const __m256i*)(st[s][0][1]+jj)),d=_mm256_load_si256((const __m256i*)(st[s][1][1]+jj));
    auto ab=_mm256_add_epi64(a,br),ad=_mm256_sub_epi64(a,br),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
    _mm256_storeu_si256((__m256i*)(f+o+jj),_mm256_add_epi64(ab,cd));
    _mm256_storeu_si256((__m256i*)(f+o+jj+H2),_mm256_add_epi64(ad,dd));
    _mm256_storeu_si256((__m256i*)(f+o+jj+L+PB),_mm256_sub_epi64(ab,cd));
    _mm256_storeu_si256((__m256i*)(f+o+jj+L+PB+H2),_mm256_sub_epi64(ad,dd));}}
 }
}
inline void quarter_fwht_z3(u64*const seg[4],size_t q){
 for(unsigned s=0;s<3;++s)fwht64(seg[s],q);
 for(size_t i=0;i<q;i+=4){
  __m256i a=_mm256_loadu_si256((const __m256i*)(seg[0]+i)),b=_mm256_loadu_si256((const __m256i*)(seg[1]+i)),c=_mm256_loadu_si256((const __m256i*)(seg[2]+i));
  _mm_prefetch((const char*)(seg[0]+i+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+i+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+i+32),_MM_HINT_T0);
  __m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b);
  _mm256_storeu_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,c));_mm256_storeu_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,c));
  _mm256_storeu_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,c));_mm256_storeu_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,c));
 }
}
inline void quarter_merge_z3(u64*const seg[4],size_t q){

 for(size_t i=0;i<q;i+=4){
  __m256i a=_mm256_loadu_si256((const __m256i*)(seg[0]+i)),b=_mm256_loadu_si256((const __m256i*)(seg[1]+i)),c=_mm256_loadu_si256((const __m256i*)(seg[2]+i));
  _mm_prefetch((const char*)(seg[0]+i+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+i+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+i+32),_MM_HINT_T0);
  __m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b);
  _mm256_storeu_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,c));_mm256_storeu_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,c));
  _mm256_storeu_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,c));
 }
}
inline void quarter_fwht(u64*const seg[4],size_t q){
 for(unsigned s=0;s<4;++s)fwht64(seg[s],q);
 for(size_t i=0;i<q;i+=4){
  __m256i a=_mm256_loadu_si256((const __m256i*)(seg[0]+i)),b=_mm256_loadu_si256((const __m256i*)(seg[1]+i)),c=_mm256_loadu_si256((const __m256i*)(seg[2]+i)),d=_mm256_loadu_si256((const __m256i*)(seg[3]+i));
  __m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
  _mm256_storeu_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,dd));
  _mm256_storeu_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,dd));
 }
}
template<unsigned N,unsigned H> inline void form4(const u32*a,u64*const v[4]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32;
 for(size_t j=0;j<S;j+=4){
  __m256i z0=_mm256_setzero_si256(),z1=z0,z2=z0,z3=z0;
  #pragma GCC unroll 8
  for(unsigned t=0;t<8;++t){
   __m256i x[4];
   #pragma GCC unroll 4
   for(unsigned u=0;u<4;++u){size_t pos=(4*t+u)*S+j;
    if(pos+4<=N)x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(a+pos)));
    else if(pos>=N)x[u]=_mm256_setzero_si256();
    else{u32 tail[4]={};for(unsigned l=0;l<4&&pos+l<N;++l)tail[l]=a[pos+l];x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)tail));}
   }
   __m256i p=_mm256_add_epi64(x[0],x[1]),q=_mm256_sub_epi64(x[0],x[1]),r=_mm256_add_epi64(x[2],x[3]),s=_mm256_sub_epi64(x[2],x[3]);
   __m256i y0=_mm256_add_epi64(p,r),y1=_mm256_add_epi64(q,s),y2=_mm256_sub_epi64(p,r),y3=_mm256_sub_epi64(q,s);
   if(__builtin_parity(H&t)){z0=_mm256_sub_epi64(z0,y0);z1=_mm256_sub_epi64(z1,y1);z2=_mm256_sub_epi64(z2,y2);z3=_mm256_sub_epi64(z3,y3);}
   else{z0=_mm256_add_epi64(z0,y0);z1=_mm256_add_epi64(z1,y1);z2=_mm256_add_epi64(z2,y2);z3=_mm256_add_epi64(z3,y3);}
  }
  _mm256_storeu_si256((__m256i*)(v[0]+j),z0);_mm256_storeu_si256((__m256i*)(v[1]+j),z1);_mm256_storeu_si256((__m256i*)(v[2]+j),z2);_mm256_storeu_si256((__m256i*)(v[3]+j),z3);
 }
}
template<unsigned N,unsigned H> inline void process4(const u32*a,u64*const seg[4],u64*const v[4]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q=M/4;
 form4<N,H>(a,v);
 for(unsigned r=0;r<4;++r){const size_t off=(4*H+r)*S;u64*t=seg[off/Q]+off%Q;fwht64_multiply(v[r],t,S);}
}

template<unsigned K> inline void inv_top_pack(u64*f,size_t n,size_t count,u32*out){
 const size_t q=n/4;const __m256i pick=_mm256_setr_epi32(0,2,4,6,0,2,4,6);
 for(unsigned r=0;r<4;r++)fwht64_after5(f+r*q,q);
 for(size_t j=0;j<q;j+=8){
  _mm_prefetch((const char*)(f+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+192),_MM_HINT_T0);
  _mm_prefetch((const char*)(f+2*q+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+192),_MM_HINT_T0);
  auto a0=_mm256_load_si256((const __m256i*)(f+j)),a1=_mm256_load_si256((const __m256i*)(f+q+j));
  auto a2=_mm256_load_si256((const __m256i*)(f+2*q+j)),a3=_mm256_load_si256((const __m256i*)(f+3*q+j));
  auto c0=_mm256_load_si256((const __m256i*)(f+j+4)),c1=_mm256_load_si256((const __m256i*)(f+q+j+4));
  auto c2=_mm256_load_si256((const __m256i*)(f+2*q+j+4)),c3=_mm256_load_si256((const __m256i*)(f+3*q+j+4));
  auto ab0=_mm256_add_epi64(a0,a1),ad0=_mm256_sub_epi64(a0,a1),cd0=_mm256_add_epi64(a2,a3),dd0=_mm256_sub_epi64(a2,a3);
  auto ab1=_mm256_add_epi64(c0,c1),ad1=_mm256_sub_epi64(c0,c1),cd1=_mm256_add_epi64(c2,c3),dd1=_mm256_sub_epi64(c2,c3);
  {auto v0=_mm256_add_epi64(ab0,cd0),v1=_mm256_add_epi64(ab1,cd1);
   if(j<count){auto pa=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(v0,K),pick),pb=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(v1,K),pick);
    _mm256_stream_si256((__m256i*)(out+j),_mm256_inserti128_si256(_mm256_castsi128_si256(_mm256_castsi256_si128(pa)),_mm256_castsi256_si128(pb),1));}
   if(2*q+j<count){auto w0=_mm256_sub_epi64(ab0,cd0),w1=_mm256_sub_epi64(ab1,cd1);auto pa=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(w0,K),pick),pb=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(w1,K),pick);
    _mm256_stream_si256((__m256i*)(out+2*q+j),_mm256_inserti128_si256(_mm256_castsi128_si256(_mm256_castsi256_si128(pa)),_mm256_castsi256_si128(pb),1));}}
  {auto v0=_mm256_add_epi64(ad0,dd0),v1=_mm256_add_epi64(ad1,dd1);
   if(q+j<count){auto pa=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(v0,K),pick),pb=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(v1,K),pick);
    _mm256_stream_si256((__m256i*)(out+q+j),_mm256_inserti128_si256(_mm256_castsi128_si256(_mm256_castsi256_si128(pa)),_mm256_castsi256_si128(pb),1));}
   if(3*q+j<count){auto w0=_mm256_sub_epi64(ad0,dd0),w1=_mm256_sub_epi64(ad1,dd1);auto pa=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(w0,K),pick),pb=_mm256_permutevar8x32_epi32(_mm256_srli_epi64(w1,K),pick);
    _mm256_stream_si256((__m256i*)(out+3*q+j),_mm256_inserti128_si256(_mm256_castsi128_si256(_mm256_castsi256_si128(pa)),_mm256_castsi256_si128(pb),1));}}
 }
}
template<unsigned N,unsigned K>inline void quarter_finish_output_original(u64*const seg[4],u32*c){constexpr size_t M=size_t(1)<<K,S=M/4,H=S/2;static_assert(N<=3*S,"last quarter unused");
for(size_t j=0;j<H;j+=4){
 _mm_prefetch((const char*)(seg[0]+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[3]+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[0]+H+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+H+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+H+j+192),_MM_HINT_T0);_mm_prefetch((const char*)(seg[3]+H+j+192),_MM_HINT_T0);
auto a0=_mm256_load_si256((const __m256i*)(seg[0]+j)),a1=_mm256_load_si256((const __m256i*)(seg[1]+j)),a2=_mm256_load_si256((const __m256i*)(seg[2]+j)),a3=_mm256_load_si256((const __m256i*)(seg[3]+j));
 auto ab=_mm256_add_epi64(a0,a1),ad=_mm256_sub_epi64(a0,a1),cd=_mm256_add_epi64(a2,a3),dd=_mm256_sub_epi64(a2,a3);
 auto x0=_mm256_add_epi64(ab,cd),x1=_mm256_add_epi64(ad,dd),x2=_mm256_sub_epi64(ab,cd);
 auto b0=_mm256_load_si256((const __m256i*)(seg[0]+H+j)),b1=_mm256_load_si256((const __m256i*)(seg[1]+H+j)),b2=_mm256_load_si256((const __m256i*)(seg[2]+H+j)),b3=_mm256_load_si256((const __m256i*)(seg[3]+H+j));
 auto ba=_mm256_add_epi64(b0,b1),bd=_mm256_sub_epi64(b0,b1),bc=_mm256_add_epi64(b2,b3),be=_mm256_sub_epi64(b2,b3);
 auto y0=_mm256_add_epi64(ba,bc),y1=_mm256_add_epi64(bd,be),y2=_mm256_sub_epi64(ba,bc);
 _mm256_store_si256((__m256i*)(seg[0]+j),_mm256_add_epi64(x0,y0));_mm256_store_si256((__m256i*)(seg[0]+H+j),_mm256_sub_epi64(x0,y0));
 _mm256_store_si256((__m256i*)(seg[1]+j),_mm256_add_epi64(x1,y1));_mm256_store_si256((__m256i*)(seg[1]+H+j),_mm256_sub_epi64(x1,y1));
 if constexpr(N>2*S)_mm256_store_si256((__m256i*)(seg[2]+j),_mm256_add_epi64(x2,y2));
 if constexpr(N>2*S+H)_mm256_store_si256((__m256i*)(seg[2]+H+j),_mm256_sub_epi64(x2,y2));
}
inv_top_pack<K>(seg[0],H,N>0?std::min(size_t(N),H):0,c);if(N>H)inv_top_pack<K>(seg[0]+H,H,std::min(size_t(N)-H,H),c+H);inv_top_pack<K>(seg[1],H,N>S?std::min(size_t(N)-S,H):0,c+S);if(N>S+H)inv_top_pack<K>(seg[1]+H,H,std::min(size_t(N)-S-H,H),c+S+H);inv_top_pack<K>(seg[2],H,N>2*S?std::min(size_t(N)-2*S,H):0,c+2*S);if(N>2*S+H)inv_top_pack<K>(seg[2]+H,H,std::min(size_t(N)-2*S-H,H),c+2*S+H);
_mm_sfence();}

static inline __attribute__((always_inline))__m256i sxpack(__m256i lo,__m256i hi){return _mm256_permute4x64_epi64(_mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(lo),_mm256_castsi256_ps(hi),0x88)),0xd8);}
template<unsigned N,unsigned K>inline void quarter_finish_output(u64*const seg[4],u32*c){
if constexpr(N!=100000000u){quarter_finish_output_original<N,K>(seg,c);return;}else{
 constexpr size_t M=size_t(1)<<K,S=M/4,L=S/8,Q=L/4,PB8=4104;
 
 auto ar_finish_plane=[&](auto tag){constexpr unsigned plane=decltype(tag)::value;
  u64*f=seg[plane];
  for(unsigned row=0;row<8;row++)for(unsigned arm=0;arm<4;arm++)fwht64_after5(f+row*(L+PB8)+arm*Q,Q);
  for(size_t j=0;j<Q;j+=128){alignas(64)u64 tile[4][8][128];
   for(unsigned row=0;row<8;row++){
    #pragma GCC unroll 2
    for(unsigned h=0;h<32;h++){
     const u64*p=f+row*(L+PB8)+j+4*h;
     auto a=_mm256_load_si256((const __m256i*)p),b=_mm256_load_si256((const __m256i*)(p+Q)),cc=_mm256_load_si256((const __m256i*)(p+2*Q)),d=_mm256_load_si256((const __m256i*)(p+3*Q));
     auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(cc,d),dd=_mm256_sub_epi64(cc,d);
     _mm256_store_si256((__m256i*)(tile[0][row]+4*h),_mm256_add_epi64(ab,cd));
     _mm256_store_si256((__m256i*)(tile[1][row]+4*h),_mm256_add_epi64(ad,dd));
     _mm256_store_si256((__m256i*)(tile[2][row]+4*h),_mm256_sub_epi64(ab,cd));
     _mm256_store_si256((__m256i*)(tile[3][row]+4*h),_mm256_sub_epi64(ad,dd));
    }
   }
   for(unsigned arm=0;arm<4;arm++){
    for(unsigned g=0;g<8;g++){__m256i parts[8][4];
    #pragma GCC unroll 2
    for(unsigned k=0;k<4;k++){__m256i v[8];
     #pragma GCC unroll 8
     for(unsigned row=0;row<8;row++)v[row]=_mm256_load_si256((const __m256i*)(tile[arm][row]+16*g+4*k));
     #pragma GCC unroll 3
     for(unsigned bit=0;bit<3;bit++){
      #pragma GCC unroll 8
      for(unsigned row=0;row<8;row++)if(!(row&(1u<<bit))){auto a=v[row],b=v[row+(1u<<bit)];v[row]=_mm256_add_epi64(a,b);v[row+(1u<<bit)]=_mm256_sub_epi64(a,b);}
     }
     #pragma GCC unroll 8
     for(unsigned row=0;row<8;row++){
      parts[row][k]=_mm256_srli_epi64(v[row],K);
     }
    }
    #pragma GCC unroll 8
    for(unsigned row=0;row<8;row++){size_t off=plane*S+row*L+arm*Q+j+16*g;if(plane<2||row<7||arm<3||off<size_t(N)){
     _mm256_stream_si256((__m256i*)(c+off),sxpack(parts[row][0],parts[row][1]));
     _mm256_stream_si256((__m256i*)(c+off+8),sxpack(parts[row][2],parts[row][3]));
    }}
   }}
  }
 };ar_finish_plane(std::integral_constant<unsigned,0>{});ar_finish_plane(std::integral_constant<unsigned,1>{});ar_finish_plane(std::integral_constant<unsigned,2>{});
 _mm_sfence();
}}







template<unsigned N> inline void form8_3(const u32*a,u64*const*vv[3]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32;
 constexpr size_t T=64,LP=T+8,Q4=S/4,PDF=(N==100000000u)?4096:0;alignas(64)u64 tile[3][8][LP];
 alignas(64)u32 raw[32][264];static_assert(S%(4*T)==0,"complete four-block batches");
 for(size_t at=0;at<S;at+=4*T){for(unsigned stream=0;stream<(24*S>=N?24u:32u);stream++){
#pragma GCC unroll 4
 for(size_t block=at;block<at+4*T;block+=64){size_t pos=stream*S+block;
 if(pos+64<=N){asm volatile("vmovdqu 0(%[src]),%%ymm0\n\tvmovdqu 32(%[src]),%%ymm1\n\tvmovdqu 64(%[src]),%%ymm2\n\tvmovdqu 96(%[src]),%%ymm3\n\tvmovdqu 128(%[src]),%%ymm4\n\tvmovdqu 160(%[src]),%%ymm5\n\tvmovdqu 192(%[src]),%%ymm6\n\tvmovdqu 224(%[src]),%%ymm7\n\tvmovdqu %%ymm0,0(%[dst])\n\tvmovdqu %%ymm1,32(%[dst])\n\tvmovdqu %%ymm2,64(%[dst])\n\tvmovdqu %%ymm3,96(%[dst])\n\tvmovdqu %%ymm4,128(%[dst])\n\tvmovdqu %%ymm5,160(%[dst])\n\tvmovdqu %%ymm6,192(%[dst])\n\tvmovdqu %%ymm7,224(%[dst])":"=m"(*(unsigned char(*)[256])(raw[stream]+(block-at))):[src]"r"(a+pos),[dst]"r"(raw[stream]+(block-at)),[input]"m"(*(const unsigned char(*)[256])(a+pos)):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7");}
 else for(unsigned z=0;z<64;z++)raw[stream][(block-at)+z]=pos+z<N?a[pos+z]:0;
 }
 
 }
 for(unsigned blk=0;blk<4;blk++){const size_t bs=at+blk*64;for(size_t j=bs;j<bs+64;j+=4){__m256i W[2][3][4];
#pragma GCC unroll 2
 for(unsigned low=0;low<2;low++){
  __m256i X[3][4];
#pragma GCC unroll 4
  for(unsigned u=0;u<4;u++){__m256i L[4];
#pragma GCC unroll 4
   for(unsigned z=0;z<4;z++){unsigned t=low+2*z;__m256i q;if constexpr(24*S>=N){if(z==3)q=_mm256_setzero_si256();else q=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(raw[4*t+u]+(j-at))));}else q=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(raw[4*t+u]+(j-at))));
    L[z]=q;}
   __m256i e0=_mm256_add_epi64(L[0],L[1]),e1=_mm256_sub_epi64(L[0],L[1]),e2=_mm256_add_epi64(L[2],L[3]),e3=_mm256_sub_epi64(L[2],L[3]);
   __m256i s0=_mm256_add_epi64(e0,e2),s1=_mm256_add_epi64(e1,e3),s2=_mm256_sub_epi64(e0,e2),s3=_mm256_sub_epi64(e1,e3);
   X[0][u]=s0;X[1][u]=s1;X[2][u]=s2;}
#pragma GCC unroll 4
  for(unsigned p=0;p<3;p++){
   __m256i A=_mm256_add_epi64(X[p][0],X[p][1]),B=_mm256_sub_epi64(X[p][0],X[p][1]),C=_mm256_add_epi64(X[p][2],X[p][3]),D=_mm256_sub_epi64(X[p][2],X[p][3]);
   W[low][p][0]=_mm256_add_epi64(A,C);W[low][p][1]=_mm256_add_epi64(B,D);W[low][p][2]=_mm256_sub_epi64(A,C);W[low][p][3]=_mm256_sub_epi64(B,D);}
 }
#pragma GCC unroll 4
 for(unsigned p=0;p<3;p++){u64*const*v=vv[p];
#pragma GCC unroll 4
  for(unsigned u=0;u<4;u++){_mm256_store_si256((__m256i*)(tile[p][u]+(j-bs)),_mm256_add_epi64(W[0][p][u],W[1][p][u]));_mm256_store_si256((__m256i*)(tile[p][4+u]+(j-bs)),_mm256_sub_epi64(W[0][p][u],W[1][p][u]));}}
 }
for(unsigned p=0;p<3;p++){u64*const*v=vv[p];const size_t pa=(bs/Q4)*(Q4+PDF)+(bs%Q4);for(unsigned r=0;r<8;r++){leaf64_low5(tile[p][r],T);for(size_t j=0;j<T;j+=4)_mm256_stream_si256((__m256i*)(v[r]+pa+j),_mm256_load_si256((const __m256i*)(tile[p][r]+j)));}}
 }
 }
 _mm_sfence();
}
template<unsigned N>inline void process8_3(const u32*a,u64*const seg[4],u64*const*vv[3]){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q4=S/4,PDF=(N==100000000u)?4096:0,PB8=(N==100000000u)?4104:0,QF=Q4+PDF;
static_assert(N<=24*S&&Q4%32==0&&S>=4096,"three-character joint products");form8_3<N>(a,vv);
for(unsigned r=0;r<8;r++){
for(unsigned p=0;p<3;p++)for(unsigned z=0;z<4;z++)fwht64_after6(vv[p][r]+z*QF,Q4);
u64*tp[4];for(unsigned p=0;p<4;p++){const unsigned H=(r<4)?2*p:2*p+1,bi=4*H+(r&3);tp[p]=seg[bi>>3]+(bi&7)*(S+PB8);}
for(size_t j=0;j<Q4;j+=32){alignas(64)u64 prod[N==100000000u?3:4][4][32];
if constexpr(N==100000000u){for(unsigned u=0;u<8;u++){size_t i=j+4*u;__m256i w[3][4];
#pragma GCC unroll 3
for(unsigned p=0;p<3;p++){const u64*f=vv[p][r];auto a=_mm256_load_si256((const __m256i*)(f+i)),b=_mm256_load_si256((const __m256i*)(f+QF+i)),c=_mm256_load_si256((const __m256i*)(f+2*QF+i)),d=_mm256_load_si256((const __m256i*)(f+3*QF+i));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);w[p][0]=_mm256_add_epi64(ab,cd);w[p][1]=_mm256_add_epi64(ad,dd);w[p][2]=_mm256_sub_epi64(ab,cd);w[p][3]=_mm256_sub_epi64(ad,dd);
}
#pragma GCC unroll 4
for(unsigned z=0;z<4;z++){
 auto b0=_mm256_load_si256((const __m256i*)(tp[0]+z*Q4+i));
 auto b1=_mm256_load_si256((const __m256i*)(tp[1]+z*Q4+i));
 auto b2=_mm256_load_si256((const __m256i*)(tp[2]+z*Q4+i));
 auto a3=_mm256_sub_epi64(_mm256_add_epi64(w[1][z],w[2][z]),w[0][z]);
 auto b3=_mm256_sub_epi64(_mm256_add_epi64(b1,b2),b0);
 auto p0=mul64(w[0][z],b0),p1=mul64(w[1][z],b1);
 auto p2=mul64(w[2][z],b2),p3=mul64(a3,b3);
 auto ab=_mm256_add_epi64(p0,p1),ad=_mm256_sub_epi64(p0,p1);
 auto cd=_mm256_add_epi64(p2,p3),dd=_mm256_sub_epi64(p2,p3);
 _mm256_store_si256((__m256i*)(prod[0][z]+4*u),_mm256_add_epi64(ab,cd));
 _mm256_store_si256((__m256i*)(prod[1][z]+4*u),_mm256_add_epi64(ad,dd));
 _mm256_store_si256((__m256i*)(prod[2][z]+4*u),_mm256_sub_epi64(ab,cd));
}}
}else{for(unsigned u=0;u<8;u++){size_t i=j+4*u;__m256i w[3][4];
#pragma GCC unroll 3
for(unsigned p=0;p<3;p++){const u64*f=vv[p][r];auto a=_mm256_load_si256((const __m256i*)(f+i)),b=_mm256_load_si256((const __m256i*)(f+QF+i)),c=_mm256_load_si256((const __m256i*)(f+2*QF+i)),d=_mm256_load_si256((const __m256i*)(f+3*QF+i));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);w[p][0]=_mm256_add_epi64(ab,cd);w[p][1]=_mm256_add_epi64(ad,dd);w[p][2]=_mm256_sub_epi64(ab,cd);w[p][3]=_mm256_sub_epi64(ad,dd);
#pragma GCC unroll 4
for(unsigned z=0;z<4;z++)_mm256_store_si256((__m256i*)(prod[p][z]+4*u),mul64(_mm256_load_si256((const __m256i*)(tp[p]+z*Q4+i)),w[p][z]));}
#pragma GCC unroll 4
for(unsigned z=0;z<4;z++){auto fourth=_mm256_sub_epi64(_mm256_add_epi64(w[1][z],w[2][z]),w[0][z]);_mm256_store_si256((__m256i*)(prod[3][z]+4*u),mul64(_mm256_sub_epi64(_mm256_add_epi64(_mm256_load_si256((const __m256i*)(tp[1]+z*Q4+i)),_mm256_load_si256((const __m256i*)(tp[2]+z*Q4+i))),_mm256_load_si256((const __m256i*)(tp[0]+z*Q4+i))),fourth));}}
}

for(unsigned p=0;p<(N==100000000u?3:4);p++)for(unsigned z=0;z<4;z++)leaf32_to(prod[p][z],tp[p]+z*Q4+j);
}}
_mm_sfence();
}
template<unsigned N,unsigned H0,unsigned H1> inline void form8(const u32*a,u64*const v[8]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32;static_assert(!(H0&1)&&H1==H0+1,"adjacent character pair");
 for(size_t j=0;j<S;j+=4){__m256i w[2][4];
#pragma GCC unroll 2
 for(unsigned low=0;low<2;low++){
 __m256i x[4];
#pragma GCC unroll 4
 for(unsigned u=0;u<4;u++){__m256i sum=_mm256_setzero_si256();
#pragma GCC unroll 4
 for(unsigned z=0;z<4;z++){unsigned t=low+2*z;size_t pos=(4*t+u)*S+j;__m256i q;if(pos+4<=N)q=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(a+pos)));else if(pos>=N)q=_mm256_setzero_si256();else{u32 tail[4]={};for(unsigned r=0;r<4&&pos+r<N;r++)tail[r]=a[pos+r];q=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)tail));}if(__builtin_parity(H0&t))sum=_mm256_sub_epi64(sum,q);else sum=_mm256_add_epi64(sum,q);}
 x[u]=sum;}
 __m256i p=_mm256_add_epi64(x[0],x[1]),q=_mm256_sub_epi64(x[0],x[1]),r=_mm256_add_epi64(x[2],x[3]),z=_mm256_sub_epi64(x[2],x[3]);w[low][0]=_mm256_add_epi64(p,r);w[low][1]=_mm256_add_epi64(q,z);w[low][2]=_mm256_sub_epi64(p,r);w[low][3]=_mm256_sub_epi64(q,z);}
#pragma GCC unroll 4
 for(unsigned u=0;u<4;u++){_mm256_storeu_si256((__m256i*)(v[u]+j),_mm256_add_epi64(w[0][u],w[1][u]));_mm256_storeu_si256((__m256i*)(v[4+u]+j),_mm256_sub_epi64(w[0][u],w[1][u]));}
 }
}

template<unsigned N,unsigned H0,unsigned H1> inline void process8(const u32*a,u64*const seg[4],u64*const v[8]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q=M/4;
 form8<N,H0,H1>(a,v);
 #pragma GCC unroll 8
 for(unsigned r=0;r<8;++r){const unsigned H=(r<4)?H0:H1;const size_t off=(4*H+(r&3))*S;u64*t=seg[off/Q]+off%Q;fwht64_multiply(v[r],t,S);}
}
template<unsigned N>static void ar_b_root(u64*const seg[4],const unsigned*in,size_t Q,size_t L,size_t PB){const size_t H=Q/64;constexpr unsigned BW=128;alignas(64)u64 v[3][64][BW+8];
for(unsigned r=0;r<3;r++)for(unsigned t=0;t<64;t++){size_t z=t*H;fwht64_from_u32(seg[r]+z+(z/L)*PB,in,H,N,r*Q+z);}
for(size_t j0=0;j0<H;j0+=BW){
for(unsigned t=0;t<64;t+=4){const u64*p[3][4];for(unsigned r=0;r<3;r++)for(unsigned k=0;k<4;k++){size_t z=(t+k)*H+j0;p[r][k]=seg[r]+z+(z/L)*PB;}
for(unsigned j=0;j<BW;j+=4){__m256i x[3][4];
#pragma GCC unroll 3
for(unsigned r=0;r<3;r++){auto a=_mm256_load_si256((const __m256i*)(p[r][0]+j)),b=_mm256_load_si256((const __m256i*)(p[r][1]+j)),c=_mm256_load_si256((const __m256i*)(p[r][2]+j)),d=_mm256_load_si256((const __m256i*)(p[r][3]+j));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);x[r][0]=_mm256_add_epi64(ab,cd);x[r][1]=_mm256_add_epi64(ad,dd);x[r][2]=_mm256_sub_epi64(ab,cd);x[r][3]=_mm256_sub_epi64(ad,dd);}
#pragma GCC unroll 4
for(unsigned k=0;k<4;k++){auto a=x[0][k],b=x[1][k],c=x[2][k],ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b);_mm256_store_si256((__m256i*)(v[0][t+k]+j),_mm256_add_epi64(ab,c));_mm256_store_si256((__m256i*)(v[1][t+k]+j),_mm256_add_epi64(ad,c));_mm256_store_si256((__m256i*)(v[2][t+k]+j),_mm256_sub_epi64(ab,c));}}}
for(unsigned r=0;r<3;r++)for(unsigned h=4;h<64;h*=4)for(unsigned q=0;q<64;q+=4*h)for(unsigned k=0;k<h;k++)for(unsigned j=0;j<BW;j+=4){auto a=_mm256_load_si256((const __m256i*)(v[r][q+k]+j)),b=_mm256_load_si256((const __m256i*)(v[r][q+h+k]+j)),c=_mm256_load_si256((const __m256i*)(v[r][q+2*h+k]+j)),d=_mm256_load_si256((const __m256i*)(v[r][q+3*h+k]+j));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
if(h==4){_mm256_store_si256((__m256i*)(v[r][q+k]+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(v[r][q+h+k]+j),_mm256_add_epi64(ad,dd));_mm256_store_si256((__m256i*)(v[r][q+2*h+k]+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(v[r][q+3*h+k]+j),_mm256_sub_epi64(ad,dd));}else{
size_t z0=(q+k)*H+j0,z1=(q+h+k)*H+j0,z2=(q+2*h+k)*H+j0,z3=(q+3*h+k)*H+j0;_mm256_stream_si256((__m256i*)(seg[r]+z0+(z0/L)*PB+j),_mm256_add_epi64(ab,cd));_mm256_stream_si256((__m256i*)(seg[r]+z1+(z1/L)*PB+j),_mm256_add_epi64(ad,dd));_mm256_stream_si256((__m256i*)(seg[r]+z2+(z2/L)*PB+j),_mm256_sub_epi64(ab,cd));_mm256_stream_si256((__m256i*)(seg[r]+z3+(z3/L)*PB+j),_mm256_sub_epi64(ad,dd));}}}
_mm_sfence();}
template<unsigned N> inline void xor_stream(const unsigned*a,const unsigned*b,unsigned*c){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),Q=M/4,S=M/32;constexpr unsigned K=32-__builtin_clz(N-1);
 constexpr size_t PDF=(N==100000000u)?4096:0;static_assert(size_t(N)*4>=(8*(S+3*PDF)+7*4104)*8,"output accommodates every temporary character block");
 constexpr size_t PBK=(N==100000000u)?4104:0;
 constexpr size_t QSTEP=8*(S+PBK)+4096;
 alignas(2097152)static u64 arena[4*QSTEP+256];u64*heap=arena+192;
 u64*seg[4]={heap,heap+QSTEP,heap+2*QSTEP,heap+3*QSTEP};
 u64*v[8];for(unsigned r=0;r<8;r++)v[r]=(u64*)c+r*(S+3*PDF+4104);
 {constexpr bool z3 = 3*Q >= size_t(N);
  if constexpr(z3){if constexpr(N==100000000u)ar_b_root<N>(seg,b,Q,S,PBK);else{for(unsigned r=0;r<3;r++)fwht64_from_u32(seg[r],b,Q,N,r*Q);quarter_merge_z3(seg,Q);}}
  else{for(unsigned r=0;r<4;r++)for(size_t j=0;j<Q;j++){size_t i=r*Q+j;seg[r][j]=i<N?b[i]:0;}quarter_fwht(seg,Q);}
 }
 alignas(2097152)static u64 v1buf[8*(S+3*PDF+4104)+262152];u64*w[8];{const size_t cph=(((size_t)(void*)c)>>3)&((size_t(1)<<18)-1);const size_t dw=((cph+4088)&((((size_t(1)<<18)-1))&~size_t(3)));for(unsigned r=0;r<8;r++)w[r]=v1buf+8+dw+r*(S+3*PDF+4104);}
 alignas(2097152)static u64 extra[8*(S+3*PDF+4104)+262160];u64*v2[8];{const size_t cph=(((size_t)(void*)c)>>3)&((size_t(1)<<18)-1);const size_t dv=((cph+8176)&((((size_t(1)<<18)-1))&~size_t(3)));for(unsigned r=0;r<8;r++)v2[r]=extra+16+dv+r*(S+3*PDF+4104);}u64*const*vv[3]={v,w,v2};process8_3<N>(a,seg,vv);
 quarter_finish_output<N,K>(seg,c);

}
}

template<unsigned FixedN>static void ar_entry(unsigned input_n,const unsigned*a,const unsigned*b,unsigned*c){const unsigned n=FixedN?FixedN:input_n;if(n==100000000u)bitconv::xor_stream<100000000u>(a,b,c);else if(n==6250000u)bitconv::xor_stream<6250000u>(a,b,c);else bitconv::xor_small(n,a,b,c);}

void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){if(n==100000000u){ar_entry<100000000u>(n,a,b,c);return;}if(!n)return;
 size_t m=1;unsigned k=0;while(m<n){m*=2;k++;}uint64_t*x=(uint64_t*)std::calloc(m,8),*y=(uint64_t*)std::calloc(m,8);
 for(unsigned i=0;i<n;i++){x[i]=a[i];y[i]=b[i];}auto w=[&](uint64_t*v){for(size_t h=1;h<m;h*=2)for(size_t g=0;g<m;g+=2*h)for(size_t j=0;j<h;j++){auto a=v[g+j],b=v[g+j+h];v[g+j]=a+b;v[g+j+h]=a-b;}};
 w(x);w(y);for(size_t j=0;j<m;j++)x[j]*=y[j];w(x);for(unsigned j=0;j<n;j++)c[j]=unsigned(x[j]>>k);std::free(x);std::free(y);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.141 s1661 MB + 1020 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-19 09:41:17 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠