CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: Multiplication of Big Integers (verify/bigint/multiplication.test.cpp)

Depends on

Code

// @brief Multiplication of Big Integers
#define PROBLEM "https://judge.yosupo.jp/problem/multiplication_of_big_integers"
#pragma GCC optimize("O3,unroll-loops")
#include <bits/allocator.h>
#pragma GCC target("avx2")
//#define CP_ALGO_CHECKPOINT
#include <iostream>
#include "blazingio/blazingio.min.hpp"
#include "cp-algo/math/bigint.hpp"
#include "cp-algo/util/checkpoint.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::math;

void solve() {
    bigint a, b;
    cin >> a >> b;
    a.mul_inplace(b);
    cout << a << "\n";
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    //cp_algo::checkpoint<1>();
}
#line 1 "verify/bigint/multiplication.test.cpp"
// @brief Multiplication of Big Integers
#define PROBLEM "https://judge.yosupo.jp/problem/multiplication_of_big_integers"
#pragma GCC optimize("O3,unroll-loops")
#include <bits/allocator.h>
#pragma GCC target("avx2")
//#define CP_ALGO_CHECKPOINT
#include <iostream>
#line 1 "blazingio/blazingio.min.hpp"
// NOLINTBEGIN
// clang-format off
// DO NOT REMOVE THIS MESSAGE. The mess that follows is a minified build of
// https://github.com/purplesyringa/blazingio. Refer to the repository for
// a human-readable version and documentation.
// Options: cbfoiedrhWLMXaIaAn
#define M$(x,...)_mm256_##x##_epi8(__VA_ARGS__)
#define $u(...)__VA_ARGS__
#if __APPLE__
#define $m(A,B)A
#else
#define $m(A,B)B
#endif
#if _WIN32
#define $w(A,B)A
#else
#define $w(A,B)B
#endif
#if __i386__|_M_IX86
#define $H(A,B)A
#else
#define $H(A,B)B
#endif
#if __aarch64__
#define $a(A,B)A
#else
#define $a(A,B)B
#endif
#define $P(x)void F(x K){
#define $T template<$c T
#define $c class
#define $C constexpr
#define $R return
#define $O operator
#define u$ uint64_t
#define $r $R*this;
#include<array>
#include<bitset>
#include<complex>
#include<cstring>
#include $a(<arm_neon.h>,<immintrin.h>)
#include<stdint.h>
#include $w(<windows.h>,<sys/mman.h>)
#include<sys/stat.h>
#include $w(<io.h>,<unistd.h>)
#include $w(<ios>,<sys/resource.h>)
#if _MSC_VER
#define __builtin_add_overflow(a,b,c)_addcarry_u64(0,a,b,c)
#define $s
#else
$H(,u$ _umul128(u$ a,u$ b,u$*D){auto x=(__uint128_t)a*b;*D=u$(x>>64);$R(u$)x;})
#define $s $a(,__attribute__((target("avx2"))))
#endif
#define $z $a(16,32)
#define $t $a(uint8x16_t,__m256i)
#define $I $w(__forceinline,__attribute__((always_inline)))
#define $F M(),
#define E$(x)if(!(x))abort();
$w(LONG WINAPI $x(_EXCEPTION_POINTERS*);,)namespace $f{using namespace std;struct B{enum $c A:char{}c;B&$O=(char x){c=A{x};$r}$O char(){$R(char)c;}};$C u$ C=~0ULL/255;struct D{string&K;};static B E[65568];template<int F>struct G{B*H,*S;void K(off_t C){$w(char*D=(char*)VirtualAlloc(0,(C+8191)&-4096,8192,1);E$(D)E$(VirtualFree(D,0,32768))DWORD A=C&-65536;E$(!A||MapViewOfFileEx(CreateFileMapping(GetStdHandle(-10),0,2,0,A,0),4,0,0,0,D)==D)E$(VirtualAlloc(D+A,65536,12288,4)==D+A)E$(~_lseek(0,A,0))DWORD E=0;ReadFile(GetStdHandle(-10),D+A,65536,&E,0);,int A=getpagesize();char*D=(char*)mmap(0,C+A,3,2,0,0);E$(D!=(void*)-1)E$(mmap(D+((C+A-1)&-A),A,3,$m(4114,50),-1,0)!=(void*)-1))H=(B*)D+C;*H=10;H[1]=48;H[2]=0;S=(B*)D;}void L(){H=S=E;}$I void M(){if(F&&S==H){$w(DWORD A=0;ReadFile(GetStdHandle(-10),S=E,65536,&A,0);,$a($u(register long A asm("x0")=0,D asm("x1")=(long)E,G asm("x2")=65536,C asm($m("x16","x8"))=$m(3,63);asm volatile("svc 0" $m("x80",):"+r"(A),"+r"(D):"r"(C),"r"(G));S=launder(E);),off_t A=$H(3,$m(33554435,0));B*D=E;asm volatile($H("int $128","syscall"):"+a"(A),$H("+c"(D):"b","+S"(D):"D")(0),"d"(65536)$H(,$u(:"rcx","r11")));S=D;))H=S+A;*H=10;if(!A)E[1]=48,E[2]=0;}}$T>$I void N(T&x){while($F(*S&240)==48)x=T(x*10+(*S++-48));}$T>$I decltype((void)~T{1})O(T&x){M();int A=is_signed_v<T>&&*S==45;S+=A;N(x=0);x=A?1+~x:x;}$T>$I decltype((void)T{1.})O(T&x){M();int A=*S==45;S+=A;$F S+=*S==43;u$ n=0;int i=0;for(;i<18&&($F*S&240)==48;i++)n=n*10+*S++-48;int B=20;int C=*S==46;S+=C;for(;i<18&&($F*S&240)==48;i++)n=n*10+*S++-48,B-=C;x=(T)n;while(($F*S&240)==48)x=x*10+*S++-48,B-=C;if(*S==46)S++,C=1;while(($F*S&240)==48)x=x*10+*S++-48,B-=C;int D;if((*S|32)==101)S++,$F S+=*S==43,O(D),B+=D;static $C auto E=[](){array<T,41>E{};T x=1;for(int i=21;i--;)E[40-i]=x,E[i]=1/x,x*=10;$R E;}();while(B>40)x*=(T)1e10,B-=10;while(B<0)x*=(T)1e-10,B+=10;x*=E[B];x=A?-x:x;}$I void O(bool&x){$F x=*S++==49;}$I void O(char&x){$F x=*S++;}$I void O(uint8_t&x){$F x=*S++;}$I void O(int8_t&x){$F x=*S++;}$T>$s void P(string&K,T C){M();B*G=S;C();K.assign((char*)G,S-G);while(F&&S==H&&($F H!=E)){C();K.append(E,S);}}$s void O(string&K){P(K,[&]()$s{B*p=S;$w(ULONG R;,)$t x;$a(uint64x2_t A;while(memcpy(&x,p,16),A=uint64x2_t(x<33),!(A[0]|A[1]))p+=16;S=p+(A[0]?0:8)+$w((_BitScanForward64(&R,A[0]?A[0]:A[1]),R),__builtin_ctzll(A[0]?A[0]:A[1]))/8;,int J;$t C=M$(set1,32);while(memcpy(&x,p,32),!(J=M$(movemask,M$(cmpeq,C,_mm256_max_epu8(C,x)))))p+=32;S=p+$w((_BitScanForward(&R,J),R),__builtin_ctz(J));)});}$s void O(D&A){P(A.K,[&](){S=(B*)memchr(S,10,H-S+1);});if(A.K.size()&&A.K.back()==13)A.K.pop_back();if(A.K.empty()||S<H)S+=*S==10;}$T>$I void O(complex<T>&K){T A,B{};if($F*S==40){S++;O(A);if($F*S++==44)Q(B),S++;}else O(A);K={A,B};}template<size_t N>$s void O(bitset<N>&K){if(N>4095&&!*this)$R;ptrdiff_t i=N;while(i)if($F i%$z||H-S<$z)K[--i]=*S++==49;else{B*p=S;for(int64_t j=0;j<min(i,H-S)/$z;j++){i-=$z;$t x;memcpy(&x,p,$z);$a(auto B=(uint8x16_t)vdupq_n_u64(~2ULL/254)&(48-x);auto C=vzip_u8(vget_high_u8(B),vget_low_u8(B));auto y=vaddvq_u16((uint16x8_t)vcombine_u8(C.val[0],C.val[1]));,u$ a=~0ULL/65025;auto y=$w(_byteswap_ulong,__builtin_bswap32)(M$(movemask,M$(shuffle,_mm256_slli_epi32(x,7),_mm256_set_epi64x(a+C*24,a+C*16,a+C*8,a))));)p+=$z;memcpy((char*)&K+i/8,&y,$z/8);}S=p;}}$T>$I void Q(T&K){if(!is_same_v<T,D>)while($F(uint8_t)*S<33)S++;O(K);}$O bool(){$R!!*this;}bool $O!(){$R S>H;}};struct U{G<0>A;G<1>B;U(){struct stat D;E$(~fstat(0,&D))(D.st_mode>>12)==8?A.K(D.st_size):B.L();}U*tie(nullptr_t){$R this;}void sync_with_stdio(bool){}$T>$I U&$O>>(T&K){A.S?A.Q(K):B.Q(K);$r}$O bool(){$R!!*this;}bool $O!(){$R A.S?!A:!B;}};short A[100];char L[64]{1};struct
V{char*D;B*S;int J;V(){$w(E$(D=(char*)VirtualAlloc(0,536870912,8192,4))E$(VirtualAlloc(D,4096,4096,260))AddVectoredExceptionHandler(1,$x);,size_t C=536870912;$m(,rlimit E;getrlimit(RLIMIT_AS,&E);if(~E.rlim_cur)C=25165824;)D=(char*)mmap(0,C,3,$m(4162,16418),-1,0);E$(D!=(void*)-1))S=(B*)D;for(int i=0;i<100;i++)A[i]=short((48+i/10)|((48+i%10)<<8));for(int i=1;i<64;i++)L[i]=L[i-1]+(0x8922489224892249>>i&1);}~V(){flush($w(!J,));}void flush($w(int F=0,)){$w(J=1;auto E=GetStdHandle(-11);auto C=F?ReOpenFile(E,1073741824,7,2684354560):(void*)-1;DWORD A;E$(C==(void*)-1?WriteFile(E,D,DWORD((char*)S-D),&A,0):(WriteFile(C,D,DWORD(((char*)S-D+4095)&-4096),&A,0)&&~_chsize(1,int((char*)S-D)))),auto G=D;ssize_t A;while((A=write(1,G,(char*)S-G))>0)G+=A;E$(~A))S=(B*)D;}$P(char)*S++=K;}$P(uint8_t)*S++=K;}$P(int8_t)*S++=K;}$P(bool)*S++=48+K;}$T>decltype((void)~T{1})F(T K){using D=make_unsigned_t<T>;D C=K;if(K<0)F('-'),C=1+~C;static $C auto N=[](){array<D,5*sizeof(T)/2>N{};D n=1;for(size_t i=1;i<N.size();i++)n*=10,N[i]=n;$R N;}();$w(ULONG M;,)int G=L[$w(($H(_BitScanReverse(&M,ULONG((int64_t)C>>32))?M+=32:_BitScanReverse(&M,(ULONG)C|1),_BitScanReverse64(&M,C|1)),M),63^__builtin_clzll(C|1))];G-=C<N[G-1];short H[20];if $C(sizeof(T)==2){auto n=33555U*C-C/2;u$ H=A[n>>25];n=(n&33554431)*25;H|=A[n>>23]<<16;H|=u$(48+((n&8388607)*5>>22))<<32;H>>=40-G*8;memcpy(S,&H,8);}else if $C(sizeof(T)==4){auto n=1441151881ULL*C;$H(n>>=25;n++;for(int i=0;i<5;i++){H[i]=A[n>>32];n=(n&~0U)*100;},int K=57;auto J=~0ULL>>7;for(int i=0;i<5;i++){H[i]=A[n>>K];n=(n&J)*25;K-=2;J/=4;})memcpy(S,(B*)H+10-G,16);}else{$H($u(if(C<(1ULL<<32)){$R F((uint32_t)C);}auto J=(u$)1e10;auto x=C/J,y=C%J;int K=100000,b[]{int(x/K),int(x%K),int(y/K),int(y%K)};B H[40];for(int i=0;i<4;i++){int n=int((429497ULL*b[i]>>7)+1);B*p=H+i*5;*p=48+char(n>>25);n=(n&~0U>>7)*25;memcpy(p+1,A+(n>>23),2);memcpy(p+3,A+((n&~0U>>9)*25>>21),2);}),$u(u$ D,E=_umul128(18,C,&D),F;_umul128(0x725dd1d243aba0e8,C,&F);D+=__builtin_add_overflow(E,F+1,&E);for(int i=0;i<10;i++)H[i]=A[D],E=_umul128(100,E,&D);))memcpy(S,(B*)H+20-G,20);}S+=G;}$T>decltype((void)T{1.})F(T K){if(K<0)F('-'),K=-K;auto G=[&](){auto x=u$(K*1e12);$H($u(x-=x>999999999999;uint32_t n[]{uint32_t(x/1000000*429497>>7)+1,uint32_t(x%1000000*429497>>7)+1};int K=25,J=~0U>>7;for(int i=0;i<3;i++){for(int j=0;j<2;j++)memcpy(S+i*2+j*6,A+(n[j]>>K),2),n[j]=(n[j]&J)*25;K-=2;J/=4;}S+=12;),$u(u$ D,E=_umul128(472236648287,x,&D)>>8;E|=D<<56;D>>=8;E++;for(int i=0;i<6;i++)memcpy(S,A+D,2),S+=2,E=_umul128(100,E,&D);))};if(K==0)$R F('0');if(K>=1e16){K*=(T)1e-16;int B=16;while(K>=1)K*=(T).1,B++;F("0.");G();F('e');F(B);}else if(K>=1){auto B=(u$)K;F(B);if((K-=(T)B)>0)F('.'),G();}else F("0."),G();}$P(const char*)$w(size_t A=strlen(K);memcpy((char*)S,K,A);S+=A;,S=(B*)stpcpy((char*)S,K);)}$P(const uint8_t*)F((char*)K);}$P(const int8_t*)F((char*)K);}$P(string_view)memcpy(S,K.data(),K.size());S+=K.size();}$T>$P(complex<T>)*this<<'('<<K.real()<<','<<K.imag()<<')';}template<size_t N>$s $P(const bitset<N>&)auto i=N;while(i%$z)*S++=48+K[--i];B*p=S;while(i){i-=$z;$a(short,int)x;memcpy(&x,(char*)&K+i/8,$z/8);$a(auto A=(uint8x8_t)vdup_n_u16(x);vst1q_u8((uint8_t*)p,48-vtstq_u8(vcombine_u8(vuzp2_u8(A,A),vuzp1_u8(A,A)),(uint8x16_t)vdupq_n_u64(~2ULL/254)));,auto b=_mm256_set1_epi64x(~2ULL/254);_mm256_storeu_si256(($t*)p,M$(sub,M$(set1,48),M$(cmpeq,_mm256_and_si256(M$(shuffle,_mm256_set1_epi32(x),_mm256_set_epi64x(0,C,C*2,C*3)),b),b)));)p+=$z;}S=p;}$T>V&$O<<(const T&K){F(K);$r}V&$O<<(V&(*A)(V&)){$R A(*this);}};struct W{$T>W&$O<<(const T&K){$r}W&$O<<(W&(*A)(W&)){$R A(*this);}};}namespace std{$f::U i$;$f::V o$;$f::W e$;$f::U&getline($f::U&B,string&K){$f::D A{K};$R B>>A;}$f::V&flush($f::V&B){if(!i$.A.S)B.flush();$R B;}$f::V&endl($f::V&B){$R B<<'\n'<<flush;}$f::W&endl($f::W&B){$R B;}$f::W&flush($f::W&B){$R B;}}$w(LONG WINAPI $x(_EXCEPTION_POINTERS*A){auto C=A->ExceptionRecord;auto B=C->ExceptionInformation[1];if(C->ExceptionCode==2147483649&&B-(ULONG_PTR)std::o$.D<0x40000000){E$(VirtualAlloc((char*)B,16777216,4096,4)&&VirtualAlloc((char*)(B+16777216),4096,4096,260))$R-1;}$R 0;},)
#define freopen(...)if(freopen(__VA_ARGS__)==stdin)std::i$=$f::U{}
#define cin i$
#define cout o$
#ifdef ONLINE_JUDGE
#define cerr e$
#define clog e$
#endif
// End of blazingio
// NOLINTEND
// clang-format on
#line 1 "cp-algo/math/bigint.hpp"


#line 1 "cp-algo/util/big_alloc.hpp"



#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#line 14 "cp-algo/util/big_alloc.hpp"
#include <forward_list>

// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif

namespace cp_algo {
    template<typename T, size_t Align = 32>
    class big_alloc {
        static_assert(Align >= alignof(void*), "Align must be at least pointer-size");
        static_assert(std::has_single_bit(Align), "Align must be a power of two");

    public:
        using value_type = T;
        template<class U>
        struct rebind {
            using other = big_alloc<U, Align>;
        };
        constexpr bool operator==(const big_alloc&) const = default;

        big_alloc() noexcept = default;
        template<typename U, std::size_t A>
        big_alloc(const big_alloc<U, A>&) noexcept {}

        [[nodiscard]] T* allocate(std::size_t n) {
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
            if(padded >= MEGABYTE) {
                void* raw = mmap(nullptr, padded, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
                madvise(raw, padded, MADV_HUGEPAGE);
                return static_cast<T*>(raw);
            }
#endif
            return static_cast<T*>(::operator new(padded, std::align_val_t(align)));
        }

        void deallocate(T* p, std::size_t n) noexcept {
            if(!p) {
                return;
            }
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
            if(padded >= MEGABYTE) {
                munmap(p, padded);
                return;
            }
#endif
            ::operator delete(p, padded, std::align_val_t(align));
        }

    private:
        static constexpr std::size_t MEGABYTE = 1 << 20;
        static constexpr std::size_t round_up(std::size_t x) noexcept {
            return (x + Align - 1) / Align * Align;
        }
    };

    template<typename T>
    using big_vector = std::vector<T, big_alloc<T>>;
    template<typename T>
    using big_basic_string = std::basic_string<T, std::char_traits<T>, big_alloc<T>>;
    template<typename T>
    using big_deque = std::deque<T, big_alloc<T>>;
    template<typename T>
    using big_stack = std::stack<T, big_deque<T>>;
    template<typename T>
    using big_queue = std::queue<T, big_deque<T>>;
    template<typename T>
    using big_priority_queue = std::priority_queue<T, big_vector<T>>;
    template<typename T>
    using big_forward_list = std::forward_list<T, big_alloc<T>>;
    using big_string = big_basic_string<char>;

    template<typename Key, typename Value, typename Compare = std::less<Key>>
    using big_map = std::map<Key, Value, Compare, big_alloc<std::pair<const Key, Value>>>;
    template<typename T, typename Compare = std::less<T>>
    using big_multiset = std::multiset<T, Compare, big_alloc<T>>;
    template<typename T, typename Compare = std::less<T>>
    using big_set = std::set<T, Compare, big_alloc<T>>;
}


#line 1 "cp-algo/math/fft_simple.hpp"


#line 1 "cp-algo/random/rng.hpp"


#include <chrono>
#include <random>
namespace cp_algo::random {
    std::mt19937_64 gen(
        std::chrono::steady_clock::now().time_since_epoch().count()
    );
    uint64_t rng() {
        return gen();
    }
}

#line 1 "cp-algo/math/common.hpp"


#include <functional>
#include <cstdint>
#include <cassert>
#line 8 "cp-algo/math/common.hpp"
#include <algorithm>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
    const int maxn = CP_ALGO_MAXN;
#else
    const int maxn = 1 << 19;
#endif
    const int magic = 64; // threshold for sizes to run the naive algo

    // Nonnegative 64-bit exponents, with an associative operation and its identity.
    // Windows >1 precompute odd powers only when that saves operations.
    template<int window = 1>
    auto bpow(auto const& x, auto n, auto const& one, auto op) {
        static_assert(window >= 1 && window <= 6);
        if constexpr(window > 1) {
            if(n == 0) {return one;}
            int bits = std::bit_width(uint64_t(n));
            auto low_bit = [&](int high) {
                int low = std::max(0, high - window + 1);
                while(!((n >> low) & 1)) {low++;}
                return low;
            };
            int first = low_bit(bits - 1);
            int cost = (1 << (window - 1)) + first;
            for(int j = first - 1; j >= 0;) {
                if(!((n >> j) & 1)) {j--;}
                else {cost++; j = low_bit(j) - 1;}
            }
            // Do not pay for the table when binary powering uses fewer operations.
            if(cost >= bits + std::popcount(uint64_t(n)) - 2) {return bpow<1>(x, n, one, op);}
            using T = std::decay_t<decltype(x)>;
            std::vector<T> odd;
            odd.reserve(1 << (window - 1));
            odd.push_back(x);
            auto square = op(x, x);
            while(odd.size() < size_t(1 << (window - 1))) {odd.push_back(op(odd.back(), square));}
            auto ans = odd[(n >> first) / 2];
            for(int j = first - 1; j >= 0;) {
                if(!((n >> j) & 1)) {ans = op(ans, ans); j--;}
                else {
                    int low = low_bit(j), length = j - low + 1;
                    auto digit = (n >> low) & ((1u << length) - 1);
                    for(int i = 0; i < length; i++) {ans = op(ans, ans);}
                    ans = op(ans, odd[digit / 2]);
                    j = low - 1;
                }
            }
            return ans;
        } else {
            if (n == 0) {
                return one;
            }
            auto ans = x;
            for(int j = std::bit_width<uint64_t>(n) - 2; ~j; j--) {
                ans = op(ans, ans);
                if((n >> j) & 1) {
                    ans = op(ans, x);
                }
            }
            return ans;
        }
    }
    template<int window = 1>
    auto bpow(auto x, auto n, auto ans) {
        return bpow<window>(x, n, ans, std::multiplies{});
    }
    template<typename T>
    T bpow(T const& x, auto n) {
        return bpow(x, n, T(1));
    }
    inline constexpr auto inv2(auto x) {
        assert(x % 2);
        std::make_unsigned_t<decltype(x)> y = 1;
        while(y * x != 1) {
            y *= 2 - x * y;
        }
        return y;
    }
}

#line 1 "cp-algo/math/cvector.hpp"


#line 1 "cp-algo/util/simd.hpp"


#include <experimental/simd>
#line 6 "cp-algo/util/simd.hpp"
#include <memory>

#if defined(__x86_64__) && !defined(CP_ALGO_DISABLE_AVX2)
#define CP_ALGO_SIMD_AVX2_TARGET _Pragma("GCC target(\"avx2,fma\")")
#else
#define CP_ALGO_SIMD_AVX2_TARGET
#endif

#define CP_ALGO_SIMD_PRAGMA_PUSH \
    _Pragma("GCC push_options") \
    CP_ALGO_SIMD_AVX2_TARGET

CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo {
    template<typename T, size_t len>
    using simd [[gnu::vector_size(len * sizeof(T))]] = T;
    using u64x8 = simd<uint64_t, 8>;
    using u32x16 = simd<uint32_t, 16>;
    using i64x4 = simd<int64_t, 4>;
    using u64x4 = simd<uint64_t, 4>;
    using u32x8 = simd<uint32_t, 8>;
    using u16x16 = simd<uint16_t, 16>;
    using i32x4 = simd<int32_t, 4>;
    using u32x4 = simd<uint32_t, 4>;
    using u16x8 = simd<uint16_t, 8>;
    using u16x4 = simd<uint16_t, 4>;
    using i16x4 = simd<int16_t, 4>;
    using u8x32 = simd<uint8_t, 32>;
    using u8x16 = simd<uint8_t, 16>;
    using u8x8 = simd<uint8_t, 8>;
    using u8x4 = simd<uint8_t, 4>;
    using dx4 = simd<double, 4>;

    inline dx4 abs(dx4 a) {
        return dx4{
            std::abs(a[0]),
            std::abs(a[1]),
            std::abs(a[2]),
            std::abs(a[3])
        };
    }

    // https://stackoverflow.com/a/77376595
    // works for ints in (-2^51, 2^51)
    static constexpr dx4 magic = dx4() + (3ULL << 51);
    inline i64x4 lround(dx4 x) {
        return i64x4(x + magic) - i64x4(magic);
    }
    inline dx4 to_double(i64x4 x) {
        return dx4(x + i64x4(magic)) - magic;
    }

    inline dx4 round(dx4 a) {
        return dx4{
            std::nearbyint(a[0]),
            std::nearbyint(a[1]),
            std::nearbyint(a[2]),
            std::nearbyint(a[3])
        };
    }

    inline u64x4 low32(u64x4 x) {
        return x & uint32_t(-1);
    }
    inline auto swap_bytes(auto x) {
        return decltype(x)(__builtin_shufflevector(u32x8(x), u32x8(x), 1, 0, 3, 2, 5, 4, 7, 6));
    }
    inline u64x4 montgomery_reduce(u64x4 x, uint32_t mod, uint32_t imod) {
#ifdef __AVX2__
        auto x_ninv = u64x4(_mm256_mul_epu32(__m256i(x), __m256i() + imod));
        x += u64x4(_mm256_mul_epu32(__m256i(x_ninv), __m256i() + mod));
#else
        auto x_ninv = u64x4(u32x8(low32(x)) * imod);
        x += x_ninv * uint64_t(mod);
#endif
        return swap_bytes(x);
    }

    // x - mod where x >= mod, for x in [0, 2 mod). Unsigned, so it holds up to mod < 2^31;
    // zero upper halves of 64-bit lanes stay zero.
    inline u32x8 reduce_once(u32x8 x, uint32_t mod) {
        auto y = x - mod;
        return x < y ? x : y;
    }
    inline u64x4 reduce_once(u64x4 x, uint32_t mod) {
        return u64x4(reduce_once(u32x8(x), mod));
    }

    inline u64x4 montgomery_mul(u64x4 x, u64x4 y, uint32_t mod, uint32_t imod) {
#ifdef __AVX2__
        return montgomery_reduce(u64x4(_mm256_mul_epu32(__m256i(x), __m256i(y))), mod, imod);
#else
        return montgomery_reduce(x * y, mod, imod);
#endif
    }
    inline u32x8 montgomery_mul(u32x8 x, u32x8 y, uint32_t mod, uint32_t imod) {
        return u32x8(montgomery_mul(u64x4(x), u64x4(y), mod, imod)) |
               u32x8(swap_bytes(montgomery_mul(u64x4(swap_bytes(x)), u64x4(swap_bytes(y)), mod, imod)));
    }
    inline dx4 rotate_right(dx4 x) {
        static constexpr u64x4 shuffler = {3, 0, 1, 2};
        return __builtin_shuffle(x, shuffler);
    }

    template<std::size_t Align = 32>
    inline bool is_aligned(const auto *p) noexcept {
        return (reinterpret_cast<std::uintptr_t>(p) % Align) == 0;
    }

    template<class Target>
    inline Target& vector_cast(auto &&p) {
        return *reinterpret_cast<Target*>(std::assume_aligned<alignof(Target)>(&p));
    }
}
#pragma GCC pop_options

#line 1 "cp-algo/util/complex.hpp"


#line 4 "cp-algo/util/complex.hpp"
#include <cmath>
#include <type_traits>
#line 7 "cp-algo/util/complex.hpp"
CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo {
    // Custom implementation, since std::complex is UB on non-floating types
    template<typename T>
    struct complex {
        using value_type = T;
        T x, y;
        inline constexpr complex(): x(), y() {}
        inline constexpr complex(T const& x): x(x), y() {}
        inline constexpr complex(T const& x, T const& y): x(x), y(y) {}
        inline complex& operator *= (T const& t) {x *= t; y *= t; return *this;}
        inline complex& operator /= (T const& t) {x /= t; y /= t; return *this;}
        inline complex operator * (T const& t) const {return complex(*this) *= t;}
        inline complex operator / (T const& t) const {return complex(*this) /= t;}
        inline complex& operator += (complex const& t) {x += t.x; y += t.y; return *this;}
        inline complex& operator -= (complex const& t) {x -= t.x; y -= t.y; return *this;}
        inline complex operator * (complex const& t) const {return {x * t.x - y * t.y, x * t.y + y * t.x};}
        inline complex operator / (complex const& t) const {return *this * t.conj() / t.norm();}
        inline complex operator + (complex const& t) const {return complex(*this) += t;}
        inline complex operator - (complex const& t) const {return complex(*this) -= t;}
        inline complex& operator *= (complex const& t) {return *this = *this * t;}
        inline complex& operator /= (complex const& t) {return *this = *this / t;}
        inline complex operator - () const {return {-x, -y};}
        inline complex conj() const {return {x, -y};}
        inline T norm() const {return x * x + y * y;}
        inline T abs() const {return std::sqrt(norm());}
        inline T const real() const {return x;}
        inline T const imag() const {return y;}
        inline T& real() {return x;}
        inline T& imag() {return y;}
        inline static constexpr complex polar(T r, T theta) {return {T(r * cos(theta)), T(r * sin(theta))};}
        inline auto operator <=> (complex const& t) const = default;
    };
    template<typename T> inline complex<T> conj(complex<T> const& x) {return x.conj();}
    template<typename T> inline T norm(complex<T> const& x) {return x.norm();}
    template<typename T> inline T abs(complex<T> const& x) {return x.abs();}
    template<typename T> inline T& real(complex<T> &x) {return x.real();}
    template<typename T> inline T& imag(complex<T> &x) {return x.imag();}
    template<typename T> inline T const real(complex<T> const& x) {return x.real();}
    template<typename T> inline T const imag(complex<T> const& x) {return x.imag();}
    template<typename T>
    inline constexpr complex<T> polar(T r, T theta) {
        return complex<T>::polar(r, theta);
    }
    template<typename T>
    inline std::ostream& operator << (std::ostream &out, complex<T> const& x) {
        return out << x.real() << ' ' << x.imag();
    }
}
#pragma GCC pop_options

#line 1 "cp-algo/util/checkpoint.hpp"


#line 8 "cp-algo/util/checkpoint.hpp"
namespace cp_algo {
#ifdef CP_ALGO_CHECKPOINT
    big_map<big_string, double> checkpoints;
    double last;
#endif
    template<bool final = false>
    void checkpoint([[maybe_unused]] auto const& _msg) {
#ifdef CP_ALGO_CHECKPOINT
        big_string msg = _msg;
        double now = (double)clock() / CLOCKS_PER_SEC;
        double delta = now - last;
        last = now;
        if(msg.size() && !final) {
            checkpoints[msg] += delta;
        }
        if(final) {
            for(auto const& [key, value] : checkpoints) {
                std::cerr << key << ": " << value * 1000 << " ms\n";
            }
            std::cerr << "Total: " << now * 1000 << " ms\n";
        }
#endif
    }
    template<bool final = false>
    void checkpoint() {
        checkpoint<final>("");
    }
}

#line 7 "cp-algo/math/cvector.hpp"
#include <immintrin.h>
#include <numbers>
#line 10 "cp-algo/math/cvector.hpp"
#include <ranges>
#line 13 "cp-algo/math/cvector.hpp"
CP_ALGO_SIMD_PRAGMA_PUSH
namespace stdx = std::experimental;
namespace cp_algo::math::fft {
    static constexpr size_t flen = 4;
    using ftype = double;
    using vftype = dx4;
    using point = complex<ftype>;
    using vpoint = complex<vftype>;
    static constexpr vftype vz = {};
    vpoint vi(vpoint const& r) {
        return {-imag(r), real(r)};
    }

    // Spectrum storage skips zero-filling on resize; every user writes before reading.
    template<class T>
    struct spectrum_alloc: big_alloc<T> {
        using big_alloc<T>::big_alloc;
        template<class U>
        struct rebind {
            using other = spectrum_alloc<U>;
        };
        template<class U>
            requires(std::is_same_v<U, vpoint>)
        void construct(U*) noexcept {}
    };
    using spectrum_vector = std::vector<vpoint, spectrum_alloc<vpoint>>;

    struct cvector {
        spectrum_vector r;
        cvector(size_t n) {
            n = std::max(flen, std::bit_ceil(n));
            r.assign(n / flen, vpoint{});
            prepare_roots(n / 16);
            checkpoint("cvector create");
        }

        vpoint& at(size_t k) { return r[k / flen]; }
        vpoint at(size_t k) const { return r[k / flen]; }
        template<class pt = point>
        inline void set(size_t k, pt const& t) {
            if constexpr(std::is_same_v<pt, point>) {
                real(r[k / flen])[k % flen] = real(t);
                imag(r[k / flen])[k % flen] = imag(t);
            } else {
                at(k) = t;
            }
        }
        template<class pt = point>
        inline pt get(size_t k) const {
            if constexpr(std::is_same_v<pt, point>) {
                return {real(r[k / flen])[k % flen], imag(r[k / flen])[k % flen]};
            } else {
                return at(k);
            }
        }

        size_t size() const {
            return flen * r.size();
        }
        static constexpr size_t eval_arg(size_t n) {
            if(n < pre_evals) {
                return eval_args[n];
            } else {
                return eval_arg(n / 2) | (n & 1) << (std::bit_width(n) - 1);
            }
        }
        static constexpr point eval_point(size_t n) {
            if(n % 2) {
                return -eval_point(n - 1);
            } else if(n % 4) {
                return eval_point(n - 2) * point(0, 1);
            } else if(n / 4 < pre_evals) {
                return evalp[n / 4];
            } else if(n / 4 - pre_evals < extra.size()) {
                return extra[n / 4 - pre_evals];
            } else {
                return polar<ftype>(1., std::numbers::pi / (ftype)std::bit_floor(n) * (ftype)eval_arg(n));
            }
        }
        static constexpr std::array<point, 32> roots = []() {
            std::array<point, 32> res;
            for(size_t i = 2; i < 32; i++) {
                res[i] = polar<ftype>(1., std::numbers::pi / (1ull << (i - 2)));
            }
            return res;
        }();
        static constexpr point root(size_t n) {
            return roots[std::bit_width(n)];
        }
        template<int step>
        static void exec_on_eval(size_t n, size_t k, auto &&callback) {
            callback(k, root(4 * step * n) * eval_point(step * k));
        }
        template<int step>
        static void exec_on_evals(size_t n, auto &&callback) {
            point factor = root(4 * step * n);
            if constexpr(step == 1 || step == 2 || step == 4) {
                prepare_roots((step * n + 3) / 4);
                size_t i = 0;
                if constexpr(step == 1) {
                    for(; i + 4 <= n; i += 4) {
                        size_t k = i / 4;
                        point e = k < pre_evals ? evalp[k] : extra[k - pre_evals];
                        point v = factor * e;
                        callback(i, v);
                        callback(i + 1, -v);
                        point iv(-imag(v), real(v));
                        callback(i + 2, iv);
                        callback(i + 3, -iv);
                    }
                } else if constexpr(step == 2) {
                    for(; i + 2 <= n; i += 2) {
                        size_t k = i / 2;
                        point e = k < pre_evals ? evalp[k] : extra[k - pre_evals];
                        point v = factor * e;
                        callback(i, v);
                        callback(i + 1, point(-imag(v), real(v)));
                    }
                }
                for(; i < n; i++) {
                    size_t index = step * i, k = index / 4;
                    point e = k < pre_evals ? evalp[k] : extra[k - pre_evals];
                    if(index & 2) {
                        e = e * point(0, 1);
                    }
                    if(index & 1) {
                        e = -e;
                    }
                    callback(i, factor * e);
                }
            } else {
                for(size_t i = 0; i < n; i++) {
                    callback(i, factor * eval_point(step * i));
                }
            }
        }

        static void do_dot_iter(point rt, vpoint& Bv, vpoint const& Av, vpoint& res) {
            res += Av * Bv;
            real(Bv) = rotate_right(real(Bv));
            imag(Bv) = rotate_right(imag(Bv));
            auto x = real(Bv)[0], y = imag(Bv)[0];
            real(Bv)[0] = x * real(rt) - y * imag(rt);
            imag(Bv)[0] = x * imag(rt) + y * real(rt);
        }

        template<size_t fixed = 0>
        void dot(cvector const& t) {
            size_t n = fixed ? fixed : this->size();
            exec_on_evals<1>(n / flen, [&] [[gnu::always_inline]] (size_t k, point rt) {
                k *= flen;
                auto [Ax, Ay] = at(k);
                auto Cv = t.at(k);
                vpoint vrt = {vz + real(rt), vz + imag(rt)};
                auto Cr = Cv * vrt;
                vpoint res = vz;
                auto iter = [&]<int i> [[gnu::always_inline]] () {
                    auto wrap = [&](vftype original, vftype rotated) {
                        if constexpr(i == 0) {
                            return original;
                        } else {
                            return __builtin_shufflevector(rotated, original, 4 - i, 5 - i, 6 - i, 7 - i);
                        }
                    };
                    vpoint Cw = {wrap(real(Cv), real(Cr)), wrap(imag(Cv), imag(Cr))};
                    vpoint Av = {vz + Ax[i], vz + Ay[i]};
                    return Av * Cw;
                };
                auto p0 = iter.template operator()<0>(), p1 = iter.template operator()<1>();
                auto p2 = iter.template operator()<2>(), p3 = iter.template operator()<3>();
                res = (p0 + p1) + (p2 + p3);
                set(k, res);
            });
            checkpoint("dot");
        }
        // normalize=false leaves the inverse-transform scale for the caller.
        template<bool partial = true, bool normalize = true, size_t fixed = 0>
        void ifft() {
            size_t n = fixed ? fixed : size();
            if constexpr(!partial) {
                prepare_roots(n / 4);
                point pi(0, 1);
                exec_on_evals<4>(n / 4, [&] [[gnu::always_inline]] (size_t k, point rt) {
                    k *= 4;
                    point v1 = conj(rt);
                    point v2 = v1 * v1;
                    point v3 = v1 * v2;
                    auto A = get(k);
                    auto B = get(k + 1);
                    auto C = get(k + 2);
                    auto D = get(k + 3);
                    set(k, (A + B) + (C + D));
                    set(k + 2, ((A + B) - (C + D)) * v2);
                    set(k + 1, ((A - B) - pi * (C - D)) * v1);
                    set(k + 3, ((A - B) + pi * (C - D)) * v3);
                });
            }
            bool parity = std::countr_zero(n) % 2;
            if(parity) {
                exec_on_evals<2>(n / (2 * flen), [&] [[gnu::always_inline]] (size_t k, point rt) {
                    k *= 2 * flen;
                    vpoint cvrt = {vz + real(rt), vz - imag(rt)};
                    auto B = at(k) - at(k + flen);
                    at(k) += at(k + flen);
                    at(k + flen) = B * cvrt;
                });
            }

            transform<true, fixed>(n, parity);
            checkpoint("ifft");
            if constexpr(normalize) {
                auto scale = vz + ftype(partial ? flen : 1) / ftype(n);
                for(size_t k = 0; k < n; k += flen) {
                    set(k, get<vpoint>(k) * scale);
                }
            }
        }
        template<bool partial = true, size_t fixed = 0>
        void fft() {
            size_t n = fixed ? fixed : size();
            prepare_roots(n / (partial ? 16 : 4));
            bool parity = std::countr_zero(n) % 2;
            transform<false, fixed>(n, parity);
            if(parity) {
                exec_on_evals<2>(n / (2 * flen), [&] [[gnu::always_inline]] (size_t k, point rt) {
                    k *= 2 * flen;
                    vpoint vrt = {vz + real(rt), vz + imag(rt)};
                    auto t = at(k + flen) * vrt;
                    at(k + flen) = at(k) - t;
                    at(k) += t;
                });
            }
            if constexpr(!partial) {
                prepare_roots(n / 4);
                point pi(0, 1);
                exec_on_evals<4>(n / 4, [&] [[gnu::always_inline]] (size_t k, point rt) {
                    k *= 4;
                    point v1 = rt;
                    point v2 = v1 * v1;
                    point v3 = v1 * v2;
                    auto A = get(k);
                    auto B = get(k + 1) * v1;
                    auto C = get(k + 2) * v2;
                    auto D = get(k + 3) * v3;
                    set(k, (A + C) + (B + D));
                    set(k + 1, (A + C) - (B + D));
                    set(k + 2, (A - C) + pi * (B - D));
                    set(k + 3, (A - C) - pi * (B - D));
                });
            }
            checkpoint("fft");
        }
        static std::array<vpoint, 4> transpose(std::array<vpoint, 4> const& a) {
            auto half = [](auto part) {
                auto a0 = __m256d(part(0)), a1 = __m256d(part(1)), a2 = __m256d(part(2)), a3 = __m256d(part(3));
                auto t0 = _mm256_unpacklo_pd(a0, a1), t1 = _mm256_unpackhi_pd(a0, a1), t2 = _mm256_unpacklo_pd(a2, a3),
                     t3 = _mm256_unpackhi_pd(a2, a3);
                return std::array<vftype, 4>{
                    vftype(_mm256_permute2f128_pd(t0, t2, 0x20)), vftype(_mm256_permute2f128_pd(t1, t3, 0x20)),
                    vftype(_mm256_permute2f128_pd(t0, t2, 0x31)), vftype(_mm256_permute2f128_pd(t1, t3, 0x31))};
            };
            auto re = half([&](int k) { return real(a[k]); }), im = half([&](int k) { return imag(a[k]); });
            return {vpoint{re[0], im[0]}, vpoint{re[1], im[1]}, vpoint{re[2], im[2]}, vpoint{re[3], im[3]}};
        }
        // Multiply groups of 16 points as polynomials modulo x^16 - rt: one radix-4 level on
        // each operand, a lane-parallel 4-coefficient Karatsuba product, one inverse level.
        // The weights rt, rt^2, rt^3 of a tile of groups are computed four groups per SIMD
        // operation ahead of the tile, so the product loop only broadcasts them from memory.
        static constexpr size_t dot_tile = 64;
        template<size_t fixed, bool square = false>
        void dot_fused16(cvector const& t, size_t offset, size_t length) {
            constexpr size_t T = dot_tile;
            const size_t n = fixed ? fixed : size();
            point factor = root(n);
            auto fr = _mm256_set1_pd(real(factor)), fi = _mm256_set1_pd(imag(factor));
            alignas(32) double tw[6][T];
            const bool ahead = offset + length < n;
            auto cmadd = [] [[gnu::always_inline]] (vpoint x, vpoint y, vpoint c) {
                auto re = _mm256_fmadd_pd(__m256d(real(x)), __m256d(real(y)),
                                          _mm256_fnmadd_pd(__m256d(imag(x)), __m256d(imag(y)), __m256d(real(c))));
                auto im = _mm256_fmadd_pd(__m256d(real(x)), __m256d(imag(y)),
                                          _mm256_fmadd_pd(__m256d(imag(x)), __m256d(real(y)), __m256d(imag(c))));
                return vpoint{vftype(re), vftype(im)};
            };
            auto cmcross = [] [[gnu::always_inline]] (vpoint x, vpoint y, vpoint p, vpoint q) {
                auto re = _mm256_sub_pd(_mm256_fmsub_pd(__m256d(real(x)), __m256d(real(y)), __m256d(real(p))),
                                        _mm256_fmadd_pd(__m256d(imag(x)), __m256d(imag(y)), __m256d(real(q))));
                auto im = _mm256_add_pd(_mm256_fmsub_pd(__m256d(real(x)), __m256d(imag(y)), __m256d(imag(p))),
                                        _mm256_fmsub_pd(__m256d(imag(x)), __m256d(real(y)), __m256d(imag(q))));
                return vpoint{vftype(re), vftype(im)};
            };
            // z * conj(v)
            auto mulconj = [] [[gnu::always_inline]] (vpoint z, vpoint v) {
                auto re = _mm256_fmadd_pd(__m256d(real(z)), __m256d(real(v)),
                                          _mm256_mul_pd(__m256d(imag(z)), __m256d(imag(v))));
                auto im = _mm256_fmsub_pd(__m256d(imag(z)), __m256d(real(v)),
                                          _mm256_mul_pd(__m256d(real(z)), __m256d(imag(v))));
                return vpoint{vftype(re), vftype(im)};
            };
            for(size_t tile = offset; tile < offset + length; tile += 16 * T) {
                size_t k0 = tile / 16;
                auto const* e = reinterpret_cast<double const*>(k0 < pre_evals ? evalp.data() + k0
                                                                               : extra.data() + (k0 - pre_evals));
                for(size_t g = 0; g < T; g += 4) {
                    auto x = _mm256_loadu_pd(e + 2 * g), y = _mm256_loadu_pd(e + 2 * g + 4);
                    auto er = _mm256_permute4x64_pd(_mm256_unpacklo_pd(x, y), 0xD8),
                         ei = _mm256_permute4x64_pd(_mm256_unpackhi_pd(x, y), 0xD8);
                    auto r1 = _mm256_fmsub_pd(fr, er, _mm256_mul_pd(fi, ei)),
                         i1 = _mm256_fmadd_pd(fr, ei, _mm256_mul_pd(fi, er));
                    auto r2 = _mm256_fmsub_pd(r1, r1, _mm256_mul_pd(i1, i1)),
                         i2 = _mm256_fmadd_pd(r1, i1, _mm256_mul_pd(i1, r1));
                    auto r3 = _mm256_fmsub_pd(r1, r2, _mm256_mul_pd(i1, i2)),
                         i3 = _mm256_fmadd_pd(r1, i2, _mm256_mul_pd(i1, r2));
                    _mm256_store_pd(tw[0] + g, r1);
                    _mm256_store_pd(tw[1] + g, i1);
                    _mm256_store_pd(tw[2] + g, r2);
                    _mm256_store_pd(tw[3] + g, i2);
                    _mm256_store_pd(tw[4] + g, r3);
                    _mm256_store_pd(tw[5] + g, i3);
                }
                for(size_t g = 0; g < T; g++) {
                    size_t pos = tile + 16 * g;
                    if(ahead) {
                        // Pull the next block of both operands towards the cache while this one is multiplied.
                        auto const* pa = reinterpret_cast<char const*>(r.data() + (pos + length) / flen);
                        auto const* pb = reinterpret_cast<char const*>(t.r.data() + (pos + length) / flen);
                        for(size_t c = 0; c < 4; c++) {
                            _mm_prefetch(pa + 64 * c, _MM_HINT_T2);
                            _mm_prefetch(pb + 64 * c, _MM_HINT_T2);
                        }
                    }
                    auto bc = [&] [[gnu::always_inline]] (size_t c) {
                        return vftype(_mm256_broadcast_sd(tw[c] + g));
                    };
                    vpoint v1 = {bc(0), bc(1)}, v2 = {bc(2), bc(3)}, v3 = {bc(4), bc(5)};
                    auto forward = [&] [[gnu::always_inline]] (cvector const& a) {
                        auto A = a.at(pos), B = a.at(pos + 4) * v1, C = a.at(pos + 8) * v2, D = a.at(pos + 12) * v3;
                        return std::array<vpoint, 4>{(A + C) + (B + D), (A + C) - (B + D), (A - C) + vi(B - D),
                                                     (A - C) - vi(B - D)};
                    };
                    auto a = transpose(forward(*this));
                    auto b = [&] {
                        if constexpr(square) {
                            return a;
                        } else {
                            return transpose(forward(t));
                        }
                    }();
                    // The four residues are taken modulo x^4 - rt * {1, -1, i, -i}.
                    const auto flip_re = _mm256_set_pd(0., -0., -0., 0.), flip_im = _mm256_set_pd(-0., 0., -0., 0.);
                    vpoint w = {
                        vftype(_mm256_xor_pd(_mm256_blend_pd(__m256d(real(v1)), __m256d(imag(v1)), 0b1100), flip_re)),
                        vftype(_mm256_xor_pd(_mm256_blend_pd(__m256d(imag(v1)), __m256d(real(v1)), 0b1100), flip_im))};
                    auto mul = [&] [[gnu::always_inline]] (vpoint a0, vpoint a1, vpoint b0, vpoint b1) {
                        auto p = a0 * b0, q = a1 * b1;
                        return std::array<vpoint, 2>{cmadd(w, q, p), cmcross(a0 + a1, b0 + b1, p, q)};
                    };
                    auto p = mul(a[0], a[2], b[0], b[2]), q = mul(a[1], a[3], b[1], b[3]);
                    auto m = mul(a[0] + a[1], a[2] + a[3], b[0] + b[1], b[2] + b[3]);
                    auto c = transpose({cmadd(w, q[1], p[0]), (m[0] - p[0]) - q[0], p[1] + q[0], (m[1] - p[1]) - q[1]});
                    auto A = c[0], B = c[1], C = c[2], D = c[3];
                    at(pos) = (A + B) + (C + D);
                    at(pos + 8) = mulconj((A + B) - (C + D), v2);
                    at(pos + 4) = mulconj((A - B) - vi(C - D), v1);
                    at(pos + 12) = mulconj((A - B) + vi(C - D), v3);
                }
            }
        }
        // A product in two steps, this <- this * t modulo x^n - i up to the factor n / flen:
        // forward() on both operands, then multiply(t), which may be *this for a square.
        // The forward transform stops at groups of 16 points and dot_fused16 multiplies those,
        // which saves a pass over each operand and one over the result. That needs powers of
        // four, so a length 2 * 4^k takes its radix-two level at the top, modulo
        // x^(n/2) -+ sqrt(i); short lengths take the complete transform and the 4-point product.
        void forward() {
            if(!fused_leaves()) {
                return fft();
            }
            size_t n = size(), part = fused_part();
            if(part < n) {
                vpoint vrt = {vz + real(roots[4]), vz + imag(roots[4])};
                for(size_t k = 0; k < part; k += flen) {
                    auto t = at(k + part) * vrt;
                    at(k + part) = at(k) - t;
                    at(k) += t;
                }
            }
            for(size_t offset = 0; offset < n; offset += part) {
                transform<false, 0, 0, true>(n, false, offset, part);
            }
            checkpoint("fft");
        }
        void multiply(cvector const& t) {
            if(!fused_leaves()) {
                dot(t);
                return ifft<true, false>();
            }
            size_t n = size(), part = fused_part();
            dot_fused16<0>(t, 0, n);
            checkpoint("dot");
            for(size_t offset = 0; offset < n; offset += part) {
                transform<true, 0, 0, true>(n, false, offset, part);
            }
            if(part < n) {
                vpoint cvrt = {vz + real(roots[4]), vz - imag(roots[4])};
                for(size_t k = 0; k < part; k += flen) {
                    auto t = at(k) - at(k + part);
                    at(k) += at(k + part);
                    at(k + part) = t * cvrt;
                }
            }
            checkpoint("ifft");
        }
        // Radix-64 out-of-cache pass for n = 2^24, run as two tiled radix-8 stages.
        // With Fuse=1 (forward only) the first stage lifts u32 residues to Gaussian
        // coordinates on load, so the spectrum buffer is written once and never re-read
        // before the in-cache block phase. The index-keyed noise makes both branches see
        // the same representatives.
        struct fuse_args {
            const uint32_t* src = nullptr;
            size_t count = 0;
            uint64_t seed = 0;
            double a = 0, b = 0, a_over_p = 0, b_over_p = 0;
        };
        static constexpr size_t sweep_tile = 256;
        template<bool inverse, int Mode, size_t Tile, int Fuse = 0, bool Neg = false>
        void sweep8(fuse_args const& fa = {}) {
            constexpr size_t n = 1 << 24;
            static const std::array<std::array<point, 7>, 9> weights = []() {
                std::array<std::array<point, 7>, 9> table;
                for(size_t count: {size_t(1), size_t(8)}) {
                    for(size_t k = 0; k < count; k++) {
                        size_t rev = 0, x = k;
                        for(size_t c = count; c > 1; c >>= 1) {
                            rev = (rev << 1) | (x & 1);
                            x >>= 1;
                        }
                        long double angle = std::numbers::pi_v<long double> * (1 + 4 * rev) / (16 * count);
                        if(k & 1) {
                            angle -= std::numbers::pi_v<long double> / 4;
                        }
                        for(size_t j = 1; j < 8; j++) {
                            long double a = j * angle;
                            if constexpr(Mode == 0) {
                                table[(count - 1) / 7 + k][j - 1] = {double(cosl(a)), double(sinl(a))};
                            } else {
                                table[(count - 1) / 7 + k][j - 1] = {double(sinl(a)), double(tanl(a / 2))};
                            }
                        }
                    }
                }
                return table;
            }();
            auto lift = [&] [[gnu::always_inline]] (size_t idx) -> vpoint {
                i32x4 bits{};
                if(idx + 4 <= fa.count) {
                    std::memcpy(&bits, fa.src + idx, sizeof(bits));
                } else if(idx < fa.count) {
                    for(size_t j = 0; j < fa.count - idx; j++) {
                        bits[j] = int32_t(fa.src[idx + j]);
                    }
                } else {
                    return vpoint{vz, vz};
                }
                auto x = __builtin_convertvector(bits, vftype);
                u32x4 h =
                    u32x4{uint32_t(idx), uint32_t(idx + 1), uint32_t(idx + 2), uint32_t(idx + 3)} ^ uint32_t(fa.seed);
                h *= 0x9E3779B1u;
                h ^= h >> 15;
                h *= 0x85EBCA77u;
                h ^= h >> 13;
                h *= 0xC2B2AE3Du;
                h ^= h >> 16;
                auto noise = __builtin_convertvector(i32x4(h), vftype) * 0x1p-32;
                auto q = round(x * fa.a_over_p + noise), t = round(x * fa.b_over_p + noise);
                auto re = x - q * fa.a - t * fa.b, im = t * fa.a - q * fa.b;
                return vpoint{re, Neg ? -im : im};
            };
            auto stage = [&]<bool top> [[gnu::always_inline]] (size_t offset, size_t length, size_t begin, size_t end) {
                size_t step = length / 8, k = offset / length;
                auto const& w = weights[(n / length - 1) / 7 + k];
                auto rot = [&]<size_t J> [[gnu::always_inline]] (vpoint z) {
                    auto c = w[J - 1];
                    if constexpr(Mode == 0) {
                        return z * vpoint{vz + real(c), inverse ? vz - imag(c) : vz + imag(c)};
                    } else {
                        auto s = inverse ? vz - real(c) : vz + real(c), t = inverse ? vz - imag(c) : vz + imag(c);
                        auto x = vftype(_mm256_fnmadd_pd(__m256d(t), __m256d(imag(z)), __m256d(real(z))));
                        auto y = vftype(_mm256_fmadd_pd(__m256d(s), __m256d(x), __m256d(imag(z))));
                        return vpoint{vftype(_mm256_fnmadd_pd(__m256d(t), __m256d(y), __m256d(x))), y};
                    }
                };
                auto add = [] [[gnu::always_inline]] (vpoint a, vpoint b) {
                    if constexpr(Mode != 2) {
                        return a + b;
                    } else {
                        return vpoint{vftype(_mm256_fmadd_pd(__m256d(real(a)), _mm256_set1_pd(1), __m256d(real(b)))),
                                      vftype(_mm256_fmadd_pd(__m256d(imag(a)), _mm256_set1_pd(1), __m256d(imag(b))))};
                    }
                };
                auto sub = [] [[gnu::always_inline]] (vpoint a, vpoint b) {
                    if constexpr(Mode != 2) {
                        return a - b;
                    } else {
                        return vpoint{vftype(_mm256_fmsub_pd(__m256d(real(a)), _mm256_set1_pd(1), __m256d(real(b)))),
                                      vftype(_mm256_fmsub_pd(__m256d(imag(a)), _mm256_set1_pd(1), __m256d(imag(b))))};
                    }
                };
                auto d4 = [] [[gnu::always_inline]] (vpoint a, vpoint b, vpoint c, vpoint d) {
                    auto s = a + c, t = a - c, u = b + d, v = vi(b - d);
                    if constexpr(inverse) {
                        return std::array<vpoint, 4>{s + u, t - v, s - u, t + v};
                    } else {
                        return std::array<vpoint, 4>{s + u, t + v, s - u, t - v};
                    }
                };
                constexpr double q = 0.707106781186547524400844362104849039;
                auto r1 = [] [[gnu::always_inline]] (vpoint z) {
                    if constexpr(inverse) {
                        return vpoint{(real(z) + imag(z)) * q, (imag(z) - real(z)) * q};
                    } else {
                        return vpoint{(real(z) - imag(z)) * q, (real(z) + imag(z)) * q};
                    }
                };
                auto r3 = [] [[gnu::always_inline]] (vpoint z) {
                    if constexpr(inverse) {
                        return vpoint{(imag(z) - real(z)) * q, (-imag(z) - real(z)) * q};
                    } else {
                        return vpoint{(-real(z) - imag(z)) * q, (real(z) - imag(z)) * q};
                    }
                };
                std::array<vpoint*, 8> input, output;
                for(size_t j = 0; j < 8; j++) {
                    input[j] = output[j] = r.data() + (offset + begin + j * step) / flen;
                }
                if(k & 1) {
                    constexpr std::array<size_t, 8> perm = {7, 6, 4, 5, 0, 1, 2, 3};
                    for(size_t j = 0; j < 8; j++) {
                        if constexpr(inverse) {
                            input[j] = output[perm[j]];
                        } else {
                            output[j] = input[perm[j]];
                        }
                    }
                }
                constexpr bool fused_in = top && Fuse == 1 && !inverse;
                for(size_t j = 0; j < (end - begin) / flen; j++) {
                    size_t base = offset + begin + j * flen;
                    auto in = [&]<size_t S> [[gnu::always_inline]] () {
                        if constexpr(fused_in) {
                            return lift(base + S * step);
                        } else {
                            return input[S][j];
                        }
                    };
                    if constexpr(!inverse) {
                        auto E =
                            d4(in.template operator()<0>(), rot.template operator()<2>(in.template operator()<2>()),
                               rot.template operator()<4>(in.template operator()<4>()),
                               rot.template operator()<6>(in.template operator()<6>()));
                        auto O = d4(rot.template operator()<1>(in.template operator()<1>()),
                                    rot.template operator()<3>(in.template operator()<3>()),
                                    rot.template operator()<5>(in.template operator()<5>()),
                                    rot.template operator()<7>(in.template operator()<7>()));
                        auto a = O[0], b = r1(O[1]), c = vi(O[2]), d = r3(O[3]);
                        output[0][j] = add(E[0], a);
                        output[1][j] = sub(E[0], a);
                        output[2][j] = add(E[2], c);
                        output[3][j] = sub(E[2], c);
                        output[4][j] = add(E[1], b);
                        output[5][j] = sub(E[1], b);
                        output[6][j] = add(E[3], d);
                        output[7][j] = sub(E[3], d);
                    } else {
                        auto E = d4(add(input[0][j], input[1][j]), add(input[4][j], input[5][j]),
                                    add(input[2][j], input[3][j]), add(input[6][j], input[7][j]));
                        auto O = d4(sub(input[0][j], input[1][j]), r1(sub(input[4][j], input[5][j])),
                                    -vi(sub(input[2][j], input[3][j])), r3(sub(input[6][j], input[7][j])));
                        output[0][j] = E[0];
                        output[1][j] = rot.template operator()<1>(O[0]);
                        output[2][j] = rot.template operator()<2>(E[1]);
                        output[3][j] = rot.template operator()<3>(O[1]);
                        output[4][j] = rot.template operator()<4>(E[2]);
                        output[5][j] = rot.template operator()<5>(O[2]);
                        output[6][j] = rot.template operator()<6>(E[3]);
                        output[7][j] = rot.template operator()<7>(O[3]);
                    }
                }
            };
            constexpr size_t h = n / 64;
            for(size_t j = 0; j < h; j += Tile) {
                size_t end = std::min(h, j + Tile);
                auto first = [&]() {
                    for(size_t t = 0; t < 8; t++) {
                        stage.template operator()<true>(0, n, j + t * h, end + t * h);
                    }
                };
                auto second = [&]() {
                    for(size_t k = 0; k < 8; k++) {
                        stage.template operator()<false>(k * n / 8, n / 8, j, end);
                    }
                };
                if constexpr(inverse) {
                    second();
                    first();
                } else {
                    first();
                    second();
                }
            }
        }
        // Product for n = 2^24: the top three stages split each input into 64 independent
        // blocks. Both forward transforms read the u32 inputs directly; each block then
        // completes its two forward transforms, the product, and the inverse before the
        // final three inverse stages combine the results.
        // Fusing the Gaussian lift into the first pass saves a write and a read of each
        // spectrum, but makes that pass compute-bound on the judge (measured slower there),
        // so it stays opt-in; by default both spectra are filled first and swept in place.
        static constexpr bool fuse_forward = false;
        template<bool Neg, bool Fused = fuse_forward, bool Square = false>
        void cache_product(cvector& b, fuse_args const& fa = {}, fuse_args const& fb = {}) {
            constexpr size_t n = 1 << 24, block = 1 << 18;
            prepare_roots(n / 16);
            prepare_shear_roots();
            if constexpr(Fused) {
                sweep8<false, 2, sweep_tile, 1, Neg>(fa);
                if constexpr(!Square) {
                    b.sweep8<false, 2, sweep_tile, 1, Neg>(fb);
                }
            } else {
                sweep8<false, 2, sweep_tile>();
                if constexpr(!Square) {
                    b.sweep8<false, 2, sweep_tile>();
                }
            }
            checkpoint("sweep forward");
            for(size_t offset = 0; offset < n; offset += block) {
                transform<false, n, block, true>(n, false, offset, block);
                if constexpr(!Square) {
                    b.transform<false, n, block, true>(n, false, offset, block);
                }
                dot_fused16<n, Square>(b, offset, block);
                transform<true, n, block, true>(n, false, offset, block);
            }
            checkpoint("blocks");
            sweep8<true, 2, sweep_tile>();
            checkpoint("sweep inverse");
        }
        static constexpr size_t pre_evals = 1 << 16;
        static const std::array<size_t, pre_evals> eval_args;
        static const std::array<point, pre_evals> evalp;

    private:
        // The power of four that the fused product works on: all of n = 4^k, half of n = 2 * 4^k.
        size_t fused_part() const {
            return size() >> (std::countr_zero(size()) % 2);
        }
        bool fused_leaves() const {
            return fused_part() >= 16 * dot_tile;
        }
        // Tile two radix-four stages together before descending into each child.
        template<bool inverse, size_t fixed = 0, size_t range_fixed = 0, bool omit16 = false>
        void transform(size_t input_n, bool parity, size_t range_offset = 0, size_t range_length = 0) {
            if constexpr(range_fixed) {
                range_length = range_fixed;
            }
            const size_t n = fixed ? fixed : input_n;
            if constexpr(!range_fixed) {
                prepare_roots(n / 16);
                if constexpr(fixed == (1 << 24)) {
                    prepare_shear_roots();
                }
            }
            size_t log_n = std::countr_zero(n);
            auto butterfly = [&] [[gnu::always_inline]] (size_t offset, size_t length, size_t begin, size_t end) {
                if constexpr(omit16) {
                    if(length == 16) {
                        return;
                    }
                }
                size_t step = length / 4, log_length = std::countr_zero(length), k = offset >> log_length;
                auto *p0 = r.data() + (offset + begin) / flen, *p1 = r.data() + (offset + begin + step) / flen,
                     *p2 = r.data() + (offset + begin + 2 * step) / flen,
                     *p3 = r.data() + (offset + begin + 3 * step) / flen;
                auto run = [&]<bool shear> [[gnu::always_inline]] () {
                    vpoint v1, v2, v3;
                    vftype t1{}, t2{}, t3{};
                    if constexpr(shear && fixed == (1 << 24)) {
                        auto const& c = shear_roots[((n >> log_length) - 1) / 3 + k];
                        v1 = {vz, inverse ? vz - real(c[0]) : vz + real(c[0])};
                        v2 = {vz, inverse ? vz - real(c[1]) : vz + real(c[1])};
                        v3 = {vz, inverse ? vz - real(c[2]) : vz + real(c[2])};
                        t1 = inverse ? vz - imag(c[0]) : vz + imag(c[0]);
                        t2 = inverse ? vz - imag(c[1]) : vz + imag(c[1]);
                        t3 = inverse ? vz - imag(c[2]) : vz + imag(c[2]);
                    } else {
                        point e = k < pre_evals ? evalp[k] : extra[k - pre_evals];
                        point rt = roots[log_n + 5 - log_length] * e;
                        v1 = {vz + real(rt), inverse ? vz - imag(rt) : vz + imag(rt)};
                        if constexpr(shear) {
                            if(k & 1) {
                                if constexpr(inverse) {
                                    v1 = vi(v1);
                                } else {
                                    v1 = -vi(v1);
                                }
                            }
                        }
                        v2 = v1 * v1;
                        v3 = v1 * v2;
                        if constexpr(shear) {
                            t1 = imag(v1) / (vz + 1.0 + real(v1));
                            t2 = imag(v2) / (vz + 1.0 + real(v2));
                            t3 = imag(v3) / (vz + 1.0 + real(v3));
                        }
                    }
                    auto rotate = [] [[gnu::always_inline]] (vpoint z, vpoint v, vftype t) {
                        if constexpr(!shear) {
                            return z * v;
                        } else {
                            auto x = vftype(_mm256_fnmadd_pd(__m256d(t), __m256d(imag(z)), __m256d(real(z))));
                            auto y = vftype(_mm256_fmadd_pd(__m256d(imag(v)), __m256d(x), __m256d(imag(z))));
                            return vpoint{vftype(_mm256_fnmadd_pd(__m256d(t), __m256d(y), __m256d(x))), y};
                        }
                    };
                    auto *i0 = p0, *i1 = p1, *i2 = p2, *i3 = p3, *o0 = p0, *o1 = p1, *o2 = p2, *o3 = p3;
                    if constexpr(shear) {
                        if(k & 1) {
                            if constexpr(inverse) {
                                i0 = p3;
                                i1 = p2;
                                i2 = p0;
                                i3 = p1;
                            } else {
                                o0 = p3;
                                o1 = p2;
                                o2 = p0;
                                o3 = p1;
                            }
                        }
                    }
                    for(size_t j = 0; j < (end - begin) / flen; j++) {
                        auto A = i0[j], B = i1[j], C = i2[j], D = i3[j];
                        if constexpr(inverse) {
                            o0[j] = (A + B) + (C + D);
                            o2[j] = rotate((A + B) - (C + D), v2, t2);
                            o1[j] = rotate((A - B) - vi(C - D), v1, t1);
                            o3[j] = rotate((A - B) + vi(C - D), v3, t3);
                        } else {
                            B = rotate(B, v1, t1);
                            C = rotate(C, v2, t2);
                            D = rotate(D, v3, t3);
                            o0[j] = (A + C) + (B + D);
                            o1[j] = (A + C) - (B + D);
                            o2[j] = (A - C) + vi(B - D);
                            o3[j] = (A - C) - vi(B - D);
                        }
                    }
                };
                if(length >= shear_min<fixed>) {
                    run.template operator()<true>();
                } else {
                    run.template operator()<false>();
                }
            };
            auto recurse = [&](this auto const& self, size_t offset, size_t length) -> void {
                if(length < 4 * flen) {
                    return;
                }
                if(length >= (1 << 15)) {
                    size_t step = length / 16;
                    if constexpr(inverse) {
                        for(size_t t = 0; t < 16; t++) {
                            self(offset + t * step, step);
                        }
                    }
                    for(size_t j = 0; j < step; j += 256) {
                        size_t end = std::min(step, j + 256);
                        if constexpr(inverse) {
                            for(size_t t = 0; t < 4; t++) {
                                butterfly(offset + t * length / 4, length / 4, j, end);
                            }
                            for(size_t t = 0; t < 4; t++) {
                                butterfly(offset, length, j + t * step, end + t * step);
                            }
                        } else {
                            for(size_t t = 0; t < 4; t++) {
                                butterfly(offset, length, j + t * step, end + t * step);
                            }
                            for(size_t t = 0; t < 4; t++) {
                                butterfly(offset + t * length / 4, length / 4, j, end);
                            }
                        }
                    }
                    if constexpr(!inverse) {
                        for(size_t t = 0; t < 16; t++) {
                            self(offset + t * step, step);
                        }
                    }
                } else if(length >= (size_t(1) << (6 + parity))) {
                    auto finish = [&]<bool par>() {
                        constexpr size_t chunk = size_t(1) << (6 + par);
                        constexpr size_t bottom = size_t(1) << (4 + par);
                        auto small = [&]<size_t L> [[gnu::always_inline]] (this auto const& self, size_t pos) -> void {
                            if constexpr(inverse && L > bottom) {
                                for(size_t q = 0; q < 4; q++) {
                                    self.template operator()<L / 4>(pos + q * (L / 4));
                                }
                            }
                            butterfly(pos, L, 0, L / 4);
                            if constexpr(!inverse && L > bottom) {
                                for(size_t q = 0; q < 4; q++) {
                                    self.template operator()<L / 4>(pos + q * (L / 4));
                                }
                            }
                        };
                        for(size_t leaf = offset; leaf < offset + length; leaf += chunk) {
                            if constexpr(inverse) {
                                small.template operator()<chunk>(leaf);
                                size_t level =
                                    std::min<size_t>(std::countr_one(leaf + chunk - 1), std::countr_zero(length));
                                for(size_t lvl = 6 + 2 + par; lvl <= level; lvl += 2) {
                                    size_t len = size_t(1) << lvl;
                                    butterfly(leaf & ~(len - 1), len, 0, len / 4);
                                }
                            } else {
                                size_t level = std::min<size_t>(std::countr_zero(n + leaf), std::countr_zero(length));
                                level -= level % 2 != par;
                                for(size_t lvl = level; lvl >= 6 + 2 + par; lvl -= 2) {
                                    size_t len = size_t(1) << lvl;
                                    butterfly(leaf & ~(len - 1), len, 0, len / 4);
                                }
                                small.template operator()<chunk>(leaf);
                            }
                        }
                    };
                    if(parity) {
                        finish.template operator()<true>();
                    } else {
                        finish.template operator()<false>();
                    }
                } else {
                    if constexpr(inverse) {
                        for(size_t leaf = offset + 3 * flen; leaf < offset + length; leaf += 4 * flen) {
                            size_t level = std::min<size_t>(std::countr_one(leaf + 3), std::countr_zero(length));
                            for(size_t lvl = 4 + parity; lvl <= level; lvl += 2) {
                                size_t len = size_t(1) << lvl;
                                butterfly(leaf & ~(len - 1), len, 0, len / 4);
                            }
                        }
                    } else {
                        for(size_t leaf = offset; leaf < offset + length; leaf += 4 * flen) {
                            size_t level = std::min<size_t>(std::countr_zero(n + leaf), std::countr_zero(length));
                            level -= level % 2 != parity;
                            for(size_t lvl = level; lvl >= 4; lvl -= 2) {
                                size_t len = size_t(1) << lvl;
                                butterfly(leaf & ~(len - 1), len, 0, len / 4);
                            }
                        }
                    }
                }
            };
            // Radix two is performed separately at the leaves.
            recurse(range_offset, range_length ? range_length : n);
        }
        // Shortest butterfly that uses the shear rotation; the fixed 2^24 transform reads its
        // shear roots from a table, so they are worth using down to the last in-block level.
        template<size_t fixed>
        static constexpr size_t shear_min = fixed == (1 << 24) ? 64 : 256;
        static big_vector<std::array<point, 3>> shear_roots;
        static void prepare_shear_roots() {
            constexpr size_t n = 1 << 24;
            if(!shear_roots.empty()) {
                return;
            }
            shear_roots.resize((n / 16 - 1) / 3, std::array<point, 3>{});
            for(size_t len = n; len >= shear_min<n>; len /= 4) {
                size_t count = n / len, base = (count - 1) / 3;
                point factor = roots[29 - std::countr_zero(len)];
                for(size_t k = 0; k < count; k++) {
                    point rt = factor * (k < pre_evals ? evalp[k] : extra[k - pre_evals]);
                    vpoint v1 = {vz + real(rt), vz + imag(rt)};
                    if(k & 1) {
                        v1 = -vi(v1);
                    }
                    vpoint v2 = v1 * v1, v3 = v1 * v2;
                    vftype t1 = imag(v1) / (vz + 1.0 + real(v1)), t2 = imag(v2) / (vz + 1.0 + real(v2)),
                           t3 = imag(v3) / (vz + 1.0 + real(v3));
                    shear_roots[base + k] = {point(imag(v1)[0], t1[0]), point(imag(v2)[0], t2[0]),
                                             point(imag(v3)[0], t3[0])};
                }
            }
        }
        static big_vector<point> extra;
        // Keep the usual table small; cache additional roots for large transforms.
        static void prepare_roots(size_t n) {
            if(n <= pre_evals + extra.size()) {
                return;
            }
            size_t old = extra.size();
            extra.resize(std::bit_ceil(n) - pre_evals);
            static const std::array<point, 256> coarse = []() {
                std::array<point, 256> out;
                for(size_t i = 0; i < 256; i++) {
                    out[i] = polar<ftype>(1., std::numbers::pi * double((eval_args[256 + i] - 1) / 2) / 512.0);
                }
                return out;
            }();
            for(size_t h = pre_evals + old; h < pre_evals + extra.size(); h *= 2) {
                for(size_t i = h; i < 2 * h; i += 256) {
                    point fine = polar<ftype>(1., std::numbers::pi / double(4 * h) * double(eval_arg(4 * i)));
                    for(size_t j = 0; j < 256; j++) {
                        extra[i + j - pre_evals] = coarse[j] * fine;
                    }
                }
            }
        }
    };

    big_vector<std::array<point, 3>> cvector::shear_roots;
    big_vector<point> cvector::extra;

    const std::array<size_t, cvector::pre_evals> cvector::eval_args = []() {
        std::array<size_t, pre_evals> res = {};
        for(size_t i = 1; i < pre_evals; i++) {
            res[i] = res[i >> 1] | (i & 1) << (std::bit_width(i) - 1);
        }
        return res;
    }();
    const std::array<point, cvector::pre_evals> cvector::evalp = []() {
        std::array<point, pre_evals> res = {};
        res[0] = 1;
        for(size_t n = 1; n < pre_evals; n++) {
            res[n] = polar<ftype>(1., std::numbers::pi * ftype(eval_args[n]) / ftype(4 * std::bit_floor(n)));
        }
        return res;
    }();
}
#pragma GCC pop_options

#line 6 "cp-algo/math/fft_simple.hpp"
CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo::math::fft {
    struct dft_simple {
        cp_algo::math::fft::cvector cv;

        dft_simple(auto const& a, size_t n): cv(n) {
            for(size_t i = 0; i < std::min(std::size(a), n); i++) {
                real(cv.at(i))[i % 4] = ftype(a[i]);
                imag(cv.at(i))[i % 4] = ftype(i + n < std::size(a) ? a[i + n] : 0);
            }
            checkpoint("dft64 init");
            cv.fft();
        }

        void dot(dft_simple const& t) {
            cv.dot(t.cv);
        }

        void recover_mod(auto &res, size_t k) {
            cv.ifft();
            size_t n = cv.size();
            for(size_t i = 0; i < std::min(k, n); i++) {
                res[i] = llround(real(cv.get(i)));
            }
            for(size_t i = n; i < k; i++) {
                res[i] = llround(imag(cv.get(i - n)));
            }
            cp_algo::checkpoint("recover mod");
        }
    };

    // Multiplies a and b, assuming perfect precision and no overflow
    void conv_simple(auto& a, auto const& b) {
        if (empty(a) || empty(b)) {
            a.clear();
            return;
        }
        size_t n = a.size(), m = b.size();
        size_t N = std::max(flen, std::bit_ceil(n + m - 1) / 2);
        dft_simple A(a, N), B(b, N);
        A.dot(B);
        a.resize(n + m - 1);
        A.recover_mod(a, n + m - 1);
    }
}
#pragma GCC pop_options

#line 5 "cp-algo/math/bigint.hpp"
#include <bits/stdc++.h>

namespace cp_algo::math {
    enum base_v {
        x10 = uint64_t(1e16),
        x16 = uint64_t(1ull << 60)
    };
    template<base_v base = x10>
    struct bigint {
        static constexpr uint64_t Base = uint64_t(base);
        static constexpr uint16_t digit_length = base == x10 ? 16 : 15;
        static constexpr uint16_t sub_base = base == x10 ? 10 : 16;
        static constexpr uint32_t meta_base = base == x10 ? uint32_t(1e4) : uint32_t(1 << 15);
        big_basic_string<uint64_t> digits;
        bool negative;

        auto operator <=> (bigint const& other) const {
            auto sign = [](bigint const& x) { return x.digits.empty() ? 0 : x.negative ? -1 : 1; };
            if(auto cmp = sign(*this) <=> sign(other); cmp != 0) {
                return cmp;
            }
            auto cmp = digits.size() <=> other.digits.size();
            if(cmp == 0) {
                cmp = std::lexicographical_compare_three_way(
                    digits.rbegin(), digits.rend(), other.digits.rbegin(), other.digits.rend());
            }
            return !digits.empty() && negative ? 0 <=> cmp : cmp;
        }

        bigint() {}

        bigint(big_basic_string<uint64_t> d, bool neg): digits(std::move(d)), negative(neg) {
            normalize();
        }

        bigint& pad_inplace(size_t to_add) {
            digits.insert(0, to_add, 0);
            return normalize();
        }
        bigint& drop_inplace(size_t to_drop) {
            digits.erase(0, std::min(to_drop, size(digits)));
            return normalize();
        }
        bigint& take_inplace(size_t to_keep) {
            digits.erase(std::min(to_keep, size(digits)), std::string::npos);
            return normalize();
        }
        bigint& top_inplace(size_t to_keep) {
            if (to_keep >= size(digits)) {
                return pad_inplace(to_keep - size(digits));
            } else {
                return drop_inplace(size(digits) - to_keep);
            }
        }
        bigint pad(size_t to_add) const {
            return bigint{big_basic_string<uint64_t>(to_add, 0) + digits, negative};
        }
        bigint drop(size_t to_drop) const {
            return bigint{digits.substr(std::min(to_drop, size(digits))), negative};
        }
        bigint take(size_t to_keep) const {
            return bigint{digits.substr(0, std::min(to_keep, size(digits))), negative};
        }
        bigint top(size_t to_keep) const {
            if (to_keep >= size(digits)) {
                return pad(to_keep - size(digits));
            } else {
                return drop(size(digits) - to_keep);
            }
        }

        bigint& normalize() {
            while (!empty(digits) && digits.back() == 0) {
                digits.pop_back();
            }
            if (digits.empty()) {
                negative = false;
            }
            return *this;
        }
        bigint& negate() {
            negative ^= 1;
            return *this;
        }
        bigint operator -() {
            return bigint(*this).negate();
        }
        bigint& operator -= (const bigint& other) {
            if (negative != other.negative) {
                return (negate() += other).negate().normalize();
            }
            digits.resize(std::max(size(digits), size(other.digits)));
            bool carry = false;
            auto d_ptr = std::assume_aligned<32>(digits.data());
            auto o_ptr = std::assume_aligned<32>(other.digits.data());
            size_t N = size(other.digits);
            size_t i = 0;
            for (; i < N; i++) {
                d_ptr[i] -= o_ptr[i] + carry;
                carry = d_ptr[i] >= base;
                d_ptr[i] += carry ? uint64_t(base) : 0;
            }
            if (carry) {
                N = size(digits);   
                for (; i < N && d_ptr[i] == 0; i++) {
                    d_ptr[i] = base - 1;
                }
                if (i < N) {
                    d_ptr[i]--;
                } else {
                    // Two's complement: flip all digits then add 1
                    for (i = 0; i < N; i++) {
                        d_ptr[i] = base - d_ptr[i] - 1;
                    }
                    bool carry = true;
                    for (i = 0; i < N && carry; i++) {
                        d_ptr[i]++;
                        carry = d_ptr[i] >= base;
                        d_ptr[i] -= carry * base;
                    }
                    negate();
                }
            }
            return normalize();
        }
        bigint& operator += (const bigint& other) {
            if (negative != other.negative) {
                return (negate() -= other).negate().normalize();
            }
            digits.resize(std::max(size(digits), size(other.digits)));
            bool carry = false;
            auto d_ptr = std::assume_aligned<32>(digits.data());
            auto o_ptr = std::assume_aligned<32>(other.digits.data());
            size_t N = size(other.digits);
            size_t i = 0;
            for (; i < N; i++) {
                d_ptr[i] += o_ptr[i] + carry;
                carry = d_ptr[i] >= base;
                d_ptr[i] -= carry ? uint64_t(base) : 0;
            }
            if (carry) {
                N = size(digits);
                for (; i < N && d_ptr[i] == uint64_t(base) - 1; i++) {
                    d_ptr[i] = 0;
                }
                if (i < N) {
                    d_ptr[i]++;
                } else {
                    digits.push_back(1);
                }
            }
            return *this;
        }
        bigint(int64_t x) {
            negative = x < 0;
            x = negative ? -x : x;
            digits = x ? big_basic_string<uint64_t>{uint64_t(x)} : big_basic_string<uint64_t>{};
        }
        bigint(std::span<char> s): negative(false) {
            if (size(s) < digit_length) {
                int64_t val = 0;
                std::from_chars(s.data(), s.data() + size(s), val, sub_base);
                *this = bigint(val);
                return;
            }
            if (!empty(s) && s[0] == '-') {
                negative = true;
                s = s.subspan(1);
            }
            size_t len = size(s);
            assert(len > 0);
            size_t num_digits = (len + digit_length - 1) / digit_length;
            digits.resize(num_digits);
            size_t i = len;
            for (size_t j = 0; j < num_digits - 1; j++) {
                std::from_chars(s.data() + i - digit_length, s.data() + i, digits[j], sub_base);
                i -= digit_length;
            }
            std::from_chars(s.data(), s.data() + i, digits.back(), sub_base);
            normalize();
        }

        bigint operator + (const bigint& other) const {
            return bigint(*this) += other;
        }
        bigint operator - (const bigint& other) const {
            return bigint(*this) -= other;
        }
        void to_metabase() {
            auto N = ssize(digits);
            digits.resize(4 * N);
            for (auto i = N - 1; i >= 0; i--) {
                uint64_t val = digits[i];
                digits[4 * i] = val % meta_base;
                val /= meta_base;
                digits[4 * i + 1] = val % meta_base;
                val /= meta_base;
                digits[4 * i + 2] = val % meta_base;
                val /= meta_base;
                digits[4 * i + 3] = val;
            }
        }
        void from_metabase() {
            auto N = (ssize(digits) + 3) / 4;
            digits.resize(4 * N);
            uint64_t carry = 0;
            for (int i = 0; i < N; i++) {
                __uint128_t val = digits[4 * i + 3];
                val = val * meta_base + digits[4 * i + 2];
                val = val * meta_base + digits[4 * i + 1];
                val = val * meta_base + digits[4 * i];
                val += carry;
                digits[i] = uint64_t(val % base);
                carry = uint64_t(val / base);
            }
            digits.resize(N);
            while (carry) {
                digits.push_back(carry % base);
                carry /= base;
            }
        }
        bigint& operator *= (int64_t other) {
            if (other < 0) {
                negative ^= 1;
                other = -other;
            }
            if (other == 0) {
                return *this = bigint(0);
            } else if (other == 1) {
                return *this;
            }
            uint64_t carry = 0;
            for (auto &d: digits) {
                __uint128_t val = __uint128_t(d) * other + carry;
                d = uint64_t(val % base);
                carry = uint64_t(val / base);
            }
            if (carry) {
                digits.push_back(carry % base);
                carry /= base;
            }
            return *this;
        }
        bigint operator * (int64_t other) const {
            return bigint(*this) *= other;
        }
        friend bigint operator * (int64_t lhs, const bigint& rhs) {
            return bigint(rhs) *= lhs;
        }
        bigint& mul_inplace(auto &&other) {
            negative ^= other.negative;
            auto n = size(digits), m = size(other.digits);
            if (n < m) {
                std::swap(n, m);
                std::swap(digits, other.digits);
            }
            if (m <= 1) {
                return *this *= int64_t(m == 0 ? 0 : other.digits[0]);
            }
            // Small m: use schoolbook long multiplication in base `Base`
            // Threshold chosen empirically to avoid FFT overhead on small sizes
            constexpr size_t SMALL_M_THRESHOLD = 32;
            if (m <= SMALL_M_THRESHOLD) {
                big_basic_string<uint64_t> res;
                res.assign(n + m, 0);
                for (size_t i = 0; i < n; i++) {
                    if (digits[i] == 0) continue;
                    uint64_t carry = 0;
                    for (size_t j = 0; j < m; j++) {
                        __uint128_t cur = res[i + j]
                                        + (__uint128_t)digits[i] * other.digits[j]
                                        + carry;
                        res[i + j] = uint64_t(cur % Base);
                        carry = uint64_t(cur / Base);
                    }
                    size_t k = i + m;
                    if (carry) {
                        uint64_t cur = res[k] + carry;
                        res[k] = cur % Base;
                        carry = cur / Base;
                        k++;
                    }
                }
                digits = std::move(res);
                return normalize();
            }
            to_metabase();
            other.to_metabase();
            fft::conv_simple(digits, other.digits);
            from_metabase();
            return normalize();
        }
        bigint& operator *= (bigint const& other) {
            return mul_inplace(bigint(other));
        }
        bigint operator * (const bigint& other) const {
            return bigint(*this).mul_inplace(bigint(other));
        }
    };

    template<base_v base>
    decltype(std::cin)& operator >> (decltype(std::cin) &in, cp_algo::math::bigint<base> &x) {
        std::string s;
        in >> s;
        x = {s};
        return in;
    }

    template<base_v base, bool fill = true>
    auto& print_digit(auto &out, uint64_t d) {
        char buf[16];
        auto [ptr, ec] = std::to_chars(buf, buf + sizeof(buf), d, bigint<base>::sub_base);
        if constexpr (base == x16) {
            std::ranges::transform(buf, buf, toupper);
        }
        auto len = ptr - buf;
        if constexpr (fill) {
            out << std::string(bigint<base>::digit_length - len, '0');
        }
        return out << std::string_view(buf, len);
    }

    template<bool fill_all = false, base_v base>
    auto& print_bigint(auto &out, cp_algo::math::bigint<base> const& x) {
        if (x.negative) {
            out << '-';
        }
        if (empty(x.digits)) {
            return print_digit<base, fill_all>(out, 0);
        }
        print_digit<base, fill_all>(out, x.digits.back());
        for (auto d: x.digits | std::views::reverse | std::views::drop(1)) {
            print_digit<base, true>(out, d);
        }
        return out;
    }

    template<base_v base>
    decltype(std::cout)& operator << (decltype(std::cout) &out, cp_algo::math::bigint<base> const& x) {
        return print_bigint(out, x);
    }
}


#line 12 "verify/bigint/multiplication.test.cpp"

using namespace std;
using namespace cp_algo::math;

void solve() {
    bigint a, b;
    cin >> a >> b;
    a.mul_inplace(b);
    cout << a << "\n";
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    //cp_algo::checkpoint<1>();
}

Test cases

Env Name Status Elapsed Memory
g++ example_00 :heavy_check_mark: AC 2 ms 4 MB
g++ fft_killer_00 :heavy_check_mark: AC 29 ms 41 MB
g++ fft_killer_01 :heavy_check_mark: AC 30 ms 41 MB
g++ large_00 :heavy_check_mark: AC 36 ms 13 MB
g++ large_01 :heavy_check_mark: AC 37 ms 13 MB
g++ large_02 :heavy_check_mark: AC 37 ms 12 MB
g++ large_small_00 :heavy_check_mark: AC 30 ms 29 MB
g++ max_max_00 :heavy_check_mark: AC 32 ms 41 MB
g++ max_max_01 :heavy_check_mark: AC 32 ms 41 MB
g++ max_max_02 :heavy_check_mark: AC 31 ms 41 MB
g++ max_max_03 :heavy_check_mark: AC 31 ms 41 MB
g++ max_max_04 :heavy_check_mark: AC 31 ms 41 MB
g++ max_max_05 :heavy_check_mark: AC 31 ms 41 MB
g++ max_max_06 :heavy_check_mark: AC 31 ms 41 MB
g++ max_max_07 :heavy_check_mark: AC 31 ms 41 MB
g++ medium_00 :heavy_check_mark: AC 28 ms 12 MB
g++ medium_01 :heavy_check_mark: AC 27 ms 12 MB
g++ medium_02 :heavy_check_mark: AC 28 ms 12 MB
g++ small_00 :heavy_check_mark: AC 33 ms 12 MB
g++ zero_00 :heavy_check_mark: AC 6 ms 8 MB
Back to top page