using O=void;using R=long long;using ab=long double;using af=bool;using ap=double;using az=unsigned;using aA=unsigned char;using aK=char;using aO=unsigned long long;using aP=__uint128_t;using aS=__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 aT const
#define aU return
#define aX constexpr
#define aZ template
#define bd operator
#define bh int
#define bi static_cast
#define bp reinterpret_cast
#define bq class
#define br static
#define by auto
#define bC noexcept
#define bD namespace
#define bE using
#define bH for
#define bI while
#define bP 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<bq...T>bE aB=std::pair<T...>;
#include <valarray>
#include <variant>
#include <vector>
aZ<bq...T>bE 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(...)
bD bc{bD ew{bD au{aZ<bq T,bq=O>ca iI:std::false_type{};aZ<bq T>ca iI<T,std::void_t<cJ(std::begin(std::declval<T&>())),cJ(std::end(std::declval<T&>()))>>:std::true_type{};aZ<bq T>bP aX af ev=iI<T>::value;aZ<bq T>bE jS=cJ(*std::begin(std::declval<T&>()));aZ<bq T>bE kl=std::remove_cv_t<std::remove_reference_t<jS<T>>>;aZ<bq T,bq=O>ca hK{bE type=kl<T>;};aZ<bq T>ca hK<T,std::void_t<ch std::remove_cv_t<std::remove_reference_t<T>>::value_type>>{bE type=ch std::remove_cv_t<std::remove_reference_t<T>>::value_type;};aZ<bq T>bE hE=ch hK<T>::type;aZ<bq T>ca hX:std::false_type{};aZ<bq T,std::size_t N>ca hX<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,aK>>{};aZ<bq T>ca kc:std::bool_constant<std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,aT aK*>||std::is_same_v<std::decay_t<T>,aK*>||hX<std::remove_reference_t<T>>::value>{};aZ<bq T>bP aX af fs=kc<T>::value;aZ<bq T,bq=O>ca hT:std::false_type{};aZ<bq T>ca hT<T,std::void_t<cJ(std::declval<aT T&>().val())>>:std::true_type{};aZ<bq T>bP aX af hO=hT<T>::value;aZ<bq T,bq=O>ca hI:std::false_type{};aZ<bq T>ca hI<T,std::void_t<cJ(T::D()),cJ(T::cT(std::declval<uint32_t>()))>>:std::true_type{};aZ<bq T>bP aX af jN=hI<T>::value;aZ<bq T>bP aX af fB=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,aS>||std::is_same_v<std::remove_cv_t<T>,aP>;aZ<bq T>bP aX af gq=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,aS>;aZ<bq T>ca gl{bE type=std::make_unsigned_t<T>;};aZ<>ca gl<aS>{bE type=aP;};aZ<>ca gl<aP>{bE type=aP;};aZ<bq T>bE ka=ch gl<std::remove_cv_t<T>>::type;}ca dx{br aX bh cz=1<<20;dp:std::FILE*dZ;aK ba[cz];bh am;bh bJ;bh fr;af gr;af iY(){am=0;if(gr){ssize_t ae;do{ae=::read(fr,ba,cz);}bI(ae<0&&errno==EINTR);if(ae<=0){bJ=0;aU ci;}bJ=bh(ae);}cq{bJ=bh(std::fread(ba,1,cz,dZ));}aU bJ!=0;}aZ<bq T>af jJ(T&w){if(!fE())aU ci;bh c=bR();af cC=ci;if(c=='-'){cC=cw;c=bR();}if aX(au::gq<T>){T o=0;bI('0'<=c&&c<='9'){o=cC?o*10-(c-'0'):o*10+(c-'0');c=bR();}w=o;}cq{T o=0;bI('0'<=c&&c<='9'){o=o*10+T(c-'0');c=bR();}w=cC?T(0)-o:o;}aU cw;}af kf(){if(bJ-am>=64)aU cw;aT bh dz=bJ-am;if(dz>0)std::memmove(ba,ba+am,dz);aT bh kN=bh(std::fread(ba+dz,1,cz-dz,dZ));am=0;bJ=dz+kN;if(bJ<cz)ba[bJ]='\0';aU bJ!=0;}dr:dq dx(std::FILE*fP=stdin):dZ(fP),am(0),bJ(0),fr(::fileno(fP)),gr([&]{ca stat jb;aU fr>=0&&::fstat(fr,&jb)==0&&!S_ISREG(jb.st_mode);}()){}dx(aT dx&)=cK;dx&bd=(aT dx&)=cK;bh bR(){if(am==bJ&&!iY())aU EOF;aU ba[am++];}af fE(){bh c=bR();bI(c!=EOF&&c<=' ')c=bR();if(c==EOF)aU ci;--am;aU cw;}af read(aK&w){if(!fE())aU ci;w=aK(bR());aU cw;}af read(std::string&w){if(!fE())aU ci;w.clear();bI(cw){aT bh begin=am;bI(am<bJ&&bi<aA>(ba[am])>' '){++am;}w.append(ba+begin,am-begin);if(am<bJ){++am;aU cw;}if(!iY())aU cw;}}af read(af&w){bh x;if(!read(x))aU ci;w=x!=0;aU cw;}aZ<bq 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(gr)aU jJ(w);if(!kf())aU ci;bh c=bi<aA>(ba[am++]);bI(c<=' ')c=bi<aA>(ba[am++]);af cC=ci;if(c=='-'){cC=cw;c=bi<aA>(ba[am++]);}if aX(au::gq<T>){T o=0;bI('0'<=c&&c<='9'){aT bh ad=c-'0';aT bh al=bi<aA>(ba[am])-'0';if(0<=al&&al<=9){o=cC?o*100-(ad*10+al):o*100+(ad*10+al);++am;}cq{o=cC?o*10-ad:o*10+ad;}c=bi<aA>(ba[am++]);}w=o;}cq{T o=0;bI('0'<=c&&c<='9'){aT az ad=az(c-'0');aT bh al=bi<aA>(ba[am])-'0';if(0<=al&&al<=9){o=o*100+T(ad*10+az(al));++am;}cq{o=o*10+T(ad);}c=bi<aA>(ba[am++]);}w=cC?T(0)-o:o;}if(am>bJ)am=bJ;aU cw;}aZ<bq T>std::enable_if_t<std::is_floating_point_v<T>,af>read(T&w){if(!fE())aU ci;bh c=bR();af cC=ci;if(c=='-'||c=='+'){cC=c=='-';c=bR();}ab o=0;bI('0'<=c&&c<='9'){o=o*10+(c-'0');c=bR();}if(c=='.'){ab je=0.1L;c=bR();bI('0'<=c&&c<='9'){o+=(c-'0')*je;je*=0.1L;c=bR();}}if(c=='e'||c=='E'){c=bR();af hM=ci;if(c=='-'||c=='+'){hM=c=='-';c=bR();}bh bk=0;bI('0'<=c&&c<='9'){bk=bk*10+(c-'0');c=bR();}ab gZ=1;ab gV=10;bI(bk>0){if(bk&1)gZ*=gV;gV*=gV;bk>>=1;}o=hM?o/gZ:o*gZ;}w=bi<T>(cC?-o:o);aU cw;}aZ<bq T>std::enable_if_t<au::hO<T>&&!au::fB<T>&&!au::ev<T>,af>read(T&w){R x;if(!read(x))aU ci;if aX(au::jN<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);}aU cw;}aZ<bq eb,bq eW>af read(aB<eb,eW>&w){if(!read(w.first))aU ci;aU read(w.second);}aZ<bq dh>std::enable_if_t<au::ev<dh>&&!au::fs<dh>,af>read(dh&gY){bE dR=au::hE<dh>;aX af fO=au::ev<dR>&&!au::fs<dR>;bH(by&&w:gY){if aX(std::is_same_v<dR,af>&&!fO){af x;if(!read(x))aU ci;w=x;}cq{if(!read(w))aU ci;}}aU cw;}aZ<bq eb,bq eW,bq...hc>af read(eb&ad,eW&al,hc&...rest){if(!read(ad))aU ci;aU read(al,rest...);}aZ<bq T>dx&bd>>(T&w){if(!read(w))std::abort();aU*cb;}};ca cY{br aX bh cz=1<<20;dp:bP br aT by eQ=[]{std::array<aK,40000>o{};bH(bh i=0;i<10000;i++){bh w=i;bH(bh j=3;j>=0;j--){o[4*i+j]=aK('0'+w%10);w/=10;}}aU o;}();std::FILE*dZ;aK ba[cz];bh am;bh eR;std::chars_format fA;aK gg;dr:dq cY(std::FILE*fP=stdout):dZ(fP),am(0),eR(6),fA(std::chars_format::general),gg(' '){}cY(aT cY&)=cK;cY&bd=(aT cY&)=cK;~cY(){fR();}O fR(){if(am!=0){std::fwrite(ba,1,am,dZ);am=0;}std::fflush(dZ);}O cA(aK c){if(am==cz)fR();ba[am++]=c;}O bL(aT aK*s){bI(*s!='\0')cA(*s++);}O bL(aT std::string&s){std::size_t bt=0;bI(bt<s.size()){if(am==cz)fR();aT std::size_t ez=std::min<std::size_t>(cz-am,s.size()-bt);std::memcpy(ba+am,s.data()+bt,ez);am+=bh(ez);bt+=ez;}}O bL(aK c){cA(c);}O bL(af w){cA(w?'1':'0');}aZ<bq T>std::enable_if_t<std::is_floating_point_v<T>>bL(T w){aK df[128];by[end,kP]=std::to_chars(df,df+cI(df),w,fA,eR);if(kP!=std::errc())std::abort();bH(aT aK*gI=df;gI!=end;gI++){cA(*gI);}}aZ<bq 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> >bL(T w){bE jj=std::remove_cv_t<T>;bE eU=au::ka<jj>;eU aV;if aX(au::gq<jj>){if(w<0){cA('-');aV=eU(0)-eU(w);}cq{aV=eU(w);}}cq{aV=w;}if(aV==0){cA('0');aU;}az iS[16];bh ce=0;bI(aV>=10000){aT eU ay=aV/10000;iS[ce++]=az(aV-ay*10000);aV=ay;}if(am>cz-64)fR();aT az cE=az(aV);aT aK*ad=eQ.data()+4*cE;bh hj=cE<10?3:cE<100?2:cE<1000?1:0;bH(;hj<4;hj++)ba[am++]=ad[hj];bI(ce--){aT aK*df=eQ.data()+4*iS[ce];std::memcpy(ba+am,df,4);am+=4;}}aZ<bq T>std::enable_if_t<au::hO<T>&&!au::fB<T>&&!au::ev<T> >bL(aT T&w){bL(w.val());}aZ<bq eb,bq eW>O bL(aT aB<eb,eW>&w){bL(w.first);cA(' ');bL(w.second);}aZ<bq dh>std::enable_if_t<au::ev<dh>&&!au::fs<dh> >bL(aT dh&gY){bE dR=au::hE<aT dh>;aX af fO=au::ev<dR>&&!au::fs<dR>;af ad=cw;bH(aT by&w:gY){if(!ad)cA(fO?'\n':gg);ad=ci;if aX(std::is_same_v<dR,af>&&!fO){bL(bi<af>(w));}cq{bL(w);}}}aZ<bq eb,bq...hc>O gW(aT eb&ad,aT hc&...rest){bL(ad);((cA(' '),bL(rest)),...);}O println(){cA('\n');}O lz(bh bT){eR=bT;}O lJ(bh bT=6){fA=std::chars_format::fixed;eR=bT;}O lD(bh bT=6){fA=std::chars_format::general;eR=bT;}O lu(aK kE){gg=kE;}aZ<bq...Args>O println(aT Args&...args){gW(args...);cA('\n');}aZ<bq T>cY&bd<<(aT T&w){bL(w);aU*cb;}};}}bE bD std;bD bc{bD cN{bP ew::dx&cu(){br ew::dx gy;aU gy;}bP ew::cY&bV(){br ew::cY gy;aU gy;}}}bE ll=R;bE Y=cg bh;bE cv=aO;bE hg=__int128;bE md=cg __int128;
#ifdef __SIZEOF_FLOAT128__
bE mb=__float128;
#endif
aZ<bq 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 hg bX<hg> =hg(bX<ll>)*bX<ll>;aZ<>aX ap bX<ap> =bX<ll>;aZ<>aX ab bX<ab> =bX<ll>;bE pi=pair<bh,bh>;bE pl=pair<ll,ll>;bE vi=vector<bh>;bE vl=vector<ll>;aZ<bq T>bE vc=vector<T>;aZ<bq T>bE ht=vector<vc<T>>;bE mk=ht<bh>;bE ml=ht<ll>;aZ<bq T>bE la=vector<ht<T>>;aZ<bq T>bE kX=vector<la<T>>;aZ<bq T>bE lS=vector<kX<T>>;aZ<bq T>bE mj=std::priority_queue<T,vector<T>,greater<T>>;aZ<bq T,bq U>bE me=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 gQ(bh x){aU __builtin_popcount(x);}bh gQ(Y x){aU __builtin_popcount(x);}bh gQ(ll x){aU __builtin_popcountll(x);}bh gQ(cv x){aU __builtin_popcountll(x);}bh go(bh x){aU __builtin_parity(x);}bh go(Y x){aU __builtin_parity(x);}bh go(ll x){aU __builtin_parityll(x);}bh go(cv x){aU __builtin_parityll(x);}bh gS(bh x){aU(x==0?-1:31-__builtin_clz(x));}bh gS(Y x){aU(x==0?-1:31-__builtin_clz(x));}bh gS(ll x){aU(x==0?-1:63-__builtin_clzll(x));}bh gS(cv x){aU(x==0?-1:63-__builtin_clzll(x));}bh gO(bh x){aU(x==0?-1:__builtin_ctz(x));}bh gO(Y x){aU(x==0?-1:__builtin_ctz(x));}bh gO(ll x){aU(x==0?-1:__builtin_ctzll(x));}bh gO(cv x){aU(x==0?-1:__builtin_ctzll(x));}aZ<ch T>T fQ(T a,T b){aU a/b-(a%b&&(a^b)<0);}aZ<ch T>T kY(T x,T y){aU fQ(x+y-1,y);}aZ<ch T>T lZ(T x,T y){aU x-y*fQ(x,y);}aZ<ch T>pair<T,T>gM(T x,T y){T q=fQ(x,y);aU{q,x-q*y};}aZ<ch T,ch U>T mf(U x_,bh n){T x=x_;T js=1;bI(n>0){if(n&1)js*=x;x*=x;n>>=1;}aU js;}aZ<ch T,ch U>T mg(aT vector<U>&A){T sm=0;bH(by&&a:A)sm+=a;aU 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<bq T,bq S>bP af lV(T&a,aT S&b){aU(a<b?a=b,1:0);}aZ<bq T,bq S>bP af lW(T&a,aT S&b){aU(a>b?a=b,1:0);}vc<bh>lO(aT string&S,aK ku){vc<bh>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-ku:-1);}aU A;}aZ<ch T,ch U>vector<T>lQ(vector<U>&A,bh lh=1){bh N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(lh==0)B.erase(B.begin());aU B;}aZ<ch T>vector<bh>lL(aT vector<T>&A){vector<bh>hm(A.size());iota(all(hm),0);sort(all(hm),[&](bh i,bh j){aU(A[i]==A[j]?i<j:A[i]<A[j]);});aU hm;}aZ<ch T>vc<T>lI(aT vc<T>&A,aT vc<bh>&I){vc<T>B(I.size());FOR(i,I.size())B[i]=A[I[i]];aU B;}aZ<bq...T>aX by lf(T...a){aU lf(initializer_list<common_type_t<T...>>{a...});}aZ<bq...T>aX by le(T...a){aU le(initializer_list<common_type_t<T...>>{a...});}aZ<bq...Ts>af ji(Ts&...ac){aU bc::cN::cu().read(ac...);}aZ<bq...Ts>O gW(aT Ts&...ac){bc::cN::bV().println(ac...);}O lT(af b){bc::cN::bV().println(b?"YES":"NO");}O lU(af b){bc::cN::bV().println(b?"Yes":"No");}O mh(){bc::cN::bV().println("YES");}O NO(){bc::cN::bV().println("NO");}O mi(){bc::cN::bV().println("Yes");}O No(){bc::cN::bV().println("No");}by&lR=bc::cN::cu();by&lM=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
bD bc{bD hl{bD au{bD cZ{bE Y=az;bE cv=aO;bE aJ=std::size_t;bE G=__m256i;bP O ar(O*p,G x){_mm256_store_si256((G*)p,x);}bP G ai(aT O*p){aU _mm256_load_si256((aT G*)p);}aX Y eE(Y x,Y M){aU std::min(x,x-M);}aX Y ma(Y x,Y M){aU std::min(x,x+M);}aX Y eA(cv x,Y H,Y M){aU(x+cv(Y(x)*H)*M)>>32;}aX Y co(Y x,Y y,Y H,Y M){aU eA(cv(x)*y,H,M);}aX Y bm(Y x,Y y,Y H,Y M){aU eE(eA(cv(x)*y,H,M),M);}aX Y hq(Y a,Y b,Y H,Y M,Y r){bH(;b;b>>=1,a=co(a,a,H,M)){if(b&1){r=co(r,a,H,M);}}aU r;}aX Y jf(Y a,Y b,Y H,Y M,Y r){aU eE(hq(a,b,H,M,r),M);}bP G bv(G x,G M){aU _mm256_min_epu32(x,_mm256_sub_epi32(x,M));}bP G kL(G x,G M){aU _mm256_min_epu32(x,_mm256_add_epi32(x,M));}bP G cF(G x,G y,G){aU _mm256_add_epi32(x,y);}bP G bK(G x,G y,G M){aU _mm256_add_epi32(_mm256_sub_epi32(x,y),M);}bP G bl(G x,G y,G M){aU bv(_mm256_add_epi32(x,y),M);}bP G cf(G x,G y,G M){aU kL(_mm256_sub_epi32(x,y),M);}aZ<bh lg>bP G lN(G x,G M){aU _mm256_blend_epi32(x,_mm256_sub_epi32(M,x),lg);}bP 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);aU _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(a,c),32),_mm256_add_epi64(b,d),0xaa);}bP G co(G a,G b,G H,G M){aU eA(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32)),H,M);}bP G bm(G a,G b,G H,G M){aU bv(co(a,b,H,M),M);}bP G dC(G a,G b,G H,G M){aU eA(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),b),H,M);}bP G cm(G a,G b,G ff,G M){G cc=_mm256_mul_epu32(a,ff),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),ff);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);aU _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}bP G lK(G a,G b,G ff,G M){G cc=_mm256_mul_epu32(a,ff),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(ff,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);aU _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}bP 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);aU bv(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),M);}aX by ct=26,ex=6;aX by dE=aJ(1)<<ex;ca dQ{Y D,cQ,H,aE,r2,r3,cS,fN,eg[ct];alignas(32)std::array<Y,8>fT[ct-2],fS[ct-2],hf,hk,he,fm[ct-3],iZ[ct-3],fg[ct-3],iO[ct-3],ho,hp,iW,iX,hh,iM,hi,iN;aX dQ(aT Y m):D(m),cQ(m*2),H([&]{Y n=2+m;bH(bh i=0;i<4;++i){n*=2+m*n;}aU n;}()),aE((-m)%m),r2((-cv(m))%m),r3(bm(r2,r2,H,m)),cS{},fN{},eg{},fT{},fS{},hf{},hk{},he{},fm{},iZ{},fg{},iO{},ho{},hp{},iW{},iX{},hh{},iM{},hi{},iN{}{aT bh k=__builtin_ctz(m-1);Y _g=co(3,r2,H,D);bH(;;++_g){if(jf(_g,D>>1,H,D,aE)!=aE){break;}}_g=hq(_g,D>>k,H,D,aE);Y bZ[ct-1],bO[ct-1];bZ[k-2]=_g,bO[k-2]=hq(_g,D-2,H,D,aE);bH(bh i=k-2;i>0;--i){bZ[i-1]=co(bZ[i],bZ[i],H,D);bO[i-1]=co(bO[i],bO[i],H,D);}eg[k-1]=jf(_g,3,H,D,aE);bH(bh i=k-1;i>0;--i){eg[i-1]=bm(eg[i],eg[i],H,D);}cS=bZ[0],fN=cS*H;hf={aE,0,aE,0,aE};hk={bZ[1],0,bZ[0],0,D-bm(bZ[0],bZ[1],H,D)};he={bO[1],0,bO[0],0,bm(bO[0],bO[1],H,D)};Y pr=aE,ei=aE;bH(bh i=0;i<k-2;++i){aT Y r=bm(pr,bZ[i+1],H,D),ri=bm(ei,bO[i+1],H,D);aT Y r2=bm(r,r,H,D),hr=bm(ri,ri,H,D);aT Y r3=bm(r,r2,H,D),jr=bm(ri,hr,H,D);fT[i]={r*H,r,r2*H,r2,r3*H,r3};fS[i]={ri*H,ri,hr*H,hr,jr*H,jr};pr=co(pr,bO[i+1],H,D),ei=co(ei,bZ[i+1],H,D);}pr=aE,ei=aE;bH(bh i=0;i<k-3;++i){aT Y r=bm(pr,bZ[i+2],H,D),ri=bm(ei,bO[i+2],H,D);fm[i][0]=fg[i][0]=aE;bH(bh j=1;j<8;++j){fm[i][j]=bm(fm[i][j-1],r,H,D);fg[i][j]=bm(fg[i][j-1],ri,H,D);}bH(bh j=0;j<8;++j){iZ[i][j]=fm[i][j]*H;iO[i][j]=fg[i][j]*H;}pr=co(pr,bO[i+2],H,D),ei=co(ei,bZ[i+2],H,D);}ho={aE,aE,aE,cS,aE,aE,aE,cS};hp={aE,aE,aE,aE,aE,bZ[1],cS,bm(cS,bZ[1],H,D)};aT Y eI=D-r2,jd=bm(cS,r2,H,D);hh={eI,eI,eI,jd,eI,eI,eI,jd};hi={aE,aE,aE,aE,aE,bO[1],bO[0],bm(bO[0],bO[1],H,D)};bH(bh j=0;j<8;++j){iW[j]=ho[j]*H,iX[j]=hp[j]*H;iM[j]=hh[j]*H,iN[j]=hi[j]*H;}}};bP O gs(G*aT f,aT aJ n,aT dQ*aC){alignas(32)std::array<Y,8>bY[ct>>1];aT G ao=_mm256_set1_epi32(aC->D),J=_mm256_set1_epi32(aC->cQ),bG=_mm256_set1_epi32(aC->H);aT G dH=_mm256_set1_epi32(aC->cS),dD=_mm256_set1_epi32(aC->fN),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);aT bh eG=__builtin_ctzll(n);std::fill(bY,bY+(eG>>1),aC->hk);aT aJ nn=n>>(eG&1),m=std::min(n,dE),mm=std::min(nn,dE);if(nn!=n){bH(aJ i=0;i<nn;++i){by aT p0=f+i,p1=f+nn+i;aT by f0=ai(p0),f1=ai(p1);aT by g0=bl(f0,f1,J),g1=bK(f0,f1,J);ar(p0,g0),ar(p1,g1);}}bH(aJ L=nn>>2;L>0;L>>=2){bH(aJ i=0;i<L;++i){by aT p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aT by f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aT by g3=cm(bK(f1,f3,J),dH,dD,ao),g1=bl(f1,f3,J);aT by g0=bl(f0,f2,J),g2=cf(f0,f2,J);aT by h0=bl(g0,g1,J),h1=bK(g0,g1,J);aT by h2=cF(g2,g3,J),h3=bK(g2,g3,J);ar(p0,h0),ar(p1,h1),ar(p2,h2),ar(p3,h3);}}bH(aJ j=0;j<n;j+=m){bh t=((j==0)?std::min(ex,eG):__builtin_ctzll(j))&-2,p=(t-2)>>1;bH(aJ L=(aJ(1)<<t)>>2;L>=dE;L>>=2,t-=2,--p){by rt=ai(bY+p);aT by r1=_mm256_permutevar8x32_epi32(rt,id);aT by ed=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bG),id);rt=fG(rt,ai(aC->fT+__builtin_ctzll(~j>>t)),ao);aT by r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),hn=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);aT by gX=_mm256_shuffle_epi32(ed,_MM_PERM_BBBB),kM=_mm256_shuffle_epi32(ed,_MM_PERM_DDDD);ar(bY+p,rt);bH(aJ i=0;i<L;++i){by aT p0=f+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aT by f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aT by g1=cm(f1,r1,ed,ao),fj=cm(f3,hn,kM,ao);aT by g2=cm(f2,r2,gX,ao),g0=bv(f0,J);aT by h3=cm(cF(g1,fj,J),dH,dD,ao),h1=cf(g1,fj,J);aT by h0=bl(g0,g2,J),h2=cf(g0,g2,J);aT by u0=cF(h0,h1,J),u1=bK(h0,h1,J);aT by u2=cF(h2,h3,J),u3=bK(h2,h3,J);ar(p0,u0),ar(p1,u1),ar(p2,u2),ar(p3,u3);}}G*aT g=f+j;bH(aJ l=mm,L=mm>>2;L;l=L,L>>=2,t-=2,--p){by rt=ai(bY+p);bH(aJ i=(j==0?l:0),k=(j+i)>>t;i<m;i+=l,++k){aT by r1=_mm256_permutevar8x32_epi32(rt,id);aT by r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);aT by hn=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);bH(aJ j=0;j<L;++j){by aT p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aT by f1=ai(p1),f3=ai(p3),f2=ai(p2),f0=ai(p0);aT by g1=dC(f1,r1,bG,ao),fj=dC(f3,hn,bG,ao);aT by g2=dC(f2,r2,bG,ao),g0=bv(f0,J);aT by h3=cm(cF(g1,fj,J),dH,dD,ao),h1=cf(g1,fj,J);aT by h0=bl(g0,g2,J),h2=cf(g0,g2,J);aT by u0=cF(h0,h1,J),u1=bK(h0,h1,J);aT by u2=cF(h2,h3,J),u3=bK(h2,h3,J);ar(p0,u0),ar(p1,u1),ar(p2,u2),ar(p3,u3);}rt=fG(rt,ai(aC->fT+__builtin_ctzll(~k)),ao);}ar(bY+p,rt);}}}aZ<af eE=ci>bP O iy(G*aT f,aJ n,aT dQ*aT aC){alignas(32)std::array<Y,8>bY[ct>>1];aT G ao=_mm256_set1_epi32(aC->D),J=_mm256_set1_epi32(aC->cQ),bG=_mm256_set1_epi32(aC->H);aT G dH=_mm256_set1_epi32(aC->cS),dD=_mm256_set1_epi32(aC->fN),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);aT bh eG=__builtin_ctzll(n);std::fill(bY,bY+(ex>>1),aC->hf);std::fill(bY+(ex>>1),bY+(ct>>1),aC->he);aT aJ nn=n>>(eG&1),mm=std::min(nn,dE);bH(aJ j=0;j<n;j+=mm){G*aT g=f+j;bh t=2,p=0;bH(aJ l=4,L=1;l<=mm;L=l,l<<=2,t+=2,++p){by rt=ai(bY+p);bH(aJ i=0,k=j>>t;i<mm;i+=l,++k){aT by r1=_mm256_permutevar8x32_epi32(rt,id);aT by r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);aT by r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);bH(aJ j=0;j<L;++j){by aT p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;aT by f0=ai(p0),f1=ai(p1),f2=ai(p2),f3=ai(p3);aT by g0=bl(f0,f1,J),g1=cf(f0,f1,J);aT by g2=bl(f2,f3,J),g3=cm(bK(f3,f2,J),dH,dD,ao);aT by h0=cF(g0,g2,J),h1=cF(g1,g3,J);aT by h2=bK(g0,g2,J),h3=bK(g1,g3,J);aT by u0=bv(h0,J),u1=dC(h1,r1,bG,ao);aT by u2=dC(h2,r2,bG,ao),u3=dC(h3,r3,bG,ao);ar(p0,u0),ar(p1,u1),ar(p2,u2),ar(p3,u3);}rt=fG(rt,ai(aC->fS+__builtin_ctzll(~k)),ao);}ar(bY+p,rt);}bh tt=std::min(__builtin_ctzll(~(j>>ex))+ex,eG);bH(aJ L=dE,l=L<<2;t<=tt;L=l,l<<=2,t+=2,++p){if((j+dE)==l){if(eE&&l==n){bH(aJ i=0;i<L;++i){by aT p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aT by f2=ai(p2),f3=ai(p3),f0=ai(p0),f1=ai(p1);aT by g3=cm(bK(f3,f2,J),dH,dD,ao),g2=bl(f2,f3,J);aT by g0=bl(f0,f1,J),g1=cf(f0,f1,J);aT by h0=bl(g0,g2,J),h1=bl(g1,g3,J);aT by h2=cf(g0,g2,J),h3=cf(g1,g3,J);aT by u0=bv(h0,ao),u1=bv(h1,ao);aT by u2=bv(h2,ao),u3=bv(h3,ao);ar(p0,u0),ar(p1,u1),ar(p2,u2),ar(p3,u3);}}cq{bH(aJ i=0;i<L;++i){by aT p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;aT by f2=ai(p2),f3=ai(p3),f0=ai(p0),f1=ai(p1);aT by g3=cm(bK(f3,f2,J),dH,dD,ao),g2=bl(f2,f3,J);aT by g0=bl(f0,f1,J),g1=cf(f0,f1,J);aT by h0=bl(g0,g2,J),h1=bl(g1,g3,J);aT by h2=cf(g0,g2,J),h3=cf(g1,g3,J);ar(p0,h0),ar(p1,h1),ar(p2,h2),ar(p3,h3);}}}cq{by rt=ai(bY+p);aT by r1=_mm256_permutevar8x32_epi32(rt,id);aT by ed=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bG),id);rt=fG(rt,ai(aC->fS+__builtin_ctzll(~j>>t)),ao);aT by r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);aT by gX=_mm256_shuffle_epi32(ed,_MM_PERM_BBBB),kR=_mm256_shuffle_epi32(ed,_MM_PERM_DDDD);ar(bY+p,rt);bH(aJ i=0;i<L;++i){by aT p0=f+j+dE-l+i,p1=p0+L,p2=p1+L,p3=p2+L;aT by f0=ai(p0),f1=ai(p1),f2=ai(p2),f3=ai(p3);aT by g0=bl(f0,f1,J),g1=cf(f0,f1,J);aT by g2=bl(f2,f3,J),g3=cm(bK(f3,f2,J),dH,dD,ao);aT by h0=cF(g0,g2,J),h1=cF(g1,g3,J);aT by h2=bK(g0,g2,J),h3=bK(g1,g3,J);aT by u0=bv(h0,J),u1=cm(h1,r1,ed,ao);aT by u2=cm(h2,r2,gX,ao),u3=cm(h3,r3,kR,ao);ar(p0,u0),ar(p1,u1),ar(p2,u2),ar(p3,u3);}}}}if(eE&&nn==n&&n<=dE){bH(aJ i=0;i<n;++i){aT by f0=ai(f+i);ar(f+i,bv(f0,ao));}}if(nn!=n){bH(aJ i=0;i<nn;++i){by aT p0=f+i,p1=f+nn+i;aT by f0=ai(p0),f1=ai(p1);aT by g0=bl(f0,f1,J),g1=cf(f0,f1,J);if aX(eE){aT by h0=bv(g0,ao),h1=bv(g1,ao);ar(p0,h0),ar(p1,h1);}cq{ar(p0,g0),ar(p1,g1);}}}}[[gnu::always_inline]]bP G iA(aT G*f,aT G*g,G ww,G fx,G bG,G ao,G J){aT by li=ai(f),lj=ai(g);aT by jt=bv(li,J),bb=bv(dC(lj,fx,bG,ao),ao);aT by aw=bv(dC(jt,ww,bG,ao),ao);aT by aa=bv(jt,ao);aT by dI=_mm256_permute2x128_si256(aa,aw,3);aT by b0=_mm256_permute4x64_epi64(bb,0x00),b1=_mm256_shuffle_epi32(b0,_MM_PERM_CDAB);aT by a0=aa,a1=_mm256_srli_epi64(a0,32);aT by jo=_mm256_alignr_epi8(aa,dI,12);by dk=_mm256_mul_epu32(a0,b0);by dl=_mm256_mul_epu32(a1,b0);by ee=_mm256_mul_epu32(jo,b1);by ef=_mm256_mul_epu32(a0,b1);aT by b2=_mm256_permute4x64_epi64(bb,0x55),b3=_mm256_shuffle_epi32(b2,_MM_PERM_CDAB);aT by jn=_mm256_alignr_epi8(aa,dI,8);aT by jm=_mm256_alignr_epi8(aa,dI,4);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(jn,b2));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jo,b2));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(jm,b3));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(jn,b3));aT by b4=_mm256_permute4x64_epi64(bb,0xaa),b5=_mm256_shuffle_epi32(b4,_MM_PERM_CDAB);aT by jl=_mm256_alignr_epi8(dI,aw,12);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(dI,b4));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jm,b4));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(jl,b5));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(dI,b5));aT by b6=_mm256_permute4x64_epi64(bb,0xff),b7=_mm256_shuffle_epi32(b6,_MM_PERM_CDAB);aT by jk=_mm256_alignr_epi8(dI,aw,8);aT by lc=_mm256_alignr_epi8(dI,aw,4);dk=_mm256_add_epi64(dk,_mm256_mul_epu32(jk,b6));dl=_mm256_add_epi64(dl,_mm256_mul_epu32(jl,b6));ee=_mm256_add_epi64(ee,_mm256_mul_epu32(lc,b7));ef=_mm256_add_epi64(ef,_mm256_mul_epu32(jk,b7));dk=_mm256_add_epi64(dk,ee);dl=_mm256_add_epi64(dl,ef);aU bv(eA(dk,dl,bG,ao),J);}bP O jG(G*f,aT G*g,aJ lm,aT dQ*aT aC){Y RR=aC->aE;aT by D=aC->D,H=aC->H;aT by Fx=_mm256_set1_epi32(bm((D-((D-1)>>(__builtin_ctzll(lm)))),aC->r3,H,D));aT by bG=_mm256_set1_epi32(H),ao=_mm256_set1_epi32(D),J=_mm256_set1_epi32(aC->cQ);bH(aJ i=0;i<lm;++i){ar(f+i,iA(f+i,g+i,_mm256_set1_epi32(RR),Fx,bG,ao,J));RR=co(RR,aC->eg[__builtin_ctzll(~i)],H,D);}}bP O jE(G*aT o,aT G*aT f,aT G*aT g,aJ lm,aT dQ*aT aC){Y RR=aC->aE;aT by D=aC->D,H=aC->H;aT by Fx=_mm256_set1_epi32(bm((D-((D-1)>>(__builtin_ctzll(lm)))),aC->r3,H,D));aT by bG=_mm256_set1_epi32(H),ao=_mm256_set1_epi32(D),J=_mm256_set1_epi32(aC->cQ);bH(aJ i=0;i<lm;++i){aT by aj=iA(f+i,g+i,_mm256_set1_epi32(RR),Fx,bG,ao,J);ar(o+i,bl(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
bD bc{bD cP{aZ<uint32_t bU>ca ag{dp:uint32_t W;dr:br aX uint32_t D(){aU bU;}br aX ag cT(uint32_t v)bC{ag x;x.W=v;aU x;}aX ag()bC:W(0){}aZ<bq dY,std::enable_if_t<std::is_integral_v<dY>,bh> =0>aX ag(dY v)bC{if aX(std::is_signed_v<dY>){int64_t x=bi<int64_t>(v)%bi<int64_t>(bU);if(x<0)x+=bU;W=bi<uint32_t>(x);}cq{W=bi<uint32_t>(bi<uint64_t>(v)%bU);}}aX uint32_t val()aT bC{aU W;}aX ag&bd++()bC{W++;if(W==bU)W=0;aU*cb;}aX ag&bd--()bC{if(W==0)W=bU;W--;aU*cb;}aX ag bd++(bh)bC{ag bg=*cb;++*cb;aU bg;}aX ag bd--(bh)bC{ag bg=*cb;--*cb;aU bg;}aX ag&bd+=(aT ag&E)bC{W+=E.W;if(W>=bU)W-=bU;aU*cb;}aX ag&bd-=(aT ag&E)bC{W-=E.W;if(W>=bU)W+=bU;aU*cb;}aX ag&bd*=(aT ag&E)bC{uint64_t z=W;z*=E.W;W=bi<uint32_t>(z%bU);aU*cb;}aX ag&bd/=(aT ag&E)bC{aU*cb*=E.inv();}aX ag bd+(aT ag&E)aT bC{aU ag(*cb)+=E;}aX ag bd-(aT ag&E)aT bC{aU ag(*cb)-=E;}aX ag bd*(aT ag&E)aT bC{aU ag(*cb)*=E;}aX ag bd/(aT ag&E)aT bC{aU ag(*cb)/=E;}aX af bd==(aT ag&E)aT bC{aU W==E.W;}aX af bd!=(aT ag&E)aT bC{aU W!=E.W;}aX ag pow(R n)aT bC{ag bg=cT(1%bU);ag x=n<0?inv():*cb;uint64_t bk=n<0?uint64_t(-(n+1))+1:uint64_t(n);bI(bk>0){if(bk&1)bg*=x;x*=x;bk>>=1;}aU bg;}aX ag inv()aT bC{int64_t a=W,b=bU,u=1,v=0;bI(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;aU cT(bi<uint32_t>(u));}cd std::ostream&bd<<(std::ostream&os,aT ag&E){aU os<<E.W;}cd std::istream&bd>>(std::istream&is,ag&E){R v;is>>v;E=ag(v);aU is;}};bE lx=ag<998244353>;bE lw=ag<1000000007>;aZ<bh Id=0>ca as{dp:uint32_t W;bP br uint32_t bM=1;dr:br uint32_t D()bC{aU bM;}br O lP(uint32_t kI)bC{(O)0;(O)0;bM=kI;}br as cT(uint32_t v)bC{(O)0;as x;x.W=v;aU x;}as()bC:W(0){}aZ<bq dY,std::enable_if_t<std::is_integral_v<dY>,bh> =0>as(dY v)bC{if aX(std::is_signed_v<dY>){int64_t x=bi<int64_t>(v)%bi<int64_t>(bM);if(x<0)x+=bM;W=bi<uint32_t>(x);}cq{W=bi<uint32_t>(bi<uint64_t>(v)%bM);}}uint32_t val()aT bC{aU W;}as&bd++()bC{W++;if(W==bM)W=0;aU*cb;}as&bd--()bC{if(W==0)W=bM;W--;aU*cb;}as bd++(bh)bC{as o=*cb;++*cb;aU o;}as bd--(bh)bC{as o=*cb;--*cb;aU o;}as&bd+=(aT as&E)bC{W+=E.W;if(W>=bM)W-=bM;aU*cb;}as&bd-=(aT as&E)bC{W-=E.W;if(W>=bM)W+=bM;aU*cb;}as&bd*=(aT as&E)bC{W=bi<uint32_t>(uint64_t(W)*E.W%bM);aU*cb;}as&bd/=(aT as&E)bC{aU*cb*=E.inv();}as bd+(aT as&E)aT bC{aU as(*cb)+=E;}as bd-(aT as&E)aT bC{aU as(*cb)-=E;}as bd*(aT as&E)aT bC{aU as(*cb)*=E;}as bd/(aT as&E)aT bC{aU as(*cb)/=E;}af bd==(aT as&E)aT bC{aU W==E.W;}af bd!=(aT as&E)aT bC{aU W!=E.W;}as pow(R bk)aT bC{as o=cT(1%bM);as dG=bk<0?inv():*cb;uint64_t aV=bk<0?uint64_t(-(bk+1))+1:uint64_t(bk);bI(aV>0){if(aV&1)o*=dG;dG*=dG;aV>>=1;}aU o;}as inv()aT bC{int64_t a=W,b=bM,u=1,v=0;bI(b){int64_t ay=a/b;a-=ay*b;std::swap(a,b);u-=ay*v;std::swap(u,v);}(O)0;u%=bM;if(u<0)u+=bM;aU cT(bi<uint32_t>(u));}cd std::ostream&bd<<(std::ostream&os,aT as&E){aU os<<E.W;}cd std::istream&bd>>(std::istream&is,as&E){R w;is>>w;E=as(w);aU is;}};}}bD bc{bD hl{bD au{aZ<bq C,bq=O>ca hJ:std::false_type{};aZ<bq C>ca hJ<C,std::void_t<cJ(std::integral_constant<uint32_t,C::D()>{})>>:std::true_type{};aX uint32_t jI(uint32_t D){if(D==2)aU 1;if(D==167772161)aU 3;if(D==469762049)aU 3;if(D==754974721)aU 11;if(D==998244353)aU 3;if(D==1224736769)aU 3;uint32_t gx[32]={};bh ce=0;uint32_t x=D-1;bH(uint32_t p=2;uint64_t(p)*p<=x;p++){if(x%p!=0)cj;gx[ce++]=p;bI(x%p==0)x/=p;}if(x>1)gx[ce++]=x;bH(uint32_t g=2;;g++){af ok=cw;bH(bh i=0;i<ce;i++){uint64_t w=1;uint64_t dG=g;uint32_t bk=(D-1)/gx[i];bI(bk>0){if(bk&1)w=w*dG%D;dG=dG*dG%D;bk>>=1;}if(w==1){ok=ci;break;}}if(ok)aU g;}}aX bh hW(uint32_t x){bh o=0;bI((x&1)==0){x>>=1;o++;}aU o;}aZ<bq C>ca gv{br aX bh db=hW(C::D()-1);std::array<C,db+1>aN;std::array<C,db+1>eu;std::array<C,db>jh;std::array<C,db>ie;std::array<C,db>iq;std::array<C,db>hF;gv(){aX uint32_t kg=jI(C::D());bH(bh eC=1;eC<=db;eC++){aN[eC]=C(kg).pow((C::D()-1)>>eC);eu[eC]=aN[eC].inv();}C aj=1;C eO=1;bH(bh i=0;i+1<db;i++){jh[i]=aN[i+2]*aj;ie[i]=eu[i+2]*eO;aj*=eu[i+2];eO*=aN[i+2];}aj=1;eO=1;bH(bh i=0;i+2<db;i++){iq[i]=aN[i+3]*aj;hF[i]=eu[i+3]*eO;aj*=eu[i+3];eO*=aN[i+3];}}};aZ<bq C>aT gv<C>&kz(){br aT gv<C>aI;aU aI;}aZ<bq C>O fk(F<C>&a,af bf,af ky=cw){aT bh n=bh(a.size());(O)0;(O)0;aT by&aI=kz<C>();aT bh cG=hW(uint32_t(n));if(!bf){bh aR=0;bI(aR<cG){if(cG-aR==1){aT bh aY=1<<(cG-aR-1);C bF=1;bH(bh av=0;av<(1<<aR);av++){aT bh K=av<<(cG-aR);bH(bh i=0;i<aY;i++){aT C bx=a[K+i];aT C bw=a[K+i+aY]*bF;a[K+i]=bx+bw;a[K+i+aY]=bx-bw;}if(av+1!=(1<<aR))bF*=aI.jh[__builtin_ctz(~uint32_t(av))];}aR++;cj;}aT bh aY=1<<(cG-aR-2);C bF=1;aT C ax=aI.aN[2];bH(bh av=0;av<(1<<aR);av++){aT C eV=bF*bF;aT C gC=eV*bF;aT bh K=av<<(cG-aR);bH(bh i=0;i<aY;i++){aT uint64_t cQ=uint64_t(C::D())*C::D();aT uint64_t a0=a[K+i].val();aT uint64_t a1=uint64_t(a[K+i+aY].val())*bF.val();aT uint64_t a2=uint64_t(a[K+i+2*aY].val())*eV.val();aT uint64_t a3=uint64_t(a[K+i+3*aY].val())*gC.val();aT uint64_t iP=uint64_t(C(a1+cQ-a3).val())*ax.val();aT uint64_t io=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+io+iP);a[K+i+3*aY]=C(a0+io+cQ-iP);}if(av+1!=(1<<aR))bF*=aI.iq[__builtin_ctz(~uint32_t(av))];}aR+=2;}}cq{bh aR=cG;bI(aR>0){if(aR==1){aT bh aY=1<<(cG-aR);C bF=1;bH(bh av=0;av<(1<<(aR-1));av++){aT bh K=av<<(cG-aR+1);bH(bh i=0;i<aY;i++){aT C bx=a[K+i];aT C bw=a[K+i+aY];a[K+i]=bx+bw;a[K+i+aY]=(bx-bw)*bF;}if(av+1!=(1<<(aR-1)))bF*=aI.ie[__builtin_ctz(~uint32_t(av))];}aR--;cj;}aT bh aY=1<<(cG-aR);C bF=1;aT C jR=aI.eu[2];bH(bh av=0;av<(1<<(aR-2));av++){aT C eV=bF*bF;aT C gC=eV*bF;aT bh K=av<<(cG-aR+2);bH(bh i=0;i<aY;i++){aT uint64_t a0=a[K+i].val();aT uint64_t a1=a[K+i+aY].val();aT uint64_t a2=a[K+i+2*aY].val();aT uint64_t a3=a[K+i+3*aY].val();aT uint64_t iQ=uint64_t(C((C::D()+a2-a3)*jR.val()).val());a[K+i]=C(a0+a1+a2+a3);a[K+i+aY]=C((a0+C::D()-a1+iQ)*bF.val());a[K+i+2*aY]=C((a0+a1+2ULL*C::D()-a2-a3)*eV.val());a[K+i+3*aY]=C((a0+C::D()-a1+C::D()-iQ)*gC.val());}if(av+1!=(1<<(aR-2)))bF*=aI.hF[__builtin_ctz(~uint32_t(av))];}aR-=2;}if(ky){aT C fJ=C(n).inv();bH(C&w:a)w*=fJ;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
aZ<bq C>__attribute__((target("avx2,bmi"),hot))F<C>jF(aT F<C>&a,aT F<C>&b){aT bh aQ=bh(a.size()+b.size()-1);bh n=1;bI(n<aQ)n<<=1;aT af cD=&a==&b;by*ck=bi<uint32_t*>(::bd new[](cI(uint32_t)*n,std::align_val_t(32)));by*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{bH(bh i=0;i<bh(a.size());i++)ck[i]=a[i].val();if(!cD)bH(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()));br aX cZ::dQ dA(998244353);aT std::size_t dv=std::size_t(n)>>3;cZ::gs(bp<__m256i*>(ck),dv,&dA);if(!cD)cZ::gs(bp<__m256i*>(cM),dv,&dA);cZ::jG(bp<__m256i*>(ck),bp<aT __m256i*>(cM),dv,&dA);cZ::iy<cw>(bp<__m256i*>(ck),dv,&dA);F<C>o(aQ);bH(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));aU o;}
#pragma GCC pop_options
#endif
}aZ<bq C>F<C>jQ(aT F<C>&a,aT F<C>&b){if(a.empty()||b.empty())aU{};F<C>o(a.size()+b.size()-1);if(a.size()<b.size()){bH(bh i=0;i<bh(a.size());i++){bH(bh j=0;j<bh(b.size());j++)o[i+j]+=a[i]*b[j];}}cq{bH(bh j=0;j<bh(b.size());j++){bH(bh i=0;i<bh(a.size());i++)o[i+j]+=a[i]*b[j];}}aU o;}aZ<bq C>F<C>hQ(aT F<C>&a,aT F<C>&b){aT bh aQ=bh(a.size()+b.size()-1);bh n=1;bI(n<aQ)n<<=1;(O)0;
#ifdef M1UNE_FPS_HAS_X86_SIMD
if aX(C::D()==998244353){if(n>=64&&__builtin_cpu_supports("avx2"))aU au::jF(a,b);}
#endif
aT af cD=&a==&b;F<C>fa(n);std::copy(a.begin(),a.end(),fa.begin());au::fk(fa,ci);aT C fJ=C(n).inv();if(cD){bH(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);bH(bh i=0;i<n;i++)fa[i]*=fb[i]*fJ;}au::fk(fa,cw,ci);fa.resize(aQ);aU fa;}bD au{aZ<bq C>F<C>jB(aT F<C>&a,aT F<C>&b,bh aF){(O)0;(O)0;(O)0;aT bh be=aF/2;aT bh dV=bh((a.size()+be-1)/be);aT bh dW=bh((b.size()+be-1)/be);by eN=[&](aT F<C>&ac,bh dS){F<F<C>>ea;ea.reserve(dS);bH(bh av=0;av<dS;av++){aT bh begin=av*be;aT 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));}aU ea;};F<F<C>>ck=eN(a,dV);F<F<C>>cM=eN(b,dW);aT bh aQ=bh(a.size()+b.size()-1);F<C>o(aQ);F<C>cL(aF);bH(bh bA=0;bA<dV+dW-1;bA++){std::fill(cL.begin(),cL.end(),C(0));aT bh gE=std::max(0,bA-(dW-1));aT bh gN=std::min(dV-1,bA);bH(bh dc=gE;dc<=gN;dc++){aT bh gD=bA-dc;bH(bh i=0;i<aF;i++)cL[i]+=ck[dc][i]*cM[gD][i];}fk(cL,cw);aT bh et=bA*be;aT bh gn=std::min(aF,aQ-et);bH(bh i=0;i<gn;i++)o[et+i]+=cL[i];}aU o;}
#ifdef M1UNE_FPS_HAS_X86_SIMD
bq bQ{dp:uint32_t*cH;dr:dq bQ(std::size_t size):cH(bi<uint32_t*>(::bd new[](cI(uint32_t)*size,std::align_val_t(32)))){}bQ(aT bQ&)=cK;bQ&bd=(aT bQ&)=cK;bQ(bQ&&X)bC:cH(X.cH){X.cH=nullptr;}bQ&bd=(bQ&&X)bC{if(cb==&X)aU*cb;::bd cK[](cH,std::align_val_t(32));cH=X.cH;X.cH=nullptr;aU*cb;}~bQ(){::bd cK[](cH,std::align_val_t(32));}uint32_t*data(){aU cH;}aT uint32_t*data()aT{aU cH;}};aZ<bq C>__attribute__((target("avx2,bmi"),hot))F<C>jC(aT F<C>&a,aT F<C>&b,bh aF){(O)0;(O)0;(O)0;aT bh be=aF/2;aT bh dV=bh((a.size()+be-1)/be);aT bh dW=bh((b.size()+be-1)/be);br aX cZ::dQ dA(998244353);aT std::size_t dv=std::size_t(aF)/8;by eN=[&](aT F<C>&ac,bh dS){F<bQ>ea;ea.reserve(dS);bH(bh av=0;av<dS;av++){aT bh begin=av*be;aT bh ce=std::min(be,bh(ac.size())-begin);bQ cX(aF);if aX(std::is_same_v<C,cP::ag<998244353>>){std::memcpy(cX.data(),ac.data()+begin,cI(uint32_t)*ce);}cq{bH(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::gs(bp<__m256i*>(cX.data()),dv,&dA);ea.emplace_back(std::move(cX));}aU ea;};F<bQ>ck=eN(a,dV);F<bQ>cM=eN(b,dW);aT bh aQ=bh(a.size()+b.size()-1);F<C>o(aQ);bQ cL(aF);bH(bh bA=0;bA<dV+dW-1;bA++){std::memset(cL.data(),0,cI(uint32_t)*aF);aT bh gE=std::max(0,bA-(dW-1));aT bh gN=std::min(dV-1,bA);bH(bh dc=gE;dc<=gN;dc++){aT bh gD=bA-dc;cZ::jE(bp<__m256i*>(cL.data()),bp<aT __m256i*>(ck[dc].data()),bp<aT __m256i*>(cM[gD].data()),dv,&dA);}cZ::iy<cw>(bp<__m256i*>(cL.data()),dv,&dA);aT bh et=bA*be;aT bh gn=std::min(aF,aQ-et);bH(bh i=0;i<gn;i++){uint32_t w=o[et+i].val()+cL.data()[i];if(w>=C::D())w-=C::D();o[et+i]=C::cT(w);}}aU o;}
#endif
aZ<bq C>F<C>jD(aT F<C>&a,aT F<C>&b,bh aF=1<<23){
#ifdef M1UNE_FPS_HAS_X86_SIMD
if(aF>=64&&__builtin_cpu_supports("avx2"))aU jC(a,b,aF);
#endif
aU jB(a,b,aF);}}aZ<bq C>F<C>il(aT F<C>&a,aT F<C>&b){if(a.empty()||b.empty())aU{};if(std::min(a.size(),b.size())<=32)aU jQ(a,b);aT bh aQ=bh(a.size()+b.size()-1);bh n=1;bI(n<aQ)n<<=1;if aX(au::hJ<C>::value){if aX(C::D()==998244353){if(n>(1<<23))aU au::jD(a,b);}if((C::D()-1)%uint32_t(n)==0)aU hQ(a,b);}bE cO=cP::ag<167772161>;bE bW=cP::ag<469762049>;bE bB=cP::ag<754974721>;(O)0;[[maybe_unused]]aT cg __int128 gc=bi<cg __int128>(std::min(a.size(),b.size()))*(C::D()-1)*(C::D()-1);[[maybe_unused]]aT cg __int128 lB=bi<cg __int128>(cO::D())*bW::D()*bB::D();(O)0;by fW=[&]<bq fH>(){F<fH>ij(a.size());F<fH>ik(b.size());bH(bh i=0;i<bh(a.size());i++)ij[i]=fH(a[i].val());bH(bh i=0;i<bh(b.size());i++)ik[i]=fH(b[i].val());aU hQ(ij,ik);};F<cO>c1=fW.aZ bd()<cO>();F<bW>c2=fW.aZ bd()<bW>();F<bB>c3=fW.aZ bd()<bB>();br aT uint64_t gd=bW(cO::D()).inv().val();br aT uint64_t iE=cO::D()%bB::D();br aT uint64_t kd=iE*(bW::D()%bB::D())%bB::D();br aT uint64_t jK=bB(uint32_t(kd)).inv().val();aT uint64_t dw=C::D();aT uint64_t in=cO::D()%dw;aT uint64_t jZ=in*(bW::D()%dw)%dw;F<C>o(aQ);bH(bh i=0;i<aQ;i++){aT uint64_t r1=c1[i].val();aT uint64_t r2=c2[i].val();aT uint64_t r3=c3[i].val();aT uint64_t ad=(r2+bW::D()-r1%bW::D())%bW::D()*gd%bW::D();aT uint64_t ki=(r1%bB::D()+iE*(ad%bB::D()))%bB::D();aT uint64_t al=(r3+bB::D()-ki)%bB::D()*jK%bB::D();uint64_t w=r1%dw;w=(w+in*(ad%dw))%dw;w=(w+jZ*(al%dw))%dw;o[i]=C::cT(uint32_t(w));}aU o;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#undef M1UNE_FPS_HAS_X86_SIMD
#endif
bD bc{bD ew{ca V{br aX bh Z=1000000000;br aX bh du=9;F<bh>a;bh ah;V():ah(1){}V(R v){*cb=v;}V(aT std::string&s){read(s);}V&bd=(R v){ah=1;aO aV=bi<aO>(v);if(v<0){ah=-1;aV=0-aV;}a.clear();bH(;aV>0;aV/=Z){a.push_back(bh(aV%Z));}aU*cb;}V&bd=(aT std::string&s){read(s);aU*cb;}O trim(){bI(!a.empty()&&a.back()==0){a.pop_back();}if(a.empty())ah=1;}O read(aT std::string&s){ah=1;a.clear();bh dJ=0;bI(dJ<(bh)s.size()&&(s[dJ]=='-'||s[dJ]=='+')){if(s[dJ]=='-')ah=-1;++dJ;}a.reserve((bh(s.size())-dJ+du-1)/du);bH(bh i=bh(s.size())-1;i>=dJ;i-=du){bh x=0;bH(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()aT{if(a.empty())aU"0";br aT by eQ=[]{std::array<aK,40000>df{};bH(bh w=0;w<10000;++w){bh ak=w;bH(bh dj=3;dj>=0;--dj){df[4*w+dj]=aK('0'+ak%10);ak/=10;}}aU df;}();aK cE[du];aT std::to_chars_result iz=std::to_chars(cE,cE+du,a.back());(O)0;aT bh ig=bh(iz.ptr-cE);std::string bg((ah==-1)+ig+(a.size()-1)*du,'0');bh K=0;if(ah==-1)bg[K++]='-';std::copy(cE,iz.ptr,bg.begin()+K);K+=ig;bH(bh i=(bh)a.size()-2;i>=0;--i){aT az w=az(a[i]);aT az hY=w/100000000;aT az dz=w-hY*100000000;aT az iU=dz/10000;aT az kG=dz-iU*10000;bg[K]=aK('0'+hY);std::memcpy(bg.data()+K+1,eQ.data()+4*iU,4);std::memcpy(bg.data()+K+5,eQ.data()+4*kG,4);K+=du;}aU bg;}af is_zero()aT{aU a.empty()||(a.size()==1&&a[0]==0);}V bd-()aT{V bg=*cb;if(!is_zero())bg.ah=-ah;aU bg;}V abs()aT{V bg=*cb;bg.ah=1;aU bg;}cd af bd<(aT V&x,aT V&y){if(x.ah!=y.ah)aU x.ah<y.ah;if(x.a.size()!=y.a.size()){aU(x.ah==1)?(x.a.size()<y.a.size()):(x.a.size()>y.a.size());}bH(bh i=(bh)x.a.size()-1;i>=0;--i){if(x.a[i]!=y.a[i]){aU(x.ah==1)?(x.a[i]<y.a[i]):(x.a[i]>y.a[i]);}}aU ci;}cd af bd>(aT V&x,aT V&y){aU y<x;}cd af bd<=(aT V&x,aT V&y){aU!(y<x);}cd af bd>=(aT V&x,aT V&y){aU!(x<y);}cd af bd==(aT V&x,aT V&y){aU x.ah==y.ah&&x.a==y.a;}cd af bd!=(aT V&x,aT V&y){aU!(x==y);}V&bd+=(aT V&X){if(X.is_zero())aU*cb;if(is_zero())aU*cb=X;if(ah!=X.ah){aT bh eS=ge(a,X.a);if(eS==0){a.clear();ah=1;}cq if(eS>0){fq(a,X.a);}cq{F<bh>o=X.a;fq(o,a);a=std::move(o);ah=X.ah;}aU*cb;}hC(a,X.a);aU*cb;}V&bd-=(aT V&X){if(X.is_zero())aU*cb;if(is_zero())aU*cb=-X;if(ah!=X.ah){hC(a,X.a);aU*cb;}aT bh eS=ge(a,X.a);if(eS==0){a.clear();ah=1;}cq if(eS>0){fq(a,X.a);}cq{F<bh>o=X.a;fq(o,a);a=std::move(o);ah=-ah;}aU*cb;}V&bd*=(bh v){if(v==0||is_zero())aU*cb=0;R dT=v;if(dT<0){ah=-ah;dT=-dT;}a.reserve(a.size()+2);R an=0;bH(bh i=0;i<(bh)a.size()||an;++i){if(i==(bh)a.size())a.push_back(0);aT R jp=a[i]*dT+an;an=jp/Z;a[i]=(bh)(jp%Z);}trim();aU*cb;}dp:br aX bh jH=128;br aX bh jT=224;br aX bh fY=64;br aX bh da=1<<15;ca P{ap aD;ap ax;P bd+(aT P&X)aT{aU{aD+X.aD,ax+X.ax};}P bd-(aT P&X)aT{aU{aD-X.aD,ax-X.ax};}P bd*(aT P&X)aT{aU{aD*X.aD-ax*X.ax,aD*X.ax+ax*X.aD};}P bd*(ap ja)aT{aU{aD*ja,ax*ja};}P conjugate()aT{aU{aD,-ax};}};ca gp{P bA;P ec;};br aT F<P>&eT(bh size){br F<P>aI(2,P{1,0});if(bh(aI.size())<size){bh ae=bh(aI.size());aI.resize(size);bI(ae<size){aT ab jc=std::numbers::pi_v<ab>/ae;aT ab iG=std::cos(jc);aT ab hV=std::sin(jc);bH(bh i=ae;i<2*ae;++i){aI[i]=aI[i/2];if(i&1){aT ab aD=aI[i].aD;aT ab ax=aI[i].ax;aI[i]={ap(aD*iG-ax*hV),ap(aD*hV+ax*iG)};}}ae*=2;}}aU aI;}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
__attribute__((target("avx2,fma"),always_inline))br bP __m256d multiply_complex(__m256d w,__m256d aN){aT __m256d aD=_mm256_movedup_pd(w);aT __m256d ax=_mm256_permute_pd(w,0xf);aT __m256d swapped_root=_mm256_permute_pd(aN,0x5);aU _mm256_fmaddsub_pd(aD,aN,_mm256_mul_pd(ax,swapped_root));}__attribute__((target("avx2,fma"),hot))br O kF(P*ac,bh size){aT F<P>&aI=eT(size);bH(bh ae=size/2;ae>0;ae/=2){bH(bh K=0;K<size;K+=2*ae){bh i=0;bH(;i+1<ae;i+=2){aT __m256d bn=_mm256_loadu_pd(bp<aT ap*>(ac+K+i));aT __m256d bo=_mm256_loadu_pd(bp<aT ap*>(ac+K+i+ae));aT __m256d aN=_mm256_loadu_pd(bp<aT ap*>(aI.data()+ae+i));_mm256_storeu_pd(bp<ap*>(ac+K+i),_mm256_add_pd(bn,bo));_mm256_storeu_pd(bp<ap*>(ac+K+i+ae),multiply_complex(_mm256_sub_pd(bn,bo),aN));}bH(;i<ae;++i){aT P bn=ac[K+i];aT P bo=ac[K+i+ae];ac[K+i]=bn+bo;ac[K+i+ae]=(bn-bo)*aI[ae+i];}}}}__attribute__((target("avx2,fma"),hot))br O jX(P*ac,bh size){aT F<P>&aI=eT(size);aT __m256d conjugate_mask=_mm256_setr_pd(0.0,-0.0,0.0,-0.0);bH(bh ae=1;ae<size;ae*=2){bH(bh K=0;K<size;K+=2*ae){bh i=0;bH(;i+1<ae;i+=2){aT __m256d bn=_mm256_loadu_pd(bp<aT ap*>(ac+K+i));aT __m256d w=_mm256_loadu_pd(bp<aT ap*>(ac+K+i+ae));__m256d aN=_mm256_loadu_pd(bp<aT ap*>(aI.data()+ae+i));aN=_mm256_xor_pd(aN,conjugate_mask);aT __m256d bo=multiply_complex(w,aN);_mm256_storeu_pd(bp<ap*>(ac+K+i),_mm256_add_pd(bn,bo));_mm256_storeu_pd(bp<ap*>(ac+K+i+ae),_mm256_sub_pd(bn,bo));}bH(;i<ae;++i){aT P bn=ac[K+i];aT P w=ac[K+i+ae];aT P aN=aI[ae+i];aT P bo={w.aD*aN.aD+w.ax*aN.ax,w.ax*aN.aD-w.aD*aN.ax};ac[K+i]=bn+bo;ac[K+i+ae]=bn-bo;}}}aT __m256d fC=_mm256_set1_pd(1.0/ap(size));bh i=0;bH(;i+1<size;i+=2){aT __m256d w=_mm256_loadu_pd(bp<aT ap*>(ac+i));_mm256_storeu_pd(bp<ap*>(ac+i),_mm256_mul_pd(w,fC));}bH(;i<size;++i){ac[i].aD/=size;ac[i].ax/=size;}}
#endif
br O jq(P*ac,bh size){(O)0;
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
kF(ac,size);aU;
#endif
aT F<P>&aI=eT(size);bH(bh ae=size/2;ae>0;ae/=2){bH(bh K=0;K<size;K+=2*ae){bH(bh i=0;i<ae;++i){aT P bn=ac[K+i];aT P bo=ac[K+i+ae];ac[K+i]=bn+bo;ac[K+i+ae]=(bn-bo)*aI[ae+i];}}}}br O im(P*ac,bh size){(O)0;
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
jX(ac,size);aU;
#endif
aT F<P>&aI=eT(size);bH(bh ae=1;ae<size;ae*=2){bH(bh K=0;K<size;K+=2*ae){bH(bh i=0;i<ae;++i){aT P bn=ac[K+i];aT P w=ac[K+i+ae];aT P aN=aI[ae+i];aT P bo={w.aD*aN.aD+w.ax*aN.ax,w.ax*aN.aD-w.aD*aN.ax};ac[K+i]=bn+bo;ac[K+i+ae]=bn-bo;}}}aT ap fC=1.0/ap(size);bH(bh i=0;i<size;++i){ac[i].aD*=fC;ac[i].ax*=fC;}}br P iL(aT P&w,aT P&gu){aU(w+gu)*0.5;}br P iH(aT P&w,aT P&gu){aT P it=w-gu;aU{it.ax*0.5,-it.aD*0.5};}br O jY(P*ac,bh size){(O)0;aT bh dy=size/2;aT F<P>&aI=eT(size);br F<P>fZ;br bh ii=0;if(ii!=size){fZ.resize(dy);F<bh>fK(dy);aT bh kS=std::countr_zero(az(dy));bH(bh i=1;i<dy;++i){fK[i]=(fK[i/2]>>1)|((i&1)<<(kS-1));}bH(bh i=0;i<dy;++i){fZ[i]=aI[dy+fK[i]];}ii=size;}bH(bh i=0;i<dy;++i){aT P ad=ac[2*i];aT P al=ac[2*i+1];aT P bn=(ad+al)*0.5;aT P bo=((ad-al)*0.5)*fZ[i].conjugate();ac[i]={bn.aD-bo.ax,bn.ax+bo.aD};}im(ac,dy);}br O bz(F<bh>&w){bI(!w.empty()&&w.back()==0)w.pop_back();}br af fz(aT F<bh>&Q,aT F<bh>&E){aU ge(Q,E)<0;}br bh ge(aT F<bh>&Q,aT F<bh>&E){if(Q.size()!=E.size())aU Q.size()<E.size()?-1:1;bH(bh i=bh(Q.size())-1;i>=0;--i){if(Q[i]!=E[i])aU Q[i]<E[i]?-1:1;}aU 0;}br O hC(F<bh>&Q,aT F<bh>&E){aT bh iJ=bh(Q.size());aT bh fL=bh(E.size());aT bh size=std::max(iJ,fL);if(iJ<fL)Q.resize(fL);bh an=0;bh i=0;bH(;i<fL;++i){aT R ak=(R)Q[i]+E[i]+an;Q[i]=bh(ak>=Z?ak-Z:ak);an=ak>=Z;}bI(i<size&&an){++Q[i];an=Q[i]==Z;if(an)Q[i]=0;++i;}if(an)Q.push_back(1);}br O fq(F<bh>&Q,aT F<bh>&E){(O)0;bh cn=0;bH(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;bz(Q);}br af hD(aT F<bh>&Q,aT F<bh>&E){aU!fz(E,Q);}br F<bh>gk(aT F<bh>&Q,aT F<bh>&E){F<bh>o(std::max(Q.size(),E.size())+1);bH(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]++;}}bz(o);aU o;}br F<bh>cV(aT F<bh>&Q,aT F<bh>&E){(O)0;F<bh>o=Q;bh cn=0;bH(bh i=0;i<bh(o.size());++i){aT 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;bz(o);aU o;}br F<bh>ke(aT F<bh>&Q,aT F<bh>&E){if(Q.empty()||E.empty())aU F<bh>();F<R>aj(Q.size()+E.size());aX R dU=4LL*Z*Z;bH(bh i=0;i<bh(Q.size());++i){bH(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 an=0;bH(bh i=0;i<bh(aj.size())||an>0;++i){if(i<bh(aj.size()))an+=aj[i];o.push_back(bh(an%Z));an/=Z;}bz(o);aU o;}br F<bh>kp(aT F<bh>&w){if(w.empty())aU F<bh>();F<R>aj(2*w.size());aX R dU=4LL*Z*Z;bH(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;}bH(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 an=0;bH(bh i=0;i<bh(aj.size())||an>0;++i){if(i<bh(aj.size()))an+=aj[i];o.push_back(bh(an%Z));an/=Z;}bz(o);aU o;}br F<bh>ft(aT F<bh>&w,bh dT){(O)0;if(w.empty()||dT==0)aU F<bh>();F<bh>o;o.reserve(w.size()+1);uint64_t an=0;bH(bh kZ:w){aT uint64_t ak=uint64_t(kZ)*dT+an;o.push_back(bh(ak%Z));an=ak/Z;}if(an)o.push_back(bh(an));aU o;}br F<bh>gm(aT F<bh>&Q,aT F<bh>&E){bE cO=cP::ag<998244353>;bE bW=cP::ag<754974721>;bE bB=cP::ag<469762049>;aT bh aQ=bh(Q.size()+E.size()-1);(O)0;by gw=[&]<bq C>(){F<C>x(Q.begin(),Q.end());if(&Q==&E)aU hl::il(x,x);F<C>y(E.begin(),E.end());aU hl::il(x,y);};aT F<cO>kB=gw.aZ bd()<cO>();aT F<bW>kC=gw.aZ bd()<bW>();aT F<bB>kD=gw.aZ bd()<bB>();aX uint64_t hb=cO::D();aX uint64_t fd=bW::D();aX uint64_t eD=bB::D();aX uint64_t gU=hb*fd;aT br uint64_t gd=bW(hb).inv().val();aT br uint64_t jO=bB(gU%eD).inv().val();[[maybe_unused]]aT cg __int128 gc=bi<cg __int128>(std::min(Q.size(),E.size()))*(Z-1)*(Z-1);[[maybe_unused]]aX cg __int128 lA=bi<cg __int128>(gU)*eD;(O)0;F<bh>o;o.reserve(aQ+2);cg __int128 an=0;bH(bh i=0;i<aQ||an>0;++i){if(i<aQ){aT uint64_t ad=kB[i].val();aT uint64_t al=kC[i].val();aT uint64_t kU=kD[i].val();aT uint64_t km=(al+fd-ad%fd)%fd;aT uint64_t kv=km*gd%fd;aT uint64_t ir=ad+hb*kv;aT uint64_t kq=(kU+eD-ir%eD)%eD;aT uint64_t kA=kq*jO%eD;an+=ir+bi<cg __int128>(gU)*kA;}o.push_back(bh(an%Z));an/=Z;}bz(o);aU o;}ca eL{uint32_t eY;uint32_t eX;};aZ<bh hd>br uint32_t fw(uint64_t w){aX uint64_t fM=(uint64_t(1)<<hd)-1;w=(w&fM)+(w>>hd);w=(w&fM)+(w>>hd);if(w>=fM)w-=fM;aU uint32_t(w);}br eL fX(aT F<bh>&w){eL o{0,0};bH(bh i=bh(w.size())-1;i>=0;--i){o.eY=fw<31>(uint64_t(o.eY)*Z+w[i]);o.eX=fw<29>(uint64_t(o.eX)*Z+w[i]);}aU o;}br af kb(aT F<bh>&Q,aT F<bh>&E,aT F<bh>&aj){aT eL iD=fX(Q);aT eL iF=fX(E);aT eL iR=fX(aj);aU iR.eY==fw<31>(uint64_t(iD.eY)*iF.eY)&&iR.eX==fw<29>(uint64_t(iD.eX)*iF.eX);}br F<bh>ko(aT F<bh>&Q,aT F<bh>&E){aT bh aQ=bh(Q.size()+E.size()-1);aT bh aF=bh(std::bit_ceil(az(aQ)));aT cg __int128 gc=bi<cg __int128>(std::min(Q.size(),E.size()))*2*(da-1)*((Z-1)/da);if(aF>(1<<20)||gc>=(uint64_t(1)<<50)){aU gm(Q,E);}std::unique_ptr<P[]>cr(new P[aF]);bH(bh i=0;i<bh(Q.size());++i){cr[i]={ap(Q[i]%da),ap(Q[i]/da)};}std::fill(cr.get()+Q.size(),cr.get()+aF,P{0,0});jq(cr.get(),aF);aT af cD=&Q==&E;std::unique_ptr<P[]>cx(new P[aF]);if(!cD){bH(bh i=0;i<bh(E.size());++i){cx[i]={ap(E[i]%da),ap(E[i]/da)};}std::fill(cx.get()+E.size(),cx.get()+aF,P{0,0});jq(cx.get(),aF);}br F<bh>er;if(bh(er.size())<aF){aT bh kk=bh(er.size());er.resize(aF);bH(bh i=std::max(1,kk);i<aF;++i){er[i]=i^bh(std::bit_floor(az(i))-1);}}by hG=[&](bh dj){aT bh dB=er[dj];aT P hZ=cr[dB].conjugate();aT P gG=iL(cr[dj],hZ);aT P gz=iH(cr[dj],hZ);P gJ=gG;P gB=gz;if(!cD){aT P ib=cx[dB].conjugate();gJ=iL(cx[dj],ib);gB=iH(cx[dj],ib);}aT P kr=gG*gJ;aT P ic=gz*gB;aT P bA=kr+P{-ic.ax,ic.aD};aT P ec=gG*gB+gz*gJ;aU gp{bA,ec};};bH(bh i=0;i<aF;++i){aT bh dB=er[i];if(i>dB)cj;aT gp gA=hG(i);gp gf=gA;if(i!=dB)gf=hG(dB);cr[i]=gA.bA;cr[dB]=gf.bA;cx[i]=gA.ec;cx[dB]=gf.ec;}im(cr.get(),aF);jY(cx.get(),aF);F<bh>o;o.reserve(aQ+2);cg __int128 an=0;bH(bh i=0;i<aQ||an>0;++i){if(i<aQ){aT R eH=std::llround(cr[i].aD);aT R jg=std::llround(cr[i].ax);aT P ih=cx[i/2];aT R ec=std::llround((i&1)?ih.ax:ih.aD);if(eH<0||jg<0||ec<0)aU gm(Q,E);an+=eH+bi<cg __int128>(ec)*da+bi<cg __int128>(jg)*da*da;}o.push_back(bh(an%Z));an/=Z;}bz(o);if(o.empty()||!kb(Q,E,o)){aU gm(Q,E);}aU o;}br F<bh>cU(aT F<bh>&Q,aT F<bh>&E){if(Q.empty()||E.empty())aU F<bh>();if(Q.size()==1)aU ft(E,Q[0]);if(E.size()==1)aU ft(Q,E[0]);if(&Q==&E&&Q.size()<=jT){aU kp(Q);}if(std::min(Q.size(),E.size())<=jH){aU ke(Q,E);}aU ko(Q,E);}br aB<F<bh>,F<bh>>fy(aT F<bh>&aW,bh aM){(O)0;if(aM==1){aU std::make_pair(aW,F<bh>());}F<bh>ay(aW.size());R aL=0;bH(bh i=bh(aW.size())-1;i>=0;--i){aT R ak=aL*Z+aW[i];ay[i]=bh(ak/aM);aL=ak%aM;}bz(ay);F<bh>hP;if(aL!=0)hP.push_back(bh(aL));aU std::make_pair(std::move(ay),std::move(hP));}br aB<F<bh>,F<bh>>hN(aT F<bh>&aW,aT F<bh>&aM){(O)0;if(aM.size()==1)aU fy(aW,aM[0]);if(fz(aW,aM)){aU std::make_pair(F<bh>(),aW);}aT bh cy=Z/(aM.back()+1);F<bh>bs(aM.size());uint64_t an=0;bH(bh i=0;i<bh(aM.size());++i){aT uint64_t ak=uint64_t(aM[i])*cy+an;bs[i]=bh(ak%Z);an=ak/Z;}(O)0;F<bh>bj(aW.size()+1);an=0;bH(bh i=0;i<bh(aW.size());++i){aT uint64_t ak=uint64_t(aW[i])*cy+an;bj[i]=bh(ak%Z);an=ak/Z;}bj[aW.size()]=bh(an);aT bh cl=bh(bs.size());aT bh ia=bh(aW.size())-cl+1;aT uint64_t fv=bs.back();aT uint64_t kh=bs[cl-2];F<bh>ay(ia);bH(bh bt=ia-1;bt>=0;--bt){aT uint64_t gh=uint64_t(bj[bt+cl])*Z+bj[bt+cl-1];uint64_t dF=gh/fv;uint64_t aL=gh%fv;if(dF>=Z){dF=Z-1;aL=gh-dF*fv;}bI(aL<Z&&dF*kh>aL*Z+bj[bt+cl-2]){--dF;aL+=fv;}uint64_t cn=0;bH(bh i=0;i<cl;++i){aT uint64_t aj=dF*uint64_t(bs[i])+cn;aT uint64_t eH=aj%Z;cn=aj/Z;if(uint64_t(bj[bt+i])<eH){bj[bt+i]=bh(uint64_t(bj[bt+i])+Z-eH);++cn;}cq{bj[bt+i]-=bh(eH);}}R hs=(R)bj[bt+cl]-bi<R>(cn);if(hs<0){--dF;uint64_t gt=0;bH(bh i=0;i<cl;++i){aT uint64_t ak=uint64_t(bj[bt+i])+bs[i]+gt;bj[bt+i]=bh(ak%Z);gt=ak/Z;}hs+=gt;}(O)0;bj[bt+cl]=bh(hs);ay[bt]=bh(dF);}bz(ay);F<bh>aL(bj.begin(),bj.begin()+cl);bz(aL);aB<F<bh>,F<bh>>eP=fy(aL,cy);(O)0;aU std::make_pair(std::move(ay),std::move(eP.first));}br F<bh>reciprocal(aT F<bh>&w,bh de){(O)0;(O)0;(O)0;bh bT=de;aT bh ix=bh(w.size());bI(bT>fY)bT=(bT+1)/2;F<bh>bf(ix+bT+1);bf.back()=1;bf=hN(bf,w).first;bI(bT<de){F<bh>gR=cU(bf,bf);gR.insert(gR.begin(),0);aT bh ez=std::min(ix,2*bT+1);aT F<bh>cE(w.end()-ez,w.end());F<bh>fF=cU(gR,cE);(O)0;fF.erase(fF.begin(),fF.begin()+ez);F<bh>gK(bT+1);aT F<bh>iK=gk(bf,bf);gK.insert(gK.end(),iK.begin(),iK.end());bf=cV(gK,fF);(O)0;bf.erase(bf.begin());bT*=2;}(O)0;bf.erase(bf.begin(),bf.begin()+bT-de);bz(bf);aU bf;}br aB<F<bh>,F<bh>>jV(aT F<bh>&aW,aT F<bh>&aM){(O)0;if(aM.size()<=fY||bh(aW.size())-bh(aM.size())<=fY){aU hN(aW,aM);}if(aW.size()>2*aM.size()){aT bh iw=bh(aW.size()/aM.size());aT bh jU=iw>=16?3:iw>=7?2:1;aT bh be=jU*bh(aM.size());aT bh dS=(bh(aW.size())+be-1)/be;aT bh cy=Z/(aM.back()+1);aT F<bh>bs=ft(aM,cy);aT bh de=be+3;aT F<bh>bf=reciprocal(bs,de);aT bh fI=bh(aM.size())+de;by kn=[&](aT F<bh>&ak){aT F<bh>ga=ft(ak,cy);F<bh>gi=cU(ga,bf);F<bh>dt;if(bh(gi.size())>fI){dt.assign(gi.begin()+fI,gi.end());}F<bh>aj=cU(bs,dt);bI(fz(ga,aj)){dt=cV(dt,F<bh>(1,1));aj=cV(aj,bs);}F<bh>eM=cV(ga,aj);bI(hD(bs,eM)){dt=gk(dt,F<bh>(1,1));eM=cV(eM,bs);}bz(dt);bz(eM);aB<F<bh>,F<bh>>eP=fy(eM,cy);(O)0;aU std::make_pair(std::move(dt),std::move(eP.first));};F<bh>ay(aW.size());F<bh>aL;bH(bh av=dS-1;av>=0;--av){aT bh begin=av*be;aT 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());bz(ak);aB<F<bh>,F<bh>>gH=kn(ak);(O)0;std::copy(gH.first.begin(),gH.first.end(),ay.begin()+begin);aL=std::move(gH.second);}bz(ay);bz(aL);aU std::make_pair(std::move(ay),std::move(aL));}aT bh cy=Z/(aM.back()+1);aT F<bh>bj=cU(aW,F<bh>(1,cy));aT F<bh>bs=cU(aM,F<bh>(1,cy));aT bh kj=bh(bj.size());aT bh cl=bh(bs.size());aT bh de=kj-cl+2;aT F<bh>bf=reciprocal(bs,de);F<bh>ay=cU(bj,bf);aT bh fI=cl+de;(O)0;ay.erase(ay.begin(),ay.begin()+fI);F<bh>aj=cU(bs,ay);bI(fz(bj,aj)){ay=cV(ay,F<bh>(1,1));aj=cV(aj,bs);}F<bh>aL=cV(bj,aj);bI(hD(bs,aL)){ay=gk(ay,F<bh>(1,1));aL=cV(aL,bs);}bz(ay);bz(aL);aB<F<bh>,F<bh>>eP=fy(aL,cy);(O)0;aU std::make_pair(std::move(ay),std::move(eP.first));}dr:V&bd*=(aT V&X){if(is_zero()||X.is_zero())aU*cb=0;aT bh ks=ah*X.ah;a=cU(a,X.a);ah=ks;trim();aU*cb;}cd aB<V,V>gM(aT V&a1,aT V&b1){if(b1.is_zero()){throw std::domain_error("BigInt division by zero");}aB<F<bh>,F<bh>>o=jV(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();aU{q,r};}cd V fi(V ad,V al){ad.ah=1;al.ah=1;bI(!al.is_zero()){ad%=al;std::swap(ad,al);}aU ad;}V&bd/=(aT V&X){aU*cb=gM(*cb,X).first;}V&bd%=(aT V&X){aU*cb=gM(*cb,X).second;}cd V bd+(V x,aT V&y){aU x+=y;}cd V bd-(V x,aT V&y){aU x-=y;}cd V bd*(V x,aT V&y){aU x*=y;}cd V bd/(V x,aT V&y){aU x/=y;}cd V bd%(V x,aT V&y){aU x%=y;}cd std::ostream&bd<<(std::ostream&os,aT V&b){aU os<<b.to_string();}cd std::istream&bd>>(std::istream&is,V&b){std::string s;if(is>>s)b.read(s);aU is;}};}}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
#undef M1UNE_BIGINT_HAS_X86_SIMD
#endif
bD bc{bD cP{bD hS{aZ<bq 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<hS::IntegerLike T=R>ca aq{dp:br aX af fu=std::signed_integral<T>;bE at=std::conditional_t<fu,aS,T>;bE bS=std::conditional_t<fu,aP,T>;T aH;T aG;br aX bS aV(at w){if aX(fu){if(w<0){aU bi<bS>(-(w+1))+1;}aU bi<bS>(w);}cq{aU w<0?-w:w;}}br aX bS fi(bS ad,bS al){bI(al!=0){bS aL=ad%al;ad=al;al=aL;}aU ad;}br aX T iV(at w){if aX(fu){(O)0;(O)0;aU bi<T>(w);}cq{aU w;}}aX O assign_normalized(at numerator,at denominator){(O)0;if(numerator==0){aH=0;aG=1;aU;}bS aM=fi(aV(numerator),aV(denominator));numerator/=bi<at>(aM);denominator/=bi<at>(aM);if(denominator<0){numerator=-numerator;denominator=-denominator;}aH=iV(numerator);aG=iV(denominator);}br aX aq iC(at numerator,at denominator){aq o;o.assign_normalized(numerator,denominator);aU o;}br aB<ab,R>hH(aT T&w){std::ostringstream bV;bV<<w;aT 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;}bI(begin<cR.size()&&cR[begin]=='0')++begin;if(begin==cR.size())aU std::make_pair(0.0L,0LL);aX bh kJ=std::numeric_limits<ab>::digits10+1;aT std::size_t fh=std::min<std::size_t>(kJ,cR.size()-begin);ab fD=0;bH(std::size_t i=0;i<fh;++i){(O)0;fD=fD*10+(cR[begin+i]-'0');}bH(std::size_t i=1;i<fh;++i)fD/=10;aT R bk=bi<R>(cR.size()-begin-1);aU std::make_pair(ah*fD,bk);}dr:aX aq():aH(0),aG(1){}aX aq(T gF):aH(gF),aG(1){}aZ<std::integral U>cp std::constructible_from<T,U>&&(!std::same_as<std::remove_cv_t<U>,T>)aX aq(U gF):aq(T(gF)){}aX aq(T numerator,T denominator){assign_normalized(at(numerator),at(denominator));}aX T numerator()aT{aU aH;}aX T denominator()aT{aU aG;}aX af lH()aT{aU aG==1;}aX bh ah()aT{aU(aH>0)-(aH<0);}aX aq reciprocal()aT{(O)0;aU iC(at(aG),at(aH));}aX aq abs()aT{aU aH<0?-*cb:*cb;}aX ab gj()aT cp cp(aT T&w){bi<ab>(w);}{aU bi<ab>(aH)/bi<ab>(aG);}ab gj()aT cp(!cp(aT T&w){bi<ab>(w);}){aT by[numerator,jP]=hH(aH);aT by[denominator,jM]=hH(aG);aU numerator/denominator*std::pow(10.0L,jP-jM);}dq aX bd ab()aT cp cp(aT T&w){bi<ab>(w);}{aU gj();}dq bd ab()aT cp(!cp(aT T&w){bi<ab>(w);}){aU gj();}aX T lY()aT{aU aH/aG;}aX T fQ()aT{T ay=aH/aG;if(aH<0&&aH%aG!=0)ay-=T(1);aU ay;}aX T kY()aT{T ay=aH/aG;if(0<aH&&aH%aG!=0)ay+=T(1);aU ay;}aX aq bd+()aT{aU*cb;}aX aq bd-()aT{aU iC(-at(aH),at(aG));}aX aq&bd+=(aT aq&X){bS iT=fi(bi<bS>(aG),bi<bS>(X.aG));at iu=at(X.aG)/bi<at>(iT);at kt=at(aG)/bi<at>(iT);assign_normalized(at(aH)*iu+at(X.aH)*kt,at(aG)*iu);aU*cb;}aX aq&bd-=(aT aq&X){aU*cb+=-X;}aX aq&bd*=(aT aq&X){bS iB=fi(aV(at(aH)),bi<bS>(X.aG));bS iv=fi(aV(at(X.aH)),bi<bS>(aG));assign_normalized((at(aH)/bi<at>(iB))*(at(X.aH)/bi<at>(iv)),(at(aG)/bi<at>(iv))*(at(X.aG)/bi<at>(iB)));aU*cb;}aX aq&bd/=(aT aq&X){aU*cb*=X.reciprocal();}cd aX aq bd+(aq bx,aT aq&bw){aU bx+=bw;}cd aX aq bd-(aq bx,aT aq&bw){aU bx-=bw;}cd aX aq bd*(aq bx,aT aq&bw){aU bx*=bw;}cd aX aq bd/(aq bx,aT aq&bw){aU bx/=bw;}cd aX af bd==(aT aq&bx,aT aq&bw){aU bx.aH==bw.aH&&bx.aG==bw.aG;}cd aX std::strong_ordering bd<=>(aT aq&bx,aT aq&bw){at ad=at(bx.aH)*at(bw.aG);at al=at(bw.aH)*at(bx.aG);if(ad<al)aU std::strong_ordering::less;if(al<ad)aU std::strong_ordering::greater;aU std::strong_ordering::equal;}cd std::ostream&bd<<(std::ostream&bV,aT aq&w){bV<<w.aH;if(w.aG!=1){bV<<'/'<<w.aG;}aU bV;}cd std::istream&bd>>(std::istream&cu,aq&w){std::string fc;if(!(cu>>fc))aU cu;std::size_t eZ=fc.find('/');if(eZ!=std::string::npos&&fc.find('/',eZ+1)!=std::string::npos){cu.setstate(std::ios::failbit);aU cu;}T numerator=0;T denominator=1;std::istringstream hR(fc.substr(0,eZ));if(!(hR>>numerator)||hR.peek()!=std::char_traits<aK>::eof()){cu.setstate(std::ios::failbit);aU cu;}if(eZ!=std::string::npos){std::istringstream hL(fc.substr(eZ+1));if(!(hL>>denominator)||hL.peek()!=std::char_traits<aK>::eof()){cu.setstate(std::ios::failbit);aU cu;}}w=aq(numerator,denominator);aU cu;}};aZ<hS::IntegerLike T>aX aq<T>abs(aT aq<T>&w){aU w.abs();}}}bD bc{bD eB{aZ<bq T=bh>ca ha{bE kx=T;bh dn;bh to;T dm;bh id;af di;ha():dn(-1),to(-1),dm(T()),id(-1),di(cw){}ha(bh kQ,bh lk,T kO=T(1),bh ld=-1,af kK=cw):dn(kQ),to(lk),dm(kO),id(ld),di(kK){}bh X(bh v)aT{(O)0;aU dn^to^v;}};aZ<bq T=bh>ca dg{bE cB=ha<T>;bE kx=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()aT{aU _n;}af empty()aT{aU _n==0;}bh lF()aT{aU cs;}bh lE(){_g.emplace_back();aU _n++;}bh lv(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});aU id;}bh add_edge(bh u,bh v,T dm=T(1)){(O)0;(O)0;bh id=cs++;bh kV=bh(_g[u].size());_g[u].push_back(cB(u,v,dm,id));bh kW=bh(_g[v].size());_g[v].push_back(cB(v,u,dm,id));cW.emplace_back();cW.back().push_back({u,kV});cW.back().push_back({v,kW});aU id;}O hU(bh id,af di){(O)0;bH(by[v,eh]:cW[id]){_g[v][eh].di=di;}}O lG(bh id){hU(id,ci);}O lC(bh id){hU(id,cw);}af ly(bh id)aT{(O)0;(O)0;by[v,eh]=cW[id][0];aU _g[v][eh].di;}aT F<cB>&bd[](bh v)aT{(O)0;aU _g[v];}F<cB>&bd[](bh v){(O)0;aU _g[v];}aT F<F<cB>>&kw()aT{aU _g;}F<F<cB>>&kw(){aU _g;}F<cB>lX(af jW=ci)aT{F<cB>o;o.reserve(cs);F<aK>fh(cs,ci);bH(bh v=0;v<_n;v++){bH(aT by&e:_g[v]){if(!jW&&!e.di)cj;if(0<=e.id&&e.id<cs){if(fh[e.id])cj;fh[e.id]=cw;}o.push_back(e);}}aU o;}dg fK()aT{dg o(_n);o.cs=cs;o.cW.assign(cs,{});bH(bh v=0;v<_n;v++){bH(aT by&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});}}aU o;}};}}bD bc{bD eB{aZ<bq T>ca es{F<T>bN;F<aK>ey;F<bh>gP;F<bh>ip;T eF=T();af reachable(bh v)aT{(O)0;aU ey[v];}F<bh>mc(bh t)aT{(O)0;F<bh>o;bH(bh v=t;v!=-1;v=gP[v])o.push_back(v);std::reverse(o.begin(),o.end());aU o;}};bD au{aZ<bq T>ca gb{T bN;bh gT;};aZ<bq T>ca jL{af bd()(aT gb<T>&ad,aT gb<T>&al)aT{aU al.bN<ad.bN;}};}aZ<bq T>es<T>dX(aT dg<T>&g,aT F<bh>&gL){bh n=g.size();es<T>o;o.bN.resize(n);o.ey.assign(n,ci);o.gP.assign(n,-1);o.ip.assign(n,-1);bE fe=au::gb<T>;bE kH=au::jL<T>;std::priority_queue<fe,F<fe>,kH>fl;bH(bh s:gL){(O)0;if(o.ey[s])cj;o.ey[s]=cw;o.bN[s]=T();fl.push(fe{T(),s});}bI(!fl.empty()){fe ak=fl.top();fl.pop();if(o.bN[ak.gT]<ak.bN)cj;bH(aT by&e:g[ak.gT]){if(!e.di)cj;T nd=ak.bN+e.dm;if(o.ey[e.to]&&!(nd<o.bN[e.to]))cj;o.ey[e.to]=cw;o.bN[e.to]=nd;o.gP[e.to]=ak.gT;o.ip[e.to]=e.id;fl.push(fe{std::move(nd),e.to});}}aU o;}aZ<bq T>es<T>dX(aT dg<T>&g,bh s){aU dX(g,F<bh>{s});}aZ<bq T>es<T>dX(aT dg<T>&g,aT F<bh>&gL,aT T&eF){es<T>o=dX(g,gL);o.eF=eF;bH(bh v=0;v<bh(o.bN.size());v++){if(!o.reachable(v))o.bN[v]=eF;}aU o;}aZ<bq T>es<T>dX(aT dg<T>&g,bh s,aT T&eF){aU dX(g,F<bh>{s},eF);}}}bE lb=bc::cP::aq<bc::ew::V>;O kT(){bh N,M;ji(N,M);bc::eB::dg<lb>eB(N);FOR(M){bh u,v,a,b;ji(u,v,a,b);--u,--v;eB.add_edge(u,v,{a,b});}by bg=bc::eB::dX(eB,0);by&bN=bg.bN;FOR(i,1,N){gW(bN[i].numerator().to_string(),bN[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;bI(T--)kT();aU 0;}