using Y=bool;using an=__uint128_t;using ay=void;using az=unsigned char;using aB=unsigned;using aC=char;using aD=long double;using aF=__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>
#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>
#define aG return
#define aO template
#define aP constexpr
#define aQ const
#define cc class
#define cd static_cast
#define cH operator
#define cI int
#define cJ using
#define dE namespace
#define et typename
#define eu struct
#define ev false
#define ew while
#define ex friend
#define ey static
#define ez inline
#define eA true
#define eB continue
#define eC auto
#define eD for
#define eE decltype
#define eF this
#define eG private
#define eH else
#define eI explicit
#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>
aO<cc...T>cJ aE=std::pair<T...>;
#include <valarray>
#include <variant>
#include <vector>
aO<cc...T>cJ o=std::vector<T...>;
#include <version>
#include <sys/stat.h>
#include <unistd.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(...)
dE J{dE aJ{dE z{aO<cc T,cc=ay>eu cw:std::false_type{};aO<cc T>eu cw<T,std::void_t<eE(std::begin(std::declval<T&>())),eE(std::end(std::declval<T&>()))>>:std::true_type{};aO<cc T>ez aP Y aS=cw<T>::value;aO<cc T>cJ cS=eE(*std::begin(std::declval<T&>()));aO<cc T>cJ dc=std::remove_cv_t<std::remove_reference_t<cS<T>>>;aO<cc T,cc=ay>eu ci{cJ type=dc<T>;};aO<cc T>eu ci<T,std::void_t<et std::remove_cv_t<std::remove_reference_t<T>>::value_type>>{cJ type=et std::remove_cv_t<std::remove_reference_t<T>>::value_type;};aO<cc T>cJ cf=et ci<T>::type;aO<cc T>eu cr:std::false_type{};aO<cc T,std::size_t N>eu cr<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,aC>>{};aO<cc T>eu cZ:std::bool_constant<std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,aQ aC*>||std::is_same_v<std::decay_t<T>,aC*>||cr<std::remove_reference_t<T>>::value>{};aO<cc T>ez aP Y bm=cZ<T>::value;aO<cc T,cc=ay>eu cp:std::false_type{};aO<cc T>eu cp<T,std::void_t<eE(std::declval<aQ T&>().val())>>:std::true_type{};aO<cc T>ez aP Y cm=cp<T>::value;aO<cc T,cc=ay>eu ch:std::false_type{};aO<cc T>eu ch<T,std::void_t<eE(T::mod()),eE(T::raw(std::declval<uint32_t>()))>>:std::true_type{};aO<cc T>ez aP Y cN=ch<T>::value;aO<cc T>ez aP Y bp=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,aF>||std::is_same_v<std::remove_cv_t<T>,an>;aO<cc T>ez aP Y bC=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,aF>;aO<cc T>eu bA{cJ type=std::make_unsigned_t<T>;};aO<>eu bA<aF>{cJ type=an;};aO<>eu bA<an>{cJ type=an;};aO<cc T>cJ cW=et bA<std::remove_cv_t<T>>::type;}eu aA{ey aP cI ai=1<<20;eG:std::FILE*aL;aC D[ai];cI r;cI O;cI bl;Y bD;Y cA(){r=0;if(bD){ssize_t length;do{length=::read(bl,D,ai);}ew(length<0&&errno==EINTR);if(length<=0){O=0;aG ev;}O=cI(length);}eH{O=cI(std::fread(D,1,ai,aL));}aG O!=0;}aO<cc T>Y cK(T&h){if(!bq())aG ev;cI c=V();Y W=ev;if(c=='-'){W=eA;c=V();}if aP(z::bC<T>){T f=0;ew('0'<=c&&c<='9'){f=W?f*10-(c-'0'):f*10+(c-'0');c=V();}h=f;}eH{T f=0;ew('0'<=c&&c<='9'){f=f*10+T(c-'0');c=V();}h=W?T(0)-f:f;}aG eA;}Y da(){if(O-r>=64)aG eA;aQ cI be=O-r;if(be>0)std::memmove(D,D+r,be);aQ cI dq=cI(std::fread(D+be,1,ai-be,aL));r=0;O=be+dq;if(O<ai)D[O]='\0';aG O!=0;}public:eI aA(std::FILE*bu=stdin):aL(bu),r(0),O(0),bl(::fileno(bu)),bD([&]{eu stat cB;aG bl>=0&&::fstat(bl,&cB)==0&&!S_ISREG(cB.st_mode);}()){}aA(aQ aA&)=delete;aA&cH=(aQ aA&)=delete;cI V(){if(r==O&&!cA())aG EOF;aG D[r++];}Y bq(){cI c=V();ew(c!=EOF&&c<=' ')c=V();if(c==EOF)aG ev;--r;aG eA;}Y read(aC&h){if(!bq())aG ev;h=aC(V());aG eA;}Y read(std::string&h){if(!bq())aG ev;h.clear();ew(eA){aQ cI begin=r;ew(r<O&&cd<az>(D[r])>' '){++r;}h.append(D+begin,r-begin);if(r<O){++r;aG eA;}if(!cA())aG eA;}}Y read(Y&h){cI x;if(!read(x))aG ev;h=x!=0;aG eA;}aO<cc T>std::enable_if_t<z::bp<T>&&!std::is_same_v<std::remove_cv_t<T>,Y>&&!std::is_same_v<std::remove_cv_t<T>,aC>,Y>read(T&h){if(bD)aG cK(h);if(!da())aG ev;cI c=cd<az>(D[r++]);ew(c<=' ')c=cd<az>(D[r++]);Y W=ev;if(c=='-'){W=eA;c=cd<az>(D[r++]);}if aP(z::bC<T>){T f=0;ew('0'<=c&&c<='9'){aQ cI l=c-'0';aQ cI m=cd<az>(D[r])-'0';if(0<=m&&m<=9){f=W?f*100-(l*10+m):f*100+(l*10+m);++r;}eH{f=W?f*10-l:f*10+l;}c=cd<az>(D[r++]);}h=f;}eH{T f=0;ew('0'<=c&&c<='9'){aQ aB l=aB(c-'0');aQ cI m=cd<az>(D[r])-'0';if(0<=m&&m<=9){f=f*100+T(l*10+aB(m));++r;}eH{f=f*10+T(l);}c=cd<az>(D[r++]);}h=W?T(0)-f:f;}if(r>O)r=O;aG eA;}aO<cc T>std::enable_if_t<std::is_floating_point_v<T>,Y>read(T&h){if(!bq())aG ev;cI c=V();Y W=ev;if(c=='-'||c=='+'){W=c=='-';c=V();}aD f=0;ew('0'<=c&&c<='9'){f=f*10+(c-'0');c=V();}if(c=='.'){aD cC=0.1L;c=V();ew('0'<=c&&c<='9'){f+=(c-'0')*cC;cC*=0.1L;c=V();}}if(c=='e'||c=='E'){c=V();Y ck=ev;if(c=='-'||c=='+'){ck=c=='-';c=V();}cI Z=0;ew('0'<=c&&c<='9'){Z=Z*10+(c-'0');c=V();}aD aX=1;aD aW=10;ew(Z>0){if(Z&1)aX*=aW;aW*=aW;Z>>=1;}f=ck?f/aX:f*aX;}h=cd<T>(W?-f:f);aG eA;}aO<cc T>std::enable_if_t<z::cm<T>&&!z::bp<T>&&!z::aS<T>,Y>read(T&h){long long x;if(!read(x))aG ev;if aP(z::cN<T>){if(x>=0&&uint64_t(x)<uint64_t(T::mod())){h=T::raw(uint32_t(x));}eH{h=T(x);}}eH{h=T(x);}aG eA;}aO<cc aM,cc bg>Y read(aE<aM,bg>&h){if(!read(h.first))aG ev;aG read(h.second);}aO<cc av>std::enable_if_t<z::aS<av>&&!z::bm<av>,Y>read(av&bV){cJ aH=z::cf<av>;aP Y bt=z::aS<aH>&&!z::bm<aH>;eD(eC&&h:bV){if aP(std::is_same_v<aH,Y>&&!bt){Y x;if(!read(x))aG ev;h=x;}eH{if(!read(h))aG ev;}}aG eA;}aO<cc aM,cc bg,cc...bX>Y read(aM&l,bg&m,bX&...rest){if(!read(l))aG ev;aG read(m,rest...);}aO<cc T>aA&cH>>(T&h){if(!read(h))std::abort();aG*eF;}};eu as{ey aP cI ai=1<<20;eG:ez ey aQ eC ct=[]{std::array<aC,40000>f{};eD(cI i=0;i<10000;i++){cI h=i;eD(cI j=3;j>=0;j--){f[4*i+j]=aC('0'+h%10);h/=10;}}aG f;}();std::FILE*aL;aC D[ai];cI r;cI bc;std::chars_format bo;aC bz;public:eI as(std::FILE*bu=stdout):aL(bu),r(0),bc(6),bo(std::chars_format::general),bz(' '){}as(aQ as&)=delete;as&cH=(aQ as&)=delete;~as(){bv();}ay bv(){if(r!=0){std::fwrite(D,1,r,aL);r=0;}std::fflush(aL);}ay aj(aC c){if(r==ai)bv();D[r++]=c;}ay P(aQ aC*s){ew(*s!='\0')aj(*s++);}ay P(aQ std::string&s){std::size_t ae=0;ew(ae<s.size()){if(r==ai)bv();aQ std::size_t bL=std::min<std::size_t>(ai-r,s.size()-ae);std::memcpy(D+r,s.data()+ae,bL);r+=cI(bL);ae+=bL;}}ay P(aC c){aj(c);}ay P(Y h){aj(h?'1':'0');}aO<cc T>std::enable_if_t<std::is_floating_point_v<T>>P(T h){aC aU[128];eC[end,ds]=std::to_chars(aU,aU+sizeof(aU),h,bo,bc);if(ds!=std::errc())std::abort();eD(aQ aC*bH=aU;bH!=end;bH++){aj(*bH);}}aO<cc T>std::enable_if_t<z::bp<T>&&!std::is_same_v<std::remove_cv_t<T>,Y>&&!std::is_same_v<std::remove_cv_t<T>,aC> >P(T h){cJ cF=std::remove_cv_t<T>;cJ bf=z::cW<cF>;bf ad;if aP(z::bC<cF>){if(h<0){aj('-');ad=bf(0)-bf(h);}eH{ad=bf(h);}}eH{ad=h;}if(ad==0){aj('0');aG;}aB cz[16];cI bS=0;ew(ad>=10000){aQ bf H=ad/10000;cz[bS++]=aB(ad-H*10000);ad=H;}if(r>ai-64)bv();aQ aB br=aB(ad);aQ aC*l=ct.data()+4*br;cI bZ=br<10?3:br<100?2:br<1000?1:0;eD(;bZ<4;bZ++)D[r++]=l[bZ];ew(bS--){aQ aC*aU=ct.data()+4*cz[bS];std::memcpy(D+r,aU,4);r+=4;}}aO<cc T>std::enable_if_t<z::cm<T>&&!z::bp<T>&&!z::aS<T> >P(aQ T&h){P(h.val());}aO<cc aM,cc bg>ay P(aQ aE<aM,bg>&h){P(h.first);aj(' ');P(h.second);}aO<cc av>std::enable_if_t<z::aS<av>&&!z::bm<av> >P(aQ av&bV){cJ aH=z::cf<aQ av>;aP Y bt=z::aS<aH>&&!z::bm<aH>;Y l=eA;eD(aQ eC&h:bV){if(!l)aj(bt?'\n':bz);l=ev;if aP(std::is_same_v<aH,Y>&&!bt){P(cd<Y>(h));}eH{P(h);}}}aO<cc aM,cc...bX>ay bU(aQ aM&l,aQ bX&...rest){P(l);((aj(' '),P(rest)),...);}ay println(){aj('\n');}ay dI(cI bd){bc=bd;}ay dR(cI bd=6){bo=std::chars_format::fixed;bc=bd;}ay dL(cI bd=6){bo=std::chars_format::general;bc=bd;}ay dF(aC dj){bz=dj;}aO<cc...Args>ay println(aQ Args&...args){bU(args...);aj('\n');}aO<cc T>as&cH<<(aQ T&h){P(h);aG*eF;}};}}cJ dE std;dE J{dE ao{ez aJ::aA&bi(){ey aJ::aA bF;aG bF;}ez aJ::as&ap(){ey aJ::as bF;aG bF;}}}cJ ll=long long;cJ ba=unsigned cI;cJ bb=unsigned long long;cJ bY=__int128;cJ ek=unsigned __int128;
#ifdef __SIZEOF_FLOAT128__
cJ eg=__float128;
#endif
aO<cc T>aP T X=0;aO<>aP cI X<cI> =1'000'000'000;aO<>aP ll X<ll> =ll(X<cI>)*X<cI>*2;aO<>aP ba X<ba> =X<cI>;aO<>aP bb X<bb> =X<ll>;aO<>aP bY X<bY> =bY(X<ll>)*X<ll>;aO<>aP double X<double> =X<ll>;aO<>aP aD X<aD> =X<ll>;cJ pi=pair<cI,cI>;cJ pl=pair<ll,ll>;cJ vi=vector<cI>;cJ vl=vector<ll>;aO<cc T>cJ vc=vector<T>;aO<cc T>cJ cb=vector<vc<T>>;cJ er=cb<cI>;cJ es=cb<ll>;aO<cc T>cJ dy=vector<cb<T>>;aO<cc T>cJ dx=vector<dy<T>>;aO<cc T>cJ dY=vector<dx<T>>;aO<cc T>cJ eq=std::priority_queue<T,vector<T>,greater<T>>;aO<cc T,cc U>cJ el=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()
cI bP(cI x){aG __builtin_popcount(x);}cI bP(ba x){aG __builtin_popcount(x);}cI bP(ll x){aG __builtin_popcountll(x);}cI bP(bb x){aG __builtin_popcountll(x);}cI bB(cI x){aG __builtin_parity(x);}cI bB(ba x){aG __builtin_parity(x);}cI bB(ll x){aG __builtin_parityll(x);}cI bB(bb x){aG __builtin_parityll(x);}cI bQ(cI x){aG(x==0?-1:31-__builtin_clz(x));}cI bQ(ba x){aG(x==0?-1:31-__builtin_clz(x));}cI bQ(ll x){aG(x==0?-1:63-__builtin_clzll(x));}cI bQ(bb x){aG(x==0?-1:63-__builtin_clzll(x));}cI bN(cI x){aG(x==0?-1:__builtin_ctz(x));}cI bN(ba x){aG(x==0?-1:__builtin_ctz(x));}cI bN(ll x){aG(x==0?-1:__builtin_ctzll(x));}cI bN(bb x){aG(x==0?-1:__builtin_ctzll(x));}aO<et T>T bT(T a,T b){aG a/b-(a%b&&(a^b)<0);}aO<et T>T ef(T x,T y){aG bT(x+y-1,y);}aO<et T>T ee(T x,T y){aG x-y*bT(x,y);}aO<et T>pair<T,T>bM(T x,T y){T q=bT(x,y);aG{q,x-q*y};}aO<et T,et U>T em(U x_,cI n){T x=x_;T cG=1;ew(n>0){if(n&1)cG*=x;x*=x;n>>=1;}aG cG;}aO<et T,et U>T en(aQ vector<U>&A){T sm=0;eD(eC&&a:A)sm+=a;aG 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()
aO<cc T,cc S>ez Y eb(T&a,aQ S&b){aG(a<b?a=b,1:0);}aO<cc T,cc S>ez Y ec(T&a,aQ S&b){aG(a>b?a=b,1:0);}vc<cI>dV(aQ string&S,aC de){vc<cI>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-de:-1);}aG A;}aO<et T,et U>vector<T>dW(vector<U>&A,cI dC=1){cI N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(dC==0)B.erase(B.begin());aG B;}aO<et T>vector<cI>dT(aQ vector<T>&A){vector<cI>ca(A.size());iota(all(ca),0);sort(all(ca),[&](cI i,cI j){aG(A[i]==A[j]?i<j:A[i]<A[j]);});aG ca;}aO<et T>vc<T>dQ(aQ vc<T>&A,aQ vc<cI>&I){vc<T>B(I.size());FOR(i,I.size())B[i]=A[I[i]];aG B;}aO<cc...T>aP eC dB(T...a){aG dB(initializer_list<common_type_t<T...>>{a...});}aO<cc...T>aP eC dA(T...a){aG dA(initializer_list<common_type_t<T...>>{a...});}aO<cc...Ts>Y cD(Ts&...values){aG J::ao::bi().read(values...);}aO<cc...Ts>ay bU(aQ Ts&...values){J::ao::ap().println(values...);}ay dZ(Y b){J::ao::ap().println(b?"YES":"NO");}ay ea(Y b){J::ao::ap().println(b?"Yes":"No");}ay eo(){J::ao::ap().println("YES");}ay NO(){J::ao::ap().println("NO");}ay ep(){J::ao::ap().println("Yes");}ay No(){J::ao::ap().println("No");}dE J{dE aV{aO<cc T=cI>eu bW{cJ dh=T;cI ax;cI R;T ah;cI C;Y aw;bW():ax(-1),R(-1),ah(T()),C(-1),aw(eA){}bW(cI dt,cI dD,T dr=T(1),cI dz=-1,Y dn=eA):ax(dt),R(dD),ah(dr),C(dz),aw(dn){}cI aq(cI v)aQ{(ay)0;aG ax^R^v;}};aO<cc T=cI>eu au{cJ ak=bW<T>;cJ dh=T;eG:cI _n;cI ab;o<o<ak>>K;o<o<aE<cI,cI>>>ar;public:au():_n(0),ab(0){}eI au(cI n):_n(n),ab(0),K(n){(ay)0;}cI size()aQ{aG _n;}Y empty()aQ{aG _n==0;}cI dN()aQ{aG ab;}cI dM(){K.emplace_back();aG _n++;}cI dG(cI ax,cI R,T ah=T(1)){(ay)0;(ay)0;cI C=ab++;cI aN=cI(K[ax].size());K[ax].push_back(ak(ax,R,ah,C));ar.emplace_back();ar.back().push_back({ax,aN});aG C;}cI add_edge(cI u,cI v,T ah=T(1)){(ay)0;(ay)0;cI C=ab++;cI dv=cI(K[u].size());K[u].push_back(ak(u,v,ah,C));cI dw=cI(K[v].size());K[v].push_back(ak(v,u,ah,C));ar.emplace_back();ar.back().push_back({u,dv});ar.back().push_back({v,dw});aG C;}ay cq(cI C,Y aw){(ay)0;eD(eC[v,aN]:ar[C]){K[v][aN].aw=aw;}}ay dO(cI C){cq(C,ev);}ay dK(cI C){cq(C,eA);}Y dH(cI C)aQ{(ay)0;(ay)0;eC[v,aN]=ar[C][0];aG K[v][aN].aw;}aQ o<ak>&cH[](cI v)aQ{(ay)0;aG K[v];}o<ak>&cH[](cI v){(ay)0;aG K[v];}aQ o<o<ak>>&dg()aQ{aG K;}o<o<ak>>&dg(){aG K;}o<ak>ed(Y cU=ev)aQ{o<ak>f;f.reserve(ab);o<aC>cE(ab,ev);eD(cI v=0;v<_n;v++){eD(aQ eC&e:K[v]){if(!cU&&!e.aw)eB;if(0<=e.C&&e.C<ab){if(cE[e.C])eB;cE[e.C]=eA;}f.push_back(e);}}aG f;}au dS()aQ{au f(_n);f.ab=ab;f.ar.assign(ab,{});eD(cI v=0;v<_n;v++){eD(aQ eC&e:K[v]){cI aN=cI(f.K[e.R].size());f.K[e.R].push_back(ak(e.R,e.ax,e.ah,e.C,e.aw));if(0<=e.C&&e.C<ab)f.ar[e.C].push_back({e.R,aN});}}aG f;}};}}dE J{dE aV{aO<cc T>eu aR{o<T>aa;o<aC>aT;o<cI>bO;o<cI>cu;T aZ=T();Y reachable(cI v)aQ{(ay)0;aG aT[v];}o<cI>ei(cI t)aQ{(ay)0;o<cI>f;eD(cI v=t;v!=-1;v=bO[v])f.push_back(v);std::reverse(f.begin(),f.end());aG f;}};dE z{aO<cc T>eu by{T aa;cI bR;};aO<cc T>eu cM{Y cH()(aQ by<T>&l,aQ by<T>&m)aQ{aG m.aa<l.aa;}};}aO<cc T>aR<T>aK(aQ au<T>&g,aQ o<cI>&bK){cI n=g.size();aR<T>f;f.aa.resize(n);f.aT.assign(n,ev);f.bO.assign(n,-1);f.cu.assign(n,-1);cJ bj=z::by<T>;cJ dm=z::cM<T>;std::priority_queue<bj,o<bj>,dm>bk;eD(cI s:bK){(ay)0;if(f.aT[s])eB;f.aT[s]=eA;f.aa[s]=T();bk.push(bj{T(),s});}ew(!bk.empty()){bj L=bk.top();bk.pop();if(f.aa[L.bR]<L.aa)eB;eD(aQ eC&e:g[L.bR]){if(!e.aw)eB;T nd=L.aa+e.ah;if(f.aT[e.R]&&!(nd<f.aa[e.R]))eB;f.aT[e.R]=eA;f.aa[e.R]=nd;f.bO[e.R]=L.bR;f.cu[e.R]=e.C;bk.push(bj{std::move(nd),e.R});}}aG f;}aO<cc T>aR<T>aK(aQ au<T>&g,cI s){aG aK(g,o<cI>{s});}aO<cc T>aR<T>aK(aQ au<T>&g,aQ o<cI>&bK,aQ T&aZ){aR<T>f=aK(g,bK);f.aZ=aZ;eD(cI v=0;v<cI(f.aa.size());v++){if(!f.reachable(v))f.aa[v]=aZ;}aG f;}aO<cc T>aR<T>aK(aQ au<T>&g,cI s,aQ T&aZ){aG aK(g,o<cI>{s},aZ);}}}dE J{dE aJ{dE dp{aO<std::size_t bx>cc k{eG:ey aP std::size_t ac=bx/64;cJ F=std::array<std::uint64_t,ac>;public:ey aP std::size_t dP=bx;aP k()=default;aO<std::integral cx>aP k(cx h){if aP(std::signed_integral<cx>){aQ std::uint64_t di=h<0?~std::uint64_t(0):std::uint64_t(0);E.fill(di);E[0]=cd<std::uint64_t>(cd<std::int64_t>(h));}eH{E[0]=cd<std::uint64_t>(h);}}eI k(std::string_view Q){read(Q);}k&cH=(std::string_view Q){read(Q);aG*eF;}ay read(std::string_view Q){if(Q.empty()){throw std::invalid_argument("empty fixed-width integer");}aQ Y W=Q.front()=='-';std::size_t ae=(Q.front()=='-'||Q.front()=='+')?1:0;if(ae==Q.size()){throw std::invalid_argument("invalid fixed-width integer");}k f;eD(;ae<Q.size();++ae){aQ aC bh=Q[ae];if(bh<'0'||bh>'9'){throw std::invalid_argument("invalid fixed-width integer");}f.multiply_unsigned_small(10);f+=k(cd<aB>(bh-'0'));}*eF=W?-f:f;}aP Y is_zero()aQ{eD(aQ std::uint64_t aY:E){if(aY!=0)aG ev;}aG eA;}aP Y is_negative()aQ{aG(E.back()>>63)!=0;}aP cI ej()aQ{if(is_zero())aG 0;aG is_negative()?-1:1;}aP k cH+()aQ{aG*eF;}aP k cH-()aQ{k f;f.E=E;cn(f.E);aG f;}aP k&cH+=(aQ k&aq){an am=0;eD(std::size_t w=0;w<ac;++w){aQ an L=an(E[w])+aq.E[w]+am;E[w]=cd<std::uint64_t>(L);am=L>>64;}aG*eF;}aP k&cH-=(aQ k&aq){aG*eF+=-aq;}aP k&cH*=(aQ k&aq){F bI{};eD(std::size_t l=0;l<ac;++l){an am=0;eD(std::size_t m=0;l+m<ac;++m){aQ std::size_t ae=l+m;aQ an L=an(E[l])*aq.E[m]+bI[ae]+am;bI[ae]=cd<std::uint64_t>(L);am=L>>64;}}E=bI;aG*eF;}aP k&multiply_small(std::uint64_t h){multiply_unsigned_small(h);aG*eF;}aP k&cH/=(aQ k&aq){aG*eF=bM(*eF,aq).first;}aP k&cH%=(aQ k&aq){aG*eF=bM(*eF,aq).second;}std::string to_string()aQ{if(is_zero())aG"0";aQ Y W=is_negative();F ad=unsigned_magnitude();std::string f;ew(!cQ(ad)){aQ aB bh=cL(ad);f.push_back(cd<aC>('0'+bh));}if(W)f.push_back('-');std::reverse(f.begin(),f.end());aG f;}ex aP aE<k,k>bM(aQ k&at,aQ k&af){if(af.is_zero()){throw std::domain_error("fixed-width integer division by zero");}aQ Y cR=at.is_negative()!=af.is_negative();aQ Y cO=at.is_negative();eC[bn,cX]=cV(at.unsigned_magnitude(),af.unsigned_magnitude());k H;k G;H.E=bn;G.E=cX;if(cR)H=-H;if(cO)G=-G;aG std::make_pair(H,G);}ex aP aE<k,std::int64_t>cs(aQ k&at,std::uint32_t af){if(af==0){throw std::domain_error("fixed-width integer division by zero");}F bn=at.unsigned_magnitude();aQ std::uint64_t cj=ce(bn,af);k H;H.E=bn;if(at.is_negative())H=-H;aQ std::int64_t G=at.is_negative()?-std::int64_t(cj):std::int64_t(cj);aG std::make_pair(H,G);}ex aP k cH+(k l,aQ k&m){aG l+=m;}ex aP k cH-(k l,aQ k&m){aG l-=m;}ex aP k cH*(k l,aQ k&m){aG l*=m;}ex aP k cH/(k l,aQ k&m){aG l/=m;}ex aP k cH%(k l,aQ k&m){aG l%=m;}ex aP Y cH==(aQ k&l,aQ k&m)=default;ex aP Y cH<(aQ k&l,aQ k&m){aQ Y co=l.is_negative();aQ Y cY=m.is_negative();if(co!=cY)aG co;aG cl(l.E,m.E)<0;}ex aP Y cH!=(aQ k&l,aQ k&m){aG!(l==m);}ex aP Y cH>(aQ k&l,aQ k&m){aG m<l;}ex aP Y cH<=(aQ k&l,aQ k&m){aG!(m<l);}ex aP Y cH>=(aQ k&l,aQ k&m){aG!(l<m);}ex std::ostream&cH<<(std::ostream&ap,aQ k&h){aG ap<<h.to_string();}ex std::istream&cH>>(std::istream&bi,k&h){std::string Q;if(bi>>Q)h.read(Q);aG bi;}eG:F E{};aP F unsigned_magnitude()aQ{F f=E;if(is_negative())cn(f);aG f;}aP ay multiply_unsigned_small(std::uint64_t h){an am=0;eD(std::size_t w=0;w<ac;++w){aQ an L=an(E[w])*h+am;E[w]=cd<std::uint64_t>(L);am=L>>64;}}ey aP ay cn(F&h){eD(std::uint64_t&aY:h)aY=~aY;eD(std::size_t w=0;w<ac;++w){if(++h[w]!=0)break;}}ey aP cI cl(aQ F&l,aQ F&m){eD(std::size_t al=0;al<ac;++al){aQ std::size_t w=ac-1-al;if(l[w]!=m[w]){aG l[w]<m[w]?-1:1;}}aG 0;}ey aP ay cT(F&l,aQ F&m){std::uint64_t bs=0;eD(std::size_t w=0;w<ac;++w){aQ std::uint64_t dk=l[w];l[w]-=m[w]+bs;aQ Y cP=bs!=0&&m[w]==~std::uint64_t(0);bs=cP||dk<m[w]+bs;}}ey aP ay db(F&h){std::uint64_t am=0;eD(std::size_t w=0;w<ac;++w){aQ std::uint64_t df=h[w]>>63;h[w]=(h[w]<<1)|am;am=df;}}ey aP aE<F,F>cV(aQ F&at,aQ F&af){F H{};F G{};eD(std::size_t al=0;al<bx;++al){aQ std::size_t bit=bx-1-al;db(G);G[0]|=(at[bit/64]>>(bit%64))&std::uint64_t(1);if(cl(G,af)>=0){cT(G,af);H[bit/64]|=std::uint64_t(1)<<(bit%64);}}aG std::make_pair(H,G);}ey Y cQ(aQ F&h){eD(aQ std::uint64_t aY:h){if(aY!=0)aG ev;}aG eA;}ey aP std::uint64_t ce(F&h,std::uint64_t af){an G=0;eD(std::size_t al=0;al<ac;++al){aQ std::size_t w=ac-1-al;aQ an L=(G<<64)|h[w];h[w]=cd<std::uint64_t>(L/af);G=L%af;}aG cd<std::uint64_t>(G);}ey aB cL(F&h){aG cd<aB>(ce(h,10));}};}}}dE J{dE aJ{cJ ag=dp::k<512>;cJ eh=ag;ez ag dJ(std::string_view Q){aG ag(Q);}ez std::string to_string(aQ ag&h){aG h.to_string();}}}eC&dX=J::ao::bi();eC&dU=J::ao::ap();cJ ag=J::aJ::ag;o<aE<cI,cI>>dd(){o<aE<cI,cI>>f;std::array<Y,301>cv{};eD(cI p=2;p<=300;++p){if(cv[p])eB;eD(cI bG=p+p;bG<=300;bG+=p){cv[bG]=eA;}cI Z=0;cI aW=1;ew(aW<=300/p){aW*=p;++Z;}f.emplace_back(p,Z);}aG f;}ay du(){aQ o<aE<cI,cI>>cy=dd();ag cg=1;eD(eC[bw,Z]:cy){eD(cI i=0;i<Z;++i){cg.multiply_small(bw);}}std::array<ag,301>aX;eD(cI aI=1;aI<=300;++aI){eC[H,G]=cs(cg,aI);(ay)0;aX[aI]=H;}cI N,M;cD(N,M);J::aV::au<ag>aV(N);ew(M--){cI u,v,a,b;cD(u,v,a,b);--u;--v;ag ah=aX[b];ah.multiply_small(a);aV.add_edge(u,v,ah);}aQ eC dl=J::aV::aK(aV,0);eD(cI v=1;v<N;++v){ag bE=dl.aa[v];ag aI=1;eD(eC[bw,Z]:cy){cI bJ=0;ew(bJ<Z){eC[H,G]=cs(bE,bw);if(G!=0)break;bE=H;++bJ;}eD(cI i=bJ;i<Z;++i){aI.multiply_small(bw);}}bU(bE.to_string(),aI.to_string());}}cI main(){cI T=1;ew(T--)du();aG 0;}