#include #include using namespace std; using namespace atcoder; #define rep(i,n) for(int i=0; i #define vvi vector> #define vl vector #define vs vector int gi() { int i; cin >> i; return i; } ll gl() { ll l; cin >> l; return l; } double gd() { double d; cin >> d; return d; } string gs() { string s; cin >> s; return s; } vector gia(int n) { vector A(n); rep(i,n) { cin >> A[i]; } return A; } vector gla(int n) { vector A(n); rep(i,n) { cin >> A[i]; } return A; } vector gsa(int n) { vector A(n); rep(i,n) { cin >> A[i]; } return A; } vector> gsi2(int n, int m) { vector> A(n, vector(m)); rep(i,n) { rep(j,m) { cin >> A[i][j]; } } return A; } vector> readGraph(int n, int m, bool f=false) { vector> G(n); rep(i,m){ int a=gi(); int b=gi(); a--; b--; G[a].push_back(b); if(!f){ G[b].push_back(a); } } return G; } vector>> readGraphWithWeight(int n, int m, bool f=false) { vector>> G(n); rep(i,m){ int a=gi(); int b=gi(); ll c=gi(); a--; b--; pair p=make_pair(c,b); G[a].push_back(p); if(!f){ pair p2=make_pair(c,a); G[b].push_back(p2); } } return G; } void ov(vector v) { if((int)v.size()==0)return; rep(i,(int)v.size()-1) { cout << v[i] << ' '; } cout << v[v.size()-1] << endl; } // 二分グラフ判定 bool isBipartite(vector>>& E, int N) { dsu uf(N*2); rep(i,E.size()) { int a=E[i].second.first; int b=E[i].second.second; ll w=E[i].first; uf.merge(a,b+N); uf.merge(a+N,b); } rep(i,N) { if(uf.same(i,i+N))return false; } return true; } vector matrixMulti(vector& A, vector& B) { int AR=A.size(); int AC=A[0].size(); int BC=B[0].size(); vector ans(AR,vl(BC,0)); rep(i,AR) { rep(j,BC) { rep(k,AC) { ans[i][k]+=A[i][j]*B[j][k]; } } } return ans; } vector matrixPow(vector& A, int p) { int q=p; int cnt=0; while(q>0) { cnt++; q=q>>1; } vector> PAS; PAS.push_back(A); rep(i,cnt-1) { PAS.push_back(matrixMulti(PAS[i],PAS[i])); } vector ans(A.size(),vl(A.size(),0)); rep(i,ans.size()) { ans[i][i]=1; } rep(i,cnt) { if((p>>i & 1) == 0)continue; ans=matrixMulti(ans,PAS[i]); } return ans; } vector split(const string &s, char delim) { vector elems; string item; for (char ch: s) { if (ch == delim) { if (!item.empty()) elems.push_back(item); item.clear(); } else { item += ch; } } if (!item.empty()) elems.push_back(item); return elems; } // private void recursive_comb(int *indexes, int s, int rest, std::function f) { if (rest == 0) { f(indexes); } else { if (s < 0) return; recursive_comb(indexes, s - 1, rest, f); indexes[rest - 1] = s; recursive_comb(indexes, s - 1, rest - 1, f); } } // nCkの組み合わせに対して処理を実行する void foreach_comb(int n, int k, std::function f) { int indexes[k]; recursive_comb(indexes, n - 1, k, f); } vector fact, fact_inv, inv; // nCkの前計算 void init_nCk(int SIZE, int mod) { fact.resize(SIZE + 5); fact_inv.resize(SIZE + 5); inv.resize(SIZE + 5); fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; inv[1] = 1; for (int i = 2; i < SIZE + 5; i++) { fact[i] = fact[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; fact_inv[i] = fact_inv[i - 1] * inv[i] % mod; } } /* nCk :MODでの二項係数を求める(前処理 int_nCk が必要) 計算量:O(1) */ long long nCk(int n, int k, int mod) { if(n A) { int MAX=INT_MAX; vector dp((int)A.size(), MAX); rep(i, (int)A.size()) { int a=A[i]; int mn=-1; int mx=(int)A.size(); while(mx-mn>1){ int idx=(mx+mn)/2; int v=dp[idx]; if(a>v) { mn=idx; } else { mx=idx; } } dp[mx]=a; } int ans=0; rep(i, (int)A.size()) { if(dp[i]!=MAX){ ans+=1; } else { break; } } return ans; } ll uclid(ll m, ll n) { if(n==0) { return m; } else { return uclid(n,m%n); } } vector yakusu(ll N) { vector ans; for(ll i=1;iN)break; if(N%i==0) { ans.push_back(i); if(N/i!=i) { ans.push_back(N/i); } } } return ans; } vector insuB(ll N) { vector ans; ll i=2; while(i*i<=N) { if(N%i==0) { ans.push_back(i); N=N/i; } else { i++; } } if(N!=1) { ans.push_back(N); } return ans; } map insuBm(ll N) { map ans; for(ll i=2;iN)break; while(N%i==0) { ans[i]++; N=N/i; } } if(N!=1) { ans[N]++; } return ans; } void rotate(vector>& A) { vector> ra(A[0].size(),vector(A.size(),0)); rep(i, (int)A[0].size()) { rep(j,(int)A.size()) { ra[i][j]=A[A.size()-j-1][i]; } } A=ra; } vector eratostenes(int N) { vector ans(N+1,true); ans[0]=false; ans[1]=false; for(int i=2; i<=N; i++) { if(ans[i]==false)continue; for(int j=2*i; j<=N; j+=i) { ans[j]=false; } } return ans; } pair invGcd(ll a,ll b) { a%=b; if(a==0)return make_pair(b,0); ll s=b; ll t=a; ll m0=0; ll m1=1; while(t>0) { ll u=s/t; s-=t*u; m0-=m1*u; ll tmp=s; s=t; t=tmp; tmp=m0; m0=m1; m1=tmp; } if(m0<0)m0+=b/s; return make_pair(s,m0); } vector>> kruskal(int N, vector>> edges) { sort(edges.begin(), edges.end()); dsu uf(N); vector>> ans; rep(i,(int)edges.size()) { pair> edge=edges[i]; int u=edge.second.first; int v=edge.second.second; if(!uf.same(u,v)) { uf.merge(u,v); ans.push_back(edge); } } return ans; } vector dijkstra(vector>>& G, int s) { ll MAX=999999999999999999LL; vector dist(G.size(),MAX); priority_queue, vector>, greater>> pq; dist[s]=0; pq.push(make_pair(0,s)); while((int)pq.size()>0) { pair p= pq.top(); pq.pop(); ll d = p.first; ll v = p.second; if(dist[v]> el=G[v]; rep(i,(int)el.size()) { ll nd=dist[v]+el[i].first; if(nd topologicalSort(vector>& G) { vector result; vector inn((int)G.size(),0); rep(i,(int)G.size()){ vector es=G[i]; rep(j,(int)es.size()) { int e=es[j]; inn[e]++; } } deque deq; rep(i,(int)G.size()){ if(inn[i]==0)deq.push_back(i); } while((int)deq.size()>0) { int v=deq.front(); deq.pop_front(); result.push_back(v); vector es=G[v]; rep(j,(int)es.size()) { int e=es[j]; inn[e]--; if(inn[e]==0){ deq.push_back(e); } } } return result; } int search_with_suffix_array(str s, str t) { vi sa =suffix_array(s); int mn=-1; int mx=s.length(); while(mx-mn>1) { int idx=(mx+mn)/2; int si=sa[idx]; str ts=s.substr(si,min(t.length(),s.length()-si)); if(ts deq; rep(i,max(S.size(),T.size())) { int si=0; int ti=0; if(i=10) { ku=1; wa-=10; } else { ku=0; } deq.push_front(wa); } if(ku==1)deq.push_front(1); while(deq.size()>0){ cout<