結果
| 問題 | No.3669 误差绝不允许 |
| コンテスト | |
| ユーザー |
👑  みうね
|
| 提出日時 | 2026-08-13 00:53:35 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 806 ms / 3,000 ms |
| + 425µs | |
| コード長 | 62,068 bytes |
| 記録 | |
| コンパイル時間 | 10,619 ms |
| コンパイル使用メモリ | 699,220 KB |
| 実行使用メモリ | 34,292 KB |
| 最終ジャッジ日時 | 2026-09-04 22:24:27 |
| 合計ジャッジ時間 | 23,190 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
using O=void;using R=long long;using ab=long double;using af=bool;using aq=double;using az=unsigned;using aA=unsigned char;using aK=char;using aO=unsigned long long;using aP=__uint128_t;using aT=__int128_t;
#include <algorithm>
#include <any>
#include <array>
#include <atomic>
#include <barrier>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfenv>
#include <cfloat>
#include <charconv>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <clocale>
#include <cmath>
#include <codecvt>
#include <compare>
#include <complex>
#include <concepts>
#include <condition_variable>
#include <coroutine>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstring>
#include <ctime>
#include <cuchar>
#include <cwchar>
#include <cwctype>
#include <deque>
#include <exception>
#include <execution>
#include <filesystem>
#define aU const
#define aV return
#define aX constexpr
#define aZ template
#define bd operator
#define bh int
#define bi static_cast
#define bq reinterpret_cast
#define br class
#define bs static
#define bz auto
#define bD noexcept
#define bE namespace
#define bF using
#define bI for
#define bJ while
#define bQ inline
#define ca struct
#define cb this
#define cd friend
#define cg unsigned
#define ch typename
#define ci false
#define cj continue
#define cp requires
#define cq else
#define cw true
#define cI sizeof
#define cJ decltype
#define cK delete
#define dp private
#define dq explicit
#define dr public
#include <format>
#include <forward_list>
#include <fstream>
#include <functional>
#include <future>
#include <iomanip>
#include <initializer_list>
#include <iostream>
#include <ios>
#include <iosfwd>
#include <istream>
#include <iterator>
#include <latch>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <memory_resource>
#include <mutex>
#include <new>
#include <numbers>
#include <numeric>
#include <optional>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <semaphore>
#include <set>
#include <shared_mutex>
#include <source_location>
#include <span>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <stop_token>
#include <streambuf>
#include <string>
#include <string_view>
#include <syncstream>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
aZ<br...T>bF aB=std::pair<T...>;
#include <valarray>
#include <variant>
#include <vector>
aZ<br...T>bF F=std::vector<T...>;
#include <version>
#include <sys/stat.h>
#include <unistd.h>
#include <immintrin.h>
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#define dump(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(...)
bE bc{bE ew{bE au{aZ<br T,br=O>ca iM:std::false_type{};aZ<br T>ca iM<T,std::void_t<cJ(std::begin(std::declval<T&>())),cJ(std::end(std::declval<T&>()))>>:std::true_type{};aZ<br T>bQ aX af ev=iM<T>::value;aZ<br T>bF jU=cJ(*std::begin(std::declval<T&>()));aZ<br T>bF kn=std::remove_cv_t<std::remove_reference_t<jU<T>>>;aZ<br T,br=O>ca hO{bF type=kn<T>;};aZ<br T>ca hO<T,std::void_t<ch std::remove_cv_t<std::remove_reference_t<T>>::value_type>>{bF type=ch std::remove_cv_t<std::remove_reference_t<T>>::value_type;};aZ<br T>bF hI=ch hO<T>::type;aZ<br T>ca ib:std::false_type{};aZ<br T,std::size_t N>ca ib<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,aK>>{};aZ<br T>ca ke:std::bool_constant<std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,aU aK*>||std::is_same_v<std::decay_t<T>,aK*>||ib<std::remove_reference_t<T>>::value>{};aZ<br T>bQ aX af fs=ke<T>::value;aZ<br T,br=O>ca hX:std::false_type{};aZ<br T>ca hX<T,std::void_t<cJ(std::declval<aU T&>().val())>>:std::true_type{};aZ<br T>bQ aX af hS=hX<T>::value;aZ<br T,br=O>ca hM:std::false_type{};aZ<br T>ca hM<T,std::void_t<cJ(T::D()),cJ(T::cT(std::declval<uint32_t>()))>>:std::true_type{};aZ<br T>bQ aX af jP=hM<T>::value;aZ<br T>bQ aX af fB=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,aT>||std::is_same_v<std::remove_cv_t<T>,aP>;aZ<br T>bQ aX af gt=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,aT>;aZ<br T>ca go{bF type=std::make_unsigned_t<T>;};aZ<>ca go<aT>{bF type=aP;};aZ<>ca go<aP>{bF type=aP;};aZ<br T>bF kc=ch go<std::remove_cv_t<T>>::type;}ca dx{bs aX bh cz=1<<20;dp:std::FILE*dZ;aK ba[cz];bh an;bh bK;bh fr;af gu;af ja(){an=0;if(gu){ssize_t ae;do{ae=::read(fr,ba,cz);}bJ(ae<0&&errno==EINTR);if(ae<=0){bK=0;aV ci;}bK=bh(ae);}cq{bK=bh(std::fread(ba,1,cz,dZ));}aV bK!=0;}aZ<br T>af jL(T&w){if(!fE())aV ci;bh c=bS();af cC=ci;if(c=='-'){cC=cw;c=bS();}if aX(au::gt<T>){T o=0;bJ('0'<=c&&c<='9'){o=cC?o*10-(c-'0'):o*10+(c-'0');c=bS();}w=o;}cq{T o=0;bJ('0'<=c&&c<='9'){o=o*10+T(c-'0');c=bS();}w=cC?T(0)-o:o;}aV cw;}af kh(){if(bK-an>=64)aV cw;aU bh dz=bK-an;if(dz>0)std::memmove(ba,ba+an,dz);aU bh kP=bh(std::fread(ba+dz,1,cz-dz,dZ));an=0;bK=dz+kP;if(bK<cz)ba[bK]='\0';aV bK!=0;}dr:dq dx(std::FILE*fS=stdin):dZ(fS),an(0),bK(0),fr(::fileno(fS)),gu([&]{ca stat jd;aV fr>=0&&::fstat(fr,&jd)==0&&!S_ISREG(jd.st_mode);}()){}dx(aU dx&)=cK;dx&bd=(aU dx&)=cK;bh bS(){if(an==bK&&!ja())aV EOF;aV ba[an++];}af fE(){bh c=bS();bJ(c!=EOF&&c<=' ')c=bS();if(c==EOF)aV ci;--an;aV cw;}af read(aK&w){if(!fE())aV ci;w=aK(bS());aV cw;}af read(std::string&w){if(!fE())aV ci;w.clear();bJ(cw){aU bh begin=an;bJ(an<bK&&bi<aA>(ba[an])>' '){++an;}w.append(ba+begin,an-begin);if(an<bK){++an;aV cw;}if(!ja())aV cw;}}af read(af&w){bh x;if(!read(x))aV ci;w=x!=0;aV cw;}aZ<br T>std::enable_if_t<au::fB<T>&&!std::is_same_v<std::remove_cv_t<T>,af>&&!std::is_same_v<std::remove_cv_t<T>,aK>,af>read(T&w){if(gu)aV jL(w);if(!kh())aV ci;bh c=bi<aA>(ba[an++]);bJ(c<=' ')c=bi<aA>(ba[an++]);af cC=ci;if(c=='-'){cC=cw;c=bi<aA>(ba[an++]);}if aX(au::gt<T>){T o=0;bJ('0'<=c&&c<='9'){aU bh ad=c-'0';aU bh al=bi<aA>(ba[an])-'0';if(0<=al&&al<=9){o=cC?o*100-(ad*10+al):o*100+(ad*10+al);++an;}cq{o=cC?o*10-ad:o*10+ad;}c=bi<aA>(ba[an++]);}w=o;}cq{T o=0;bJ('0'<=c&&c<='9'){aU az ad=az(c-'0');aU bh al=bi<aA>(ba[an])-'0';if(0<=al&&al<=9){o=o*100+T(ad*10+az(al));++an;}cq{o=o*10+T(ad);}c=bi<aA>(ba[an++]);}w=cC?T(0)-o:o;}if(an>bK)an=bK;aV cw;}aZ<br T>std::enable_if_t<std::is_floating_point_v<T>,af>read(T&w){if(!fE())aV ci;bh c=bS();af cC=ci;if(c=='-'||c=='+'){cC=c=='-';c=bS();}ab o=0;bJ('0'<=c&&c<='9'){o=o*10+(c-'0');c=bS();}if(c=='.'){ab jg=0.1L;c=bS();bJ('0'<=c&&c<='9'){o+=(c-'0')*jg;jg*=0.1L;c=bS();}}if(c=='e'||c=='E'){c=bS();af hQ=ci;if(c=='-'||c=='+'){hQ=c=='-';c=bS();}bh bl=0;bJ('0'<=c&&c<='9'){bl=bl*10+(c-'0');c=bS();}ab hc=1;ab gY=10;bJ(bl>0){if(bl&1)hc*=gY;gY*=gY;bl>>=1;}o=hQ?o/hc:o*hc;}w=bi<T>(cC?-o:o);aV cw;}aZ<br T>std::enable_if_t<au::hS<T>&&!au::fB<T>&&!au::ev<T>,af>read(T&w){R x;if(!read(x))aV ci;if aX(au::jP<T>){if(x>=0&&uint64_t(x)<uint64_t(T::D())){w=T::cT(uint32_t(x));}cq{w=T(x);}}cq{w=T(x);}aV cw;}aZ<br eb,br eX>af read(aB<eb,eX>&w){if(!read(w.first))aV ci;aV read(w.second);}aZ<br dh>std::enable_if_t<au::ev<dh>&&!au::fs<dh>,af>read(dh&hb){bF dR=au::hI<dh>;aX af fR=au::ev<dR>&&!au::fs<dR>;bI(bz&&w:hb){if aX(std::is_same_v<dR,af>&&!fR){af x;if(!read(x))aV ci;w=x;}cq{if(!read(w))aV ci;}}aV cw;}aZ<br eb,br eX,br...hf>af read(eb&ad,eX&al,hf&...rest){if(!read(ad))aV ci;aV read(al,rest...);}aZ<br T>dx&bd>>(T&w){if(!read(w))std::abort();aV*cb;}};ca cY{bs aX bh cz=1<<20;dp:bQ bs aU bz eR=[]{std::array<aK,40000>o{};bI(bh i=0;i<10000;i++){bh w=i;bI(bh j=3;j>=0;j--){o[4*i+j]=aK('0'+w%10);w/=10;}}aV o;}();std::FILE*dZ;aK ba[cz];bh an;bh eS;std::chars_format fA;aK gj;dr:dq cY(std::FILE*fS=stdout):dZ(fS),an(0),eS(6),fA(std::chars_format::general),gj(' '){}cY(aU cY&)=cK;cY&bd=(aU cY&)=cK;~cY(){fU();}O fU(){if(an!=0){std::fwrite(ba,1,an,dZ);an=0;}std::fflush(dZ);}O cA(aK c){if(an==cz)fU();ba[an++]=c;}O bM(aU aK*s){bJ(*s!='\0')cA(*s++);}O bM(aU std::string&s){std::size_t bv=0;bJ(bv<s.size()){if(an==cz)fU();aU std::size_t ez=std::min<std::size_t>(cz-an,s.size()-bv);std::memcpy(ba+an,s.data()+bv,ez);an+=bh(ez);bv+=ez;}}O bM(aK c){cA(c);}O bM(af w){cA(w?'1':'0');}aZ<br T>std::enable_if_t<std::is_floating_point_v<T>>bM(T w){aK df[128];bz[end,kR]=std::to_chars(df,df+cI(df),w,fA,eS);if(kR!=std::errc())std::abort();bI(aU aK*gL=df;gL!=end;gL++){cA(*gL);}}aZ<br T>std::enable_if_t<au::fB<T>&&!std::is_same_v<std::remove_cv_t<T>,af>&&!std::is_same_v<std::remove_cv_t<T>,aK> >bM(T w){bF jl=std::remove_cv_t<T>;bF eV=au::kc<jl>;eV aR;if aX(au::gt<jl>){if(w<0){cA('-');aR=eV(0)-eV(w);}cq{aR=eV(w);}}cq{aR=w;}if(aR==0){cA('0');aV;}az iW[16];bh ce=0;bJ(aR>=10000){aU eV ay=aR/10000;iW[ce++]=az(aR-ay*10000);aR=ay;}if(an>cz-64)fU();aU az cE=az(aR);aU aK*ad=eR.data()+4*cE;bh hm=cE<10?3:cE<100?2:cE<1000?1:0;bI(;hm<4;hm++)ba[an++]=ad[hm];bJ(ce--){aU aK*df=eR.data()+4*iW[ce];std::memcpy(ba+an,df,4);an+=4;}}aZ<br T>std::enable_if_t<au::hS<T>&&!au::fB<T>&&!au::ev<T> >bM(aU T&w){bM(w.val());}aZ<br eb,br eX>O bM(aU aB<eb,eX>&w){bM(w.first);cA(' ');bM(w.second);}aZ<br dh>std::enable_if_t<au::ev<dh>&&!au::fs<dh> >bM(aU dh&hb){bF dR=au::hI<aU dh>;aX af fR=au::ev<dR>&&!au::fs<dR>;af ad=cw;bI(aU bz&w:hb){if(!ad)cA(fR?'\n':gj);ad=ci;if aX(std::is_same_v<dR,af>&&!fR){bM(bi<af>(w));}cq{bM(w);}}}aZ<br eb,br...hf>O gZ(aU eb&ad,aU hf&...rest){bM(ad);((cA(' '),bM(rest)),...);}O println(){cA('\n');}O lB(bh bT){eS=bT;}O lL(bh bT=6){fA=std::chars_format::fixed;eS=bT;}O lF(bh bT=6){fA=std::chars_format::general;eS=bT;}O lw(aK kG){gj=kG;}aZ<br...Args>O println(aU Args&...args){gZ(args...);cA('\n');}aZ<br T>cY&bd<<(aU T&w){bM(w);aV*cb;}};}}bF bE std;bE bc{bE cN{bQ ew::dx&cu(){bs ew::dx gB;aV gB;}bQ ew::cY&bV(){bs ew::cY gB;aV gB;}}}bF ll=R;bF Y=cg bh;bF cv=aO;bF hj=__int128;bF mf=cg __int128;
#ifdef __SIZEOF_FLOAT128__
bF md=__float128;
#endif
aZ<br T>aX T bX=0;aZ<>aX bh bX<bh> =1'000'000'000;aZ<>aX ll bX<ll> =ll(bX<bh>)*bX<bh>*2;aZ<>aX Y bX<Y> =bX<bh>;aZ<>aX cv bX<cv> =bX<ll>;aZ<>aX hj bX<hj> =hj(bX<ll>)*bX<ll>;aZ<>aX aq bX<aq> =bX<ll>;aZ<>aX ab bX<ab> =bX<ll>;bF pi=pair<bh,bh>;bF pl=pair<ll,ll>;bF vi=vector<bh>;bF vl=vector<ll>;aZ<br T>bF vc=vector<T>;aZ<br T>bF hw=vector<vc<T>>;bF mn=hw<bh>;bF mo=hw<ll>;aZ<br T>bF lc=vector<hw<T>>;aZ<br T>bF kZ=vector<lc<T>>;aZ<br T>bF lU=vector<kZ<T>>;aZ<br T>bF ml=std::priority_queue<T,vector<T>,greater<T>>;aZ<br T,br U>bF mg=unordered_map<T,U>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) vector<vector<vector<vector<type>>>> name( a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR1(a) for (ll _ = 0; _ < (ll)a; ++_)
#define FOR2(i, a) for (ll i = 0; i < (ll)a; ++i)
#define FOR3(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < (ll)b; i += (c))
#define FOR1_R(a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR2_R(i, a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= (ll)a; --i)
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FORI1(a) for (int _ = 0; _ < (int)a; ++_)
#define FORI2(i, a) for (int i = 0; i < (int)a; ++i)
#define FORI3(i, a, b) for (int i = a; i < (int)b; ++i)
#define FORI4(i, a, b, c) for (int i = a; i < (int)b; i += (c))
#define FORI1_R(a) for (int i = (a) - 1; i >= 0; --i)
#define FORI2_R(i, a) for (int i = (a) - 1; i >= 0; --i)
#define FORI3_R(i, a, b) for (int i = (b) - 1; i >= (int)a; --i)
#define FORI(...) overload4(__VA_ARGS__, FORI4, FORI3, FORI2, FORI1)(__VA_ARGS__)
#define FORI_R(...) overload3(__VA_ARGS__, FORI3_R, FORI2_R, FORI1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (int t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
bh gT(bh x){aV __builtin_popcount(x);}bh gT(Y x){aV __builtin_popcount(x);}bh gT(ll x){aV __builtin_popcountll(x);}bh gT(cv x){aV __builtin_popcountll(x);}bh gr(bh x){aV __builtin_parity(x);}bh gr(Y x){aV __builtin_parity(x);}bh gr(ll x){aV __builtin_parityll(x);}bh gr(cv x){aV __builtin_parityll(x);}bh gV(bh x){aV(x==0?-1:31-__builtin_clz(x));}bh gV(Y x){aV(x==0?-1:31-__builtin_clz(x));}bh gV(ll x){aV(x==0?-1:63-__builtin_clzll(x));}bh gV(cv x){aV(x==0?-1:63-__builtin_clzll(x));}bh gR(bh x){aV(x==0?-1:__builtin_ctz(x));}bh gR(Y x){aV(x==0?-1:__builtin_ctz(x));}bh gR(ll x){aV(x==0?-1:__builtin_ctzll(x));}bh gR(cv x){aV(x==0?-1:__builtin_ctzll(x));}aZ<ch T>T fT(T a,T b){aV a/b-(a%b&&(a^b)<0);}aZ<ch T>T la(T x,T y){aV fT(x+y-1,y);}aZ<ch T>T mb(T x,T y){aV x-y*fT(x,y);}aZ<ch T>pair<T,T>gP(T x,T y){T q=fT(x,y);aV{q,x-q*y};}aZ<ch T,ch U>T mh(U x_,bh n){T x=x_;T ju=1;bJ(n>0){if(n&1)ju*=x;x*=x;n>>=1;}aV ju;}aZ<ch T,ch U>T mi(aU vector<U>&A){T sm=0;bI(bz&&a:A)sm+=a;aV sm;}
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
aZ<br T,br S>bQ af lX(T&a,aU S&b){aV(a<b?a=b,1:0);}aZ<br T,br S>bQ af lY(T&a,aU S&b){aV(a>b?a=b,1:0);}vc<bh>lQ(aU string&S,aK kv){vc<bh>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-kv:-1);}aV A;}aZ<ch T,ch U>vector<T>lS(vector<U>&A,bh lj=1){bh N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(lj==0)B.erase(B.begin());aV B;}aZ<ch T>vector<bh>lN(aU vector<T>&A){vector<bh>hp(A.size());iota(all(hp),0);sort(all(hp),[&](bh i,bh j){aV(A[i]==A[j]?i<j:A[i]<A[j]);});aV hp;}aZ<ch T>vc<T>lK(aU vc<T>&A,aU vc<bh>&I){vc<T>B(I.size());FOR(i,I.size())B[i]=A[I[i]];aV B;}aZ<br...T>aX bz lh(T...a){aV lh(initializer_list<common_type_t<T...>>{a...});}aZ<br...T>aX bz lg(T...a){aV lg(initializer_list<common_type_t<T...>>{a...});}aZ<br...Ts>af jk(Ts&...ac){aV bc::cN::cu().read(ac...);}aZ<br...Ts>O gZ(aU Ts&...ac){bc::cN::bV().println(ac...);}O lV(af b){bc::cN::bV().println(b?"YES":"NO");}O lW(af b){bc::cN::bV().println(b?"Yes":"No");}O mj(){bc::cN::bV().println("YES");}O NO(){bc::cN::bV().println("NO");}O mk(){bc::cN::bV().println("Yes");}O No(){bc::cN::bV().println("No");}bz&lT=bc::cN::cu();bz&lO=bc::cN::bV();
#if (defined(__GNUC__) || defined(__clang__)) && (defined(__x86_64__) || defined(__i386__))
#define M1UNE_BIGINT_HAS_X86_SIMD 1
#endif
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__)) && !defined(M1UNE_FPS_DISABLE_X86_SIMD)
#define M1UNE_FPS_HAS_X86_SIMD 1
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
#endif
#ifdef M1UNE_FPS_HAS_X86_SIMD
bE bc{bE ho{bE au{bE cZ{bF Y=az;bF cv=aO;bF aJ=std::size_t;bF G=__m256i;bQ O as(O*p,G x){_mm256_store_si256((G*)p,x);}bQ G ai(aU O*p){aV _mm256_load_si256((aU G*)p);}aX Y eE(Y x,Y M){aV std::min(x,x-M);}aX Y mc(Y x,Y M){aV std::min(x,x+M);}aX Y eA(cv x,Y H,Y M){aV(x+cv(Y(x)*H)*M)>>32;}aX Y co(Y x,Y y,Y H,Y M){aV eA(cv(x)*y,H,M);}aX Y bn(Y x,Y y,Y H,Y M){aV eE(eA(cv(x)*y,H,M),M);}aX Y ht(Y a,Y b,Y H,Y M,Y r){bI(;b;b>>=1,a=co(a,a,H,M)){if(b&1){r=co(r,a,H,M);}}aV r;}aX Y jh(Y a,Y b,Y H,Y M,Y r){aV eE(ht(a,b,H,M,r),M);}bQ G bw(G x,G M){aV _mm256_min_epu32(x,_mm256_sub_epi32(x,M));}bQ G kN(G x,G M){aV _mm256_min_epu32(x,_mm256_add_epi32(x,M));}bQ G cF(G x,G y,G){aV _mm256_add_epi32(x,y);}bQ G bL(G x,G y,G M){aV _mm256_add_epi32(_mm256_sub_epi32(x,y),M);}bQ G bm(G x,G y,G M){aV bw(_mm256_add_epi32(x,y),M);}bQ G cf(G x,G y,G M){aV kN(_mm256_sub_epi32(x,y),M);}aZ<bh li>bQ G lP(G x,G M){aV _mm256_blend_epi32(x,_mm256_sub_epi32(M,x),li);}bQ G eA(G a,G b,G H,G M){G c=_mm256_mul_epu32(a,H),d=_mm256_mul_epu32(b,H);c=_mm256_mul_epu32(c,M),d=_mm256_mul_epu32(d,M);aV _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(a,c),32),_mm256_add_epi64(b,d),0xaa);}bQ G co(G a,G b,G H,G M){aV eA(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32)),H,M);}bQ G bn(G a,G b,G H,G M){aV bw(co(a,b,H,M),M);}bQ G dC(G a,G b,G H,G M){aV eA(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),b),H,M);}bQ G cm(G a,G b,G fg,G M){G cc=_mm256_mul_epu32(a,fg),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),fg);G c=_mm256_mul_epu32(a,b),d=_mm256_mul_epu32(_mm256_srli_epi64(a,32),b);cc=_mm256_mul_epu32(cc,M),dd=_mm256_mul_epu32(dd,M);aV _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}bQ G lM(G a,G b,G fg,G M){G cc=_mm256_mul_epu32(a,fg),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(fg,32));G c=_mm256_mul_epu32(a,b),d=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32));cc=_mm256_mul_epu32(cc,M),dd=_mm256_mul_epu32(dd,M);aV _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}bQ G fG(G a,G bu,G M){G cc=_mm256_mul_epu32(a,bu),c=_mm256_mul_epu32(a,_mm256_srli_epi64(bu,32));cc=_mm256_mul_epu32(cc,M);aV bw(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),M);}aX bz ct=26,ex=6;aX bz dE=aJ(1)<<ex;ca dQ{Y D,cQ,H,aE,r2,r3,cS,fP,eg[ct];alignas(32)std::array<Y,8>fW[ct-2],fV[ct-2],hi,hn,hh,fm[ct-3],jb[ct-3],fh[ct-3],iS[ct-3],hr,hs,iY,iZ,hk,iQ,hl,iR;aX dQ(aU Y m):D(m),cQ(m*2),H([&]{Y n=2+m;bI(bh i=0;i<4;++i){n*=2+m*n;}aV n;}()),aE((-m)%m),r2((-cv(m))%m),r3(bn(r2,r2,H,m)),cS{},fP{},eg{},fW{},fV{},hi{},hn{},hh{},fm{},jb{},fh{},iS{},hr{},hs{},iY{},iZ{},hk{},iQ{},hl{},iR{}{aU bh k=__builtin_ctz(m-1);Y _g=co(3,r2,H,D);bI(;;++_g){if(jh(_g,D>>1,H,D,aE)!=aE){break;}}_g=ht(_g,D>>k,H,D,aE);Y bZ[ct-1],bP[ct-1];bZ[k-2]=_g,bP[k-2]=ht(_g,D-2,H,D,aE);bI(bh i=k-2;i>0;--i){bZ[i-1]=co(bZ[i],bZ[i],H,D);bP[i-1]=co(bP[i],bP[i],H,D);}eg[k-1]=jh(_g,3,H,D,aE);bI(bh i=k-1;i>0;--i){eg[i-1]=bn(eg[i],eg[i],H,D);}cS=bZ[0],fP=cS*H;hi={aE,0,aE,0,aE};hn={bZ[1],0,bZ[0],0,D-bn(bZ[0],bZ[1],H,D)};hh={bP[1],0,bP[0],0,bn(bP[0],bP[1],H,D)};Y pr=aE,ei=aE;bI(bh i=0;i<k-2;++i){aU Y r=bn(pr,bZ[i+1],H,D),ri=bn(ei,bP[i+1],H,D);aU Y r2=bn(r,r,H,D),hu=bn(ri,ri,H,D);aU Y r3=bn(r,r2,H,D),jt=bn(ri,hu,H,D);fW[i]={r*H,r,r2*H,r2,r3*H,r3};fV[i]={ri*H,ri,hu*H,hu,jt*H,jt};pr=co(pr,bP[i+1],H,D),ei=co(ei,bZ[i+1],H,D);}pr=aE,ei=aE;bI(bh i=0;i<k-3;++i){aU Y r=bn(pr,bZ[i+2],H,D),ri=bn(ei,bP[i+2],H,D);fm[i][0]=fh[i][0]=aE;bI(bh j=1;j<8;++j){fm[i][j]=bn(fm[i][j-1],r,H,D);fh[i][j]=bn(fh[i][j-1],ri,H,D);}bI(bh j=0;j<8;++j){jb[i][j]=fm[i][j]*H;iS[i][j]=fh[i][j]*H;}pr=co(pr,bP[i+2],H,D),ei=co(ei,bZ[i+2],H,D);}hr={aE,aE,aE,cS,aE,aE,aE,cS};hs={aE,aE,aE,aE,aE,bZ[1],cS,bn(cS,bZ[1],H,D)};aU Y eJ=D-r2,jf=bn(cS,r2,H,D);hk={eJ,eJ,eJ,jf,eJ,eJ,eJ,jf};hl={aE,aE,aE,aE,aE,bP[1],bP[0],bn(bP[0],bP[1],H,D)};bI(bh j=0;j<8;++j){iY[j]=hr[j]*H,iZ[j]=hs[j]*H;iQ[j]=hk[j]*H,iR[j]=hl[j]*H;}}};bQ O gv(G*aU f,aU aJ n,aU dQ*aC){alignas(32)std::array<Y,8>bY[ct>>1];aU G ap=_mm256_set1_epi32(aC->D),J=_mm256_set1_epi32(aC->cQ),bH=_mm256_set1_epi32(aC->H);aU G dH=_mm256_set1_epi32(aC->cS),dD=_mm256_set1_epi32(aC->fP),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);aU bh eH=__builtin_ctzll(n);std::fill(bY,bY+(eH>>1),aC->hn);aU aJ nn=n>>(eH&1),m=std::min(n,dE),mm=std::min(nn,dE);if(nn!=n){bI(aJ i=0;i<nn;++i){bz aU p0=f+i,p1=f+nn+i;aU bz f0=ai(p0),f1=ai(p1);aU bz g0=bm(f0,f1,J),g1=bL(f0,f1,J);as(p0,g0),as(p1,g1);}}bI(aJ L=nn>>2;L>0;L>>=2){bI(aJ i=0;i<L;++i){bz aU p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aU bz g3=cm(bL(f1,f3,J),dH,dD,ap),g1=bm(f1,f3,J);aU bz g0=bm(f0,f2,J),g2=cf(f0,f2,J);aU bz h0=bm(g0,g1,J),h1=bL(g0,g1,J);aU bz h2=cF(g2,g3,J),h3=bL(g2,g3,J);as(p0,h0),as(p1,h1),as(p2,h2),as(p3,h3);}}bI(aJ j=0;j<n;j+=m){bh t=((j==0)?std::min(ex,eH):__builtin_ctzll(j))&-2,p=(t-2)>>1;bI(aJ L=(aJ(1)<<t)>>2;L>=dE;L>>=2,t-=2,--p){bz rt=ai(bY+p);aU bz r1=_mm256_permutevar8x32_epi32(rt,id);aU bz ed=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bH),id);rt=fG(rt,ai(aC->fW+__builtin_ctzll(~j>>t)),ap);aU bz r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),hq=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);aU bz ha=_mm256_shuffle_epi32(ed,_MM_PERM_BBBB),kO=_mm256_shuffle_epi32(ed,_MM_PERM_DDDD);as(bY+p,rt);bI(aJ i=0;i<L;++i){bz aU p0=f+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aU bz g1=cm(f1,r1,ed,ap),fj=cm(f3,hq,kO,ap);aU bz g2=cm(f2,r2,ha,ap),g0=bw(f0,J);aU bz h3=cm(cF(g1,fj,J),dH,dD,ap),h1=cf(g1,fj,J);aU bz h0=bm(g0,g2,J),h2=cf(g0,g2,J);aU bz u0=cF(h0,h1,J),u1=bL(h0,h1,J);aU bz u2=cF(h2,h3,J),u3=bL(h2,h3,J);as(p0,u0),as(p1,u1),as(p2,u2),as(p3,u3);}}G*aU g=f+j;bI(aJ l=mm,L=mm>>2;L;l=L,L>>=2,t-=2,--p){bz rt=ai(bY+p);bI(aJ i=(j==0?l:0),k=(j+i)>>t;i<m;i+=l,++k){aU bz r1=_mm256_permutevar8x32_epi32(rt,id);aU bz r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);aU bz hq=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);bI(aJ j=0;j<L;++j){bz aU p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aU bz g1=dC(f1,r1,bH,ap),fj=dC(f3,hq,bH,ap);aU bz g2=dC(f2,r2,bH,ap),g0=bw(f0,J);aU bz h3=cm(cF(g1,fj,J),dH,dD,ap),h1=cf(g1,fj,J);aU bz h0=bm(g0,g2,J),h2=cf(g0,g2,J);aU bz u0=cF(h0,h1,J),u1=bL(h0,h1,J);aU bz u2=cF(h2,h3,J),u3=bL(h2,h3,J);as(p0,u0),as(p1,u1),as(p2,u2),as(p3,u3);}rt=fG(rt,ai(aC->fW+__builtin_ctzll(~k)),ap);}as(bY+p,rt);}}}aZ<af eE=ci>bQ O iC(G*aU f,aJ n,aU dQ*aU aC){alignas(32)std::array<Y,8>bY[ct>>1];aU G ap=_mm256_set1_epi32(aC->D),J=_mm256_set1_epi32(aC->cQ),bH=_mm256_set1_epi32(aC->H);aU G dH=_mm256_set1_epi32(aC->cS),dD=_mm256_set1_epi32(aC->fP),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);aU bh eH=__builtin_ctzll(n);std::fill(bY,bY+(ex>>1),aC->hi);std::fill(bY+(ex>>1),bY+(ct>>1),aC->hh);aU aJ nn=n>>(eH&1),mm=std::min(nn,dE);bI(aJ j=0;j<n;j+=mm){G*aU g=f+j;bh t=2,p=0;bI(aJ l=4,L=1;l<=mm;L=l,l<<=2,t+=2,++p){bz rt=ai(bY+p);bI(aJ i=0,k=j>>t;i<mm;i+=l,++k){aU bz r1=_mm256_permutevar8x32_epi32(rt,id);aU bz r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);aU bz r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);bI(aJ j=0;j<L;++j){bz aU p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f0=ai(p0),f1=ai(p1),f2=ai(p2),f3=ai(p3);aU bz g0=bm(f0,f1,J),g1=cf(f0,f1,J);aU bz g2=bm(f2,f3,J),g3=cm(bL(f3,f2,J),dH,dD,ap);aU bz h0=cF(g0,g2,J),h1=cF(g1,g3,J);aU bz h2=bL(g0,g2,J),h3=bL(g1,g3,J);aU bz u0=bw(h0,J),u1=dC(h1,r1,bH,ap);aU bz u2=dC(h2,r2,bH,ap),u3=dC(h3,r3,bH,ap);as(p0,u0),as(p1,u1),as(p2,u2),as(p3,u3);}rt=fG(rt,ai(aC->fV+__builtin_ctzll(~k)),ap);}as(bY+p,rt);}bh tt=std::min(__builtin_ctzll(~(j>>ex))+ex,eH);bI(aJ L=dE,l=L<<2;t<=tt;L=l,l<<=2,t+=2,++p){if((j+dE)==l){if(eE&&l==n){bI(aJ i=0;i<L;++i){bz aU p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f2=ai(p2),f3=ai(p3),f0=ai(p0),f1=ai(p1);aU bz g3=cm(bL(f3,f2,J),dH,dD,ap),g2=bm(f2,f3,J);aU bz g0=bm(f0,f1,J),g1=cf(f0,f1,J);aU bz h0=bm(g0,g2,J),h1=bm(g1,g3,J);aU bz h2=cf(g0,g2,J),h3=cf(g1,g3,J);aU bz u0=bw(h0,ap),u1=bw(h1,ap);aU bz u2=bw(h2,ap),u3=bw(h3,ap);as(p0,u0),as(p1,u1),as(p2,u2),as(p3,u3);}}cq{bI(aJ i=0;i<L;++i){bz aU p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f2=ai(p2),f3=ai(p3),f0=ai(p0),f1=ai(p1);aU bz g3=cm(bL(f3,f2,J),dH,dD,ap),g2=bm(f2,f3,J);aU bz g0=bm(f0,f1,J),g1=cf(f0,f1,J);aU bz h0=bm(g0,g2,J),h1=bm(g1,g3,J);aU bz h2=cf(g0,g2,J),h3=cf(g1,g3,J);as(p0,h0),as(p1,h1),as(p2,h2),as(p3,h3);}}}cq{bz rt=ai(bY+p);aU bz r1=_mm256_permutevar8x32_epi32(rt,id);aU bz ed=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bH),id);rt=fG(rt,ai(aC->fV+__builtin_ctzll(~j>>t)),ap);aU bz r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);aU bz ha=_mm256_shuffle_epi32(ed,_MM_PERM_BBBB),kT=_mm256_shuffle_epi32(ed,_MM_PERM_DDDD);as(bY+p,rt);bI(aJ i=0;i<L;++i){bz aU p0=f+j+dE-l+i,p1=p0+L,p2=p1+L,p3=p2+L;aU bz f0=ai(p0),f1=ai(p1),f2=ai(p2),f3=ai(p3);aU bz g0=bm(f0,f1,J),g1=cf(f0,f1,J);aU bz g2=bm(f2,f3,J),g3=cm(bL(f3,f2,J),dH,dD,ap);aU bz h0=cF(g0,g2,J),h1=cF(g1,g3,J);aU bz h2=bL(g0,g2,J),h3=bL(g1,g3,J);aU bz u0=bw(h0,J),u1=cm(h1,r1,ed,ap);aU bz u2=cm(h2,r2,ha,ap),u3=cm(h3,r3,kT,ap);as(p0,u0),as(p1,u1),as(p2,u2),as(p3,u3);}}}}if(eE&&nn==n&&n<=dE){bI(aJ i=0;i<n;++i){aU bz f0=ai(f+i);as(f+i,bw(f0,ap));}}if(nn!=n){bI(aJ i=0;i<nn;++i){bz aU p0=f+i,p1=f+nn+i;aU bz f0=ai(p0),f1=ai(p1);aU bz g0=bm(f0,f1,J),g1=cf(f0,f1,J);if aX(eE){aU bz h0=bw(g0,ap),h1=bw(g1,ap);as(p0,h0),as(p1,h1);}cq{as(p0,g0),as(p1,g1);}}}}[[gnu::always_inline]]bQ G iE(aU G*f,aU G*g,G ww,G fx,G bH,G ap,G J){aU bz lk=ai(f),ln=ai(g);aU bz jv=bw(lk,J),bb=bw(dC(ln,fx,bH,ap),ap);aU bz aw=bw(dC(jv,ww,bH,ap),ap);aU bz aa=bw(jv,ap);aU bz dI=_mm256_permute2x128_si256(aa,aw,3);aU bz b0=_mm256_permute4x64_epi64(bb,0x00),b1=_mm256_shuffle_epi32(b0,_MM_PERM_CDAB);aU bz a0=aa,a1=_mm256_srli_epi64(a0,32);aU bz jq=_mm256_alignr_epi8(aa,dI,12);bz dk=_mm256_mul_epu32(a0,b0);bz dl=_mm256_mul_epu32(a1,b0);bz ee=_mm256_mul_epu32(jq,b1);bz ef=_mm256_mul_epu32(a0,b1);aU bz b2=_mm256_permute4x64_epi64(bb,0x55),b3=_mm256_shuffle_epi32(b2,_MM_PERM_CDAB);aU bz jp=_mm256_alignr_epi8(aa,dI,8);aU bz jo=_mm256_alignr_epi8(aa,dI,4);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(jp,b2));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jq,b2));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(jo,b3));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(jp,b3));aU bz b4=_mm256_permute4x64_epi64(bb,0xaa),b5=_mm256_shuffle_epi32(b4,_MM_PERM_CDAB);aU bz jn=_mm256_alignr_epi8(dI,aw,12);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(dI,b4));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jo,b4));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(jn,b5));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(dI,b5));aU bz b6=_mm256_permute4x64_epi64(bb,0xff),b7=_mm256_shuffle_epi32(b6,_MM_PERM_CDAB);aU bz jm=_mm256_alignr_epi8(dI,aw,8);aU bz le=_mm256_alignr_epi8(dI,aw,4);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(jm,b6));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jn,b6));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(le,b7));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(jm,b7));dk=_mm256_add_epi64(dk,ee);dl=_mm256_add_epi64(dl,ef);aV bw(eA(dk,dl,bH,ap),J);}bQ O jI(G*f,aU G*g,aJ lm,aU dQ*aU aC){Y RR=aC->aE;aU bz D=aC->D,H=aC->H;aU bz Fx=_mm256_set1_epi32(bn((D-((D-1)>>(__builtin_ctzll(lm)))),aC->r3,H,D));aU bz bH=_mm256_set1_epi32(H),ap=_mm256_set1_epi32(D),J=_mm256_set1_epi32(aC->cQ);bI(aJ i=0;i<lm;++i){as(f+i,iE(f+i,g+i,_mm256_set1_epi32(RR),Fx,bH,ap,J));RR=co(RR,aC->eg[__builtin_ctzll(~i)],H,D);}}bQ O jG(G*aU o,aU G*aU f,aU G*aU g,aJ lm,aU dQ*aU aC){Y RR=aC->aE;aU bz D=aC->D,H=aC->H;aU bz Fx=_mm256_set1_epi32(bn((D-((D-1)>>(__builtin_ctzll(lm)))),aC->r3,H,D));aU bz bH=_mm256_set1_epi32(H),ap=_mm256_set1_epi32(D),J=_mm256_set1_epi32(aC->cQ);bI(aJ i=0;i<lm;++i){aU bz aj=iE(f+i,g+i,_mm256_set1_epi32(RR),Fx,bH,ap,J);as(o+i,bm(ai(o+i),aj,J));RR=co(RR,aC->eg[__builtin_ctzll(~i)],H,D);}}}}}}
#endif
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC pop_options
#endif
bE bc{bE cP{aZ<uint32_t bU>ca ag{dp:uint32_t X;dr:bs aX uint32_t D(){aV bU;}bs aX ag cT(uint32_t v)bD{ag x;x.X=v;aV x;}aX ag()bD:X(0){}aZ<br dY,std::enable_if_t<std::is_integral_v<dY>,bh> =0>aX ag(dY v)bD{if aX(std::is_signed_v<dY>){int64_t x=bi<int64_t>(v)%bi<int64_t>(bU);if(x<0)x+=bU;X=bi<uint32_t>(x);}cq{X=bi<uint32_t>(bi<uint64_t>(v)%bU);}}aX uint32_t val()aU bD{aV X;}aX ag&bd++()bD{X++;if(X==bU)X=0;aV*cb;}aX ag&bd--()bD{if(X==0)X=bU;X--;aV*cb;}aX ag bd++(bh)bD{ag bg=*cb;++*cb;aV bg;}aX ag bd--(bh)bD{ag bg=*cb;--*cb;aV bg;}aX ag&bd+=(aU ag&E)bD{X+=E.X;if(X>=bU)X-=bU;aV*cb;}aX ag&bd-=(aU ag&E)bD{X-=E.X;if(X>=bU)X+=bU;aV*cb;}aX ag&bd*=(aU ag&E)bD{uint64_t z=X;z*=E.X;X=bi<uint32_t>(z%bU);aV*cb;}aX ag&bd/=(aU ag&E)bD{aV*cb*=E.inv();}aX ag bd+(aU ag&E)aU bD{aV ag(*cb)+=E;}aX ag bd-(aU ag&E)aU bD{aV ag(*cb)-=E;}aX ag bd*(aU ag&E)aU bD{aV ag(*cb)*=E;}aX ag bd/(aU ag&E)aU bD{aV ag(*cb)/=E;}aX af bd==(aU ag&E)aU bD{aV X==E.X;}aX af bd!=(aU ag&E)aU bD{aV X!=E.X;}aX ag pow(R n)aU bD{ag bg=cT(1%bU);ag x=n<0?inv():*cb;uint64_t bl=n<0?uint64_t(-(n+1))+1:uint64_t(n);bJ(bl>0){if(bl&1)bg*=x;x*=x;bl>>=1;}aV bg;}aX ag inv()aU bD{int64_t a=X,b=bU,u=1,v=0;bJ(b){int64_t t=a/b;a-=t*b;std::swap(a,b);u-=t*v;std::swap(u,v);}(O)0;u%=bU;if(u<0)u+=bU;aV cT(bi<uint32_t>(u));}cd std::ostream&bd<<(std::ostream&os,aU ag&E){aV os<<E.X;}cd std::istream&bd>>(std::istream&is,ag&E){R v;is>>v;E=ag(v);aV is;}};bF lz=ag<998244353>;bF ly=ag<1000000007>;aZ<bh Id=0>ca at{dp:uint32_t X;bQ bs uint32_t bN=1;dr:bs uint32_t D()bD{aV bN;}bs O lR(uint32_t kK)bD{(O)0;(O)0;bN=kK;}bs at cT(uint32_t v)bD{(O)0;at x;x.X=v;aV x;}at()bD:X(0){}aZ<br dY,std::enable_if_t<std::is_integral_v<dY>,bh> =0>at(dY v)bD{if aX(std::is_signed_v<dY>){int64_t x=bi<int64_t>(v)%bi<int64_t>(bN);if(x<0)x+=bN;X=bi<uint32_t>(x);}cq{X=bi<uint32_t>(bi<uint64_t>(v)%bN);}}uint32_t val()aU bD{aV X;}at&bd++()bD{X++;if(X==bN)X=0;aV*cb;}at&bd--()bD{if(X==0)X=bN;X--;aV*cb;}at bd++(bh)bD{at o=*cb;++*cb;aV o;}at bd--(bh)bD{at o=*cb;--*cb;aV o;}at&bd+=(aU at&E)bD{X+=E.X;if(X>=bN)X-=bN;aV*cb;}at&bd-=(aU at&E)bD{X-=E.X;if(X>=bN)X+=bN;aV*cb;}at&bd*=(aU at&E)bD{X=bi<uint32_t>(uint64_t(X)*E.X%bN);aV*cb;}at&bd/=(aU at&E)bD{aV*cb*=E.inv();}at bd+(aU at&E)aU bD{aV at(*cb)+=E;}at bd-(aU at&E)aU bD{aV at(*cb)-=E;}at bd*(aU at&E)aU bD{aV at(*cb)*=E;}at bd/(aU at&E)aU bD{aV at(*cb)/=E;}af bd==(aU at&E)aU bD{aV X==E.X;}af bd!=(aU at&E)aU bD{aV X!=E.X;}at pow(R bl)aU bD{at o=cT(1%bN);at dG=bl<0?inv():*cb;uint64_t aR=bl<0?uint64_t(-(bl+1))+1:uint64_t(bl);bJ(aR>0){if(aR&1)o*=dG;dG*=dG;aR>>=1;}aV o;}at inv()aU bD{int64_t a=X,b=bN,u=1,v=0;bJ(b){int64_t ay=a/b;a-=ay*b;std::swap(a,b);u-=ay*v;std::swap(u,v);}(O)0;u%=bN;if(u<0)u+=bN;aV cT(bi<uint32_t>(u));}cd std::ostream&bd<<(std::ostream&os,aU at&E){aV os<<E.X;}cd std::istream&bd>>(std::istream&is,at&E){R w;is>>w;E=at(w);aV is;}};}}bE bc{bE ho{bE au{aZ<br C,br=O>ca hN:std::false_type{};aZ<br C>ca hN<C,std::void_t<cJ(std::integral_constant<uint32_t,C::D()>{})>>:std::true_type{};aX uint32_t jK(uint32_t D){if(D==2)aV 1;if(D==167772161)aV 3;if(D==469762049)aV 3;if(D==754974721)aV 11;if(D==998244353)aV 3;if(D==1224736769)aV 3;uint32_t gA[32]={};bh ce=0;uint32_t x=D-1;bI(uint32_t p=2;uint64_t(p)*p<=x;p++){if(x%p!=0)cj;gA[ce++]=p;bJ(x%p==0)x/=p;}if(x>1)gA[ce++]=x;bI(uint32_t g=2;;g++){af ok=cw;bI(bh i=0;i<ce;i++){uint64_t w=1;uint64_t dG=g;uint32_t bl=(D-1)/gA[i];bJ(bl>0){if(bl&1)w=w*dG%D;dG=dG*dG%D;bl>>=1;}if(w==1){ok=ci;break;}}if(ok)aV g;}}aX bh ia(uint32_t x){bh o=0;bJ((x&1)==0){x>>=1;o++;}aV o;}aZ<br C>ca gy{bs aX bh db=ia(C::D()-1);std::array<C,db+1>aN;std::array<C,db+1>eu;std::array<C,db>jj;std::array<C,db>ij;std::array<C,db>iv;std::array<C,db>hJ;gy(){aX uint32_t ki=jK(C::D());bI(bh eC=1;eC<=db;eC++){aN[eC]=C(ki).pow((C::D()-1)>>eC);eu[eC]=aN[eC].inv();}C aj=1;C eP=1;bI(bh i=0;i+1<db;i++){jj[i]=aN[i+2]*aj;ij[i]=eu[i+2]*eP;aj*=eu[i+2];eP*=aN[i+2];}aj=1;eP=1;bI(bh i=0;i+2<db;i++){iv[i]=aN[i+3]*aj;hJ[i]=eu[i+3]*eP;aj*=eu[i+3];eP*=aN[i+3];}}};aZ<br C>aU gy<C>&kB(){bs aU gy<C>aI;aV aI;}aZ<br C>O fk(F<C>&a,af bf,af kA=cw){aU bh n=bh(a.size());(O)0;(O)0;aU bz&aI=kB<C>();aU bh cG=ia(uint32_t(n));if(!bf){bh aS=0;bJ(aS<cG){if(cG-aS==1){aU bh aY=1<<(cG-aS-1);C bG=1;bI(bh av=0;av<(1<<aS);av++){aU bh K=av<<(cG-aS);bI(bh i=0;i<aY;i++){aU C by=a[K+i];aU C bx=a[K+i+aY]*bG;a[K+i]=by+bx;a[K+i+aY]=by-bx;}if(av+1!=(1<<aS))bG*=aI.jj[__builtin_ctz(~uint32_t(av))];}aS++;cj;}aU bh aY=1<<(cG-aS-2);C bG=1;aU C ax=aI.aN[2];bI(bh av=0;av<(1<<aS);av++){aU C eW=bG*bG;aU C gF=eW*bG;aU bh K=av<<(cG-aS);bI(bh i=0;i<aY;i++){aU uint64_t cQ=uint64_t(C::D())*C::D();aU uint64_t a0=a[K+i].val();aU uint64_t a1=uint64_t(a[K+i+aY].val())*bG.val();aU uint64_t a2=uint64_t(a[K+i+2*aY].val())*eW.val();aU uint64_t a3=uint64_t(a[K+i+3*aY].val())*gF.val();aU uint64_t iT=uint64_t(C(a1+cQ-a3).val())*ax.val();aU uint64_t it=cQ-a2;a[K+i]=C(a0+a2+a1+a3);a[K+i+aY]=C(a0+a2+2*cQ-a1-a3);a[K+i+2*aY]=C(a0+it+iT);a[K+i+3*aY]=C(a0+it+cQ-iT);}if(av+1!=(1<<aS))bG*=aI.iv[__builtin_ctz(~uint32_t(av))];}aS+=2;}}cq{bh aS=cG;bJ(aS>0){if(aS==1){aU bh aY=1<<(cG-aS);C bG=1;bI(bh av=0;av<(1<<(aS-1));av++){aU bh K=av<<(cG-aS+1);bI(bh i=0;i<aY;i++){aU C by=a[K+i];aU C bx=a[K+i+aY];a[K+i]=by+bx;a[K+i+aY]=(by-bx)*bG;}if(av+1!=(1<<(aS-1)))bG*=aI.ij[__builtin_ctz(~uint32_t(av))];}aS--;cj;}aU bh aY=1<<(cG-aS);C bG=1;aU C jT=aI.eu[2];bI(bh av=0;av<(1<<(aS-2));av++){aU C eW=bG*bG;aU C gF=eW*bG;aU bh K=av<<(cG-aS+2);bI(bh i=0;i<aY;i++){aU uint64_t a0=a[K+i].val();aU uint64_t a1=a[K+i+aY].val();aU uint64_t a2=a[K+i+2*aY].val();aU uint64_t a3=a[K+i+3*aY].val();aU uint64_t iU=uint64_t(C((C::D()+a2-a3)*jT.val()).val());a[K+i]=C(a0+a1+a2+a3);a[K+i+aY]=C((a0+C::D()-a1+iU)*bG.val());a[K+i+2*aY]=C((a0+a1+2ULL*C::D()-a2-a3)*eW.val());a[K+i+3*aY]=C((a0+C::D()-a1+C::D()-iU)*gF.val());}if(av+1!=(1<<(aS-2)))bG*=aI.hJ[__builtin_ctz(~uint32_t(av))];}aS-=2;}if(kA){aU C fJ=C(n).inv();bI(C&w:a)w*=fJ;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
aZ<br C>__attribute__((target("avx2,bmi"),hot))F<C>jH(aU F<C>&a,aU F<C>&b){aU bh aQ=bh(a.size()+b.size()-1);bh n=1;bJ(n<aQ)n<<=1;aU af cD=&a==&b;bz*ck=bi<uint32_t*>(::bd new[](cI(uint32_t)*n,std::align_val_t(32)));bz*cM=cD?ck:bi<uint32_t*>(::bd new[](cI(uint32_t)*n,std::align_val_t(32)));if aX(std::is_same_v<C,cP::ag<998244353>>){std::memcpy(ck,a.data(),cI(uint32_t)*a.size());if(!cD)std::memcpy(cM,b.data(),cI(uint32_t)*b.size());}cq{bI(bh i=0;i<bh(a.size());i++)ck[i]=a[i].val();if(!cD)bI(bh i=0;i<bh(b.size());i++)cM[i]=b[i].val();}std::memset(ck+a.size(),0,cI(uint32_t)*(n-a.size()));if(!cD)std::memset(cM+b.size(),0,cI(uint32_t)*(n-b.size()));bs aX cZ::dQ dA(998244353);aU std::size_t dv=std::size_t(n)>>3;cZ::gv(bq<__m256i*>(ck),dv,&dA);if(!cD)cZ::gv(bq<__m256i*>(cM),dv,&dA);cZ::jI(bq<__m256i*>(ck),bq<aU __m256i*>(cM),dv,&dA);cZ::iC<cw>(bq<__m256i*>(ck),dv,&dA);F<C>o(aQ);bI(bh j=0;j<aQ;j++)o[j]=C::cT(ck[j]);::bd cK[](ck,std::align_val_t(32));if(!cD)::bd cK[](cM,std::align_val_t(32));aV o;}
#pragma GCC pop_options
#endif
}aZ<br C>F<C>jS(aU F<C>&a,aU F<C>&b){if(a.empty()||b.empty())aV{};F<C>o(a.size()+b.size()-1);if(a.size()<b.size()){bI(bh i=0;i<bh(a.size());i++){bI(bh j=0;j<bh(b.size());j++)o[i+j]+=a[i]*b[j];}}cq{bI(bh j=0;j<bh(b.size());j++){bI(bh i=0;i<bh(a.size());i++)o[i+j]+=a[i]*b[j];}}aV o;}aZ<br C>F<C>hU(aU F<C>&a,aU F<C>&b){aU bh aQ=bh(a.size()+b.size()-1);bh n=1;bJ(n<aQ)n<<=1;(O)0;
#ifdef M1UNE_FPS_HAS_X86_SIMD
if aX(C::D()==998244353){if(n>=64&&__builtin_cpu_supports("avx2"))aV au::jH(a,b);}
#endif
aU af cD=&a==&b;F<C>fa(n);std::copy(a.begin(),a.end(),fa.begin());au::fk(fa,ci);aU C fJ=C(n).inv();if(cD){bI(bh i=0;i<n;i++)fa[i]*=fa[i]*fJ;}cq{F<C>fb(n);std::copy(b.begin(),b.end(),fb.begin());au::fk(fb,ci);bI(bh i=0;i<n;i++)fa[i]*=fb[i]*fJ;}au::fk(fa,cw,ci);fa.resize(aQ);aV fa;}bE au{aZ<br C>F<C>jD(aU F<C>&a,aU F<C>&b,bh aF){(O)0;(O)0;(O)0;aU bh be=aF/2;aU bh dV=bh((a.size()+be-1)/be);aU bh dW=bh((b.size()+be-1)/be);bz eO=[&](aU F<C>&ac,bh dS){F<F<C>>ea;ea.reserve(dS);bI(bh av=0;av<dS;av++){aU bh begin=av*be;aU bh ce=std::min(be,bh(ac.size())-begin);F<C>cX(aF);std::copy_n(ac.begin()+begin,ce,cX.begin());fk(cX,ci);ea.emplace_back(std::move(cX));}aV ea;};F<F<C>>ck=eO(a,dV);F<F<C>>cM=eO(b,dW);aU bh aQ=bh(a.size()+b.size()-1);F<C>o(aQ);F<C>cL(aF);bI(bh bB=0;bB<dV+dW-1;bB++){std::fill(cL.begin(),cL.end(),C(0));aU bh gH=std::max(0,bB-(dW-1));aU bh gQ=std::min(dV-1,bB);bI(bh dc=gH;dc<=gQ;dc++){aU bh gG=bB-dc;bI(bh i=0;i<aF;i++)cL[i]+=ck[dc][i]*cM[gG][i];}fk(cL,cw);aU bh et=bB*be;aU bh gq=std::min(aF,aQ-et);bI(bh i=0;i<gq;i++)o[et+i]+=cL[i];}aV o;}
#ifdef M1UNE_FPS_HAS_X86_SIMD
br bR{dp:uint32_t*cH;dr:dq bR(std::size_t size):cH(bi<uint32_t*>(::bd new[](cI(uint32_t)*size,std::align_val_t(32)))){}bR(aU bR&)=cK;bR&bd=(aU bR&)=cK;bR(bR&&W)bD:cH(W.cH){W.cH=nullptr;}bR&bd=(bR&&W)bD{if(cb==&W)aV*cb;::bd cK[](cH,std::align_val_t(32));cH=W.cH;W.cH=nullptr;aV*cb;}~bR(){::bd cK[](cH,std::align_val_t(32));}uint32_t*data(){aV cH;}aU uint32_t*data()aU{aV cH;}};aZ<br C>__attribute__((target("avx2,bmi"),hot))F<C>jE(aU F<C>&a,aU F<C>&b,bh aF){(O)0;(O)0;(O)0;aU bh be=aF/2;aU bh dV=bh((a.size()+be-1)/be);aU bh dW=bh((b.size()+be-1)/be);bs aX cZ::dQ dA(998244353);aU std::size_t dv=std::size_t(aF)/8;bz eO=[&](aU F<C>&ac,bh dS){F<bR>ea;ea.reserve(dS);bI(bh av=0;av<dS;av++){aU bh begin=av*be;aU bh ce=std::min(be,bh(ac.size())-begin);bR cX(aF);if aX(std::is_same_v<C,cP::ag<998244353>>){std::memcpy(cX.data(),ac.data()+begin,cI(uint32_t)*ce);}cq{bI(bh i=0;i<ce;i++)cX.data()[i]=ac[begin+i].val();}std::memset(cX.data()+ce,0,cI(uint32_t)*(aF-ce));cZ::gv(bq<__m256i*>(cX.data()),dv,&dA);ea.emplace_back(std::move(cX));}aV ea;};F<bR>ck=eO(a,dV);F<bR>cM=eO(b,dW);aU bh aQ=bh(a.size()+b.size()-1);F<C>o(aQ);bR cL(aF);bI(bh bB=0;bB<dV+dW-1;bB++){std::memset(cL.data(),0,cI(uint32_t)*aF);aU bh gH=std::max(0,bB-(dW-1));aU bh gQ=std::min(dV-1,bB);bI(bh dc=gH;dc<=gQ;dc++){aU bh gG=bB-dc;cZ::jG(bq<__m256i*>(cL.data()),bq<aU __m256i*>(ck[dc].data()),bq<aU __m256i*>(cM[gG].data()),dv,&dA);}cZ::iC<cw>(bq<__m256i*>(cL.data()),dv,&dA);aU bh et=bB*be;aU bh gq=std::min(aF,aQ-et);bI(bh i=0;i<gq;i++){uint32_t w=o[et+i].val()+cL.data()[i];if(w>=C::D())w-=C::D();o[et+i]=C::cT(w);}}aV o;}
#endif
aZ<br C>F<C>jF(aU F<C>&a,aU F<C>&b,bh aF=1<<23){
#ifdef M1UNE_FPS_HAS_X86_SIMD
if(aF>=64&&__builtin_cpu_supports("avx2"))aV jE(a,b,aF);
#endif
aV jD(a,b,aF);}}aZ<br C>F<C>ip(aU F<C>&a,aU F<C>&b){if(a.empty()||b.empty())aV{};if(std::min(a.size(),b.size())<=32)aV jS(a,b);aU bh aQ=bh(a.size()+b.size()-1);bh n=1;bJ(n<aQ)n<<=1;if aX(au::hN<C>::value){if aX(C::D()==998244353){if(n>(1<<23))aV au::jF(a,b);}if((C::D()-1)%uint32_t(n)==0)aV hU(a,b);}bF cO=cP::ag<167772161>;bF bW=cP::ag<469762049>;bF bC=cP::ag<754974721>;(O)0;[[maybe_unused]]aU cg __int128 gf=bi<cg __int128>(std::min(a.size(),b.size()))*(C::D()-1)*(C::D()-1);[[maybe_unused]]aU cg __int128 lD=bi<cg __int128>(cO::D())*bW::D()*bC::D();(O)0;bz fZ=[&]<br fH>(){F<fH>in(a.size());F<fH>io(b.size());bI(bh i=0;i<bh(a.size());i++)in[i]=fH(a[i].val());bI(bh i=0;i<bh(b.size());i++)io[i]=fH(b[i].val());aV hU(in,io);};F<cO>c1=fZ.aZ bd()<cO>();F<bW>c2=fZ.aZ bd()<bW>();F<bC>c3=fZ.aZ bd()<bC>();bs aU uint64_t gg=bW(cO::D()).inv().val();bs aU uint64_t iI=cO::D()%bC::D();bs aU uint64_t kf=iI*(bW::D()%bC::D())%bC::D();bs aU uint64_t jM=bC(uint32_t(kf)).inv().val();aU uint64_t dw=C::D();aU uint64_t ir=cO::D()%dw;aU uint64_t kb=ir*(bW::D()%dw)%dw;F<C>o(aQ);bI(bh i=0;i<aQ;i++){aU uint64_t r1=c1[i].val();aU uint64_t r2=c2[i].val();aU uint64_t r3=c3[i].val();aU uint64_t ad=(r2+bW::D()-r1%bW::D())%bW::D()*gg%bW::D();aU uint64_t kk=(r1%bC::D()+iI*(ad%bC::D()))%bC::D();aU uint64_t al=(r3+bC::D()-kk)%bC::D()*jM%bC::D();uint64_t w=r1%dw;w=(w+ir*(ad%dw))%dw;w=(w+kb*(al%dw))%dw;o[i]=C::cT(uint32_t(w));}aV o;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#undef M1UNE_FPS_HAS_X86_SIMD
#endif
bE bc{bE ew{ca V{bs aX bh Z=1000000000;bs aX bh du=9;F<bh>a;bh ah;V():ah(1){}V(R v){*cb=v;}V(aU std::string&s){read(s);}V&bd=(R v){ah=1;aO aR=bi<aO>(v);if(v<0){ah=-1;aR=0-aR;}a.clear();bI(;aR>0;aR/=Z){a.push_back(bh(aR%Z));}aV*cb;}V&bd=(aU std::string&s){read(s);aV*cb;}O trim(){bJ(!a.empty()&&a.back()==0){a.pop_back();}if(a.empty())ah=1;}O read(aU std::string&s){ah=1;a.clear();bh dJ=0;bJ(dJ<(bh)s.size()&&(s[dJ]=='-'||s[dJ]=='+')){if(s[dJ]=='-')ah=-1;++dJ;}a.reserve((bh(s.size())-dJ+du-1)/du);bI(bh i=bh(s.size())-1;i>=dJ;i-=du){bh x=0;bI(bh j=std::max(dJ,i-du+1);j<=i;++j){x=x*10+(s[j]-'0');}a.push_back(x);}trim();}std::string to_string()aU{if(a.empty())aV"0";bs aU bz eR=[]{std::array<aK,40000>df{};bI(bh w=0;w<10000;++w){bh ak=w;bI(bh dj=3;dj>=0;--dj){df[4*w+dj]=aK('0'+ak%10);ak/=10;}}aV df;}();aK cE[du];aU std::to_chars_result iD=std::to_chars(cE,cE+du,a.back());(O)0;aU bh ik=bh(iD.ptr-cE);std::string bg((ah==-1)+ik+(a.size()-1)*du,'0');bh K=0;if(ah==-1)bg[K++]='-';std::copy(cE,iD.ptr,bg.begin()+K);K+=ik;bI(bh i=(bh)a.size()-2;i>=0;--i){aU az w=az(a[i]);aU az ic=w/100000000;aU az dz=w-ic*100000000;aU az iX=dz/10000;aU az kI=dz-iX*10000;bg[K]=aK('0'+ic);std::memcpy(bg.data()+K+1,eR.data()+4*iX,4);std::memcpy(bg.data()+K+5,eR.data()+4*kI,4);K+=du;}aV bg;}af is_zero()aU{aV a.empty()||(a.size()==1&&a[0]==0);}V bd-()aU{V bg=*cb;if(!is_zero())bg.ah=-ah;aV bg;}V abs()aU{V bg=*cb;bg.ah=1;aV bg;}cd af bd<(aU V&x,aU V&y){if(x.ah!=y.ah)aV x.ah<y.ah;if(x.a.size()!=y.a.size()){aV(x.ah==1)?(x.a.size()<y.a.size()):(x.a.size()>y.a.size());}bI(bh i=(bh)x.a.size()-1;i>=0;--i){if(x.a[i]!=y.a[i]){aV(x.ah==1)?(x.a[i]<y.a[i]):(x.a[i]>y.a[i]);}}aV ci;}cd af bd>(aU V&x,aU V&y){aV y<x;}cd af bd<=(aU V&x,aU V&y){aV!(y<x);}cd af bd>=(aU V&x,aU V&y){aV!(x<y);}cd af bd==(aU V&x,aU V&y){aV x.ah==y.ah&&x.a==y.a;}cd af bd!=(aU V&x,aU V&y){aV!(x==y);}V&bd+=(aU V&W){if(W.is_zero())aV*cb;if(is_zero())aV*cb=W;if(ah!=W.ah){aU bh eT=gh(a,W.a);if(eT==0){a.clear();ah=1;}cq if(eT>0){fq(a,W.a);}cq{F<bh>o=W.a;fq(o,a);a=std::move(o);ah=W.ah;}aV*cb;}hF(a,W.a);aV*cb;}V&bd-=(aU V&W){if(W.is_zero())aV*cb;if(is_zero())aV*cb=-W;if(ah!=W.ah){hF(a,W.a);aV*cb;}aU bh eT=gh(a,W.a);if(eT==0){a.clear();ah=1;}cq if(eT>0){fq(a,W.a);}cq{F<bh>o=W.a;fq(o,a);a=std::move(o);ah=-ah;}aV*cb;}V&bd*=(bh v){if(v==0||is_zero())aV*cb=0;R dT=v;if(dT<0){ah=-ah;dT=-dT;}a.reserve(a.size()+2);R ao=0;bI(bh i=0;i<(bh)a.size()||ao;++i){if(i==(bh)a.size())a.push_back(0);aU R jr=a[i]*dT+ao;ao=jr/Z;a[i]=(bh)(jr%Z);}trim();aV*cb;}dp:bs aX bh jJ=128;bs aX bh jV=224;bs aX bh gb=64;bs aX bh da=1<<15;ca P{aq aD;aq ax;P bd+(aU P&W)aU{aV{aD+W.aD,ax+W.ax};}P bd-(aU P&W)aU{aV{aD-W.aD,ax-W.ax};}P bd*(aU P&W)aU{aV{aD*W.aD-ax*W.ax,aD*W.ax+ax*W.aD};}P bd*(aq jc)aU{aV{aD*jc,ax*jc};}P conjugate()aU{aV{aD,-ax};}};ca gs{P bB;P ec;};bs aU F<P>&eU(bh size){bs F<P>aI(2,P{1,0});if(bh(aI.size())<size){bh ae=bh(aI.size());aI.resize(size);bJ(ae<size){aU ab je=std::numbers::pi_v<ab>/ae;aU ab iK=std::cos(je);aU ab hZ=std::sin(je);bI(bh i=ae;i<2*ae;++i){aI[i]=aI[i/2];if(i&1){aU ab aD=aI[i].aD;aU ab ax=aI[i].ax;aI[i]={aq(aD*iK-ax*hZ),aq(aD*hZ+ax*iK)};}}ae*=2;}}aV aI;}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
__attribute__((target("avx2,fma"),always_inline))bs bQ __m256d multiply_complex(__m256d w,__m256d aN){aU __m256d aD=_mm256_movedup_pd(w);aU __m256d ax=_mm256_permute_pd(w,0xf);aU __m256d swapped_root=_mm256_permute_pd(aN,0x5);aV _mm256_fmaddsub_pd(aD,aN,_mm256_mul_pd(ax,swapped_root));}__attribute__((target("avx2,fma"),hot))bs O kH(P*ac,bh size){aU F<P>&aI=eU(size);bI(bh ae=size/2;ae>0;ae/=2){bI(bh K=0;K<size;K+=2*ae){bh i=0;bI(;i+1<ae;i+=2){aU __m256d bo=_mm256_loadu_pd(bq<aU aq*>(ac+K+i));aU __m256d bp=_mm256_loadu_pd(bq<aU aq*>(ac+K+i+ae));aU __m256d aN=_mm256_loadu_pd(bq<aU aq*>(aI.data()+ae+i));_mm256_storeu_pd(bq<aq*>(ac+K+i),_mm256_add_pd(bo,bp));_mm256_storeu_pd(bq<aq*>(ac+K+i+ae),multiply_complex(_mm256_sub_pd(bo,bp),aN));}bI(;i<ae;++i){aU P bo=ac[K+i];aU P bp=ac[K+i+ae];ac[K+i]=bo+bp;ac[K+i+ae]=(bo-bp)*aI[ae+i];}}}}__attribute__((target("avx2,fma"),hot))bs O jZ(P*ac,bh size){aU F<P>&aI=eU(size);aU __m256d conjugate_mask=_mm256_setr_pd(0.0,-0.0,0.0,-0.0);bI(bh ae=1;ae<size;ae*=2){bI(bh K=0;K<size;K+=2*ae){bh i=0;bI(;i+1<ae;i+=2){aU __m256d bo=_mm256_loadu_pd(bq<aU aq*>(ac+K+i));aU __m256d w=_mm256_loadu_pd(bq<aU aq*>(ac+K+i+ae));__m256d aN=_mm256_loadu_pd(bq<aU aq*>(aI.data()+ae+i));aN=_mm256_xor_pd(aN,conjugate_mask);aU __m256d bp=multiply_complex(w,aN);_mm256_storeu_pd(bq<aq*>(ac+K+i),_mm256_add_pd(bo,bp));_mm256_storeu_pd(bq<aq*>(ac+K+i+ae),_mm256_sub_pd(bo,bp));}bI(;i<ae;++i){aU P bo=ac[K+i];aU P w=ac[K+i+ae];aU P aN=aI[ae+i];aU P bp={w.aD*aN.aD+w.ax*aN.ax,w.ax*aN.aD-w.aD*aN.ax};ac[K+i]=bo+bp;ac[K+i+ae]=bo-bp;}}}aU __m256d fC=_mm256_set1_pd(1.0/aq(size));bh i=0;bI(;i+1<size;i+=2){aU __m256d w=_mm256_loadu_pd(bq<aU aq*>(ac+i));_mm256_storeu_pd(bq<aq*>(ac+i),_mm256_mul_pd(w,fC));}bI(;i<size;++i){ac[i].aD/=size;ac[i].ax/=size;}}
#endif
bs O js(P*ac,bh size){(O)0;
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
kH(ac,size);aV;
#endif
aU F<P>&aI=eU(size);bI(bh ae=size/2;ae>0;ae/=2){bI(bh K=0;K<size;K+=2*ae){bI(bh i=0;i<ae;++i){aU P bo=ac[K+i];aU P bp=ac[K+i+ae];ac[K+i]=bo+bp;ac[K+i+ae]=(bo-bp)*aI[ae+i];}}}}bs O iq(P*ac,bh size){(O)0;
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
jZ(ac,size);aV;
#endif
aU F<P>&aI=eU(size);bI(bh ae=1;ae<size;ae*=2){bI(bh K=0;K<size;K+=2*ae){bI(bh i=0;i<ae;++i){aU P bo=ac[K+i];aU P w=ac[K+i+ae];aU P aN=aI[ae+i];aU P bp={w.aD*aN.aD+w.ax*aN.ax,w.ax*aN.aD-w.aD*aN.ax};ac[K+i]=bo+bp;ac[K+i+ae]=bo-bp;}}}aU aq fC=1.0/aq(size);bI(bh i=0;i<size;++i){ac[i].aD*=fC;ac[i].ax*=fC;}}bs P iP(aU P&w,aU P&gx){aV(w+gx)*0.5;}bs P iL(aU P&w,aU P&gx){aU P iy=w-gx;aV{iy.ax*0.5,-iy.aD*0.5};}bs O ka(P*ac,bh size){(O)0;aU bh dy=size/2;aU F<P>&aI=eU(size);bs F<P>gc;bs bh im=0;if(im!=size){gc.resize(dy);F<bh>fL(dy);aU bh kU=std::countr_zero(az(dy));bI(bh i=1;i<dy;++i){fL[i]=(fL[i/2]>>1)|((i&1)<<(kU-1));}bI(bh i=0;i<dy;++i){gc[i]=aI[dy+fL[i]];}im=size;}bI(bh i=0;i<dy;++i){aU P ad=ac[2*i];aU P al=ac[2*i+1];aU P bo=(ad+al)*0.5;aU P bp=((ad-al)*0.5)*gc[i].conjugate();ac[i]={bo.aD-bp.ax,bo.ax+bp.aD};}iq(ac,dy);}bs O bA(F<bh>&w){bJ(!w.empty()&&w.back()==0)w.pop_back();}bs af fz(aU F<bh>&Q,aU F<bh>&E){aV gh(Q,E)<0;}bs bh gh(aU F<bh>&Q,aU F<bh>&E){if(Q.size()!=E.size())aV Q.size()<E.size()?-1:1;bI(bh i=bh(Q.size())-1;i>=0;--i){if(Q[i]!=E[i])aV Q[i]<E[i]?-1:1;}aV 0;}bs O hF(F<bh>&Q,aU F<bh>&E){aU bh iN=bh(Q.size());aU bh fM=bh(E.size());aU bh size=std::max(iN,fM);if(iN<fM)Q.resize(fM);bh ao=0;bh i=0;bI(;i<fM;++i){aU R ak=(R)Q[i]+E[i]+ao;Q[i]=bh(ak>=Z?ak-Z:ak);ao=ak>=Z;}bJ(i<size&&ao){++Q[i];ao=Q[i]==Z;if(ao)Q[i]=0;++i;}if(ao)Q.push_back(1);}bs O fq(F<bh>&Q,aU F<bh>&E){(O)0;bh cn=0;bI(bh i=0;i<bh(E.size())||cn;++i){bh ak=Q[i]-cn-(i<bh(E.size())?E[i]:0);cn=ak<0;if(cn)ak+=Z;Q[i]=ak;}(O)0;bA(Q);}bs af hH(aU F<bh>&Q,aU F<bh>&E){aV!fz(E,Q);}bs F<bh>gn(aU F<bh>&Q,aU F<bh>&E){F<bh>o(std::max(Q.size(),E.size())+1);bI(bh i=0;i<bh(o.size())-1;++i){if(i<bh(Q.size()))o[i]+=Q[i];if(i<bh(E.size()))o[i]+=E[i];if(o[i]>=Z){o[i]-=Z;o[i+1]++;}}bA(o);aV o;}bs F<bh>cV(aU F<bh>&Q,aU F<bh>&E){(O)0;F<bh>o=Q;bh cn=0;bI(bh i=0;i<bh(o.size());++i){aU R ak=(R)o[i]-cn-(i<bh(E.size())?E[i]:0);if(ak<0){o[i]=bh(ak+Z);cn=1;}cq{o[i]=bh(ak);cn=0;}}(O)0;bA(o);aV o;}bs F<bh>kg(aU F<bh>&Q,aU F<bh>&E){if(Q.empty()||E.empty())aV F<bh>();F<R>aj(Q.size()+E.size());aX R dU=4LL*Z*Z;bI(bh i=0;i<bh(Q.size());++i){bI(bh j=0;j<bh(E.size());++j){aj[i+j]+=(R)Q[i]*E[j];if(aj[i+j]>=dU){aj[i+j]-=dU;aj[i+j+1]+=4LL*Z;}}}F<bh>o;o.reserve(aj.size()+1);R ao=0;bI(bh i=0;i<bh(aj.size())||ao>0;++i){if(i<bh(aj.size()))ao+=aj[i];o.push_back(bh(ao%Z));ao/=Z;}bA(o);aV o;}bs F<bh>kr(aU F<bh>&w){if(w.empty())aV F<bh>();F<R>aj(2*w.size());aX R dU=4LL*Z*Z;bI(bh i=0;i<bh(w.size());++i){aj[2*i]+=(R)w[i]*w[i];if(aj[2*i]>=dU){aj[2*i]-=dU;aj[2*i+1]+=4LL*Z;}bI(bh j=i+1;j<bh(w.size());++j){aj[i+j]+=2LL*w[i]*w[j];if(aj[i+j]>=dU){aj[i+j]-=dU;aj[i+j+1]+=4LL*Z;}}}F<bh>o;o.reserve(aj.size()+1);R ao=0;bI(bh i=0;i<bh(aj.size())||ao>0;++i){if(i<bh(aj.size()))ao+=aj[i];o.push_back(bh(ao%Z));ao/=Z;}bA(o);aV o;}bs F<bh>ft(aU F<bh>&w,bh dT){(O)0;if(w.empty()||dT==0)aV F<bh>();F<bh>o;o.reserve(w.size()+1);uint64_t ao=0;bI(bh lb:w){aU uint64_t ak=uint64_t(lb)*dT+ao;o.push_back(bh(ak%Z));ao=ak/Z;}if(ao)o.push_back(bh(ao));aV o;}bs F<bh>gp(aU F<bh>&Q,aU F<bh>&E){bF cO=cP::ag<998244353>;bF bW=cP::ag<754974721>;bF bC=cP::ag<469762049>;aU bh aQ=bh(Q.size()+E.size()-1);(O)0;bz gz=[&]<br C>(){F<C>x(Q.begin(),Q.end());if(&Q==&E)aV ho::ip(x,x);F<C>y(E.begin(),E.end());aV ho::ip(x,y);};aU F<cO>kD=gz.aZ bd()<cO>();aU F<bW>kE=gz.aZ bd()<bW>();aU F<bC>kF=gz.aZ bd()<bC>();aX uint64_t he=cO::D();aX uint64_t fe=bW::D();aX uint64_t eD=bC::D();aX uint64_t gX=he*fe;aU bs uint64_t gg=bW(he).inv().val();aU bs uint64_t jQ=bC(gX%eD).inv().val();[[maybe_unused]]aU cg __int128 gf=bi<cg __int128>(std::min(Q.size(),E.size()))*(Z-1)*(Z-1);[[maybe_unused]]aX cg __int128 lC=bi<cg __int128>(gX)*eD;(O)0;F<bh>o;o.reserve(aQ+2);cg __int128 ao=0;bI(bh i=0;i<aQ||ao>0;++i){if(i<aQ){aU uint64_t ad=kD[i].val();aU uint64_t al=kE[i].val();aU uint64_t kW=kF[i].val();aU uint64_t ko=(al+fe-ad%fe)%fe;aU uint64_t kx=ko*gg%fe;aU uint64_t ix=ad+he*kx;aU uint64_t ks=(kW+eD-ix%eD)%eD;aU uint64_t kC=ks*jQ%eD;ao+=ix+bi<cg __int128>(gX)*kC;}o.push_back(bh(ao%Z));ao/=Z;}bA(o);aV o;}ca eM{uint32_t eZ;uint32_t eY;};aZ<bh hg>bs uint32_t fw(uint64_t w){aX uint64_t fN=(uint64_t(1)<<hg)-1;w=(w&fN)+(w>>hg);w=(w&fN)+(w>>hg);if(w>=fN)w-=fN;aV uint32_t(w);}bs eM ga(aU F<bh>&w){eM o{0,0};bI(bh i=bh(w.size())-1;i>=0;--i){o.eZ=fw<31>(uint64_t(o.eZ)*Z+w[i]);o.eY=fw<29>(uint64_t(o.eY)*Z+w[i]);}aV o;}bs af kd(aU F<bh>&Q,aU F<bh>&E,aU F<bh>&aj){aU eM iH=ga(Q);aU eM iJ=ga(E);aU eM iV=ga(aj);aV iV.eZ==fw<31>(uint64_t(iH.eZ)*iJ.eZ)&&iV.eY==fw<29>(uint64_t(iH.eY)*iJ.eY);}bs F<bh>kq(aU F<bh>&Q,aU F<bh>&E){aU bh aQ=bh(Q.size()+E.size()-1);aU bh aF=bh(std::bit_ceil(az(aQ)));aU cg __int128 gf=bi<cg __int128>(std::min(Q.size(),E.size()))*2*(da-1)*((Z-1)/da);if(aF>(1<<20)||gf>=(uint64_t(1)<<50)){aV gp(Q,E);}std::unique_ptr<P[]>cr(new P[aF]);bI(bh i=0;i<bh(Q.size());++i){cr[i]={aq(Q[i]%da),aq(Q[i]/da)};}std::fill(cr.get()+Q.size(),cr.get()+aF,P{0,0});js(cr.get(),aF);aU af cD=&Q==&E;std::unique_ptr<P[]>cx(new P[aF]);if(!cD){bI(bh i=0;i<bh(E.size());++i){cx[i]={aq(E[i]%da),aq(E[i]/da)};}std::fill(cx.get()+E.size(),cx.get()+aF,P{0,0});js(cx.get(),aF);}bs F<bh>er;if(bh(er.size())<aF){aU bh km=bh(er.size());er.resize(aF);bI(bh i=std::max(1,km);i<aF;++i){er[i]=i^bh(std::bit_floor(az(i))-1);}}bz hK=[&](bh dj){aU bh dB=er[dj];aU P ie=cr[dB].conjugate();aU P gJ=iP(cr[dj],ie);aU P gC=iL(cr[dj],ie);P gM=gJ;P gE=gC;if(!cD){aU P ih=cx[dB].conjugate();gM=iP(cx[dj],ih);gE=iL(cx[dj],ih);}aU P kt=gJ*gM;aU P ii=gC*gE;aU P bB=kt+P{-ii.ax,ii.aD};aU P ec=gJ*gE+gC*gM;aV gs{bB,ec};};bI(bh i=0;i<aF;++i){aU bh dB=er[i];if(i>dB)cj;aU gs gD=hK(i);gs gi=gD;if(i!=dB)gi=hK(dB);cr[i]=gD.bB;cr[dB]=gi.bB;cx[i]=gD.ec;cx[dB]=gi.ec;}iq(cr.get(),aF);ka(cx.get(),aF);F<bh>o;o.reserve(aQ+2);cg __int128 ao=0;bI(bh i=0;i<aQ||ao>0;++i){if(i<aQ){aU R eI=std::llround(cr[i].aD);aU R ji=std::llround(cr[i].ax);aU P il=cx[i/2];aU R ec=std::llround((i&1)?il.ax:il.aD);if(eI<0||ji<0||ec<0)aV gp(Q,E);ao+=eI+bi<cg __int128>(ec)*da+bi<cg __int128>(ji)*da*da;}o.push_back(bh(ao%Z));ao/=Z;}bA(o);if(o.empty()||!kd(Q,E,o)){aV gp(Q,E);}aV o;}bs F<bh>cU(aU F<bh>&Q,aU F<bh>&E){if(Q.empty()||E.empty())aV F<bh>();if(Q.size()==1)aV ft(E,Q[0]);if(E.size()==1)aV ft(Q,E[0]);if(&Q==&E&&Q.size()<=jV){aV kr(Q);}if(std::min(Q.size(),E.size())<=jJ){aV kg(Q,E);}aV kq(Q,E);}bs aB<F<bh>,F<bh>>fy(aU F<bh>&aW,bh aM){(O)0;if(aM==1){aV std::make_pair(aW,F<bh>());}F<bh>ay(aW.size());R aL=0;bI(bh i=bh(aW.size())-1;i>=0;--i){aU R ak=aL*Z+aW[i];ay[i]=bh(ak/aM);aL=ak%aM;}bA(ay);F<bh>hT;if(aL!=0)hT.push_back(bh(aL));aV std::make_pair(std::move(ay),std::move(hT));}bs aB<F<bh>,F<bh>>hR(aU F<bh>&aW,aU F<bh>&aM){(O)0;if(aM.size()==1)aV fy(aW,aM[0]);if(fz(aW,aM)){aV std::make_pair(F<bh>(),aW);}aU bh cy=Z/(aM.back()+1);F<bh>bt(aM.size());uint64_t ao=0;bI(bh i=0;i<bh(aM.size());++i){aU uint64_t ak=uint64_t(aM[i])*cy+ao;bt[i]=bh(ak%Z);ao=ak/Z;}(O)0;F<bh>bj(aW.size()+1);ao=0;bI(bh i=0;i<bh(aW.size());++i){aU uint64_t ak=uint64_t(aW[i])*cy+ao;bj[i]=bh(ak%Z);ao=ak/Z;}bj[aW.size()]=bh(ao);aU bh cl=bh(bt.size());aU bh ig=bh(aW.size())-cl+1;aU uint64_t fv=bt.back();aU uint64_t kj=bt[cl-2];F<bh>ay(ig);bI(bh bv=ig-1;bv>=0;--bv){aU uint64_t gk=uint64_t(bj[bv+cl])*Z+bj[bv+cl-1];uint64_t dF=gk/fv;uint64_t aL=gk%fv;if(dF>=Z){dF=Z-1;aL=gk-dF*fv;}bJ(aL<Z&&dF*kj>aL*Z+bj[bv+cl-2]){--dF;aL+=fv;}uint64_t cn=0;bI(bh i=0;i<cl;++i){aU uint64_t aj=dF*uint64_t(bt[i])+cn;aU uint64_t eI=aj%Z;cn=aj/Z;if(uint64_t(bj[bv+i])<eI){bj[bv+i]=bh(uint64_t(bj[bv+i])+Z-eI);++cn;}cq{bj[bv+i]-=bh(eI);}}R hv=(R)bj[bv+cl]-bi<R>(cn);if(hv<0){--dF;uint64_t gw=0;bI(bh i=0;i<cl;++i){aU uint64_t ak=uint64_t(bj[bv+i])+bt[i]+gw;bj[bv+i]=bh(ak%Z);gw=ak/Z;}hv+=gw;}(O)0;bj[bv+cl]=bh(hv);ay[bv]=bh(dF);}bA(ay);F<bh>aL(bj.begin(),bj.begin()+cl);bA(aL);aB<F<bh>,F<bh>>eQ=fy(aL,cy);(O)0;aV std::make_pair(std::move(ay),std::move(eQ.first));}bs F<bh>reciprocal(aU F<bh>&w,bh de){(O)0;(O)0;(O)0;bh bT=de;aU bh iB=bh(w.size());bJ(bT>gb)bT=(bT+1)/2;F<bh>bf(iB+bT+1);bf.back()=1;bf=hR(bf,w).first;bJ(bT<de){F<bh>gU=cU(bf,bf);gU.insert(gU.begin(),0);aU bh ez=std::min(iB,2*bT+1);aU F<bh>cE(w.end()-ez,w.end());F<bh>fF=cU(gU,cE);(O)0;fF.erase(fF.begin(),fF.begin()+ez);F<bh>gN(bT+1);aU F<bh>iO=gn(bf,bf);gN.insert(gN.end(),iO.begin(),iO.end());bf=cV(gN,fF);(O)0;bf.erase(bf.begin());bT*=2;}(O)0;bf.erase(bf.begin(),bf.begin()+bT-de);bA(bf);aV bf;}bs aB<F<bh>,F<bh>>jX(aU F<bh>&aW,aU F<bh>&aM){(O)0;if(aM.size()<=gb||bh(aW.size())-bh(aM.size())<=gb){aV hR(aW,aM);}if(aW.size()>2*aM.size()){aU bh iA=bh(aW.size()/aM.size());aU bh jW=iA>=16?3:iA>=7?2:1;aU bh be=jW*bh(aM.size());aU bh dS=(bh(aW.size())+be-1)/be;aU bh cy=Z/(aM.back()+1);aU F<bh>bt=ft(aM,cy);aU bh de=be+3;aU F<bh>bf=reciprocal(bt,de);aU bh fI=bh(aM.size())+de;bz kp=[&](aU F<bh>&ak){aU F<bh>gd=ft(ak,cy);F<bh>gl=cU(gd,bf);F<bh>dt;if(bh(gl.size())>fI){dt.assign(gl.begin()+fI,gl.end());}F<bh>aj=cU(bt,dt);bJ(fz(gd,aj)){dt=cV(dt,F<bh>(1,1));aj=cV(aj,bt);}F<bh>eN=cV(gd,aj);bJ(hH(bt,eN)){dt=gn(dt,F<bh>(1,1));eN=cV(eN,bt);}bA(dt);bA(eN);aB<F<bh>,F<bh>>eQ=fy(eN,cy);(O)0;aV std::make_pair(std::move(dt),std::move(eQ.first));};F<bh>ay(aW.size());F<bh>aL;bI(bh av=dS-1;av>=0;--av){aU bh begin=av*be;aU bh end=std::min(begin+be,bh(aW.size()));F<bh>ak(aW.begin()+begin,aW.begin()+end);ak.insert(ak.end(),aL.begin(),aL.end());bA(ak);aB<F<bh>,F<bh>>gK=kp(ak);(O)0;std::copy(gK.first.begin(),gK.first.end(),ay.begin()+begin);aL=std::move(gK.second);}bA(ay);bA(aL);aV std::make_pair(std::move(ay),std::move(aL));}aU bh cy=Z/(aM.back()+1);aU F<bh>bj=cU(aW,F<bh>(1,cy));aU F<bh>bt=cU(aM,F<bh>(1,cy));aU bh kl=bh(bj.size());aU bh cl=bh(bt.size());aU bh de=kl-cl+2;aU F<bh>bf=reciprocal(bt,de);F<bh>ay=cU(bj,bf);aU bh fI=cl+de;(O)0;ay.erase(ay.begin(),ay.begin()+fI);F<bh>aj=cU(bt,ay);bJ(fz(bj,aj)){ay=cV(ay,F<bh>(1,1));aj=cV(aj,bt);}F<bh>aL=cV(bj,aj);bJ(hH(bt,aL)){ay=gn(ay,F<bh>(1,1));aL=cV(aL,bt);}bA(ay);bA(aL);aB<F<bh>,F<bh>>eQ=fy(aL,cy);(O)0;aV std::make_pair(std::move(ay),std::move(eQ.first));}dr:V&bd*=(aU V&W){if(is_zero()||W.is_zero())aV*cb=0;aU bh ku=ah*W.ah;a=cU(a,W.a);ah=ku;trim();aV*cb;}cd aB<V,V>gP(aU V&a1,aU V&b1){if(b1.is_zero()){throw std::domain_error("BigInt division by zero");}aB<F<bh>,F<bh>>o=jX(a1.a,b1.a);V q,r;q.a=std::move(o.first);r.a=std::move(o.second);q.ah=a1.ah*b1.ah;r.ah=a1.ah;q.trim();r.trim();aV{q,r};}cd V eF(V ad,V al){ad.ah=1;al.ah=1;bJ(!al.is_zero()){ad%=al;std::swap(ad,al);}aV ad;}V&bd/=(aU V&W){aV*cb=gP(*cb,W).first;}V&bd%=(aU V&W){aV*cb=gP(*cb,W).second;}cd V bd+(V x,aU V&y){aV x+=y;}cd V bd-(V x,aU V&y){aV x-=y;}cd V bd*(V x,aU V&y){aV x*=y;}cd V bd/(V x,aU V&y){aV x/=y;}cd V bd%(V x,aU V&y){aV x%=y;}cd std::ostream&bd<<(std::ostream&os,aU V&b){aV os<<b.to_string();}cd std::istream&bd>>(std::istream&is,V&b){std::string s;if(is>>s)b.read(s);aV is;}};}}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
#undef M1UNE_BIGINT_HAS_X86_SIMD
#endif
bE bc{bE cP{bE hW{aZ<br T>concept IntegerLike=std::signed_integral<T>||(!std::integral<T>&&std::copyable<T>&&cp(T ad,T al){T(0);T(1);{-ad}->std::same_as<T>;{ad+al}->std::same_as<T>;{ad-al}->std::same_as<T>;{ad*al}->std::same_as<T>;{ad/al}->std::same_as<T>;{ad%al}->std::same_as<T>;{ad+=al}->std::same_as<T&>;{ad-=al}->std::same_as<T&>;{ad/=al}->std::same_as<T&>;{ad==al}->std::convertible_to<af>;{ad<al}->std::convertible_to<af>;});}aZ<hW::IntegerLike T=R>ca ar{dp:bs aX af fu=std::signed_integral<T>;bF am=std::conditional_t<fu,aT,T>;bF bk=std::conditional_t<fu,aP,T>;T aH;T aG;bs aX bk aR(am w){if aX(fu){if(w<0){aV bi<bk>(-(w+1))+1;}aV bi<bk>(w);}cq{aV w<0?-w:w;}}bs aX bk eF(bk ad,bk al){bJ(al!=0){bk aL=ad%al;ad=al;al=aL;}aV ad;}bs aX T fQ(am w){if aX(fu){(O)0;(O)0;aV bi<T>(w);}cq{aV w;}}aX O assign_normalized(am numerator,am denominator){(O)0;if(numerator==0){aH=0;aG=1;aV;}bk aM=eF(aR(numerator),aR(denominator));numerator/=bi<am>(aM);denominator/=bi<am>(aM);if(denominator<0){numerator=-numerator;denominator=-denominator;}aH=fQ(numerator);aG=fQ(denominator);}bs aX ar iG(am numerator,am denominator){ar o;o.assign_normalized(numerator,denominator);aV o;}bs aB<ab,R>hL(aU T&w){std::ostringstream bV;bV<<w;aU std::string cR=bV.str();std::size_t begin=0;bh ah=1;if(!cR.empty()&&(cR[0]=='-'||cR[0]=='+')){if(cR[0]=='-')ah=-1;begin=1;}bJ(begin<cR.size()&&cR[begin]=='0')++begin;if(begin==cR.size())aV std::make_pair(0.0L,0LL);aX bh kL=std::numeric_limits<ab>::digits10+1;aU std::size_t fi=std::min<std::size_t>(kL,cR.size()-begin);ab fD=0;bI(std::size_t i=0;i<fi;++i){(O)0;fD=fD*10+(cR[begin+i]-'0');}bI(std::size_t i=1;i<fi;++i)fD/=10;aU R bl=bi<R>(cR.size()-begin-1);aV std::make_pair(ah*fD,bl);}dr:aX ar():aH(0),aG(1){}aX ar(T gI):aH(gI),aG(1){}aZ<std::integral U>cp std::constructible_from<T,U>&&(!std::same_as<std::remove_cv_t<U>,T>)aX ar(U gI):ar(T(gI)){}aX ar(T numerator,T denominator){assign_normalized(am(numerator),am(denominator));}aX T numerator()aU{aV aH;}aX T denominator()aU{aV aG;}aX af lJ()aU{aV aG==1;}aX bh ah()aU{aV(aH>0)-(aH<0);}aX ar reciprocal()aU{(O)0;aV iG(am(aG),am(aH));}aX ar abs()aU{aV aH<0?-*cb:*cb;}aX ab gm()aU cp cp(aU T&w){bi<ab>(w);}{aV bi<ab>(aH)/bi<ab>(aG);}ab gm()aU cp(!cp(aU T&w){bi<ab>(w);}){aU bz[numerator,jR]=hL(aH);aU bz[denominator,jO]=hL(aG);aV numerator/denominator*std::pow(10.0L,jR-jO);}dq aX bd ab()aU cp cp(aU T&w){bi<ab>(w);}{aV gm();}dq bd ab()aU cp(!cp(aU T&w){bi<ab>(w);}){aV gm();}aX T ma()aU{aV aH/aG;}aX T fT()aU{T ay=aH/aG;if(aH<0&&aH%aG!=0)ay-=T(1);aV ay;}aX T la()aU{T ay=aH/aG;if(0<aH&&aH%aG!=0)ay+=T(1);aV ay;}aX ar bd+()aU{aV*cb;}aX ar bd-()aU{aV iG(-am(aH),am(aG));}aX ar&bd+=(aU ar&W){bk fO=eF(bi<bk>(aG),bi<bk>(W.aG));am kw=am(W.aG)/bi<am>(fO);am iw=am(aG)/bi<am>(fO);am numerator=am(aH)*kw+am(W.aH)*iw;bk fK=fO==bk(1)?bk(1):eF(aR(numerator),fO);if(fK!=bk(1)){numerator/=bi<am>(fK);}am hG=am(W.aG);if(fK!=bk(1)){hG/=bi<am>(fK);}aH=fQ(numerator);aG=fQ(iw*hG);aV*cb;}aX ar&bd-=(aU ar&W){aV*cb+=-W;}aX ar&bd*=(aU ar&W){bk iF=eF(aR(am(aH)),bi<bk>(W.aG));bk iz=eF(aR(am(W.aH)),bi<bk>(aG));assign_normalized((am(aH)/bi<am>(iF))*(am(W.aH)/bi<am>(iz)),(am(aG)/bi<am>(iz))*(am(W.aG)/bi<am>(iF)));aV*cb;}aX ar&bd/=(aU ar&W){aV*cb*=W.reciprocal();}cd aX ar bd+(ar by,aU ar&bx){aV by+=bx;}cd aX ar bd-(ar by,aU ar&bx){aV by-=bx;}cd aX ar bd*(ar by,aU ar&bx){aV by*=bx;}cd aX ar bd/(ar by,aU ar&bx){aV by/=bx;}cd aX af bd==(aU ar&by,aU ar&bx){aV by.aH==bx.aH&&by.aG==bx.aG;}cd aX std::strong_ordering bd<=>(aU ar&by,aU ar&bx){am ad=am(by.aH)*am(bx.aG);am al=am(bx.aH)*am(by.aG);if(ad<al)aV std::strong_ordering::less;if(al<ad)aV std::strong_ordering::greater;aV std::strong_ordering::equal;}cd std::ostream&bd<<(std::ostream&bV,aU ar&w){bV<<w.aH;if(w.aG!=1){bV<<'/'<<w.aG;}aV bV;}cd std::istream&bd>>(std::istream&cu,ar&w){std::string fd;if(!(cu>>fd))aV cu;std::size_t fc=fd.find('/');if(fc!=std::string::npos&&fd.find('/',fc+1)!=std::string::npos){cu.setstate(std::ios::failbit);aV cu;}T numerator=0;T denominator=1;std::istringstream hV(fd.substr(0,fc));if(!(hV>>numerator)||hV.peek()!=std::char_traits<aK>::eof()){cu.setstate(std::ios::failbit);aV cu;}if(fc!=std::string::npos){std::istringstream hP(fd.substr(fc+1));if(!(hP>>denominator)||hP.peek()!=std::char_traits<aK>::eof()){cu.setstate(std::ios::failbit);aV cu;}}w=ar(numerator,denominator);aV cu;}};aZ<hW::IntegerLike T>aX ar<T>abs(aU ar<T>&w){aV w.abs();}}}bE bc{bE eB{aZ<br T=bh>ca hd{bF kz=T;bh dn;bh to;T dm;bh id;af di;hd():dn(-1),to(-1),dm(T()),id(-1),di(cw){}hd(bh kS,bh lo,T kQ=T(1),bh lf=-1,af kM=cw):dn(kS),to(lo),dm(kQ),id(lf),di(kM){}bh W(bh v)aU{(O)0;aV dn^to^v;}};aZ<br T=bh>ca dg{bF cB=hd<T>;bF kz=T;dp:bh _n;bh cs;F<F<cB>>_g;F<F<aB<bh,bh>>>cW;dr:dg():_n(0),cs(0){}dq dg(bh n):_n(n),cs(0),_g(n){(O)0;}bh size()aU{aV _n;}af empty()aU{aV _n==0;}bh lH()aU{aV cs;}bh lG(){_g.emplace_back();aV _n++;}bh lx(bh dn,bh to,T dm=T(1)){(O)0;(O)0;bh id=cs++;bh eh=bh(_g[dn].size());_g[dn].push_back(cB(dn,to,dm,id));cW.emplace_back();cW.back().push_back({dn,eh});aV id;}bh add_edge(bh u,bh v,T dm=T(1)){(O)0;(O)0;bh id=cs++;bh kX=bh(_g[u].size());_g[u].push_back(cB(u,v,dm,id));bh kY=bh(_g[v].size());_g[v].push_back(cB(v,u,dm,id));cW.emplace_back();cW.back().push_back({u,kX});cW.back().push_back({v,kY});aV id;}O hY(bh id,af di){(O)0;bI(bz[v,eh]:cW[id]){_g[v][eh].di=di;}}O lI(bh id){hY(id,ci);}O lE(bh id){hY(id,cw);}af lA(bh id)aU{(O)0;(O)0;bz[v,eh]=cW[id][0];aV _g[v][eh].di;}aU F<cB>&bd[](bh v)aU{(O)0;aV _g[v];}F<cB>&bd[](bh v){(O)0;aV _g[v];}aU F<F<cB>>&ky()aU{aV _g;}F<F<cB>>&ky(){aV _g;}F<cB>lZ(af jY=ci)aU{F<cB>o;o.reserve(cs);F<aK>fi(cs,ci);bI(bh v=0;v<_n;v++){bI(aU bz&e:_g[v]){if(!jY&&!e.di)cj;if(0<=e.id&&e.id<cs){if(fi[e.id])cj;fi[e.id]=cw;}o.push_back(e);}}aV o;}dg fL()aU{dg o(_n);o.cs=cs;o.cW.assign(cs,{});bI(bh v=0;v<_n;v++){bI(aU bz&e:_g[v]){bh eh=bh(o._g[e.to].size());o._g[e.to].push_back(cB(e.to,e.dn,e.dm,e.id,e.di));if(0<=e.id&&e.id<cs)o.cW[e.id].push_back({e.to,eh});}}aV o;}};}}bE bc{bE eB{aZ<br T>ca es{F<T>bO;F<aK>ey;F<bh>gS;F<bh>iu;T eG=T();af reachable(bh v)aU{(O)0;aV ey[v];}F<bh>me(bh t)aU{(O)0;F<bh>o;bI(bh v=t;v!=-1;v=gS[v])o.push_back(v);std::reverse(o.begin(),o.end());aV o;}};bE au{aZ<br T>ca ge{T bO;bh gW;};aZ<br T>ca jN{af bd()(aU ge<T>&ad,aU ge<T>&al)aU{aV al.bO<ad.bO;}};}aZ<br T>es<T>dX(aU dg<T>&g,aU F<bh>&gO){bh n=g.size();es<T>o;o.bO.resize(n);o.ey.assign(n,ci);o.gS.assign(n,-1);o.iu.assign(n,-1);bF ff=au::ge<T>;bF kJ=au::jN<T>;std::priority_queue<ff,F<ff>,kJ>fl;bI(bh s:gO){(O)0;if(o.ey[s])cj;o.ey[s]=cw;o.bO[s]=T();fl.push(ff{T(),s});}bJ(!fl.empty()){ff ak=fl.top();fl.pop();if(o.bO[ak.gW]<ak.bO)cj;bI(aU bz&e:g[ak.gW]){if(!e.di)cj;T nd=ak.bO+e.dm;if(o.ey[e.to]&&!(nd<o.bO[e.to]))cj;o.ey[e.to]=cw;o.bO[e.to]=nd;o.gS[e.to]=ak.gW;o.iu[e.to]=e.id;fl.push(ff{std::move(nd),e.to});}}aV o;}aZ<br T>es<T>dX(aU dg<T>&g,bh s){aV dX(g,F<bh>{s});}aZ<br T>es<T>dX(aU dg<T>&g,aU F<bh>&gO,aU T&eG){es<T>o=dX(g,gO);o.eG=eG;bI(bh v=0;v<bh(o.bO.size());v++){if(!o.reachable(v))o.bO[v]=eG;}aV o;}aZ<br T>es<T>dX(aU dg<T>&g,bh s,aU T&eG){aV dX(g,F<bh>{s},eG);}}}bF ld=bc::cP::ar<bc::ew::V>;O kV(){bh N,M;jk(N,M);bc::eB::dg<ld>eB(N);FOR(M){bh u,v,a,b;jk(u,v,a,b);--u,--v;eB.add_edge(u,v,{a,b});}bz bg=bc::eB::dX(eB,0);bz&bO=bg.bO;FOR(i,1,N){gZ(bO[i].numerator().to_string(),bO[i].denominator().to_string());}}bh main(){CPP_DUMP_SET_OPTION(max_line_width,80);CPP_DUMP_SET_OPTION(log_label_func,cpp_dump::log_label::filename());CPP_DUMP_SET_OPTION(enable_asterisk,cw);bh T=1;bJ(T--)kV();aV 0;}