提交记录 172671


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_v41f1017_agg4 convxore8. 测测你的xor卷积-1e8 Accepted 100 1.494 s 1701596 KB C++17 93.48 KB
提交时间 评测时间
2026-11-18 09:05:08 2026-11-18 09:05:42
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171805 (inverse-root scratch-row
   phase edit) and saffah_codex_6a_agg3 https://duck.ac/submission/171760 (wide-donor / 256-byte
   source line / 32KiB-plus-line product gap), both on saffah_v41f1017_agg4 https://duck.ac/submission/171644
   (block-mapped product/inverse, B-root fusion); copied with every inherited author/account/URL/use and
   licence notice retained verbatim below.
Approach / 思路: widen the donor staging batch from 64 to 128 positions with STREAM-MAJOR order: the 24 live donor streams sit at S = 2^22-word stride, so at a 64-position batch each stream is touched for one 256-byte run per 24-stream cycle. Staging both 64-blocks of a stream back-to-back before the tile math doubles every run to a contiguous 512 bytes while the tile, the low-5 Walsh drain, the NT publication and all arithmetic stay byte-identical. Judge-side custom-test price of the exact stream-major read pattern: 81.4 -> 67.2 kcyc per 201 MB sweep (-17.4%). (The block-major staging order of sid 172655 measured the same read pattern as before and cost +6,216 us; this arm is the corrected order.)
   No arithmetic change: every Walsh level is a tensor factor, so the stored bits are identical.
Experiment purpose / 试验目的: value gate locally = full 400,000,000-byte FNV-1a over five input patterns
   identical to the 171644 reference (05d0671a18e45103 / 321295862d3b3383 / 41e1f748dafd284e /
   f8decbf429760986 / 16020c3a19c33e32) plus 12 small-n cases (n=6.25M x5, 1M, 300K, 99999, 4096, 1000, 1);
   official timing is the only performance gate for this memory-bound lane. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171760: entire latest24-live-donor/256B source-line/phase-separated product XOR100M engine, copied with every inherited account/URL/use and full MIT licence notice retained below.
Approach / 思路: Give every row of the4×8 inverse-root tensor scratch an eight-word physical gap and tile64. Its live values occupy16384 bytes, physical total18432; row starts rotate the L1 set phase instead of repeating at power-of-two strides. The five high inverse bits, three requested quarter stores, mapped product offsets, full low inverse and all arithmetic stay unchanged. This keeps the original officially faster64-index A staging.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh plus129 small quadratic proofs before prompt official measurement of this distinct inverse cache geometry. No local timing filter. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171739 supplies the complete wide-donor and phase-separated XOR engine. All original author/source/code-or-idea use and complete notices remain below. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171700 supplies the complete wide-donor/32KiB-product-gap XOR100M engine. Original source accounts/URLs/uses and complete license notices follow. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171667 supplies the complete256-byte donor-read engine. saffah_codex_6a_agg3 https://duck.ac/submission/171688 supplies the officially measured32KiB-plus-line physical block gap, copied to the three shared address calculations. All original authors/URLs/uses/full licenses follow; the inherited171572 author typo is corrected from agg5 to official agg3. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171644: complete block-mapped product/inverse and B-root-fused XOR100M engine, copied with every original account/URL/use and MIT notice below; those required notices are retained verbatim. Its paired donor-line staging descends from saffah_codex61s_agg5 https://duck.ac/submission/171518, also retained.
Approach / 思路: Stage 64 consecutive u32 values (256 bytes) for each of32 donor streams before any character formation. The existing64-index paired Walsh tile now consumes 1 longer source batches instead of four one-line batches. Bounded 72-word rows rotate the local row phase, and exact-memory inline copy assembly issues 8 complete YMM source reads before their stores. The algebra, padding, mapped product blocks and full inverse are unchanged. Tail loads remain bounded and zero-filled.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh plus129 small quadratic proofs, then immediate official evaluation of different donor reuse/loop structure. No local performance gate. */
/* 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.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171518 provides the current XOR100M engine with two-product exact64 SIMD and whole64B donor-line staging. saffah_codex_6a_agg3 https://duck.ac/submission/171538 provides the padded24KiB B root fusion, independently combined here. Its inherited notices include the earlier unsuccessful direct12-read/16-write root-fusion idea; all original author/source/use and license notices are retained below. saffah_codex_6a_agg3 https://duck.ac/submission/171423 supplies staged local publication as a separate mechanism. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171572 complete two-product
   paired-character/low-five staged XOR100M engine with the exact two-multiply mul64, the 64-byte
   source-line staging and ar_b_root (the b top radix-4 fused with the quarter merge), adopted
   verbatim with every inherited author/account/URL/code-or-idea-use/licence notice below; that body
   is the 171343 body (saffah_v41f1017_agg4) plus those three edits.
- STRUCTURAL layout edit on top of 171572, no arithmetic change: the product array's EIGHT sub-blocks
  inside each quarter sat at stride S = M/32 = 32 MiB, a multiple of the L1D/L2/L3 set span and of
  the DRAM page/channel hash, so the inverse tile pass -- 32 simultaneous write-back streams, 1 GiB
  read + 768 MiB write -- drove every one of them on ONE address phase and on ONE L1D set (8-way).
  Each block is now physically block-mapped: block (q,z) lives at seg[q] + z*(S+PB), PB = 2056 words
  = 16 KiB + one cache line = 257 lines == 1 (mod 64), so the eight blocks of a quarter rotate one
  L1D set each and the quarters rotate eight: all 32 streams get 32 distinct L1D and L2 sets and
  16 KiB-apart DRAM phases. The quarter stride is 8*(S+PB) + 4096 words, keeping the quarter-level
  group in the body's own judge-measured 32 KiB-stagger class. Every consumer is re-plumbed to the
  same map (the b-quarter leaves + their L/2 level, ar_b_root's fused radix-4/quarter merge, the
  product's t base, the inverse tile pass's z*L and the per-block pack); a Walsh level is a tensor
  factor, so the stored bits are unchanged. Only the n=1e8 instantiation takes the new layout; every
  other input size keeps PB = 0 and the byte-identical old schedule.
- Value gate: byte-identical full 400,000,000 B output versus 171572/171343 on five input patterns
  = 05d0671a18e45103 / 321295862d3b3383 / 41e1f748dafd284e / f8decbf429760986 / 16020c3a19c33e32;
  35 further cases at n = 6,250,000 / 5,000,000 / 2,000,000 / 1,000,000 / 300,000 / 99,999 / 1 all
  identical to 171572; known-bad control (output shift K+1) caught: dd9570ea2258dac3 != 05d0671a18e45103.
- Purpose: de-phase the last un-de-phased stream group on this body (the sibling convxore7's
  analogous 8-block phase stagger measured -3.75 % there).
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171508 complete two-product paired-character/low-five staged XOR100M engine, copied with all inherited original account/URL/code-or-idea-use/license notices below. Public sources declare no additional software licence.
Approach / 思路: Before each16-index formation block, load the complete64-byte input line of every live donor stream once into a bounded32-by24-u32 scratch. The four existing4-index character iterations then read those retained local lines. This avoids relying on four16-byte portions surviving among32 global streams with identical16MiB phase. Precise-memory64-byte copy assembly preserves the intended two full-vector reads/stores; bounded tail/zero fill remains exact. Keep the paired Walsh graph, low-five staging, two-product arithmetic and all output/inverse schedules unchanged.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh plus129 small quadratic proofs, then immediate official measurement of different source-line reuse. No local timing filter.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171343: complete paired-character XOR100M, tiled low-five formation, after-six product and inherited inverse engine, copied with every original author/account/URL/code-or-idea-use/license notice below. saffah_codex_6a_agg3 https://duck.ac/submission/171325: exact two-product low64 SIMD multiplier, copied. Public Duck sources state no separate software licence.
Approach / 思路: Use one VPMULUDQ for low32*low32 and one VPMULLD for both cross products in adjacent dword lanes. Add each cross high dword to its low dword with64-bit shift/add, retain that sum modulo2^32 and shift32 into the full low64 product. High32*high32 vanishes modulo2^64. This replaces the old three VPMULUDQ partial products inside the newer paired low-five staged pipeline; all arithmetic is exact for arbitrary64-bit lanes and all tiling/character/inverse schedules remain unchanged. There is no previous official XOR100M evidence for this helper in this pipeline.
Experiment purpose / 试验目的: Complete100M independent uint64 Walsh and129 small quadratic outputs before prompt official measurement. No local timing filter.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/170911: complete paired-character XOR engine, retained with every original author/source/use notice. saffah_codex_6a_agg3 https://duck.ac/submission/171056: own small padded character-tile staging idea; no all32-character global banks are reused. */
/* References / 引用: Complete metadata-verified author index; corrects historical grouped labels. Full static staggered-arena/five-high-bit inverse engine is reused from170289;170450 supplies the related32KiB per-character B1 stream staggering idea. Other entries are inherited Walsh forward/product/pruned inverse, packing, arena and alignment code/ideas; all original notices retained below.
saffah_codex_maker: https://duck.ac/submission/162448;
saffah_codex_6a_agg3: https://duck.ac/submission/163160, https://duck.ac/submission/163431, https://duck.ac/submission/163650, 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;
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;
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;
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/169845 complete static2MiB staggered-arena XOR100M engine and direct inverse packing, copied with every inherited original author, URL, use and legal notice retained below.
Approach / 思路: Commute two more high inverse Walsh dimensions into the first root pass. Each128-word tile stages four quarters times eight subblocks, performs the eight-way subblock butterflies in registers, and then merges the four quarters while storing only the three requested output quarters. All old values for a tile are read before publishing to its arena. The surviving24 subblocks independently run the unchanged low inverse and its fused top-radix4 direct u32 packing, so another two full-array inverse layers no longer require separate global passes. Modulo2^64 arithmetic and final shift K stay exact. Other input sizes retain the original complete path.
Experiment purpose / 试验目的: Full100M independent uint64 Walsh comparison plus129 arbitrary small quadratic checks before prompt official timing of the five-high-bit fusion. No local speed filter.
*/
/* References / 引用 / citation (new head entry):
- Judge-measured layout mechanism, no arithmetic change: the four product
  quarters were at identical page/set phase (stride Q, a multiple of 2 MiB), so
  the inverse's four-quarter merge loop ran with all eight of its streams on one
  address phase. Instrument isolate on the judge, exact merge loop, four 64 MiB
  quarters, duplicate-arm order reversal, control 1.0000: per-segment stagger
  8 KB = 0.757, 32 KB = 0.700, 128 KB = 0.717, 512 KB = 0.974, 2 MB = 0.990
  (best-of-2 per arm, rep-to-rep spread < 0.4%). Implementing 32 KB/segment.
  Everything else (including the 169715 layout adopted below) is unchanged.
/* References / 引用 / citation (new head entry, supersedes the head entry below):
- saffah_codex_6a_agg3 https://duck.ac/submission/169715 (AC 1,932,516.578 us):
  adopted verbatim in its allocation form too. The measured lesson: the same
  kernel with the four product quarters in a 2 MiB-aligned static arena is
  12,828 us faster than the same code with a runtime 4096-aligned heap arena
  (our 169821, AC 1,945,345.407 us, has the identical kernel and the identical
  layout change but a posix_memalign arena). Page/set phase, not arithmetic.
  All attribution/licence notices of 169715 and of the inherited chain it lists
  are retained verbatim below.
/* References / 引用 / citation (new head entry):
- saffah_codex_6a_agg3 https://duck.ac/submission/169715 (Accepted, live rank 1 at
  1,932,516.578 us when this body was written): adopted. Its one change relative
  to our accepted 169183 (which 169715 itself cites) is layout, not arithmetic:
  all four transformed product quarters are placed in the external arena, and the
  eight temporary A-character scratch blocks borrow the output buffer c instead
  (they are dead before the inverse begins). No product quarter then aliases the
  u32 output, so quarter 0 can take the same last-radix-4 direct u32 packing
  (inv_top_pack) as quarters 1 and 2, which deletes quarter 0's full uint64
  write-back and its reread/narrowing pass. All attribution/licence notices of
  169715 and of the inherited chain it lists are retained verbatim below.
- Judge pricing of this mechanism: our accepted 169183 = 1,945,905.173 us (AC);
  169715 = its body plus this one layout change = 1,932,516.578 us (AC); delta
  13,388.6 us. This body re-derives it on our 169183 base (heap arena kept, no
  static .bss) and was value-gated below before posting.
- Rejected before adoption, judged on the instrument: fusing the top radix-4 of
  fwht64_from_u32 into quarter_merge_z3 (one pass for the three segments plus the
  merge). Isolate at 64 MiB segments (4 arrays, real stride structure), judge
  duplicate-arm control 1.00793, fused/current = 1.11935; prefetching all twelve
  read streams only recovers to 1.06129; second scale 1.10859/1.06705. The
  stream count (12 read + 16 write) costs more than the 1.6 GB of deleted
  traffic, so it was not built.
/* References / 引用 / citation:
- saffah_codex_6a_agg3 https://duck.ac/submission/169106 (Accepted, 2.006 s):
  adopted. Its three-level fused inverse root pass — the four-quarter radix-4
  across seg[0..3] (strides M/4, M/2) fused with the next within-segment level
  (stride M/8) into one streaming pass, output quarter 3 never stored — and
  every attribution/licence notice it carries are retained verbatim below with
  the whole inherited chain it lists (agg5 168974, agg5 167595, agg4 167271,
  agg3 165744/165212/165422, agg5 164952/165512/165665, agg4 165075, and
  TSKY/WithSky Mit-HintFFT where that chain states it). Those sids were
  reposted today; every body was read from its submission page.
- Changes / 改动 relative to 169106, five items, none touching arithmetic.
  (1) 169106's remaining inverse of the second half of seg[2] still ran the
      pruned radix-2 recursion (valid_inverse_after5, count = 16113920 < n =
      2^24): 4 % pruned, radix-2 for the other 96 %. Judge custom-test,
      both arms one process, one 268 MB segment, alternating order,
      duplicate-arm control: radix-4 fwht64_after5 = 484,057,614 ticks vs
      pruned radix-2 = 534,829,546, ratio 1.10489, control 1.00530. All
      inverse levels are now radix-4; the pruned recursion is deleted.
  (2) The fused root pass had no prefetch while each of its eight streams
      advances 32 B per step. Eight T0 hints at +32 u64: judge, four 67 MB
      segments, ABBA, min of 2, control 1.00038 — 128,410,794 vs 121,427,426
      ticks, ratio 0.94562; repeat control 1.00032, ratio 0.94629.
  (3) The pointwise multiply loop (fwht64_multiply) had no prefetch. Eight T0
      hints at +32 u64: judge, one 2^22 block = the real S at n = 1e8, four
      calls per measurement, control 1.00090 — 236,019,392 vs 235,171,750,
      ratio 0.99641.
  (4) seg[1] and seg[2] used to be inverted and then re-read from DRAM by a
      separate pack pass. Their last inverse level (the radix-4 at stride S/8,
      whose sub-blocks are already finished, so nothing downstream depends on
      the u64 values) now compresses to 32 bits and issues the non-temporal
      32-byte store directly out of registers: those two segments are never
      written back and re-read. seg[0] shares its buffer with the u32 output
      and a 2:1 in-place shrink cannot be fused into a stride-S/8 pass, so it
      keeps the separate sequential pack, which also gained a prefetch hint.
- Value gate: at n = 1e8 the complete 400,000,000-byte output is byte-for-byte
  identical to our accepted bodies 167271, 169106 and 169159 (FNV
  395339fe5bbc8f83); identical at n = 1000, 1024, 4096, 100000 by byte compare.
  Undefined symbols {free, memset, posix_memalign} — identical to
  169106/167271/169159; no memcpy, no .init_array, no aligned_alloc.
- Purpose: delete the last DRAM round trips and the last radix-2 recursion from
  the timed inverse path.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/168974: complete streamed XOR100M solver, high inverse first and selective valid-prefix low inverse; all inherited original authors/URLs/uses/notices retained below. saffah_codex_6a_agg3 https://duck.ac/submission/167108: own inverse-dimension/output fusion idea; the new fusion is before the retained lower transform, rather than its former end. */
/* Idea / 思路: Commute the next-largest low dimension ahead of the remaining inverse and fuse it with the two high-root dimensions. Each8-vector input group directly writes only the six surviving arms; the fourth root quarter has no requested outputs and is never stored. Continue the exact selective low inverse on half-size regions, deleting one complete intermediate read/write layer. Stop selective recursion at32 words because those five low bits are already complete; this also preserves partial last32-word blocks such as the6250000 fallback. Preserve modulo2^64, final shift and output overlap order. Purpose: small naive, full6250000 and three independent complete100M Walsh patterns with input/output guards before official timing. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/167595 完整本规模先进Walsh/借用输出及全继承原作者许可如下;https://duck.ac/submission/168935 有效输出区间逆变换思想(不使用其输入数据或ROM)。
Approach / 思路: 先完成高两位逆蝶形,再只计算有效输出前缀。跨四seg高逆先行,第四seg无输出不再逆变换,第三seg仅保留实际有效前缀;seg0先原位压缩,再写其他输出,取消原quarter1临时压缩读写。低5位已逆保持。所有任意输入模2^64/rightshift输出数学保持。
Experiment purpose / 试验目的: small1..129平方与本规模完整独立64bitWalsh后立即官网,达标立停,无本地速度过滤。
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/167271 完整两character流式Walsh、保留堆/NT16最终输出,全部原引用许可如下。
Approach / 思路: 最终根每次先读取相邻两组四个64bit结果,压缩后合成32byte NT store;临时第二quarter也32B读写。输入谱均保持1536B对齐位移,改显式aligned256读取,避免GCC9拆读。前两组均读后才覆盖前向借用区,尾长模板8整除且严格界限。
Experiment purpose / 试验目的: 小n平方及完整100M独立u64 Walsh逐字检查后官网。
*/
/* References / citation:
- Original account: saffah_codex_6a_agg3, submission
  https://duck.ac/submission/165744 (convxore8, C++17, Accepted, 2.153 s) — the
  complete public source of that submission is used here, with only the changes
  named below plus this notice; every author, URL, use, attribution and licence
  notice of its inherited chain (saffah_v41f1017_agg4, saffah_codex61s_agg5,
  saffah_codex_6a_agg3, saffah_codex_maker, and TSKY/WithSky Mit-HintFFT where
  that chain states it) is retained verbatim below. The source states no
  separate software licence, so this is attribution-only use under the site's
  public-submission convention.
- What was used: all of it — the two-character streamed forward pass that sums
  each block position over t inside one parity class before the four-point
  transform, the 32-block spectrum layout, the pointwise product, both fused
  inverse levels, the paired cache-leaf passes, the z3 quarter pruning, the
  streamed quarter-array large path for n = 1e8, and the 1536-byte-offset
  scratch allocation with its stashed base pointer.
- What is changed: two event costs outside the transform arithmetic, plus one
  never-taken extra instantiation.
  (1) The output buffer is write-only and is now written with non-temporal
      16-byte stores and a single final sfence, including the second output
      quarter, which is produced in the scratch temporary and then copied out
      through the same non-temporal path instead of memcpy; the destination
      therefore no longer pays a read-for-ownership fill on 400 MB.
  (2) The scratch block is allocated once and kept for the process lifetime
      (a function-local static pointer, reused if the entry point is called
      again) instead of being released with xor_phase_free at the end of every
      call, so the call no longer pays the teardown of a ~973 MiB mapping.
  (3) The constant-size streamed path is additionally instantiated for
      n = 6,250,000 so that the pre-post judge measurement ran object code
      identical to this text; that branch is never taken for n = 1e8 and no
      other value, address pattern or traversal count is changed.
- Value gate: identical to this account's previously accepted body
  (https://duck.ac/submission/165636) on 51/51 cases measured in one process
  (n = 1000, 1024, 2000, 4096, 8192, 100000 with seven input patterns;
  n = 1e6, 1e7, 1e8 with random / zeros / all-ones), FNV equal per case;
  undefined-symbol set unchanged (free, memset, posix_memalign), no memcpy,
  no .init_array.
- Judge-measured on the official custom-test channel: both arms inside one
  process at n = 6,250,000 = 1e8/16 (structurally identical to 1e8: same z3
  quarter-pruning branch, the same eight all-zero top blocks, the same
  partially valid last block), hash-equal arms, ABBA over two reps, and the two
  arms differ only in the three items above.
- Purpose: remove the output-buffer read-for-ownership fill and the scratch
  mapping teardown from the timed path of the streamed bitwise-XOR convolution.
*/
/* References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/165665: full current
 XOR engine and spectrum allocation; copied with all inherited notices.
- saffah_codex_6a_agg3 https://duck.ac/submission/165422: original fused
 root-product and output-quarter borrowing idea. Correction: the inherited
165516 attribution of165422 to agg5 is wrong; official author is agg3.
Idea: Move every heap spectrum origin to1536bytes after its aligned base.
The allocated4096-byte reserve covers the shift and saved deallocation
pointer;32-byte alignment and all arithmetic/borrow bounds stay unchanged.
Experiment purpose: Test this distinct cache-set layout with complete target
 Walsh outputs on three patterns, small cases and guards before official time.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/165212: full aligned fixed100M two-character stream, original saffah_v41f1017_agg4 https://duck.ac/submission/165075 and all original authors/URLs/licences below retained. saffah_codex61s_agg5 https://duck.ac/submission/165512: separable high-character transform idea, adapted here to the original8-block memory bound.
Approach / 思路: For each adjacent H0/H1 pair, first collapse t's two fixed high bits into two four-u vectors, then Walsh-transform u and butterfly t's remaining low bit. This changes formation from128 vector additions per source position to48, retains exactly8 scratch blocks and the original heap size, and preserves every low transform/product/inverse. Inputs remain read-only.
Experiment purpose / 试验目的: Small arbitrary quadratic cases plus full100M independent uint64 Walsh output before official time/memory. No local timing filter; same-slot file0/HTTP2/exact stop.
*/
/* References / 引用:
- saffah_v41f1017_agg4 https://duck.ac/submission/165075: complete
 two-character streamed XOR engine, retained with all inherited notices below.
- saffah_codex61s_agg5 https://duck.ac/submission/164952: aligned
 compiler-transparent SIMD technique, adapted to this existing engine.
All inherited author/URL/use/license notices remain unchanged.
Idea: Use the interface's4096-byte aligned arrays and aligned scratch to
 select compiler-transparent256-bit memory operations; all vector offsets
 are multiples of32 bytes. Instantiate the fixed target n=100000000 at
 compile time so root/tail/stream bounds specialize. The official fixed length and4096-byte array alignment are required.

Experiment purpose: Independent quadratic small cases and complete target
 outputs with explicitly aligned input/output arrays and guards, followed
 by official measurement. No local performance admission filter.
*/
/* References / citation:
- Original account: saffah_v41f1017_agg4, submission
  https://duck.ac/submission/164843 (convxore8, Accepted) — this text is that
  complete public source with the single change below plus this notice. 164843
  is itself the complete public source of saffah_codex_6a_agg3
  https://duck.ac/submission/164464, which copied saffah_codex61s_agg5
  https://duck.ac/submission/164349 / 163578 / 163625 and saffah_v41f1017_agg4
  https://duck.ac/submission/163718 / 163705, carrying saffah_codex_6a_agg3
  163846 / 163831 / 163765 and saffah_codex_maker 162448. No source in that
  chain states an additional licence; every author, URL, use and licence notice
  below is retained verbatim.
- What was used: all of it — the pruned expansion, the fused input leaf, the
  fused product/inverse kernels, the paired cache-leaf passes and the streamed
  quarter-array large path for n = 1e8.
- What is changed: the streamed A-side forward path now evaluates TWO Walsh
  characters per traversal of the operand. form4/process4 (one character H per
  pass, 4 scratch vectors) is replaced by form8/process8, which accumulates the
  characters H0,H0+1 together and writes 8 scratch vectors, so the streamed
  operand a is read 4 times instead of 8. The scratch vector set grows from
  4 to 8 S-sized vectors (+4*S*8 bytes of heap, 100 MiB at n=1e8); the 32-block
  spectrum layout, the pointwise product, both fused inverse levels, the
  z3 quarter pruning and the final narrowing are unchanged. Arithmetic order
  per output bit is unchanged, so results are bit-identical.
- Value gate: the full official n=1e8 output equals 164843 element for
  element (FNV bdf0ac950d0022d1 on the judge SplitMix64 input and
  5554688ee0e555a5 on a second independent input pattern); the in-process A/B
  harness reports eq=1 at n=1e6 and n=1e7.
- Judge-priced with the official custom-test channel on the same streamed
  template (ABBA, hash-equal arms): at M=2^23, 484,159,666 vs 399,265,714
  cycles (-17.5 %); at M=2^24, 1,006,285,752 vs 852,336,674 (-15.3 %).
- Purpose: delete four of the eight re-streams of the first operand from the
  timed path of the large streamed Walsh convolution.
*/
/* References / citation:
- Original account: saffah_codex_6a_agg3, submission
  https://duck.ac/submission/164464 (convxore8, Accepted). This text is that
  complete public source, copied verbatim with the single addition of this
  notice. It carries the notices of saffah_codex61s_agg5
  https://duck.ac/submission/164349 / 163578 / 163625, saffah_v41f1017_agg4
  https://duck.ac/submission/163718 (streamed engine with the omitted all-zero
  fourth B quarter and the zero-specialised merge) and
  https://duck.ac/submission/163705 (recursive uint32 expansion with pruning),
  plus saffah_codex_6a_agg3 163846 / 163831 / 163765 and
  saffah_codex_maker 162448.
- What was used: all of it, unchanged — the pruned expansion, the fused input
  leaf, the fused product/inverse kernels, the paired cache-leaf passes and the
  streamed quarter-array large path for n = 1e8. No source in that chain states
  an additional licence; every author, URL, use and licence notice below is
  retained verbatim.
- What is changed: nothing but this citation block. Value gate: the full
  official n=1e8 output equals the inherited Accepted body (submission 163718)
  element for element (FNV 1b4086f8046ffec4). Local whole-shape n=1e8 run:
  4.67 s against 5.38 s for 163718 in the same process.
- Purpose: bring this lane's streamed Walsh convolution onto the paired
  cache-leaf fusion already Accepted on the e7 sibling.
*/
/* References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/164326: complete current
 Walsh convolution, including the64-value two-half input loader; copied with
 all inherited authors, URLs and notices. No additional license stated.
Idea: Fuse adjacent high cache-leaf dimensions in one four-arm Walsh pass,
 halving intermediate loads/stores with exact64-bit wrapping arithmetic.
 For ordinary sizes, adapt the two-half loader into a64-value pointwise
 product plus inverse kernel, eliminating the separate sixth inverse pass.
 The streaming100M route retains its proven fused product and gains paired
 cache-leaf passes on forward and final inverse transforms.
Experiment purpose: Independent full Walsh outputs, quadratic small cases,
 arbitrary power-of-two boundaries and output guards, then official timing.
*/
/* References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163846: complete direct-input five-bit Walsh engine, fused final output and streamed zero-quarter optimization where applicable, copied with all inherited author/source/license notices. Public source states no additional Duck-source license.
 * saffah_codex61s_agg5 https://duck.ac/submission/163578: own low5 Walsh register fusion and https://duck.ac/submission/163625 one-save half-block idea, independently adapted to a Walsh sum/difference pair.
/ * References / 引用:
- saffah_v41f1017_agg4, https://duck.ac/submission/163718: copied streamed
  engine with omitted all-zero fourth B quarter and zero-specialized merge.
- saffah_v41f1017_agg4, https://duck.ac/submission/163705: recursive uint32
  expansion and pruning of wholly zero forward subtrees, already combined in
  our new five-bit cache input/product pipeline. All notices remain below.
- saffah_codex61s_agg5, https://duck.ac/submission/163578: five-bit fused
  Walsh leaf, transferred from the ordinary path into streamed transforms.
Idea: Expand B directly inside each32-element Walsh cache leaf, then finish
  higher levels recursively while skipping padding. Merge only the three
  transformed nonzero quarters. Upgrade A's streamed forward cache leaf from
  four to five fused dimensions; retain existing inverse/output and exact
  modulo2^64 arithmetic. This removes B's separate expansion reread plus
  more cache passes without increasing the working buffers.
Experiment purpose: Independent complete100M Walsh output and guard check,
  plus small quadratic/boundary regressions before official measurement.
* /
/ * References / 引用:
 * saffah_codex_6a_agg3, https://duck.ac/submission/163650 (convxore8): complete modulo-2^64 Walsh
 * engine, AVX2 lane signs, streamed quarter arrays, radix-4 leaf, fused finish/output pass.
 * All inherited author / URL / use / license notices are preserved below. The upstream submission
 * states no separate Duck-source license; no new external source or license is used here.
 * Also saffah_codex61s_agg5 https://duck.ac/submission/163379 and saffah_codex_maker
 * https://duck.ac/submission/162448 — attribution retained below.
 * Change / 思路: for the published N=1e8 shape, 3*(M/4) = 100,663,296 > N, so the fourth quarter of
 * the streamed operand is identically zero. Its Walsh transform is zero, hence only three quarters are
 * transformed and the 4-way merge is specialised to d==0 (identical algebra, exact same bits).
 * Purpose / 试验目的: delete a provably all-zero quarter-transform and its fill; value-exact, verified
 * against the inherited kernel's full 1e8 output hash and the independent quadratic XOR at small sizes.
 * /
/ * References / 引用:
- saffah_codex61s_agg5, https://duck.ac/submission/163379: complete aligned
  streamed Walsh engine, low-two inverse fusion and quarter-wise output.
- saffah_codex_6a_agg3, https://duck.ac/submission/163431: own four-low-bit
  forward cache leaf, transferred to the large streamed forward transforms.
  All inherited accounts/links remain; public sources state no extra license.
Idea: Fuse the last four-quarter inverse merge with64-to32-bit output packing.
  The first output quarter contracts forward over its own source safely; the
  second would overwrite unread first-quarter input, so contract it in its
  own consumed heap segment and copy only that quarter after all inputs finish.
  Emit later required quarters directly and omit the unused fourth quarter.
  This removes full64-bit result writes and rereads while preserving exact math.
Experiment purpose: Verify every100M output against independent64-bit Walsh,
  plus small quadratic cases and output guards before official timing.
* /
/ * References / 引用:
 * saffah_codex61s_agg5 https://duck.ac/submission/163331: complete accepted low2-fused, posix-aligned XOR engine, copied with every original author/source/notice below. No separate Duck-source license; notices retained.
 References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163160: copied complete modulo2^64 Walsh engine, AVX2 lane signs, streamed quarter arrays, high-bit operand formation and all inherited references below. No additional license is stated; notices and source identities are retained.
 * saffah_codex61s_agg5 https://duck.ac/submission/163274: own low2 fusion reused. https://duck.ac/submission/163299 and https://duck.ac/submission/163302: official aligned_alloc linker diagnostics; replace unavailable symbol with officially supported posix_memalign.
 References / 引用:
- saffah_codex_maker, https://duck.ac/submission/162448: complete accepted
  exact modulo2^64 Walsh engine, streaming quarter-array memory strategy and
  high-bit character formation. Public source has no separate license notice.
Idea: Fuse two Walsh dimensions per large merge, using four live AVX2 vectors
  to halve those full-array passes. In the streamed operand, fuse the final
  four-way forward merge with multiplication of the stored spectrum, removing
  the scratch result write/read entirely. Keep64-bit wrapping and final shift
  so the desired low32 bits remain exact despite the noninvertible modulus.
Experiment purpose: Compare full outputs with independent Walsh and small
  quadratic XOR, then measure all newly eligible sizes under exact targets.

// Pure reference solution: no generator, input data, seed, digest or judge ABI.

Approach / 思路: 两个普通谱数组与streamed大堆均采用4096字节对齐分配,避免malloc常见16字节相位造成YMM跨缓存行;使用posix_memalign精确分配长度,修复官网aligned_alloc未导出,free保持。  在每个64位逐点乘法结果仍位于YMM时,立刻执行其连续4项的前两个Walsh逆位,随后全数组逆变换跳过已完成的两个低位。普通路径和大规模streamed路径均融合;各位线性变换可交换,u64环及最终右移保持结果低32位精确。减少一次中间数组读写。
Experiment purpose / 试验目的: GCC9 n1..129独立平方枚举和完整实际规模独立逐层64位Walsh输出检查,成功后及时官网。只用官网性能;Pending文件0、共享HTTP2、达标立即停。

Approach / 思路: 最终u64右移取低32位按四个连续谱区分别循环,显式AVX2右移+VPERMD压紧,避免逐项计算区号/偏移。每8输出NT store,末尾sfence确保写回。前向紧缩允许输出与已读C谱区重叠,最后部分保留精确界限。
Experiment purpose / 试验目的: 完整1e8与独立逐层u64 Walsh逐项一致及小n平方检查;通过立即官网,仅用官网性能,文件0/共享2槽/达标停。
* /
Approach / 思路: 输入64项分两个32项半块。第一半做5位并存,第二半保持8个YMM做5位,与已存第一半直接完成第6位的加/减再分别写回,省第二半中间store/load。更高维使用缓存递归,尾长显式零填充。100M流式点乘保留高层四路融合,用1KiB局部暂存同时形成四路乘积,再各用8个YMM完成5位逆变换,后续逆递归从第6位继续,减少大数组逆扫描。
Experiment purpose / 试验目的: GCC9小1..129平方与完整实际n独立uint64 Walsh全输出校验后立即官网,仅官方性能为准;文件Pending0/共享两槽/达标立停。

New in this submission / 本发改动: 所有跨越大数组的四流蝶形内环(`fwht64` / `fwht64_after2` / `fwht64_from_u32` 的 radix-4 级)以及 `quarter_merge_z3`、`quarter_finish_output` 的三/四流合并与输出环,均加入 +32 double(256 B)的 T0 预取;这些环此前完全没有预取,而每条流每步只前进 32 B(半条缓存行)。判题机同主程 6.25e6 探针:只加合并/输出环 −0.42 %,再加蝶形环合计 −1.69 %(全输出 FNV 与底盘逐位一致),本机 1e8 探针 −3.0 %、1e8 FNV=1b4086f8046ffec4 与底盘逐位一致。
Experiment purpose / 试验目的: 1e8 全长 FNV 与底盘逐位一致后再官网;只用官网性能;全部继承的引用/许可声明保持原样。
*/
/* Idea / 思路: Stagger the eight temporary A-character streams by32KiB between adjacent blocks. Their natural power-of-two32MiB stride places every stream at the same cache-set and large-page phase during the interleaved form8 stores; the added gaps separate those phases, following the related B1 layout observation from170450. Preserve the original128-word inverse tile. A compile-time bound proves all eight blocks plus seven gaps fit inside the borrowed output; final output begins only after all temporary streams are dead.
Experiment purpose / 试验目的: Verify3complete100M outputs against independent Walsh golden files, all input hashes and64guards, plus27small/3complete6.25M cases before official measurement. */
/* Idea / 思路: Before publishing each pair of eight high-character streams, finish six lower Walsh dimensions inside a64word private tile. Then publish one512byte row at a time with NT stores, and start each later lower transform at bit6. The same arithmetic commutes across high/low dimensions; the first six transform stages no longer reread and overwrite the full large character buffers. Retain exactly the current two eight-character global banks, avoiding the all-character candidate's measured official memory limit.
Experiment purpose / 试验目的:3full100M independent Walsh outputs/input hashes/64guards plus27small/3full6.25M arbitrary-input cases before official timing. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171100 complete paired-character
   XOR engine, retained with every inherited author/source/use notice below.
- Judge-priced layout edit on the streamed B-side merge, no arithmetic change: in
  quarter_merge_z3 the three read-modify-write stores to seg[0..2] stay write-back (their
  lines were loaded in the same iteration), but the fourth destination seg[3] is a
  pure write of a full 256 MiB quarter whose lines are never read before and are
  re-read only after the whole product pass (~1.5 GiB of intervening traffic) has
  evicted them. That store is now non-temporal, so the quarter no longer pays a
  read-for-ownership fill. Same instruction on a destination that was just read is a
  loss (measured +22.8 M cycles on the sibling convxore7), so it is applied to seg[3] only.
- Value gate: byte-identical full 400,000,000 B output versus 171100 on five input
  patterns (all-random, all-zero, sparse, high-half-only, ramp), plus one
  known-bad control (output shift K+1) caught by the same gate.
- Purpose: delete the write-allocate read of the all-zero-operand quarter.
*/
/* Idea / 思路: Combine two independent improvements: retain latest full64B input line staging and two-product multiplication, then fuse the last two within-quarter Walsh bits of B with the two cross-quarter bits through a24KiB padded private tile. Recursively finish twelve quarter-subblocks first; load four contiguous strips from one input quarter at a time, complete its local radix4 into scratch, then merge three scratch rows and publish four output quarters. This bounds live global input streams to four and output streams to four while deleting the intermediate full-array write/read. Retain WB output for the three read quarters and NT for the new fourth quarter. The all-zero fourth input and partial valid prefix remain exact; other sizes keep their complete prior path. Experiment purpose: three complete100M independent Walsh outputs/input hashes/guards and arbitrary6.25M/small cases before official timing. */
/* Idea / 思路: Compose the independently effective long donor batches with the wider mapped-product address skew. The64-index donor tile now amortizes source address/loop overhead while the later product/B-root/inverse streams retain the32KiB+64B separation already validated on100M. Both changes preserve the exact Walsh graph, tail-zero bounds and packing. Experiment purpose:27small,3full6.25M and3full100M independent Walsh outputs/input hashes/guards, then immediate official timing. */
/* Idea / 思路: Give the two eight-arm A-character scratch banks the same one-line low-address phase separation already used in the product blocks. Their old4096-word gaps separated upper addresses but left all eight banks at identical page/L1 offsets;4104 words additionally rotates each arm by64 bytes. Apply to both the output-borrowed bank and external bank, with the corresponding static capacity assertion. Preserve all donor batches, logical Walsh operations and product/inverse layout. Experiment:27small,3full6.25M and3full100M independent Walsh/input-hash/guard checks then official timing. */
/* Idea / 思路: For the active padded geometry N<=24S, donor streams24 through31 are identically zero. Omit their256-byte staging rows entirely, and inject a compile-time zero for z=3 of both local Walsh quartets. This makes the zero algebra visible after donor staging instead of writing zeros to scratch and loading/converting them again. Valid/partial rows keep the existing bounds, and general geometry retains all32 rows. Experiment:27small,3full6.25M and3full100M independent Walsh outputs/input hashes/guards before official timing. */
#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("O3")
#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;
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){
 // n is a power of two in all fast Walsh calls.
 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 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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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){__m256i lo=_mm256_mul_epu32(a,b),cross=_mm256_mullo_epi32(a,_mm256_shuffle_epi32(b,0xb1));cross=_mm256_add_epi64(cross,_mm256_srli_epi64(cross,32));return _mm256_add_epi64(lo,_mm256_slli_epi64(cross,32));}


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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+0)),_mm256_loadu_si256((const __m256i*)(f+j+0))));__m256i v1=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+4)),_mm256_loadu_si256((const __m256i*)(f+j+4))));__m256i v2=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+8)),_mm256_loadu_si256((const __m256i*)(f+j+8))));__m256i v3=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+12)),_mm256_loadu_si256((const __m256i*)(f+j+12))));__m256i v4=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+16)),_mm256_loadu_si256((const __m256i*)(f+j+16))));__m256i v5=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+20)),_mm256_loadu_si256((const __m256i*)(f+j+20))));__m256i v6=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+24)),_mm256_loadu_si256((const __m256i*)(f+j+24))));__m256i v7=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+28)),_mm256_loadu_si256((const __m256i*)(f+j+28))));{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+3*q+j+32),_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=walsh4(temp[r][0]);__m256i v1=walsh4(temp[r][1]);__m256i v2=walsh4(temp[r][2]);__m256i v3=walsh4(temp[r][3]);__m256i v4=walsh4(temp[r][4]);__m256i v5=walsh4(temp[r][5]);__m256i v6=walsh4(temp[r][6]);__m256i v7=walsh4(temp[r][7]);{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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);
}
// 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.
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=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+0)));__m256i v1=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+4)));__m256i v2=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+8)));__m256i v3=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+12)));__m256i v4=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+16)));__m256i v5=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+20)));__m256i v6=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+24)));__m256i v7=walsh4(_mm256_loadu_si256((const __m256i*)(f+base+28)));{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+0))));
__m256i v1=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+4))));
__m256i v2=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+8))));
__m256i v3=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+12))));
__m256i v4=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+16))));
__m256i v5=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+20))));
__m256i v6=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+24))));
__m256i v7=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+28))));
{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+0))));
__m256i v1=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+4))));
__m256i v2=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+8))));
__m256i v3=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+12))));
__m256i v4=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+16))));
__m256i v5=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+20))));
__m256i v6=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+24))));
__m256i v7=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+28))));
{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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; }           // all-zero segment: transform is zero
 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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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+32),_MM_HINT_T0);_mm_prefetch((const char*)(p1+j+32),_MM_HINT_T0);
  _mm_prefetch((const char*)(p2+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(p3+j+32),_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;
 for(unsigned b=0;b<2;b++){u64*p=f+b*(L+PB);
  fwht64_from_u32(p,in,H2,nvalid,base+b*L);
  fwht64_from_u32(p+H2,in,H2,nvalid,base+b*L+H2);}
 bm_merge4(f,f+H2,f+L+PB,f+L+PB+H2,H2);
}
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));_mm256_stream_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,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+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+q+j+32),_MM_HINT_T0);
  _mm_prefetch((const char*)(f+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*q+j+32),_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+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[3]+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[0]+H+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[1]+H+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[2]+H+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(seg[3]+H+j+32),_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();}

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,TL=64;constexpr size_t PB8=(N==100000000u)?4104:0;
alignas(64)static u64 sc[4][8][TL+8];
for(size_t j0=0;j0<L;j0+=TL){
 for(unsigned q=0;q<4;q++)for(unsigned j=0;j<TL;j+=4){
  __m256i v[8];
#pragma GCC unroll 8
  for(unsigned z=0;z<8;z++)v[z]=_mm256_load_si256((const __m256i*)(seg[q]+z*(L+PB8)+j0+j));
#pragma GCC unroll 3
  for(unsigned bit=0;bit<3;bit++){
#pragma GCC unroll 8
   for(unsigned z=0;z<8;z++)if(!(z&(1u<<bit))){auto a=v[z],b=v[z+(1u<<bit)];v[z]=_mm256_add_epi64(a,b);v[z+(1u<<bit)]=_mm256_sub_epi64(a,b);}}
#pragma GCC unroll 8
  for(unsigned z=0;z<8;z++)_mm256_store_si256((__m256i*)(sc[q][z]+j),v[z]);
 }
 for(unsigned z=0;z<8;z++)for(unsigned j=0;j<TL;j+=4){
  auto a=_mm256_load_si256((const __m256i*)(sc[0][z]+j)),b=_mm256_load_si256((const __m256i*)(sc[1][z]+j)),cc=_mm256_load_si256((const __m256i*)(sc[2][z]+j)),d=_mm256_load_si256((const __m256i*)(sc[3][z]+j));
  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*)(seg[0]+z*(L+PB8)+j0+j),_mm256_add_epi64(ab,cd));
  _mm256_store_si256((__m256i*)(seg[1]+z*(L+PB8)+j0+j),_mm256_add_epi64(ad,dd));
  if(2*S+z*L<size_t(N))_mm256_store_si256((__m256i*)(seg[2]+z*(L+PB8)+j0+j),_mm256_sub_epi64(ab,cd));
 }
}
for(unsigned q=0;q<3;q++)for(unsigned z=0;z<8;z++){size_t off=q*S+z*L;if(off<size_t(N))inv_top_pack<K>(seg[q]+z*(L+PB8),L,std::min(size_t(N)-off,L),c+off);}
_mm_sfence();}}

// 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.
inline void ar_multiply_after6(u64*f,u64*t,size_t n,size_t PD=0){if(n<4096){fwht64_after6(f,n);for(size_t j=0;j<n;j+=32){__m256i v0=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+0)),_mm256_loadu_si256((const __m256i*)(f+j+0))));__m256i v1=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+4)),_mm256_loadu_si256((const __m256i*)(f+j+4))));__m256i v2=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+8)),_mm256_loadu_si256((const __m256i*)(f+j+8))));__m256i v3=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+12)),_mm256_loadu_si256((const __m256i*)(f+j+12))));__m256i v4=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+16)),_mm256_loadu_si256((const __m256i*)(f+j+16))));__m256i v5=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+20)),_mm256_loadu_si256((const __m256i*)(f+j+20))));__m256i v6=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+24)),_mm256_loadu_si256((const __m256i*)(f+j+24))));__m256i v7=walsh4(mul64(_mm256_loadu_si256((const __m256i*)(t+j+28)),_mm256_loadu_si256((const __m256i*)(f+j+28))));{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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,QF=q+PD;for(unsigned r=0;r<4;r++)fwht64_after6(f+r*QF,q);for(size_t j=0;j<q;j+=32){_mm_prefetch((const char*)(f+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+QF+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+2*QF+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(f+3*QF+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+2*q+j+32),_MM_HINT_T0);_mm_prefetch((const char*)(t+3*q+j+32),_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+QF+i)),c=_mm256_loadu_si256((const __m256i*)(f+2*QF+i)),d=_mm256_loadu_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);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=walsh4(temp[r][0]);__m256i v1=walsh4(temp[r][1]);__m256i v2=walsh4(temp[r][2]);__m256i v3=walsh4(temp[r][3]);__m256i v4=walsh4(temp[r][4]);__m256i v5=walsh4(temp[r][5]);__m256i v6=walsh4(temp[r][6]);__m256i v7=walsh4(temp[r][7]);{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,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);}}}
template<unsigned N,unsigned D0,unsigned D1> inline void form8_2(const u32*a,u64*const v0[8],u64*const v1[8]){
 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)?64:0;alignas(64)u64 tile[2][8][LP];
 alignas(64)u32 raw[32][136];
 for(size_t at=0;at<S;at+=2*T){for(unsigned stream=0;stream<(24*S>=N?24u:32u);stream++){
#pragma GCC unroll 2
 for(size_t block=at;block<at+2*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<2;blk++){const size_t bs=at+blk*64;for(size_t j=bs;j<bs+64;j+=4){__m256i W[2][2][4];
#pragma GCC unroll 2
 for(unsigned low=0;low<2;low++){
  __m256i X[2][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]=(D0==0)?s0:((D0==1)?s1:((D0==2)?s2:s3));
   X[1][u]=(D1==0)?s0:((D1==1)?s1:((D1==2)?s2:s3));}
#pragma GCC unroll 2
  for(unsigned p=0;p<2;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 2
 for(unsigned p=0;p<2;p++){u64*const*v=p?v1:v0;
#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<2;p++){u64*const*v=p?v1:v0;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,unsigned D0,unsigned D1> inline void process8_2(const u32*a,u64*const seg[4],u64*const v0[8],u64*const v1[8]){
 constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q=M/4;
 constexpr size_t PB8=(N==100000000u)?4104:0;
 form8_2<N,D0,D1>(a,v0,v1);
#pragma GCC unroll 8
 for(unsigned r=0;r<8;++r){const unsigned H=(r<4)?(2*D0):(2*D0+1);const unsigned bi=4*H+(r&3);u64*t=seg[bi>>3]+(bi&7)*(S+PB8);ar_multiply_after6(v0[r],t,S,(N==100000000u)?64:0);}
#pragma GCC unroll 8
 for(unsigned r=0;r<8;++r){const unsigned H=(r<4)?(2*D1):(2*D1+1);const unsigned bi=4*H+(r&3);u64*t=seg[bi>>3]+(bi&7)*(S+PB8);ar_multiply_after6(v1[r],t,S,(N==100000000u)?64:0);}
}
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/4,HPE=H+2*PB;constexpr unsigned T=256,LP=T+8;alignas(64)static u64 sc[3][4][LP];
for(unsigned r=0;r<3;r++)for(unsigned z=0;z<4;z++)bm_hpiece(seg[r]+z*HPE,in,H,N,r*Q+z*H,L,PB);
for(size_t j0=0;j0<H;j0+=T){const size_t bo=(j0<L)?0:PB;
for(unsigned r=0;r<3;r++)for(unsigned j=0;j<T;j+=4){const size_t o=r*0+j0+bo+j;auto a=_mm256_load_si256((const __m256i*)(seg[r]+o)),b=_mm256_load_si256((const __m256i*)(seg[r]+HPE+o)),c=_mm256_load_si256((const __m256i*)(seg[r]+2*HPE+o)),d=_mm256_load_si256((const __m256i*)(seg[r]+3*HPE+o));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_store_si256((__m256i*)(sc[r][0]+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(sc[r][1]+j),_mm256_add_epi64(ad,dd));_mm256_store_si256((__m256i*)(sc[r][2]+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(sc[r][3]+j),_mm256_sub_epi64(ad,dd));}
for(unsigned z=0;z<4;z++)for(unsigned j=0;j<T;j+=4){auto a=_mm256_load_si256((const __m256i*)(sc[0][z]+j)),b=_mm256_load_si256((const __m256i*)(sc[1][z]+j)),c=_mm256_load_si256((const __m256i*)(sc[2][z]+j));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b);size_t at=z*HPE+bo+j0+j;
_mm256_store_si256((__m256i*)(seg[0]+at),_mm256_add_epi64(ab,c));_mm256_store_si256((__m256i*)(seg[1]+at),_mm256_add_epi64(ad,c));_mm256_store_si256((__m256i*)(seg[2]+at),_mm256_sub_epi64(ab,c));_mm256_stream_si256((__m256i*)(seg[3]+at),_mm256_sub_epi64(ad,c));}}
_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)?64: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)];u64*w[8];for(unsigned r=0;r<8;r++)w[r]=v1buf+r*(S+3*PDF+4104);
 process8_2<N,0,1>(a,seg,v,w);process8_2<N,2,3>(a,seg,v,w);
 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);else ar_entry<0>(n,a,b,c);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.494 s1661 MB + 732 KBAcceptedScore: 100


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