#include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i-->0;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue #define NP(x) next_permutation(all(x)) #define M_PI 3.14159265358979323846 #define popcount __builtin_popcountll using namespace std; typedef vector vb; typedef vector vvb; typedef vector vi; typedef vector vvi; typedef long long ll; typedef vector< ll> vl; typedef vector vvl; typedef unsigned long long ull; typedef vector vu; typedef vector vvu; typedef double dbl; typedef vector vd; typedef vector vvd; typedef string str; typedef vector vs; typedef vector vvs; typedef pairpii; typedef vectorvpii; typedef mapmii; typedef pair< ll, ll>pll; typedef vectorvpll; typedef map< ll, ll>mll; typedef pairpdd; typedef vectorvpdd; typedef mapmdd; typedef pairpss; typedef vectorvpss; typedef mapmss; typedef pairpil; typedef vectorvpil; typedef mapmil; typedef pair< ll,int>pli; typedef vectorvpli; typedef map< ll,int>mli; typedef pairpdi; typedef vectorvpdi; typedef mapmdi; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatestack&operator<<(stack&s,const T t){s.push(t);return s;} templatestack&operator>>(stack&s,T&t){t=s.top();s.pop();return s;} templatequeue&operator<<(queue&q,const T t){q.push(t);return q;} templatequeue&operator>>(queue&q,T&t){t=q.front();q.pop();return q;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templatePQ,U>&operator>>(PQ,U>&q,T&t){t=q.top();q.pop();return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} istream&operator>>(istream&s,_Bit_reference b){int a;s>>a;assert(a==0||a==1);b=a;return s;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){fr(i,v.size()){i?s<<" "<ostream&operator<<(ostream&s,const dequed){fr(i,d.size()){i?s<<" "<_Bit_reference operator&=(_Bit_reference b,T t){return b=b&t;} template_Bit_reference operator^=(_Bit_reference b,T t){return b=b^t;} template_Bit_reference operator|=(_Bit_reference b,T t){return b=b|t;} templatepairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} templatepair&operator+=(pair&a,pairb){return a=a+b;} templatepair&operator-=(pair&a,pairb){return a=a-b;} void print(void){cout<<"\n";} void Print(void){cout<void print(T t){cout<void Print(T t){cout<void print(T&&t,U&&...u){cout<(u)...);} templatevoid Print(T&&t,U&&...u){cout<(u)...);} bool YN(bool b){print(b?"YES":"NO");return b;}bool PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");return b;} bool Yn(bool b){print(b?"Yes":"No");return b;}bool Pi(bool b){print(b?"Possible":"Impossible");return b;} bool yn(bool b){print(b?"yes":"no");return b;}bool pi(bool b){print(b?"possible":"impossible");return b;} const int e5=1e5; const int e9=1e9; const int MD=1e9+7; const int md=998244353; const ll e18=1e18; templatestr to_string(const T&n){ostringstream s;s<T&chmax(T&a,T b){return a=max(a,b);} templateT&chmin(T&a,T b){return a=min(a,b);} templatevector>dijkstra(const vector>>&E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.first&E,int s,int t){ll z=0;vi b(E.size(),-1);for(int i=0;;++i){static auto dfs=[&](int v,ll f,auto&dfs)->ll{if(v==t)return f;b[v]=i;for(auto&p:E[v]){if(b[p.first]T distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){assert(a.size());T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){assert(a.size());T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} templatevectorLCS(vectorA,vectorB){int N=A.size(),M=B.size();vector>>d(N+1,vector>(M+1));fr(i,N){fr(j,M){if(A[i]==B[j]){d[i+1][j+1]={d[i][j].first+1,{i,j}};}else{d[i+1][j+1]=max(d[i][j+1],d[i+1][j]);}}}vectorr;for(pii p={N,M};d[p.first][p.second].first;p=d[p.first][p.second].second){r<s=LCS(vector(S.begin(),S.end()),vector(T.begin(),T.end()));return str(s.begin(),s.end());} templatevector>ConvexHull(vector>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<>r;for(pairp:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<s[b]){swap(a,b);}s[b]+=s[a];p[a]=b;}}void unite(pii p){return unite(p.first,p.second);}bool same(int a,int b){extend(a);extend(b);return find(a)==find(b);}bool same(pii p){return same(p.first,p.second);}int size(int x){extend(x);return s[find(x)];}}; ll MST(vector>&E){Sort(E);UnionFind uf;ll z=0;for(auto&e:E){if(!uf.same(e.second)){z+=e.first;uf.unite(e.second);}}return z;} ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){assert(x!=0);return pow(x,p-2,p);} ll inv(const ll x){return inv(x,MD);} vpll fact(const int n,const int p){assert(nint MSB(T N){int r=-1;for(;N>0;N/=2){++r;}return r;} templateclass SegmentTree{vectorS;T(*const op)(T a,T b);const T zero;const int B;public:SegmentTree(int N,T(*f)(T a,T b),const T zero):S(1<v,T(*f)(T a,T b),const T zero):SegmentTree(v.size(),f,zero){fr(i,v.size()){S[S.size()/2+i]=v[i];}roof(i,S.size()/2-1,1){S[i]=op(S[i*2],S[i*2+1]);}}T calc(int l,int r){l+=B;r+=B;if(l>r){return zero;}if(l==r){return S[l];}T L=S[l],R=S[r];for(;l/20){z+=B[i];i-=i&-i;}return z;} void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<dfs=[&](int i,int p){for(int j:E[i])if(j!=p){par[0][j]=i;dep[j]=dep[i]+1;dfs(j,i);}};par[0][root]=root;dfs(root,root);fr(i,par.size()-1){fr(j,par[0].size()){par[i+1][j]=par[i][par[i][j]];}}}int operator()(int a,int b){if(dep[a]>dep[b])swap(a,b);for(int t=dep[b]-dep[a],i=0;t;t>>=1,++i){if(t&1){b=par[i][b];}}if(a==b)return a;rf(i,par.size()){if(par[i][a]!=par[i][b]){a=par[i][a];b=par[i][b];}}return par[0][a];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[operator()(a,b)];}}; vpli factor(ll N){vpli r;for(ll i=2;i*i<=N;++i){if(N%i==0){r<1){r<bool{if(rank[a]!=rank[b])return rank[a]void sort2(vector&a,vector&b){int N=a.size();assert(b.size()==N);vector>v;fr(i,N){v<{a[i],b[i]};}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second;}} templatevoid sort3(vector&a,vector&b,vector&c){int N=a.size();assert(b.size()==N);assert(c.size()==N);vector>>v;fr(i,N){v.push_back({a[i],{b[i],c[i]}});}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second.first;c[i]=v[i].second.second;}} bool iskadomatsu(int a,int b,int c){ if(a>c)swap(a,c); return a>W>>H; vvi A(H,vi(W));cin>>A; vectord(H,vvi(W,vi(4,e9))); d[0][1][0]=1; d[1][0][1]=1; queueq; q<<0<<1<<0<<1<<0<<1; vi dy={0,1,0,-1},dx={1,0,-1,0}; while(q.size()){ int y,x,t;q>>y>>x>>t; fr(i,4){ int Y=y+dy[i]; int X=x+dx[i]; if(0<=Y&&Y