using aa=long long;using ab=long double;using ad=bool;using ak=double;using as=unsigned;using aJ=void;using aM=unsigned char;using bc=char;using bj=__uint128_t;using bk=unsigned long long;using bv=__int128_t;
#define M1UNE_FPS_DISABLE_X86_SIMD 1
#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(...)
#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>
#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>
template<class...T>using ba=std::pair<T...>;
#include <valarray>
#include <variant>
#include <vector>
template<class...T>using m=std::vector<T...>;
#include <version>
#include <sys/stat.h>
#include <unistd.h>
namespace ay{namespace cy{namespace ag{template<class T,class=aJ>struct ge:std::false_type{};template<class T>struct ge<T,std::void_t<decltype(std::begin(std::declval<T&>())),decltype(std::end(std::declval<T&>()))>>:std::true_type{};template<class T>inline constexpr ad cx=ge<T>::value;template<class T>using gT=decltype(*std::begin(std::declval<T&>()));template<class T>using hm=std::remove_cv_t<std::remove_reference_t<gT<T>>>;template<class T,class=aJ>struct fk{using type=hm<T>;};template<class T>struct fk<T,std::void_t<typename std::remove_cv_t<std::remove_reference_t<T>>::value_type>>{using type=typename std::remove_cv_t<std::remove_reference_t<T>>::value_type;};template<class T>using fe=typename fk<T>::type;template<class T>struct fy:std::false_type{};template<class T,std::size_t N>struct fy<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,bc>>{};template<class T>struct hd:std::bool_constant<std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,const bc*>||std::is_same_v<std::decay_t<T>,bc*>||fy<std::remove_reference_t<T>>::value>{};template<class T>inline constexpr ad dj=hd<T>::value;template<class T,class=aJ>struct fu:std::false_type{};template<class T>struct fu<T,std::void_t<decltype(std::declval<const T&>().val())>>:std::true_type{};template<class T>inline constexpr ad fo=fu<T>::value;template<class T,class=aJ>struct fi:std::false_type{};template<class T>struct fi<T,std::void_t<decltype(T::E()),decltype(T::bZ(std::declval<uint32_t>()))>>:std::true_type{};template<class T>inline constexpr ad gO=fi<T>::value;template<class T>inline constexpr ad dr=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,bv>||std::is_same_v<std::remove_cv_t<T>,bj>;template<class T>inline constexpr ad ed=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,bv>;template<class T>struct dY{using type=std::make_unsigned_t<T>;};template<>struct dY<bv>{using type=bj;};template<>struct dY<bj>{using type=bj;};template<class T>using hb=typename dY<std::remove_cv_t<T>>::type;}struct bR{static constexpr int bn=1<<20;private:std::FILE*cj;bc aw[bn];int W;int aS;int di;ad ef;ad gp(){W=0;if(ef){ssize_t J;do{J=::read(di,aw,bn);}while(J<0&&errno==EINTR);if(J<=0){aS=0;return false;}aS=int(J);}else{aS=int(std::fread(aw,1,bn,cj));}return aS!=0;}template<class T>ad gK(T&f){if(!dv())return false;int c=aU();ad br=false;if(c=='-'){br=true;c=aU();}if constexpr(ag::ed<T>){T h=0;while('0'<=c&&c<='9'){h=br?h*10-(c-'0'):h*10+(c-'0');c=aU();}f=h;}else{T h=0;while('0'<=c&&c<='9'){h=h*10+T(c-'0');c=aU();}f=br?T(0)-h:h;}return true;}ad hg(){if(aS-W>=64)return true;const int bT=aS-W;if(bT>0)std::memmove(aw,aw+W,bT);const int hT=int(std::fread(aw+bT,1,bn-bT,cj));W=0;aS=bT+hT;if(aS<bn)aw[aS]='\0';return aS!=0;}public:explicit bR(std::FILE*dF=stdin):cj(dF),W(0),aS(0),di(::fileno(dF)),ef([&]{struct stat gr;return di>=0&&::fstat(di,&gr)==0&&!S_ISREG(gr.st_mode);}()){}bR(const bR&)=delete;bR&operator=(const bR&)=delete;int aU(){if(W==aS&&!gp())return EOF;return aw[W++];}ad dv(){int c=aU();while(c!=EOF&&c<=' ')c=aU();if(c==EOF)return false;--W;return true;}ad read(bc&f){if(!dv())return false;f=bc(aU());return true;}ad read(std::string&f){if(!dv())return false;f.clear();while(true){const int begin=W;while(W<aS&&static_cast<aM>(aw[W])>' '){++W;}f.append(aw+begin,W-begin);if(W<aS){++W;return true;}if(!gp())return true;}}ad read(ad&f){int x;if(!read(x))return false;f=x!=0;return true;}template<class T>std::enable_if_t<ag::dr<T>&&!std::is_same_v<std::remove_cv_t<T>,ad>&&!std::is_same_v<std::remove_cv_t<T>,bc>,ad>read(T&f){if(ef)return gK(f);if(!hg())return false;int c=static_cast<aM>(aw[W++]);while(c<=' ')c=static_cast<aM>(aw[W++]);ad br=false;if(c=='-'){br=true;c=static_cast<aM>(aw[W++]);}if constexpr(ag::ed<T>){T h=0;while('0'<=c&&c<='9'){const int H=c-'0';const int R=static_cast<aM>(aw[W])-'0';if(0<=R&&R<=9){h=br?h*100-(H*10+R):h*100+(H*10+R);++W;}else{h=br?h*10-H:h*10+H;}c=static_cast<aM>(aw[W++]);}f=h;}else{T h=0;while('0'<=c&&c<='9'){const as H=as(c-'0');const int R=static_cast<aM>(aw[W])-'0';if(0<=R&&R<=9){h=h*100+T(H*10+as(R));++W;}else{h=h*10+T(H);}c=static_cast<aM>(aw[W++]);}f=br?T(0)-h:h;}if(W>aS)W=aS;return true;}template<class T>std::enable_if_t<std::is_floating_point_v<T>,ad>read(T&f){if(!dv())return false;int c=aU();ad br=false;if(c=='-'||c=='+'){br=c=='-';c=aU();}ab h=0;while('0'<=c&&c<='9'){h=h*10+(c-'0');c=aU();}if(c=='.'){ab gt=0.1L;c=aU();while('0'<=c&&c<='9'){h+=(c-'0')*gt;gt*=0.1L;c=aU();}}if(c=='e'||c=='E'){c=aU();ad fm=false;if(c=='-'||c=='+'){fm=c=='-';c=aU();}int aB=0;while('0'<=c&&c<='9'){aB=aB*10+(c-'0');c=aU();}ab eM=1;ab eJ=10;while(aB>0){if(aB&1)eM*=eJ;eJ*=eJ;aB>>=1;}h=fm?h/eM:h*eM;}f=static_cast<T>(br?-h:h);return true;}template<class T>std::enable_if_t<ag::fo<T>&&!ag::dr<T>&&!ag::cx<T>,ad>read(T&f){aa x;if(!read(x))return false;if constexpr(ag::gO<T>){if(x>=0&&uint64_t(x)<uint64_t(T::E())){f=T::bZ(uint32_t(x));}else{f=T(x);}}else{f=T(x);}return true;}template<class cl,class cU>ad read(ba<cl,cU>&f){if(!read(f.first))return false;return read(f.second);}template<class bH>std::enable_if_t<ag::cx<bH>&&!ag::dj<bH>,ad>read(bH&eL){using cf=ag::fe<bH>;constexpr ad dE=ag::cx<cf>&&!ag::dj<cf>;for(auto&&f:eL){if constexpr(std::is_same_v<cf,ad>&&!dE){ad x;if(!read(x))return false;f=x;}else{if(!read(f))return false;}}return true;}template<class cl,class cU,class...eP>ad read(cl&H,cU&R,eP&...rest){if(!read(H))return false;return read(R,rest...);}template<class T>bR&operator>>(T&f){if(!read(f))std::abort();return*this;}};struct bB{static constexpr int bn=1<<20;private:inline static const auto cM=[]{std::array<bc,40000>h{};for(int i=0;i<10000;i++){int f=i;for(int j=3;j>=0;j--){h[4*i+j]=bc('0'+f%10);f/=10;}}return h;}();std::FILE*cj;bc aw[bn];int W;int cN;std::chars_format dq;bc dT;public:explicit bB(std::FILE*dF=stdout):cj(dF),W(0),cN(6),dq(std::chars_format::general),dT(' '){}bB(const bB&)=delete;bB&operator=(const bB&)=delete;~bB(){dH();}aJ dH(){if(W!=0){std::fwrite(aw,1,W,cj);W=0;}std::fflush(cj);}aJ bo(bc c){if(W==bn)dH();aw[W++]=c;}aJ aT(const bc*s){while(*s!='\0')bo(*s++);}aJ aT(const std::string&s){std::size_t aG=0;while(aG<s.size()){if(W==bn)dH();const std::size_t ck=std::min<std::size_t>(bn-W,s.size()-aG);std::memcpy(aw+W,s.data()+aG,ck);W+=int(ck);aG+=ck;}}aJ aT(bc c){bo(c);}aJ aT(ad f){bo(f?'1':'0');}template<class T>std::enable_if_t<std::is_floating_point_v<T>>aT(T f){bc bF[128];auto[end,hV]=std::to_chars(bF,bF+sizeof(bF),f,dq,cN);if(hV!=std::errc())std::abort();for(const bc*ew=bF;ew!=end;ew++){bo(*ew);}}template<class T>std::enable_if_t<ag::dr<T>&&!std::is_same_v<std::remove_cv_t<T>,ad>&&!std::is_same_v<std::remove_cv_t<T>,bc> >aT(T f){using gx=std::remove_cv_t<T>;using cS=ag::hb<gx>;cS at;if constexpr(ag::ed<gx>){if(f<0){bo('-');at=cS(0)-cS(f);}else{at=cS(f);}}else{at=f;}if(at==0){bo('0');return;}as gl[16];int bJ=0;while(at>=10000){const cS ae=at/10000;gl[bJ++]=as(at-ae*10000);at=ae;}if(W>bn-64)dH();const as bs=as(at);const bc*H=cM.data()+4*bs;int eS=bs<10?3:bs<100?2:bs<1000?1:0;for(;eS<4;eS++)aw[W++]=H[eS];while(bJ--){const bc*bF=cM.data()+4*gl[bJ];std::memcpy(aw+W,bF,4);W+=4;}}template<class T>std::enable_if_t<ag::fo<T>&&!ag::dr<T>&&!ag::cx<T> >aT(const T&f){aT(f.val());}template<class cl,class cU>aJ aT(const ba<cl,cU>&f){aT(f.first);bo(' ');aT(f.second);}template<class bH>std::enable_if_t<ag::cx<bH>&&!ag::dj<bH> >aT(const bH&eL){using cf=ag::fe<const bH>;constexpr ad dE=ag::cx<cf>&&!ag::dj<cf>;ad H=true;for(const auto&f:eL){if(!H)bo(dE?'\n':dT);H=false;if constexpr(std::is_same_v<cf,ad>&&!dE){aT(static_cast<ad>(f));}else{aT(f);}}}template<class cl,class...eP>aJ eK(const cl&H,const eP&...rest){aT(H);((bo(' '),aT(rest)),...);}aJ println(){bo('\n');}aJ iA(int aQ){cN=aQ;}aJ iI(int aQ=6){dq=std::chars_format::fixed;cN=aQ;}aJ iC(int aQ=6){dq=std::chars_format::general;cN=aQ;}aJ iv(bc hK){dT=hK;}template<class...Args>aJ println(const Args&...args){eK(args...);bo('\n');}template<class T>bB&operator<<(const T&f){aT(f);return*this;}};}}using namespace std;namespace ay{namespace bx{inline cy::bR&bg(){static cy::bR eo;return eo;}inline cy::bB&aX(){static cy::bB eo;return eo;}}}using ll=aa;using cF=unsigned int;using cG=bk;using eR=__int128;using iZ=unsigned __int128;
#ifdef __SIZEOF_FLOAT128__
using iX=__float128;
#endif
template<class T>constexpr T aZ=0;template<>constexpr int aZ<int> =1'000'000'000;template<>constexpr ll aZ<ll> =ll(aZ<int>)*aZ<int>*2;template<>constexpr cF aZ<cF> =aZ<int>;template<>constexpr cG aZ<cG> =aZ<ll>;template<>constexpr eR aZ<eR> =eR(aZ<ll>)*aZ<ll>;template<>constexpr ak aZ<ak> =aZ<ll>;template<>constexpr ab aZ<ab> =aZ<ll>;using pi=pair<int,int>;using pl=pair<ll,ll>;using vi=vector<int>;using vl=vector<ll>;template<class T>using vc=vector<T>;template<class T>using eU=vector<vc<T>>;using jg=eU<int>;using jh=eU<ll>;template<class T>using ih=vector<eU<T>>;template<class T>using ic=vector<ih<T>>;template<class T>using iP=vector<ic<T>>;template<class T>using jf=std::priority_queue<T,vector<T>,greater<T>>;template<class T,class U>using ja=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()
int eE(int x){return __builtin_popcount(x);}int eE(cF x){return __builtin_popcount(x);}int eE(ll x){return __builtin_popcountll(x);}int eE(cG x){return __builtin_popcountll(x);}int ea(int x){return __builtin_parity(x);}int ea(cF x){return __builtin_parity(x);}int ea(ll x){return __builtin_parityll(x);}int ea(cG x){return __builtin_parityll(x);}int eG(int x){return(x==0?-1:31-__builtin_clz(x));}int eG(cF x){return(x==0?-1:31-__builtin_clz(x));}int eG(ll x){return(x==0?-1:63-__builtin_clzll(x));}int eG(cG x){return(x==0?-1:63-__builtin_clzll(x));}int eC(int x){return(x==0?-1:__builtin_ctz(x));}int eC(cF x){return(x==0?-1:__builtin_ctz(x));}int eC(ll x){return(x==0?-1:__builtin_ctzll(x));}int eC(cG x){return(x==0?-1:__builtin_ctzll(x));}template<typename T>T dG(T a,T b){return a/b-(a%b&&(a^b)<0);}template<typename T>T ie(T x,T y){return dG(x+y-1,y);}template<typename T>T iW(T x,T y){return x-y*dG(x,y);}template<typename T>pair<T,T>eB(T x,T y){T q=dG(x,y);return{q,x-q*y};}template<typename T,typename U>T jb(U x_,int n){T x=x_;T gB=1;while(n>0){if(n&1)gB*=x;x*=x;n>>=1;}return gB;}template<typename T,typename U>T jc(const vector<U>&A){T sm=0;for(auto&&a:A)sm+=a;return 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()
template<class T,class S>inline ad iS(T&a,const S&b){return(a<b?a=b,1:0);}template<class T,class S>inline ad iT(T&a,const S&b){return(a>b?a=b,1:0);}vc<int>iL(const string&S,bc hA){vc<int>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-hA:-1);}return A;}template<typename T,typename U>vector<T>iN(vector<U>&A,int im=1){int N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(im==0)B.erase(B.begin());return B;}template<typename T>vector<int>iJ(const vector<T>&A){vector<int>eT(A.size());iota(all(eT),0);sort(all(eT),[&](int i,int j){return(A[i]==A[j]?i<j:A[i]<A[j]);});return eT;}template<typename T>vc<T>iH(const vc<T>&A,const vc<int>&I){vc<T>B(I.size());FOR(i,I.size())B[i]=A[I[i]];return B;}template<class...T>constexpr auto il(T...a){return il(initializer_list<common_type_t<T...>>{a...});}template<class...T>constexpr auto ik(T...a){return ik(initializer_list<common_type_t<T...>>{a...});}template<class...Ts>ad gw(Ts&...O){return ay::bx::bg().read(O...);}template<class...Ts>aJ eK(const Ts&...O){ay::bx::aX().println(O...);}aJ iQ(ad b){ay::bx::aX().println(b?"YES":"NO");}aJ iR(ad b){ay::bx::aX().println(b?"Yes":"No");}aJ jd(){ay::bx::aX().println("YES");}aJ NO(){ay::bx::aX().println("NO");}aJ je(){ay::bx::aX().println("Yes");}aJ No(){ay::bx::aX().println("No");}auto&iO=ay::bx::bg();auto&iK=ay::bx::aX();
#if (defined(__GNUC__) || defined(__clang__)) &&     (defined(__x86_64__) || defined(__i386__))
#include <immintrin.h>
#define M1UNE_BIGINT_HAS_X86_SIMD 1
#endif
#if defined(__GNUC__) && !defined(__clang__) &&     (defined(__x86_64__) || defined(__i386__)) &&     !defined(M1UNE_FPS_DISABLE_X86_SIMD)
#include <immintrin.h>
#define M1UNE_FPS_HAS_X86_SIMD 1
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
#endif
namespace ay{namespace bX{template<uint32_t aR>struct L{static_assert(0<aR,"Modulus must be positive");private:uint32_t G;public:static constexpr uint32_t E(){return aR;}static constexpr L bZ(uint32_t v)noexcept{L x;x.G=v;return x;}constexpr L()noexcept:G(0){}template<class ci,std::enable_if_t<std::is_integral_v<ci>,int> =0>constexpr L(ci v)noexcept{if constexpr(std::is_signed_v<ci>){int64_t x=static_cast<int64_t>(v)%static_cast<int64_t>(aR);if(x<0)x+=aR;G=static_cast<uint32_t>(x);}else{G=static_cast<uint32_t>(static_cast<uint64_t>(v)%aR);}}constexpr uint32_t val()const noexcept{return G;}constexpr L&operator++()noexcept{G++;if(G==aR)G=0;return*this;}constexpr L&operator--()noexcept{if(G==0)G=aR;G--;return*this;}constexpr L operator++(int)noexcept{L az=*this;++*this;return az;}constexpr L operator--(int)noexcept{L az=*this;--*this;return az;}constexpr L&operator+=(const L&k)noexcept{G+=k.G;if(G>=aR)G-=aR;return*this;}constexpr L&operator-=(const L&k)noexcept{G-=k.G;if(G>=aR)G+=aR;return*this;}constexpr L&operator*=(const L&k)noexcept{uint64_t z=G;z*=k.G;G=static_cast<uint32_t>(z%aR);return*this;}constexpr L&operator/=(const L&k)noexcept{return*this*=k.inv();}constexpr L operator+(const L&k)const noexcept{return L(*this)+=k;}constexpr L operator-(const L&k)const noexcept{return L(*this)-=k;}constexpr L operator*(const L&k)const noexcept{return L(*this)*=k;}constexpr L operator/(const L&k)const noexcept{return L(*this)/=k;}constexpr ad operator==(const L&k)const noexcept{return G==k.G;}constexpr ad operator!=(const L&k)const noexcept{return G!=k.G;}constexpr L pow(aa n)const noexcept{L az=bZ(1%aR);L x=n<0?inv():*this;uint64_t aB=n<0?uint64_t(-(n+1))+1:uint64_t(n);while(aB>0){if(aB&1)az*=x;x*=x;aB>>=1;}return az;}constexpr L inv()const noexcept{int64_t a=G,b=aR,u=1,v=0;while(b){int64_t t=a/b;a-=t*b;std::swap(a,b);u-=t*v;std::swap(u,v);}assert(a==1);u%=aR;if(u<0)u+=aR;return bZ(static_cast<uint32_t>(u));}friend std::ostream&operator<<(std::ostream&os,const L&k){return os<<k.G;}friend std::istream&operator>>(std::istream&is,L&k){aa v;is>>v;k=L(v);return is;}};using iy=L<998244353>;using ix=L<1000000007>;template<int Id=0>struct ac{private:uint32_t G;inline static uint32_t aO=1;public:static uint32_t E()noexcept{return aO;}static aJ iM(uint32_t ev)noexcept{assert(ev>0);assert(ev<=uint32_t(1)<<31);aO=ev;}static ac bZ(uint32_t v)noexcept{assert(v<aO);ac x;x.G=v;return x;}ac()noexcept:G(0){}template<class ci,std::enable_if_t<std::is_integral_v<ci>,int> =0>ac(ci v)noexcept{if constexpr(std::is_signed_v<ci>){int64_t x=static_cast<int64_t>(v)%static_cast<int64_t>(aO);if(x<0)x+=aO;G=static_cast<uint32_t>(x);}else{G=static_cast<uint32_t>(static_cast<uint64_t>(v)%aO);}}uint32_t val()const noexcept{return G;}ac&operator++()noexcept{G++;if(G==aO)G=0;return*this;}ac&operator--()noexcept{if(G==0)G=aO;G--;return*this;}ac operator++(int)noexcept{ac h=*this;++*this;return h;}ac operator--(int)noexcept{ac h=*this;--*this;return h;}ac&operator+=(const ac&k)noexcept{G+=k.G;if(G>=aO)G-=aO;return*this;}ac&operator-=(const ac&k)noexcept{G-=k.G;if(G>=aO)G+=aO;return*this;}ac&operator*=(const ac&k)noexcept{G=static_cast<uint32_t>(uint64_t(G)*k.G%aO);return*this;}ac&operator/=(const ac&k)noexcept{return*this*=k.inv();}ac operator+(const ac&k)const noexcept{return ac(*this)+=k;}ac operator-(const ac&k)const noexcept{return ac(*this)-=k;}ac operator*(const ac&k)const noexcept{return ac(*this)*=k;}ac operator/(const ac&k)const noexcept{return ac(*this)/=k;}ad operator==(const ac&k)const noexcept{return G==k.G;}ad operator!=(const ac&k)const noexcept{return G!=k.G;}ac pow(aa aB)const noexcept{ac h=bZ(1%aO);ac bW=aB<0?inv():*this;uint64_t at=aB<0?uint64_t(-(aB+1))+1:uint64_t(aB);while(at>0){if(at&1)h*=bW;bW*=bW;at>>=1;}return h;}ac inv()const noexcept{int64_t a=G,b=aO,u=1,v=0;while(b){int64_t ae=a/b;a-=ae*b;std::swap(a,b);u-=ae*v;std::swap(u,v);}assert(a==1);u%=aO;if(u<0)u+=aO;return bZ(static_cast<uint32_t>(u));}friend std::ostream&operator<<(std::ostream&os,const ac&k){return os<<k.G;}friend std::istream&operator>>(std::istream&is,ac&k){aa f;is>>f;k=ac(f);return is;}};}}namespace ay{namespace gA{namespace ag{template<class l,class=aJ>struct fj:std::false_type{};template<class l>struct fj<l,std::void_t<decltype(std::integral_constant<uint32_t,l::E()>{})>>:std::true_type{};constexpr uint32_t gJ(uint32_t E){if(E==2)return 1;if(E==167772161)return 3;if(E==469762049)return 3;if(E==754974721)return 11;if(E==998244353)return 3;if(E==1224736769)return 3;uint32_t en[32]={};int bJ=0;uint32_t x=E-1;for(uint32_t p=2;uint64_t(p)*p<=x;p++){if(x%p!=0)continue;en[bJ++]=p;while(x%p==0)x/=p;}if(x>1)en[bJ++]=x;for(uint32_t g=2;;g++){ad ok=true;for(int i=0;i<bJ;i++){uint64_t f=1;uint64_t bW=g;uint32_t aB=(E-1)/en[i];while(aB>0){if(aB&1)f=f*bW%E;bW=bW*bW%E;aB>>=1;}if(f==1){ok=false;break;}}if(ok)return g;}}constexpr int fx(uint32_t x){int h=0;while((x&1)==0){x>>=1;h++;}return h;}template<class l>struct ej{static constexpr int bE=fx(l::E()-1);std::array<l,bE+1>ap;std::array<l,bE+1>cw;std::array<l,bE>gv;std::array<l,bE>fF;std::array<l,bE>fQ;std::array<l,bE>ff;ej(){constexpr uint32_t hh=gJ(l::E());for(int cB=1;cB<=bE;cB++){ap[cB]=l(hh).pow((l::E()-1)>>cB);cw[cB]=ap[cB].inv();}l X=1;l cL=1;for(int i=0;i+1<bE;i++){gv[i]=ap[i+2]*X;fF[i]=cw[i+2]*cL;X*=cw[i+2];cL*=ap[i+2];}X=1;cL=1;for(int i=0;i+2<bE;i++){fQ[i]=ap[i+3]*X;ff[i]=cw[i+3]*cL;X*=cw[i+3];cL*=ap[i+3];}}};template<class l>const ej<l>&hF(){static const ej<l>an;return an;}template<class l>aJ dd(m<l>&a,ad ax,ad hE=true){const int n=int(a.size());assert(n>0&&(n&(n-1))==0);assert((l::E()-1)%uint32_t(n)==0);const auto&an=hF<l>();const int bu=fx(uint32_t(n));if(!ax){int ar=0;while(ar<bu){if(bu-ar==1){const int av=1<<(bu-ar-1);l aN=1;for(int aj=0;aj<(1<<ar);aj++){const int o=aj<<(bu-ar);for(int i=0;i<av;i++){const l aI=a[o+i];const l aH=a[o+i+av]*aN;a[o+i]=aI+aH;a[o+i+av]=aI-aH;}if(aj+1!=(1<<ar))aN*=an.gv[__builtin_ctz(~uint32_t(aj))];}ar++;continue;}const int av=1<<(bu-ar-2);l aN=1;const l af=an.ap[2];for(int aj=0;aj<(1<<ar);aj++){const l cT=aN*aN;const l es=cT*aN;const int o=aj<<(bu-ar);for(int i=0;i<av;i++){const uint64_t dI=uint64_t(l::E())*l::E();const uint64_t a0=a[o+i].val();const uint64_t a1=uint64_t(a[o+i+av].val())*aN.val();const uint64_t a2=uint64_t(a[o+i+2*av].val())*cT.val();const uint64_t a3=uint64_t(a[o+i+3*av].val())*es.val();const uint64_t gi=uint64_t(l(a1+dI-a3).val())*af.val();const uint64_t fO=dI-a2;a[o+i]=l(a0+a2+a1+a3);a[o+i+av]=l(a0+a2+2*dI-a1-a3);a[o+i+2*av]=l(a0+fO+gi);a[o+i+3*av]=l(a0+fO+dI-gi);}if(aj+1!=(1<<ar))aN*=an.fQ[__builtin_ctz(~uint32_t(aj))];}ar+=2;}}else{int ar=bu;while(ar>0){if(ar==1){const int av=1<<(bu-ar);l aN=1;for(int aj=0;aj<(1<<(ar-1));aj++){const int o=aj<<(bu-ar+1);for(int i=0;i<av;i++){const l aI=a[o+i];const l aH=a[o+i+av];a[o+i]=aI+aH;a[o+i+av]=(aI-aH)*aN;}if(aj+1!=(1<<(ar-1)))aN*=an.fF[__builtin_ctz(~uint32_t(aj))];}ar--;continue;}const int av=1<<(bu-ar);l aN=1;const l gS=an.cw[2];for(int aj=0;aj<(1<<(ar-2));aj++){const l cT=aN*aN;const l es=cT*aN;const int o=aj<<(bu-ar+2);for(int i=0;i<av;i++){const uint64_t a0=a[o+i].val();const uint64_t a1=a[o+i+av].val();const uint64_t a2=a[o+i+2*av].val();const uint64_t a3=a[o+i+3*av].val();const uint64_t gj=uint64_t(l((l::E()+a2-a3)*gS.val()).val());a[o+i]=l(a0+a1+a2+a3);a[o+i+av]=l((a0+l::E()-a1+gj)*aN.val());a[o+i+2*av]=l((a0+a1+2ULL*l::E()-a2-a3)*cT.val());a[o+i+3*av]=l((a0+l::E()-a1+l::E()-gj)*es.val());}if(aj+1!=(1<<(ar-2)))aN*=an.ff[__builtin_ctz(~uint32_t(aj))];}ar-=2;}if(hE){const l dx=l(n).inv();for(l&f:a)f*=dx;}}}}template<class l>m<l>gR(const m<l>&a,const m<l>&b){if(a.empty()||b.empty())return{};m<l>h(a.size()+b.size()-1);if(a.size()<b.size()){for(int i=0;i<int(a.size());i++){for(int j=0;j<int(b.size());j++)h[i+j]+=a[i]*b[j];}}else{for(int j=0;j<int(b.size());j++){for(int i=0;i<int(a.size());i++)h[i+j]+=a[i]*b[j];}}return h;}template<class l>m<l>fr(const m<l>&a,const m<l>&b){const int aF=int(a.size()+b.size()-1);int n=1;while(n<aF)n<<=1;assert((l::E()-1)%uint32_t(n)==0);const ad dA=&a==&b;m<l>fa(n);std::copy(a.begin(),a.end(),fa.begin());ag::dd(fa,false);const l dx=l(n).inv();if(dA){for(int i=0;i<n;i++)fa[i]*=fa[i]*dx;}else{m<l>fb(n);std::copy(b.begin(),b.end(),fb.begin());ag::dd(fb,false);for(int i=0;i<n;i++)fa[i]*=fb[i]*dx;}ag::dd(fa,true,false);fa.resize(aF);return fa;}namespace ag{template<class l>m<l>gG(const m<l>&a,const m<l>&b,int aq){assert(l::E()==998244353);assert(aq>=2&&(aq&(aq-1))==0);assert((l::E()-1)%uint32_t(aq)==0);const int be=aq/2;const int ek=int((a.size()+be-1)/be);const int el=int((b.size()+be-1)/be);auto fq=[&](const m<l>&O,int dt){m<m<l>>eA;eA.reserve(dt);for(int aj=0;aj<dt;aj++){const int begin=aj*be;const int bJ=std::min(be,int(O.size())-begin);m<l>ee(aq);std::copy_n(O.begin()+begin,bJ,ee.begin());dd(ee,false);eA.emplace_back(std::move(ee));}return eA;};m<m<l>>hn=fq(a,ek);m<m<l>>ho=fq(b,el);const int aF=int(a.size()+b.size()-1);m<l>h(aF);m<l>cI(aq);for(int bq=0;bq<ek+el-1;bq++){std::fill(cI.begin(),cI.end(),l(0));const int hP=std::max(0,bq-(el-1));const int hS=std::min(ek-1,bq);for(int dC=hP;dC<=hS;dC++){const int hO=bq-dC;for(int i=0;i<aq;i++)cI[i]+=hn[dC][i]*ho[hO][i];}dd(cI,true);const int fB=bq*be;const int hs=std::min(aq,aF-fB);for(int i=0;i<hs;i++)h[fB+i]+=cI[i];}return h;}template<class l>m<l>gH(const m<l>&a,const m<l>&b,int aq=1<<23){return gG(a,b,aq);}}template<class l>m<l>fL(const m<l>&a,const m<l>&b){if(a.empty()||b.empty())return{};if(std::min(a.size(),b.size())<=32)return gR(a,b);const int aF=int(a.size()+b.size()-1);int n=1;while(n<aF)n<<=1;if constexpr(ag::fj<l>::value){if constexpr(l::E()==998244353){if(n>(1<<23))return ag::gH(a,b);}if((l::E()-1)%uint32_t(n)==0)return fr(a,b);}using by=bX::L<167772161>;using aY=bX::L<469762049>;using aL=bX::L<754974721>;assert(n<=(1<<24));[[maybe_unused]]const unsigned __int128 cJ=static_cast<unsigned __int128>(std::min(a.size(),b.size()))*(l::E()-1)*(l::E()-1);[[maybe_unused]]const unsigned __int128 hv=static_cast<unsigned __int128>(by::E())*aY::E()*aL::E();assert(cJ<hv);auto dK=[&]<class dw>(){m<dw>fJ(a.size());m<dw>fK(b.size());for(int i=0;i<int(a.size());i++)fJ[i]=dw(a[i].val());for(int i=0;i<int(b.size());i++)fK[i]=dw(b[i].val());return fr(fJ,fK);};m<by>c1=dK.template operator()<by>();m<aY>c2=dK.template operator()<aY>();m<aL>c3=dK.template operator()<aL>();static const uint64_t dQ=aY(by::E()).inv().val();static const uint64_t ga=by::E()%aL::E();static const uint64_t he=ga*(aY::E()%aL::E())%aL::E();static const uint64_t gL=aL(uint32_t(he)).inv().val();const uint64_t bQ=l::E();const uint64_t fN=by::E()%bQ;const uint64_t ha=fN*(aY::E()%bQ)%bQ;m<l>h(aF);for(int i=0;i<aF;i++){const uint64_t r1=c1[i].val();const uint64_t r2=c2[i].val();const uint64_t r3=c3[i].val();const uint64_t H=(r2+aY::E()-r1%aY::E())%aY::E()*dQ%aY::E();const uint64_t hj=(r1%aL::E()+ga*(H%aL::E()))%aL::E();const uint64_t R=(r3+aL::E()-hj)%aL::E()*gL%aL::E();uint64_t f=r1%bQ;f=(f+fN*(H%bQ))%bQ;f=(f+ha*(R%bQ))%bQ;h[i]=l::bZ(uint32_t(f));}return h;}}}namespace ay{namespace cy{struct D{static constexpr int F=1000000000;static constexpr int bP=9;m<int>a;int P;D():P(1){}D(aa v){*this=v;}D(const std::string&s){read(s);}D&operator=(aa v){P=1;bk at=static_cast<bk>(v);if(v<0){P=-1;at=0-at;}a.clear();for(;at>0;at/=F){a.push_back(int(at%F));}return*this;}D&operator=(const std::string&s){read(s);return*this;}aJ trim(){while(!a.empty()&&a.back()==0){a.pop_back();}if(a.empty())P=1;}aJ read(const std::string&s){P=1;a.clear();int bY=0;while(bY<(int)s.size()&&(s[bY]=='-'||s[bY]=='+')){if(s[bY]=='-')P=-1;++bY;}a.reserve((int(s.size())-bY+bP-1)/bP);for(int i=int(s.size())-1;i>=bY;i-=bP){int x=0;for(int j=std::max(bY,i-bP+1);j<=i;++j){x=x*10+(s[j]-'0');}a.push_back(x);}trim();}std::string to_string()const{if(a.empty())return"0";static const auto cM=[]{std::array<bc,40000>bF{};for(int f=0;f<10000;++f){int Q=f;for(int bK=3;bK>=0;--bK){bF[4*f+bK]=bc('0'+Q%10);Q/=10;}}return bF;}();bc bs[bP];const std::to_chars_result eh=std::to_chars(bs,bs+bP,a.back());assert(eh.ec==std::errc());const int fG=int(eh.ptr-bs);std::string az((P==-1)+fG+(a.size()-1)*bP,'0');int o=0;if(P==-1)az[o++]='-';std::copy(bs,eh.ptr,az.begin()+o);o+=fG;for(int i=(int)a.size()-2;i>=0;--i){const as f=as(a[i]);const as fz=f/100000000;const as bT=f-fz*100000000;const as gn=bT/10000;const as hM=bT-gn*10000;az[o]=bc('0'+fz);std::memcpy(az.data()+o+1,cM.data()+4*gn,4);std::memcpy(az.data()+o+5,cM.data()+4*hM,4);o+=bP;}return az;}ad is_zero()const{return a.empty()||(a.size()==1&&a[0]==0);}D operator-()const{D az=*this;if(!is_zero())az.P=-P;return az;}D abs()const{D az=*this;az.P=1;return az;}friend ad operator<(const D&x,const D&y){if(x.P!=y.P)return x.P<y.P;if(x.a.size()!=y.a.size()){return(x.P==1)?(x.a.size()<y.a.size()):(x.a.size()>y.a.size());}for(int i=(int)x.a.size()-1;i>=0;--i){if(x.a[i]!=y.a[i]){return(x.P==1)?(x.a[i]<y.a[i]):(x.a[i]>y.a[i]);}}return false;}friend ad operator>(const D&x,const D&y){return y<x;}friend ad operator<=(const D&x,const D&y){return!(y<x);}friend ad operator>=(const D&x,const D&y){return!(x<y);}friend ad operator==(const D&x,const D&y){return x.P==y.P&&x.a==y.a;}friend ad operator!=(const D&x,const D&y){return!(x==y);}D&operator+=(const D&K){if(K.is_zero())return*this;if(is_zero())return*this=K;if(P!=K.P){const int cO=dR(a,K.a);if(cO==0){a.clear();P=1;}else if(cO>0){dh(a,K.a);}else{m<int>h=K.a;dh(h,a);a=std::move(h);P=K.P;}return*this;}fc(a,K.a);return*this;}D&operator-=(const D&K){if(K.is_zero())return*this;if(is_zero())return*this=-K;if(P!=K.P){fc(a,K.a);return*this;}const int cO=dR(a,K.a);if(cO==0){a.clear();P=1;}else if(cO>0){dh(a,K.a);}else{m<int>h=K.a;dh(h,a);a=std::move(h);P=-P;}return*this;}D&operator*=(int v){if(v==0||is_zero())return*this=0;aa bC=v;if(bC<0){P=-P;bC=-bC;}a.reserve(a.size()+2);aa V=0;for(int i=0;i<(int)a.size()||V;++i){if(i==(int)a.size())a.push_back(0);const aa gy=a[i]*bC+V;V=gy/F;a[i]=(int)(gy%F);}trim();return*this;}private:static constexpr int gI=128;static constexpr int gU=224;static constexpr int dM=64;static constexpr int bD=1<<15;struct C{ak ah;ak af;C operator+(const C&K)const{return{ah+K.ah,af+K.af};}C operator-(const C&K)const{return{ah-K.ah,af-K.af};}C operator*(const C&K)const{return{ah*K.ah-af*K.af,ah*K.af+af*K.ah};}C operator*(ak gq)const{return{ah*gq,af*gq};}C conjugate()const{return{ah,-af};}};struct eb{C bq;C cm;};static const m<C>&cR(int size){static m<C>an(2,C{1,0});if(int(an.size())<size){int J=int(an.size());an.resize(size);while(J<size){const ab gs=std::numbers::pi_v<ab>/J;const ab gc=std::cos(gs);const ab fw=std::sin(gs);for(int i=J;i<2*J;++i){an[i]=an[i/2];if(i&1){const ab ah=an[i].ah;const ab af=an[i].af;an[i]={ak(ah*gc-af*fw),ak(ah*fw+af*gc)};}}J*=2;}}return an;}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
__attribute__((target("avx2,fma"),always_inline))static inline __m256d multiply_complex(__m256d f,__m256d ap){const __m256d ah=_mm256_movedup_pd(f);const __m256d af=_mm256_permute_pd(f,0xf);const __m256d swapped_root=_mm256_permute_pd(ap,0x5);return _mm256_fmaddsub_pd(ah,ap,_mm256_mul_pd(af,swapped_root));}__attribute__((target("avx2,fma"),hot))static aJ hL(C*O,int size){const m<C>&an=cR(size);for(int J=size/2;J>0;J/=2){for(int o=0;o<size;o+=2*J){int i=0;for(;i+1<J;i+=2){const __m256d aC=_mm256_loadu_pd(reinterpret_cast<const ak*>(O+o+i));const __m256d aD=_mm256_loadu_pd(reinterpret_cast<const ak*>(O+o+i+J));const __m256d ap=_mm256_loadu_pd(reinterpret_cast<const ak*>(an.data()+J+i));_mm256_storeu_pd(reinterpret_cast<ak*>(O+o+i),_mm256_add_pd(aC,aD));_mm256_storeu_pd(reinterpret_cast<ak*>(O+o+i+J),multiply_complex(_mm256_sub_pd(aC,aD),ap));}for(;i<J;++i){const C aC=O[o+i];const C aD=O[o+i+J];O[o+i]=aC+aD;O[o+i+J]=(aC-aD)*an[J+i];}}}}__attribute__((target("avx2,fma"),hot))static aJ gY(C*O,int size){const m<C>&an=cR(size);const __m256d conjugate_mask=_mm256_setr_pd(0.0,-0.0,0.0,-0.0);for(int J=1;J<size;J*=2){for(int o=0;o<size;o+=2*J){int i=0;for(;i+1<J;i+=2){const __m256d aC=_mm256_loadu_pd(reinterpret_cast<const ak*>(O+o+i));const __m256d f=_mm256_loadu_pd(reinterpret_cast<const ak*>(O+o+i+J));__m256d ap=_mm256_loadu_pd(reinterpret_cast<const ak*>(an.data()+J+i));ap=_mm256_xor_pd(ap,conjugate_mask);const __m256d aD=multiply_complex(f,ap);_mm256_storeu_pd(reinterpret_cast<ak*>(O+o+i),_mm256_add_pd(aC,aD));_mm256_storeu_pd(reinterpret_cast<ak*>(O+o+i+J),_mm256_sub_pd(aC,aD));}for(;i<J;++i){const C aC=O[o+i];const C f=O[o+i+J];const C ap=an[J+i];const C aD={f.ah*ap.ah+f.af*ap.af,f.af*ap.ah-f.ah*ap.af};O[o+i]=aC+aD;O[o+i+J]=aC-aD;}}}const __m256d ds=_mm256_set1_pd(1.0/ak(size));int i=0;for(;i+1<size;i+=2){const __m256d f=_mm256_loadu_pd(reinterpret_cast<const ak*>(O+i));_mm256_storeu_pd(reinterpret_cast<ak*>(O+i),_mm256_mul_pd(f,ds));}for(;i<size;++i){O[i].ah/=size;O[i].af/=size;}}
#endif
static aJ gz(C*O,int size){assert(size>0&&(size&(size-1))==0);
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
hL(O,size);return;
#endif
const m<C>&an=cR(size);for(int J=size/2;J>0;J/=2){for(int o=0;o<size;o+=2*J){for(int i=0;i<J;++i){const C aC=O[o+i];const C aD=O[o+i+J];O[o+i]=aC+aD;O[o+i+J]=(aC-aD)*an[J+i];}}}}static aJ fM(C*O,int size){assert(size>0&&(size&(size-1))==0);
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
gY(O,size);return;
#endif
const m<C>&an=cR(size);for(int J=1;J<size;J*=2){for(int o=0;o<size;o+=2*J){for(int i=0;i<J;++i){const C aC=O[o+i];const C f=O[o+i+J];const C ap=an[J+i];const C aD={f.ah*ap.ah+f.af*ap.af,f.af*ap.ah-f.ah*ap.af};O[o+i]=aC+aD;O[o+i+J]=aC-aD;}}}const ak ds=1.0/ak(size);for(int i=0;i<size;++i){O[i].ah*=ds;O[i].af*=ds;}}static C gh(const C&f,const C&ei){return(f+ei)*0.5;}static C gd(const C&f,const C&ei){const C fS=f-ei;return{fS.af*0.5,-fS.ah*0.5};}static aJ gZ(C*O,int size){assert(size>=2&&(size&(size-1))==0);const int bS=size/2;const m<C>&an=cR(size);static m<C>dN;static int fI=0;if(fI!=size){dN.resize(bS);m<int>dy(bS);const int hX=std::countr_zero(as(bS));for(int i=1;i<bS;++i){dy[i]=(dy[i/2]>>1)|((i&1)<<(hX-1));}for(int i=0;i<bS;++i){dN[i]=an[bS+dy[i]];}fI=size;}for(int i=0;i<bS;++i){const C H=O[2*i];const C R=O[2*i+1];const C aC=(H+R)*0.5;const C aD=((H-R)*0.5)*dN[i].conjugate();O[i]={aC.ah-aD.af,aC.af+aD.ah};}fM(O,bS);}static aJ aK(m<int>&f){while(!f.empty()&&f.back()==0)f.pop_back();}static ad cv(const m<int>&w,const m<int>&k){return dR(w,k)<0;}static int dR(const m<int>&w,const m<int>&k){if(w.size()!=k.size())return w.size()<k.size()?-1:1;for(int i=int(w.size())-1;i>=0;--i){if(w[i]!=k[i])return w[i]<k[i]?-1:1;}return 0;}static aJ fc(m<int>&w,const m<int>&k){const int gf=int(w.size());const int dz=int(k.size());const int size=std::max(gf,dz);if(gf<dz)w.resize(dz);int V=0;int i=0;for(;i<dz;++i){const aa Q=(aa)w[i]+k[i]+V;w[i]=int(Q>=F?Q-F:Q);V=Q>=F;}while(i<size&&V){++w[i];V=w[i]==F;if(V)w[i]=0;++i;}if(V)w.push_back(1);}static aJ dh(m<int>&w,const m<int>&k){assert(!cv(w,k));int aW=0;for(int i=0;i<int(k.size())||aW;++i){int Q=w[i]-aW-(i<int(k.size())?k[i]:0);aW=Q<0;if(aW)Q+=F;w[i]=Q;}assert(aW==0);aK(w);}static ad fd(const m<int>&w,const m<int>&k){return!cv(k,w);}static m<int>dX(const m<int>&w,const m<int>&k){m<int>h(std::max(w.size(),k.size())+1);for(int i=0;i<int(h.size())-1;++i){if(i<int(w.size()))h[i]+=w[i];if(i<int(k.size()))h[i]+=k[i];if(h[i]>=F){h[i]-=F;h[i+1]++;}}aK(h);return h;}static m<int>bA(const m<int>&w,const m<int>&k){assert(!cv(w,k));m<int>h=w;int aW=0;for(int i=0;i<int(h.size());++i){const aa Q=(aa)h[i]-aW-(i<int(k.size())?k[i]:0);if(Q<0){h[i]=int(Q+F);aW=1;}else{h[i]=int(Q);aW=0;}}assert(aW==0);aK(h);return h;}static m<int>hf(const m<int>&w,const m<int>&k){if(w.empty()||k.empty())return m<int>();m<aa>X(w.size()+k.size());constexpr aa cg=4LL*F*F;for(int i=0;i<int(w.size());++i){for(int j=0;j<int(k.size());++j){X[i+j]+=(aa)w[i]*k[j];if(X[i+j]>=cg){X[i+j]-=cg;X[i+j+1]+=4LL*F;}}}m<int>h;h.reserve(X.size()+1);aa V=0;for(int i=0;i<int(X.size())||V>0;++i){if(i<int(X.size()))V+=X[i];h.push_back(int(V%F));V/=F;}aK(h);return h;}static m<int>ht(const m<int>&f){if(f.empty())return m<int>();m<aa>X(2*f.size());constexpr aa cg=4LL*F*F;for(int i=0;i<int(f.size());++i){X[2*i]+=(aa)f[i]*f[i];if(X[2*i]>=cg){X[2*i]-=cg;X[2*i+1]+=4LL*F;}for(int j=i+1;j<int(f.size());++j){X[i+j]+=2LL*f[i]*f[j];if(X[i+j]>=cg){X[i+j]-=cg;X[i+j+1]+=4LL*F;}}}m<int>h;h.reserve(X.size()+1);aa V=0;for(int i=0;i<int(X.size())||V>0;++i){if(i<int(X.size()))V+=X[i];h.push_back(int(V%F));V/=F;}aK(h);return h;}static m<int>dk(const m<int>&f,int bC){assert(0<=bC&&bC<F);if(f.empty()||bC==0)return m<int>();m<int>h;h.reserve(f.size()+1);uint64_t V=0;for(int ig:f){const uint64_t Q=uint64_t(ig)*bC+V;h.push_back(int(Q%F));V=Q/F;}if(V)h.push_back(int(V));return h;}static m<int>dZ(const m<int>&w,const m<int>&k){using by=bX::L<998244353>;using aY=bX::L<754974721>;using aL=bX::L<469762049>;const int aF=int(w.size()+k.size()-1);assert(aF<=(1<<24));auto em=[&]<class l>(){m<l>x(w.begin(),w.end());if(&w==&k)return gA::fL(x,x);m<l>y(k.begin(),k.end());return gA::fL(x,y);};const m<by>hH=em.template operator()<by>();const m<aY>hI=em.template operator()<aY>();const m<aL>hJ=em.template operator()<aL>();constexpr uint64_t eO=by::E();constexpr uint64_t cZ=aY::E();constexpr uint64_t cC=aL::E();constexpr uint64_t eI=eO*cZ;const static uint64_t dQ=aY(eO).inv().val();const static uint64_t gP=aL(eI%cC).inv().val();[[maybe_unused]]const unsigned __int128 cJ=static_cast<unsigned __int128>(std::min(w.size(),k.size()))*(F-1)*(F-1);[[maybe_unused]]constexpr unsigned __int128 hu=static_cast<unsigned __int128>(eI)*cC;assert(cJ<hu);m<int>h;h.reserve(aF+2);unsigned __int128 V=0;for(int i=0;i<aF||V>0;++i){if(i<aF){const uint64_t H=hH[i].val();const uint64_t R=hI[i].val();const uint64_t hZ=hJ[i].val();const uint64_t hp=(R+cZ-H%cZ)%cZ;const uint64_t hB=hp*dQ%cZ;const uint64_t fR=H+eO*hB;const uint64_t hw=(hZ+cC-fR%cC)%cC;const uint64_t hG=hw*gP%cC;V+=fR+static_cast<unsigned __int128>(eI)*hG;}h.push_back(int(V%F));V/=F;}aK(h);return h;}struct cH{uint32_t cW;uint32_t cV;};template<int eQ>static uint32_t dn(uint64_t f){constexpr uint64_t dB=(uint64_t(1)<<eQ)-1;f=(f&dB)+(f>>eQ);f=(f&dB)+(f>>eQ);if(f>=dB)f-=dB;return uint32_t(f);}static cH dL(const m<int>&f){cH h{0,0};for(int i=int(f.size())-1;i>=0;--i){h.cW=dn<31>(uint64_t(h.cW)*F+f[i]);h.cV=dn<29>(uint64_t(h.cV)*F+f[i]);}return h;}static ad hc(const m<int>&w,const m<int>&k,const m<int>&X){const cH fZ=dL(w);const cH gb=dL(k);const cH gk=dL(X);return gk.cW==dn<31>(uint64_t(fZ.cW)*gb.cW)&&gk.cV==dn<29>(uint64_t(fZ.cV)*gb.cV);}static m<int>hr(const m<int>&w,const m<int>&k){const int aF=int(w.size()+k.size()-1);const int aq=int(std::bit_ceil(as(aF)));const unsigned __int128 cJ=static_cast<unsigned __int128>(std::min(w.size(),k.size()))*2*(bD-1)*((F-1)/bD);if(aq>(1<<20)||cJ>=(uint64_t(1)<<50)){return dZ(w,k);}std::unique_ptr<C[]>bf(new C[aq]);for(int i=0;i<int(w.size());++i){bf[i]={ak(w[i]%bD),ak(w[i]/bD)};}std::fill(bf.get()+w.size(),bf.get()+aq,C{0,0});gz(bf.get(),aq);const ad dA=&w==&k;std::unique_ptr<C[]>bl(new C[aq]);if(!dA){for(int i=0;i<int(k.size());++i){bl[i]={ak(k[i]%bD),ak(k[i]/bD)};}std::fill(bl.get()+k.size(),bl.get()+aq,C{0,0});gz(bl.get(),aq);}static m<int>ct;if(int(ct.size())<aq){const int hl=int(ct.size());ct.resize(aq);for(int i=std::max(1,hl);i<aq;++i){ct[i]=i^int(std::bit_floor(as(i))-1);}}auto fg=[&](int bK){const int bU=ct[bK];const C fA=bf[bU].conjugate();const C eu=gh(bf[bK],fA);const C ep=gd(bf[bK],fA);C ex=eu;C er=ep;if(!dA){const C fD=bl[bU].conjugate();ex=gh(bl[bK],fD);er=gd(bl[bK],fD);}const C hx=eu*ex;const C fE=ep*er;const C bq=hx+C{-fE.af,fE.ah};const C cm=eu*er+ep*ex;return eb{bq,cm};};for(int i=0;i<aq;++i){const int bU=ct[i];if(i>bU)continue;const eb eq=fg(i);eb dS=eq;if(i!=bU)dS=fg(bU);bf[i]=eq.bq;bf[bU]=dS.bq;bl[i]=eq.cm;bl[bU]=dS.cm;}fM(bf.get(),aq);gZ(bl.get(),aq);m<int>h;h.reserve(aF+2);unsigned __int128 V=0;for(int i=0;i<aF||V>0;++i){if(i<aF){const aa cE=std::llround(bf[i].ah);const aa gu=std::llround(bf[i].af);const C fH=bl[i/2];const aa cm=std::llround((i&1)?fH.af:fH.ah);if(cE<0||gu<0||cm<0)return dZ(w,k);V+=cE+static_cast<unsigned __int128>(cm)*bD+static_cast<unsigned __int128>(gu)*bD*bD;}h.push_back(int(V%F));V/=F;}aK(h);if(h.empty()||!hc(w,k,h)){return dZ(w,k);}return h;}static m<int>bz(const m<int>&w,const m<int>&k){if(w.empty()||k.empty())return m<int>();if(w.size()==1)return dk(k,w[0]);if(k.size()==1)return dk(w,k[0]);if(&w==&k&&w.size()<=gU){return ht(w);}if(std::min(w.size(),k.size())<=gI){return hf(w,k);}return hr(w,k);}static ba<m<int>,m<int>>dp(const m<int>&au,int am){assert(0<am&&am<F);if(am==1){return std::make_pair(au,m<int>());}m<int>ae(au.size());aa ao=0;for(int i=int(au.size())-1;i>=0;--i){const aa Q=ao*F+au[i];ae[i]=int(Q/am);ao=Q%am;}aK(ae);m<int>fp;if(ao!=0)fp.push_back(int(ao));return std::make_pair(std::move(ae),std::move(fp));}static ba<m<int>,m<int>>fn(const m<int>&au,const m<int>&am){assert(!am.empty());if(am.size()==1)return dp(au,am[0]);if(cv(au,am)){return std::make_pair(m<int>(),au);}const int bm=F/(am.back()+1);m<int>aE(am.size());uint64_t V=0;for(int i=0;i<int(am.size());++i){const uint64_t Q=uint64_t(am[i])*bm+V;aE[i]=int(Q%F);V=Q/F;}assert(V==0);m<int>aA(au.size()+1);V=0;for(int i=0;i<int(au.size());++i){const uint64_t Q=uint64_t(au[i])*bm+V;aA[i]=int(Q%F);V=Q/F;}aA[au.size()]=int(V);const int bd=int(aE.size());const int fC=int(au.size())-bd+1;const uint64_t dm=aE.back();const uint64_t hi=aE[bd-2];m<int>ae(fC);for(int aG=fC-1;aG>=0;--aG){const uint64_t dU=uint64_t(aA[aG+bd])*F+aA[aG+bd-1];uint64_t bV=dU/dm;uint64_t ao=dU%dm;if(bV>=F){bV=F-1;ao=dU-bV*dm;}while(ao<F&&bV*hi>ao*F+aA[aG+bd-2]){--bV;ao+=dm;}uint64_t aW=0;for(int i=0;i<bd;++i){const uint64_t X=bV*uint64_t(aE[i])+aW;const uint64_t cE=X%F;aW=X/F;if(uint64_t(aA[aG+i])<cE){aA[aG+i]=int(uint64_t(aA[aG+i])+F-cE);++aW;}else{aA[aG+i]-=int(cE);}}aa df=(aa)aA[aG+bd]-static_cast<aa>(aW);if(df<0){--bV;uint64_t eg=0;for(int i=0;i<bd;++i){const uint64_t Q=uint64_t(aA[aG+i])+aE[i]+eg;aA[aG+i]=int(Q%F);eg=Q/F;}df+=eg;}assert(0<=df&&df<F);aA[aG+bd]=int(df);ae[aG]=int(bV);}aK(ae);m<int>ao(aA.begin(),aA.begin()+bd);aK(ao);ba<m<int>,m<int>>bO=dp(ao,bm);assert(bO.second.empty());return std::make_pair(std::move(ae),std::move(bO.first));}static m<int>reciprocal(const m<int>&f,int bt){assert(!f.empty());assert(F/2<=f.back()&&f.back()<F);assert(bt>=0);int aQ=bt;const int fW=int(f.size());while(aQ>dM)aQ=(aQ+1)/2;m<int>ax(fW+aQ+1);ax.back()=1;ax=fn(ax,f).first;while(aQ<bt){m<int>eF=bz(ax,ax);eF.insert(eF.begin(),0);const int ck=std::min(fW,2*aQ+1);const m<int>bs(f.end()-ck,f.end());m<int>cP=bz(eF,bs);assert(int(cP.size())>=ck);cP.erase(cP.begin(),cP.begin()+ck);m<int>ey(aQ+1);const m<int>gg=dX(ax,ax);ey.insert(ey.end(),gg.begin(),gg.end());ax=bA(ey,cP);assert(!ax.empty());ax.erase(ax.begin());aQ*=2;}assert(aQ>=bt);ax.erase(ax.begin(),ax.begin()+aQ-bt);aK(ax);return ax;}static ba<m<int>,m<int>>gW(const m<int>&au,const m<int>&am){assert(!am.empty());if(am.size()<=dM||int(au.size())-int(am.size())<=dM){return fn(au,am);}if(au.size()>2*am.size()){const int fV=int(au.size()/am.size());const int gV=fV>=16?3:fV>=7?2:1;const int be=gV*int(am.size());const int dt=(int(au.size())+be-1)/be;const int bm=F/(am.back()+1);const m<int>aE=dk(am,bm);const int bt=be+3;const m<int>ax=reciprocal(aE,bt);const int cQ=int(am.size())+bt;auto hq=[&](const m<int>&Q){const m<int>dO=dk(Q,bm);m<int>dV=bz(dO,ax);m<int>bN;if(int(dV.size())>cQ){bN.assign(dV.begin()+cQ,dV.end());}m<int>X=bz(aE,bN);while(cv(dO,X)){bN=bA(bN,m<int>(1,1));X=bA(X,aE);}m<int>cK=bA(dO,X);while(fd(aE,cK)){bN=dX(bN,m<int>(1,1));cK=bA(cK,aE);}aK(bN);aK(cK);ba<m<int>,m<int>>bO=dp(cK,bm);assert(bO.second.empty());return std::make_pair(std::move(bN),std::move(bO.first));};m<int>ae(au.size());m<int>ao;for(int aj=dt-1;aj>=0;--aj){const int begin=aj*be;const int end=std::min(begin+be,int(au.size()));m<int>Q(au.begin()+begin,au.begin()+end);Q.insert(Q.end(),ao.begin(),ao.end());aK(Q);ba<m<int>,m<int>>dD=hq(Q);assert(int(dD.first.size())<=end-begin);std::copy(dD.first.begin(),dD.first.end(),ae.begin()+begin);ao=std::move(dD.second);}aK(ae);aK(ao);return std::make_pair(std::move(ae),std::move(ao));}const int bm=F/(am.back()+1);const m<int>aA=bz(au,m<int>(1,bm));const m<int>aE=bz(am,m<int>(1,bm));const int hk=int(aA.size());const int bd=int(aE.size());const int bt=hk-bd+2;const m<int>ax=reciprocal(aE,bt);m<int>ae=bz(aA,ax);const int cQ=bd+bt;assert(cQ<=int(ae.size()));ae.erase(ae.begin(),ae.begin()+cQ);m<int>X=bz(aE,ae);while(cv(aA,X)){ae=bA(ae,m<int>(1,1));X=bA(X,aE);}m<int>ao=bA(aA,X);while(fd(aE,ao)){ae=dX(ae,m<int>(1,1));ao=bA(ao,aE);}aK(ae);aK(ao);ba<m<int>,m<int>>bO=dp(ao,bm);assert(bO.second.empty());return std::make_pair(std::move(ae),std::move(bO.first));}public:D&operator*=(const D&K){if(is_zero()||K.is_zero())return*this=0;const int hy=P*K.P;a=bz(a,K.a);P=hy;trim();return*this;}friend ba<D,D>eB(const D&a1,const D&b1){if(b1.is_zero()){throw std::domain_error("BigInt division by zero");}ba<m<int>,m<int>>h=gW(a1.a,b1.a);D q,r;q.a=std::move(h.first);r.a=std::move(h.second);q.P=a1.P*b1.P;r.P=a1.P;q.trim();r.trim();return{q,r};}friend D dc(D H,D R){H.P=1;R.P=1;while(!R.is_zero()){H%=R;std::swap(H,R);}return H;}D&operator/=(const D&K){return*this=eB(*this,K).first;}D&operator%=(const D&K){return*this=eB(*this,K).second;}friend D operator+(D x,const D&y){return x+=y;}friend D operator-(D x,const D&y){return x-=y;}friend D operator*(D x,const D&y){return x*=y;}friend D operator/(D x,const D&y){return x/=y;}friend D operator%(D x,const D&y){return x%=y;}friend std::ostream&operator<<(std::ostream&os,const D&b){return os<<b.to_string();}friend std::istream&operator>>(std::istream&is,D&b){std::string s;if(is>>s)b.read(s);return is;}};}}
#ifdef M1UNE_BIGINT_HAS_X86_SIMD
#undef M1UNE_BIGINT_HAS_X86_SIMD
#endif
namespace ay{namespace bX{namespace ft{template<class T>concept IntegerLike=std::signed_integral<T>||(!std::integral<T>&&std::copyable<T>&&requires(T H,T R){T(0);T(1);{-H}->std::same_as<T>;{H+R}->std::same_as<T>;{H-R}->std::same_as<T>;{H*R}->std::same_as<T>;{H/R}->std::same_as<T>;{H%R}->std::same_as<T>;{H+=R}->std::same_as<T&>;{H-=R}->std::same_as<T&>;{H/=R}->std::same_as<T&>;{H==R}->std::convertible_to<ad>;{H<R}->std::convertible_to<ad>;});}template<ft::IntegerLike T=aa>struct Y{static_assert(!std::signed_integral<T>||sizeof(T)<=sizeof(aa));private:static constexpr ad dl=std::signed_integral<T>;using Z=std::conditional_t<dl,bv,T>;using aV=std::conditional_t<dl,bj,T>;T ai;T al;static constexpr aV at(Z f){if constexpr(dl){if(f<0){return static_cast<aV>(-(f+1))+1;}return static_cast<aV>(f);}else{return f<0?-f:f;}}static constexpr aV dc(aV H,aV R){while(R!=0){aV ao=H%R;H=R;R=ao;}return H;}static constexpr T go(Z f){if constexpr(dl){assert(Z(std::numeric_limits<T>::min())<=f);assert(f<=Z(std::numeric_limits<T>::max()));return static_cast<T>(f);}else{return f;}}constexpr aJ assign_normalized(Z numerator,Z denominator){assert(denominator!=0);if(numerator==0){ai=0;al=1;return;}aV am=dc(at(numerator),at(denominator));numerator/=static_cast<Z>(am);denominator/=static_cast<Z>(am);if(denominator<0){numerator=-numerator;denominator=-denominator;}ai=go(numerator);al=go(denominator);}static constexpr Y fY(Z numerator,Z denominator){Y h;h.assign_normalized(numerator,denominator);return h;}static ba<ab,aa>fh(const T&f){std::ostringstream aX;aX<<f;const std::string bi=aX.str();std::size_t begin=0;int P=1;if(!bi.empty()&&(bi[0]=='-'||bi[0]=='+')){if(bi[0]=='-')P=-1;begin=1;}while(begin<bi.size()&&bi[begin]=='0')++begin;if(begin==bi.size())return std::make_pair(0.0L,0LL);constexpr int hQ=std::numeric_limits<ab>::digits10+1;const std::size_t db=std::min<std::size_t>(hQ,bi.size()-begin);ab du=0;for(std::size_t i=0;i<db;++i){assert('0'<=bi[begin+i]&&bi[begin+i]<='9');du=du*10+(bi[begin+i]-'0');}for(std::size_t i=1;i<db;++i)du/=10;const aa aB=static_cast<aa>(bi.size()-begin-1);return std::make_pair(P*du,aB);}public:constexpr Y():ai(0),al(1){}constexpr Y(T et):ai(et),al(1){}template<std::integral U>requires std::constructible_from<T,U>&&(!std::same_as<std::remove_cv_t<U>,T>)constexpr Y(U et):Y(T(et)){}constexpr Y(T numerator,T denominator){assign_normalized(Z(numerator),Z(denominator));}constexpr T numerator()const{return ai;}constexpr T denominator()const{return al;}constexpr ad iG()const{return al==1;}constexpr int P()const{return(ai>0)-(ai<0);}constexpr Y reciprocal()const{assert(ai!=0);return fY(Z(al),Z(ai));}constexpr Y abs()const{return ai<0?-*this:*this;}constexpr ab dW()const requires requires(const T&f){static_cast<ab>(f);}{return static_cast<ab>(ai)/static_cast<ab>(al);}ab dW()const requires(!requires(const T&f){static_cast<ab>(f);}){const auto[numerator,gQ]=fh(ai);const auto[denominator,gN]=fh(al);return numerator/denominator*std::pow(10.0L,gQ-gN);}explicit constexpr operator ab()const requires requires(const T&f){static_cast<ab>(f);}{return dW();}explicit operator ab()const requires(!requires(const T&f){static_cast<ab>(f);}){return dW();}constexpr T iV()const{return ai/al;}constexpr T dG()const{T ae=ai/al;if(ai<0&&ai%al!=0)ae-=T(1);return ae;}constexpr T ie()const{T ae=ai/al;if(0<ai&&ai%al!=0)ae+=T(1);return ae;}constexpr Y operator+()const{return*this;}constexpr Y operator-()const{return fY(-Z(ai),Z(al));}constexpr Y&operator+=(const Y&K){aV gm=dc(static_cast<aV>(al),static_cast<aV>(K.al));Z fT=Z(K.al)/static_cast<Z>(gm);Z hz=Z(al)/static_cast<Z>(gm);assign_normalized(Z(ai)*fT+Z(K.ai)*hz,Z(al)*fT);return*this;}constexpr Y&operator-=(const Y&K){return*this+=-K;}constexpr Y&operator*=(const Y&K){aV fX=dc(at(Z(ai)),static_cast<aV>(K.al));aV fU=dc(at(Z(K.ai)),static_cast<aV>(al));assign_normalized((Z(ai)/static_cast<Z>(fX))*(Z(K.ai)/static_cast<Z>(fU)),(Z(al)/static_cast<Z>(fU))*(Z(K.al)/static_cast<Z>(fX)));return*this;}constexpr Y&operator/=(const Y&K){return*this*=K.reciprocal();}friend constexpr Y operator+(Y aI,const Y&aH){return aI+=aH;}friend constexpr Y operator-(Y aI,const Y&aH){return aI-=aH;}friend constexpr Y operator*(Y aI,const Y&aH){return aI*=aH;}friend constexpr Y operator/(Y aI,const Y&aH){return aI/=aH;}friend constexpr ad operator==(const Y&aI,const Y&aH){return aI.ai==aH.ai&&aI.al==aH.al;}friend constexpr std::strong_ordering operator<=>(const Y&aI,const Y&aH){Z H=Z(aI.ai)*Z(aH.al);Z R=Z(aH.ai)*Z(aI.al);if(H<R)return std::strong_ordering::less;if(R<H)return std::strong_ordering::greater;return std::strong_ordering::equal;}friend std::ostream&operator<<(std::ostream&aX,const Y&f){aX<<f.ai;if(f.al!=1){aX<<'/'<<f.al;}return aX;}friend std::istream&operator>>(std::istream&bg,Y&f){std::string cY;if(!(bg>>cY))return bg;std::size_t cX=cY.find('/');if(cX!=std::string::npos&&cY.find('/',cX+1)!=std::string::npos){bg.setstate(std::ios::failbit);return bg;}T numerator=0;T denominator=1;std::istringstream fs(cY.substr(0,cX));if(!(fs>>numerator)||fs.peek()!=std::char_traits<bc>::eof()){bg.setstate(std::ios::failbit);return bg;}if(cX!=std::string::npos){std::istringstream fl(cY.substr(cX+1));if(!(fl>>denominator)||fl.peek()!=std::char_traits<bc>::eof()){bg.setstate(std::ios::failbit);return bg;}}f=Y(numerator,denominator);return bg;}};template<ft::IntegerLike T>constexpr Y<T>abs(const Y<T>&f){return f.abs();}}}namespace ay{namespace cA{template<class T=int>struct eN{using hD=T;int bh;int to;T bL;int id;ad bI;eN():bh(-1),to(-1),bL(T()),id(-1),bI(true){}eN(int hW,int in,T hU=T(1),int ij=-1,ad hR=true):bh(hW),to(in),bL(hU),id(ij),bI(hR){}int K(int v)const{assert(v==bh||v==to);return bh^to^v;}};template<class T=int>struct bG{using bp=eN<T>;using hD=T;private:int _n;int bb;m<m<bp>>_g;m<m<ba<int,int>>>bw;public:bG():_n(0),bb(0){}explicit bG(int n):_n(n),bb(0),_g(n){assert(0<=n);}int size()const{return _n;}ad empty()const{return _n==0;}int iE()const{return bb;}int iD(){_g.emplace_back();return _n++;}int iw(int bh,int to,T bL=T(1)){assert(0<=bh&&bh<_n);assert(0<=to&&to<_n);int id=bb++;int cn=int(_g[bh].size());_g[bh].push_back(bp(bh,to,bL,id));bw.emplace_back();bw.back().push_back({bh,cn});return id;}int add_edge(int u,int v,T bL=T(1)){assert(0<=u&&u<_n);assert(0<=v&&v<_n);int id=bb++;int ia=int(_g[u].size());_g[u].push_back(bp(u,v,bL,id));int ib=int(_g[v].size());_g[v].push_back(bp(v,u,bL,id));bw.emplace_back();bw.back().push_back({u,ia});bw.back().push_back({v,ib});return id;}aJ fv(int id,ad bI){assert(0<=id&&id<bb);for(auto[v,cn]:bw[id]){_g[v][cn].bI=bI;}}aJ iF(int id){fv(id,false);}aJ iB(int id){fv(id,true);}ad iz(int id)const{assert(0<=id&&id<bb);assert(!bw[id].empty());auto[v,cn]=bw[id][0];return _g[v][cn].bI;}const m<bp>&operator[](int v)const{assert(0<=v&&v<_n);return _g[v];}m<bp>&operator[](int v){assert(0<=v&&v<_n);return _g[v];}const m<m<bp>>&hC()const{return _g;}m<m<bp>>&hC(){return _g;}m<bp>iU(ad gX=false)const{m<bp>h;h.reserve(bb);m<bc>db(bb,false);for(int v=0;v<_n;v++){for(const auto&e:_g[v]){if(!gX&&!e.bI)continue;if(0<=e.id&&e.id<bb){if(db[e.id])continue;db[e.id]=true;}h.push_back(e);}}return h;}bG dy()const{bG h(_n);h.bb=bb;h.bw.assign(bb,{});for(int v=0;v<_n;v++){for(const auto&e:_g[v]){int cn=int(h._g[e.to].size());h._g[e.to].push_back(bp(e.to,e.bh,e.bL,e.id,e.bI));if(0<=e.id&&e.id<bb)h.bw[e.id].push_back({e.to,cn});}}return h;}};}}namespace ay{namespace cA{template<class T>struct cu{m<T>aP;m<bc>cz;m<int>eD;m<int>fP;T cD=T();ad reachable(int v)const{assert(0<=v&&v<int(aP.size()));return cz[v];}m<int>iY(int t)const{assert(reachable(t));m<int>h;for(int v=t;v!=-1;v=eD[v])h.push_back(v);std::reverse(h.begin(),h.end());return h;}};namespace ag{template<class T>struct dP{T aP;int eH;};template<class T>struct gM{ad operator()(const dP<T>&H,const dP<T>&R)const{return R.aP<H.aP;}};}template<class T>cu<T>ch(const bG<T>&g,const m<int>&ez){int n=g.size();cu<T>h;h.aP.resize(n);h.cz.assign(n,false);h.eD.assign(n,-1);h.fP.assign(n,-1);using da=ag::dP<T>;using hN=ag::gM<T>;std::priority_queue<da,m<da>,hN>de;for(int s:ez){assert(0<=s&&s<n);if(h.cz[s])continue;h.cz[s]=true;h.aP[s]=T();de.push(da{T(),s});}while(!de.empty()){da Q=de.top();de.pop();if(h.aP[Q.eH]<Q.aP)continue;for(const auto&e:g[Q.eH]){if(!e.bI)continue;T nd=Q.aP+e.bL;if(h.cz[e.to]&&!(nd<h.aP[e.to]))continue;h.cz[e.to]=true;h.aP[e.to]=nd;h.eD[e.to]=Q.eH;h.fP[e.to]=e.id;de.push(da{std::move(nd),e.to});}}return h;}template<class T>cu<T>ch(const bG<T>&g,int s){return ch(g,m<int>{s});}template<class T>cu<T>ch(const bG<T>&g,const m<int>&ez,const T&cD){cu<T>h=ch(g,ez);h.cD=cD;for(int v=0;v<int(h.aP.size());v++){if(!h.reachable(v))h.aP[v]=cD;}return h;}template<class T>cu<T>ch(const bG<T>&g,int s,const T&cD){return ch(g,m<int>{s},cD);}}}using ii=ay::bX::Y<ay::cy::D>;aJ hY(){int N,M;gw(N,M);ay::cA::bG<ii>cA(N);FOR(M){int u,v,a,b;gw(u,v,a,b);--u,--v;cA.add_edge(u,v,{a,b});}auto az=ay::cA::ch(cA,0);auto&aP=az.aP;FOR(i,1,N){eK(aP[i].numerator().to_string(),aP[i].denominator().to_string());}}int 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,true);int T=1;while(T--)hY();return 0;}
#undef M1UNE_FPS_DISABLE_X86_SIMD