//コンパイル時の引数にBLUEBERRYを渡すとdeb関数が使える#ifdef BLUEBERRY#define deb print// #define _GLIBCXX_DEBUG#else#define deb(...)//速くなる呪文// #pragma GCCtarget("arch=skylake-avx512")// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#endif#include<bits/stdc++.h>usingnamespacestd;void_main();intmain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(30);_main();quick_exit(0);return0;}typedeflonglongll;typedeflongdoubleld;typedefunsignedlonglongull;typedefunsignedintuint;typedefstringstr;#define rep1(a)          for(ll i = 0; i < (ll)(a); i++)#define rep2(i, a)       for(ll i = 0; i < (ll)(a); i++)#define rep3(i, a, b)    for(ll i = (a); i < (ll)(b); i++)#define rep4(i, a, b, c) for(ll i = (a); i < (ll)(b); i += (c))#define overload4(a, b, c, d, e, ...) e#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define ALL(x) std::begin(x),std::end(x)#define rALL(x) std::rbegin(x),std::rend(x)#define INF ((1LL<<62)-(1LL<<31))// #define inf ((1<<30)-(1<<15))#define bit(x,i) (((x)>>(i))&1)#define fi first#define se second#define pb push_back#define eb emplace_back#define Endl endl#define spa " "#define YesNo(x) cout<<(x?"Yes":"No")<<endl;#define YESNO(x) cout<<(x?"YES":"NO")<<endl;#define eps (1e-8)#define popc(x) __builtin_popcount(x)#define crmp(x,l,r) ((l<=x)&&(x<=r))//！？！？#define O print//可変長引数で入力を受け取りつつ変数を宣言inlinevoidscan(){}template<classHead,class...Tail>inlinevoidscan(Head&head,Tail&...tail){std::cin>>head;scan(tail...);}#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)//vectorのcintemplate<typenameT>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(T&in:v){is>>in;}returnis;}//vectorのcouttemplate<typenameT>std::ostream&operator<<(std::ostream&os,conststd::vector<T>&v){for(autoit=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}returnos;}//dequeのcintemplate<typenameT>std::istream&operator>>(std::istream&is,std::deque<T>&v){for(T&in:v){is>>in;}returnis;}//dequeのcouttemplate<typenameT>std::ostream&operator<<(std::ostream&os,conststd::deque<T>&v){for(autoit=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}returnos;}//pairのcin,couttemplate<typenameT,typenameU>std::ostream&operator<<(std::ostream&os,conststd::pair<T,U>&p){os<<p.first<<" "<<p.second;returnos;}template<typenameT,typenameU>std::istream&operator>>(std::istream&is,std::pair<T,U>&p){is>>p.first>>p.second;returnis;}//x,y,x,yを渡すとldで距離を返すlongdoublemy_distance(longdoublexi,longdoubleyi,longdoublexj,longdoubleyj){returnsqrtl(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}//可変長引数のprint関数#pragma GCC diagnostic ignored "-Wunused-value"voidprint(){cout<<'\n';}template<classT,class...Ts>voidprint(constT&a,constTs&...b){cout<<a;(std::cout<<...<<(cout<<' ',b));cout<<'\n';}#pragma GCC diagnostic warning "-Wunused-value"//可変長引数のmintemplate<class...T>constexprautomin(T...a){returnmin(initializer_list<common_type_t<T...>>{a...});}//可変長引数のmaxtemplate<class...T>constexprautomax(T...a){returnmax(initializer_list<common_type_t<T...>>{a...});}template<typenameT,typenameU>inlineboolchmax(T&a,Ub){if(a<b){a=b;return1;}return0;}template<typenameT,typenameU>inlineboolchmin(T&a,Ub){if(a>b){a=b;return1;}return0;}template<typenameT>inlineTsum(vector<T>&a){Tret{};for(auto&i:a)ret+=i;returnret;}template<typenameT>inlineTmin(vector<T>&a){Tret=a[0];for(auto&i:a)chmin(ret,i);returnret;}template<typenameT>inlineTmax(vector<T>&a){Tret=a[0];for(auto&i:a)chmax(ret,i);returnret;}template<typenameT>inlineintlen(vector<T>&a){returna.size();}inlineintlen(string&a){returna.size();}// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。template<typenameA,size_tN,typenameT>voidFill(A(&array)[N],constT&val){std::fill((T*)array,(T*)(array+N),val);}//こめんとを付け外ししてMODを切り替える//ll MOD = INF;// ll MOD = 1000000007;llMOD=998244353;//ax+by = 1 であるようなx,yを返す// pair<long long, long long> extgcd(long long a, long long b) {//   if (b == 0) return make_pair(1, 0);//   long long x, y;//   tie(y, x) = extgcd(b, a % b);//   y -= a / b * x;//   return make_pair(x, y);// }structRande{mt19937mt;Rande():mt(chrono::steady_clock::now().time_since_epoch().count()){}intoperator()(inta,intb){uniform_int_distribution<int>dist(a,b-1);returndist(mt);}intoperator()(intb){return(*this)(0,b);}};//from:https://kenkoooo.hatenablog.com/entry/2016/11/30/163533 int128std::ostream&operator<<(std::ostream&dest,__int128_tvalue){std::ostream::sentrys(dest);if(s){__uint128_ttmp=value<0?-value:value;charbuffer[128];char*d=std::end(buffer);do{--d;*d="0123456789"[tmp%10];tmp/=10;}while(tmp!=0);if(value<0){--d;*d='-';}intlen=std::end(buffer)-d;if(dest.rdbuf()->sputn(d,len)!=len){dest.setstate(std::ios_base::badbit);}}returndest;}__int128parsetoint128(string&s){__int128ret=0;for(inti=0;i<(int)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+(__int128_t)(s[i]-'0');returnret;}lldivide(lla,llb){if(b<0)a*=-1,b*=-1;if(a>=0)returna/b;elsereturn-(((-a)+(b-1))/b);}//回文判定booliskaibun(strings){llk=s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){returnfalse;}}returntrue;}//二部グラフ判定 重みなしグラフを引数に取り、boolを返すboolisbipartite_graph(vector<vector<ll>>&g){llv=g.size();vector<ll>col(v,-1);vector<bool>used(v,false);boolret=true;rep(i,v){if(used[i])continue;col[i]=0;[DFS([&](auto&&f,llpos,llpr)->void{if(used[pos])return;used[pos]=true;for(autoto:g[pos]){if(to==pr)continue;if(used[to]&&col[pos]==col[to]){ret=false;return;}if(used[to])continue;col[to]=col[pos]^1;f(f,to,pos);}}),&i]{DFS(DFS,i,-1);}();}returnret;}//a~bの和 a<bllran(lla,llb){return((a+b)*(b-a+1))/2;}//座圧するllzaatu(vector<ll>&A){map<ll,ll>m;for(auto&&x:A)m[x]=0;llret=0;for(auto&&[key,val]:m)val=ret++;for(auto&&x:A)x=m[x];returnret;}//約数列挙　引数に取った整数の約数のvectorを返すvector<ll>enumdiv(lln){vector<ll>s;for(lli=1;i*i<=n;i++){if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}}returns;}//トポロジカルソート グラフ、入次数カウント、頂点数を引数で渡すと、トポロジカルソートされた頂点列を返すvector<ll>topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,llv){vector<ll>ret;priority_queue<ll,vector<ll>,greater<ll>>pq;rep(i,0,v){if(nyu_cnt[i]==0)pq.push(i);}while(!pq.empty()){llpos=pq.top();pq.pop();for(lli:G[pos]){nyu_cnt[i]--;if(nyu_cnt[i]==0)pq.push(i);}ret.push_back(pos);}returnret;}//素因数分解 pair<素数、指数>のvectorを返すvector<pair<ll,ll>>soinsu_bunkai(llx){vector<pair<ll,ll>>ret;ret.reserve(1<<8);lli=2;for(i=2;i<4;i++)if(x%i==0){llcnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}for(i=1;i*i<=x;i+=2){if(i>1)if(x%i==0){llcnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}i+=4;if(x%i==0){llcnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}}if(x!=1)ret.push_back({x,1});returnret;}//二項係数MOD MODは上の方で設定、MAXまでのnCrをCOM(n,r)でとれるconstintMAX=777778;llfac[MAX],finv[MAX],invv[MAX];boolCOMINIT=false;voidCOMinit(){if(COMINIT)return;COMINIT=true;fac[0]=fac[1]=finv[0]=finv[1]=invv[1]=1;for(inti=2;i<MAX;i++){fac[i]=fac[i-1]*i%MOD;invv[i]=MOD-invv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*invv[i]%MOD;}}llCOM(intn,intk){if(n<k)return0;if(n<0||k<0)return0;if(k==0)return1;returnfac[n]*(finv[k]*finv[n-k]%MOD)%MOD;}llnPr(intn,intk){if(n<k)return0;if(n<0||k<0)return0;if(k==0)return1;returnfac[n]*(finv[n-k]);}//エラトステネスの篩　isprimeには素数かどうかが入っているvector<bool>isprime;vector<int>Era(intn){isprime.resize(n,true);vector<int>res;isprime[0]=false;isprime[1]=false;for(inti=2;i<n;++i)isprime[i]=true;for(inti=2;i<n;++i){if(isprime[i]){res.push_back(i);for(intj=i*2;j<n;j+=i)isprime[j]=false;}}returnres;}//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-findclassUnionFind{public:UnionFind()=default;explicitUnionFind(size_tn):m_parentsOrSize(n,-1){}intfind(inti){if(m_parentsOrSize[i]<0){returni;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}voidmerge(inta,intb){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}boolconnected(inta,intb){return(find(a)==find(b));}intsize(inti){return-m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};template<classT>usingpqg=priority_queue<T,vector<T>,greater<T>>;template<classF>llbin_search(llok,llng,constF&f){while(abs(ok-ng)>1){longlongmid=(ok+ng)>>1;(f(mid)?ok:ng)=mid;}returnok;}//グリッドの8近傍 4まで回せば4近傍lldx[8]={0,1,0,-1,-1,-1,1,1},dy[8]={1,0,-1,0,-1,1,-1,1};constexprldCPS=CLOCKS_PER_SEC;boolsolve();void_main(){[]{[]{[]{[]{[]{}();}();}();}();}();inttestcase=1;// cin >> testcase,cerr<<"multitestcase"<<endl;for(;testcase--;){if(solve()){// O("Possible");}else{// O("Impossible");}}cout<<flush;[]{[]{[]{[]{[]{}();}();}();}();}();}#include<atcoder/all>usingnamespaceatcoder;// using mint = modint;usingmint=modint998244353;usingmint1=modint1000000007;boolsolve(){returnfalse;}