#pragma GCC optimize ("O3,Ofast,inline,fast-math,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define int int64_t
#define double long double
#define INIT std::ios_base::sync_with_stdio(0);std::cin.tie(0);std::cout<<std::fixed<<std::setprecision(15);
#define WRITE_FUNCTION_UNDER_HERE DEFALLTYPE(VDEF)DEFALLTYPE(PDEF3)
const int MOD=1e9+7;
using namespace std;const int MAX=std::numeric_limits<int>::max();const int MIN=std::numeric_limits<int>::min();const double EPS=1e-7;
#define fou(i,a,n) for(int i=a;i<n;i++)
#define fod(i,a,n) for(int i=n-1;i>=a;i--)
#define tra(e,v) for(auto&e:v)
#define elif(c) else if(c)
#define fi first
#define se second
#define fir fi
#define sec se.fi
#define thi se.se
#define firs fi
#define seco sec
#define thir thi.fi
#define four thi.se
#define DEFALLTYPE(XDEF) XDEF(int,I)XDEF(double,D)XDEF(char,C)XDEF(String,S)XDEF(bool,B)XDEF(Modulo,M)
#define VDEF(t,T) typedef Vector<t>V##T;typedef Vector<V##T>VV##T;typedef Vector<VV##T>VVV##T;
#define PDEF(x,X,y,Y,z,Z,w,W) typedef std::pair<x,y>P##X##Y;VDEF(P##X##Y,P##X##Y)typedef std::pair<x,std::pair<y,z>>P##X##Y##Z;VDEF(P##X##Y##Z,P##X##Y##Z)typedef std::pair<x,std::pair<y,std::pair<z,w>>>P##X##Y##Z##W;VDEF(P##X##Y##Z##W,P##X##Y##Z##W)
#define PDEF1(y,Y,z,Z,w,W) PDEF(int,I,y,Y,z,Z,w,W)PDEF(double,D,y,Y,z,Z,w,W)PDEF(char,C,y,Y,z,Z,w,W)PDEF(String,S,y,Y,z,Z,w,W)PDEF(bool,B,y,Y,z,Z,w,W)PDEF(Modulo,M,y,Y,z,Z,w,W)
#define PDEF2(z,Z,w,W) PDEF1(int,I,z,Z,w,W)PDEF1(double,D,z,Z,w,W)PDEF1(char,C,z,Z,w,W)PDEF1(String,S,z,Z,w,W)PDEF1(bool,B,z,Z,w,W)PDEF1(Modulo,M,z,Z,w,W)
#define PDEF3(w,W) PDEF2(int,I,w,W)PDEF2(double,D,w,W)PDEF2(char,C,w,W)PDEF2(String,S,w,W)PDEF2(bool,B,w,W)PDEF2(Modulo,M,w,W)

// in, out


#define in(T,...) T __VA_ARGS__;_in(__VA_ARGS__)
void _in(){}template<typename Hd,typename...Tl>void _in(Hd&hd,Tl&&...tl){std::cin>>hd;_in(std::forward<Tl>(tl)...);}void out(){std::cout<<'\n';}template<typename T>void out(const T&a){std::cout<<a<<'\n';}template<typename Hd,typename ...Tl>void out(const Hd&hd,const Tl&...tl){std::cout<<hd<<' ';out(tl...);}

// std::pair io,calc
#define PairCalc(OP) template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP(const std::pair<T,U>&l,const std::pair<V,W>&r){return std::make_pair(l.first OP r.first,l.second OP r.second);}template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP##=(std::pair<T,U>&l,const std::pair<V,W>&r){return l=l OP r;}
template<typename T,typename U>std::istream&operator>>(std::istream&i,std::pair<T,U>&p){i>>p.first>>p.second;return i;}template<typename T,typename U>std::ostream&operator<<(std::ostream&o,const std::pair<T,U>&p){return o<<p.first<<' '<<p.second;}PairCalc(+)PairCalc(-)PairCalc(*)PairCalc(/)PairCalc(%)PairCalc(<<)PairCalc(>>)PairCalc(&)PairCalc(|)PairCalc(^)template<typename T,typename U>std::pair<T,U>mp(const T&t,const U&u){return std::make_pair(t,u);}template<typename T,typename U,typename V>std::pair<T,std::pair<U,V>>mp(const T&t,const U&u,const V&v){return std::make_pair(t,std::make_pair(u,v));}template<typename T,typename U,typename V,typename W>std::pair<T,std::pair<U,std::pair<V,W>>>mp(const T&t,const U&u,const V&v,const W&w){return std::make_pair(t,std::make_pair(u,std::make_pair(v,w)));}

// Slice class, Vector class
struct Slice{int first=0;int last=-1;int step=1;Slice(int f,int l=-1,int s=1):first(f),last(l),step(s){}Slice(std::initializer_list<int>l){if(l.size()!=3)return;first=*l.begin();last=*(l.begin()+1);step=*(l.begin()+2);}};
#define VecCalc(OP) Vector<T>operator OP(const Vector<T>&r)const{Vector<T>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Vector<T>operator OP(const T&r)const{Vector<T>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Vector<T>operator OP##=(const Vector<T>&r){return *this=*this OP r;}Vector<T>operator OP##=(const T&r){return *this=*this OP r;}
#define VecComp(OP) Vector<int>operator OP(const Vector<T>&r)const{Vector<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Vector<int>operator OP(const T&r)const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}
#define VVCalc(OP) template<typename T,typename U>Vector<Vector<T>>operator OP(Vector<Vector<T>>l,const U&r){for(Vector<T>&e:l)e OP##=r;return l;}template<typename T,typename U>Vector<Vector<T>>operator OP##=(Vector<Vector<T>>&l,const U&r){return l=l OP r;}
#define VVComp(OP) template<typename T,typename U>Vector<Vector<int>>operator OP(const Vector<Vector<T>>&l,const U&r){Vector<Vector<int>>v(l.size());for(int i=0;i<l.size();i++)v[i]=l[i] OP r;return v;}
template<typename T>class Vector{std::vector<T>value;public:Vector(int s=0,T v=T()){if(s>=0)assign(s,v);else{assign(-s,v);for(T&e:value)std::cin>>e;}}Vector(const std::initializer_list<T>&l){value=std::vector<T>{l};}template<typename U>Vector(const Vector<U>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];}Vector(const std::vector<T>&v){value=v;}int size()const{return value.size();}T operator[](int i)const{return value[i];}T&operator[](int i){return value[i];}Vector<T>operator[](Slice s)const{s.last=(s.last<0?s.last+size()+1:s.last);Vector<T>v;for(int i=s.first;i<s.last;i+=s.step)v.pub(value[i]);return v;}Vector<T>&operator=(const Vector<T>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];return *this;}Vector<T>operator+()const{return *this;}Vector<T>operator-()const{Vector<T>v(value.size());for(int i=0;i<size();i++)v[i]=-value[i];return v;}Vector<T>operator++(){for(T&e:value)e++;return *this;}Vector<T>operator--(){for(T&e:value)e--;return *this;}Vector<T>operator++(int32_t){Vector<T>v=*this;for(T&e:value)e++;return v;}Vector<T>operator--(int32_t){Vector<T>v=*this;for(T&e:value)e--;return v;}std::vector<T>stdVector()const{return value;}std::vector<T>&stdVector(){return value;}void out(){for(const T&e:value)std::cout<<e<<'\n';}void iota(){for(int i=0;i<size();i++)value[i]=i;}Vector<T>iotaed()const{Vector<T>r(*this);r.iota();return r;}
T last()const{return value[size()-1];}T&last(){return value[size()-1];}auto begin(){return value.begin();}auto end(){return value.end();}auto begin()const{return value.begin();}auto end()const{return value.end();}T sum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v+=value[i];return v;}T prod(int l=0,int r=-1)const{T v=T()+1;r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v*=value[i];return v;}T xorsum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v^=value[i];return v;}int argmin()const{return std::min_element(begin(),end())-begin();}int argmax()const{return std::max_element(begin(),end())-begin();}T min()const{return value[argmin()];}T max()const{return value[argmax()];}T dot(const Vector<T>&v)const{T r=T();for(int i=0;i<std::min(size(),v.size());i++)r+=value[i]*v[i];return r;}
void resize(int s,T v=T()){value.resize(s,v);}void assign(int s,const T&v){value.assign(s,v);}void pub(const T&v){value.push_back(v);}void pub(const Vector<T>&v){value.insert(end(),v.begin(),v.end());}void insert(int i,const T&v){value.insert(begin()+i,v);}void insert(int i,const Vector<T>&v){value.insert(begin()+i,v.begin(),v.end());}void pob(){value.pop_back();}void erase(int i,int j=-1){if(j<0)value.erase(begin()+i);else value.erase(begin()+i,begin()+j);}void erase_unique(){value.erase(std::unique(begin(),end()),end());}void reverse(){std::reverse(begin(),end());}void rotatedown(int i){if(i>0)std::rotate(begin(),begin()+i,end());}void rotateup(int i){if(i>0)std::rotate(value.rbegin(),value.rbegin()+i,value.rend());}void sortup(){std::sort(begin(),end());}void sortdown(){std::sort(value.rbegin(),value.rend());}void cumsum(){for(int i=0;i<size()-1;i++)value[i+1]+=value[i];}void sumdiff(){for(int i=size()-2;i>=0;i--)value[i+1]-=value[i];}T cumsumpart(int l,int r)const{return value[r-1]-(l=0?0:value[l-1]);}void cumxorsum(){for(int i=0;i<size()-1;i++)value[i+1]^=value[i];}void xorsumdiff(){for(int i=size()-2;i>=0;i--)value[i+1]^=value[i];}T cumxorsumpart(int l,int r)const{return value[r-1]^(l=0?0:value[l-1]);}
void bucketsortup(){int m=min();Vector<int>b(max()-m+1);for(int e:value)b[e-m]++;b.cumsum();for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)value[j]=m+i;}void bucketsortdown(){bucketsortup();reverse();}void compress(){Vector<T>u(value);u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<size();i++)value[i]=m[value[i]];}void argofsortup(){Vector<std::pair<T,T>>p(size());for(int i=0;i<size();i++)p[i]=std::make_pair(value[i],i);p.sortup();for(int i=0;i<size();i++)value[i]=p[i].second;}void argofsortdown(){Vector<std::pair<T,T>>p(size());for(int i=0;i<size();i++)p[i]=std::make_pair(value[i],i);p.sortdown();for(int i=0;i<size();i++)value[i]=p[i].second;}int findupgeq(const T&v){return std::lower_bound(begin(),end(),v)-begin();}int findupleq(const T&v){return std::upper_bound(begin(),end(),v)-begin()-1;}int upcount(const T&v){return findupleq(v)-findupgeq(v)+1;}int finddowngeq(const T&v){return size()-(std::lower_bound(value.rbegin(),value.rend(),v)-value.rbegin())-1;}int finddownleq(const T&v){return size()-(std::upper_bound(value.rbegin(),value.rend(),v)-value.rbegin());}int downcount(const T&v){return finddowngeq(v)-finddownleq(v)+1;}VecCalc(+)VecCalc(-)VecCalc(*)VecCalc(/)VecCalc(%)VecCalc(<<)VecCalc(>>)VecCalc(&)VecCalc(|)VecCalc(^)VecComp(==)VecComp(!=)VecComp(>=)VecComp(<=)VecComp(>)VecComp(<)
Vector<T>pubed(const T&v)const{Vector<T>r(*this);r.pub(v);return r;}Vector<T>pubed(const Vector<T>&v)const{Vector<T>r(*this);r.pub(v);return r;}Vector<T>inserted(int i,const T&v)const{Vector<T>r(*this);r.insert(i,v);return r;}Vector<T>inserted(int i,const Vector<T>&v)const{Vector<T>r(*this);r.insert(i,v);return r;}Vector<T>pobed()const{Vector<T>r(*this);r.pob();return r;}Vector<T>erased(int i,int j=-1)const{Vector<T>r(*this);r.erase(i,j);return r;}Vector<T>erase_uniqued()const{Vector<T>r(*this);r.erase_unique();return r;}Vector<T>reversed()const{Vector<T>r(*this);r.reverse();return r;}Vector<T>rotatedowned(int i)const{Vector<T>r(*this);r.rotatedown(i);return r;}Vector<T>rotateuped(int i)const{Vector<T>r(*this);r.rotateup(i);return r;}Vector<T>sortuped()const{Vector<T>r(*this);r.sortup();return r;}Vector<T>sortdowned()const{Vector<T>r(*this);r.sortdown();return r;}
Vector<T>cumsumed()const{Vector<T>r(*this);r.cumsum();return r;}Vector<T>sumdiffed()const{Vector<T>r(*this);r.sumdiff();return r;}Vector<T>cumxorsumed()const{Vector<T>r(*this);r.cumxorsum();return r;}Vector<T>xorsumdiffed()const{Vector<T>r(*this);r.xorsumdiff();return r;}Vector<T>bucketsortuped()const{Vector<T>r(*this);r.bucketsortup();return r;}Vector<T>bucketsortdowned()const{Vector<T>r(*this);r.bucketsortdown();return r;}Vector<T>compressed()const{Vector<T>r(*this);r.compress();return r;}Vector<T>argofsortuped()const{Vector<T>r(*this);r.argofsortup();return r;}Vector<T>argofsortdowned()const{Vector<T>r(*this);r.argofsortdown();return r;}};
VVCalc(+)VVCalc(-)VVCalc(*)VVCalc(/)VVCalc(%)VVCalc(<<)VVCalc(>>)VVCalc(&)VVCalc(|)VVCalc(^)VVComp(==)VVComp(!=)VVComp(>=)VVComp(<=)VVComp(>)VVComp(<)template<typename T,typename U>Vector<std::pair<T,U>>unite(const Vector<T>&v,const Vector<U>&u){int s=std::min(v.size(),u.size());Vector<std::pair<T,U>>r(s);for(int i=0;i<s;i++)r[i]=std::make_pair(v[i],u[i]);return r;}template<typename T,typename U>std::pair<Vector<T>,Vector<U>>separate(const Vector<std::pair<T,U>>&p){Vector<T>v(p.size());Vector<U>u(p.size());for(int i=0;i<p.size();i++){v[i]=p[i].first;u[i]=p[i].second;}return std::make_pair(v,u);}template<typename T>std::istream&operator>>(std::istream&i,Vector<T>&v){for(T&e:v)i>>e;return i;}template<typename T>std::ostream&operator<<(std::ostream&o,const Vector<T>&v){if(v.size()==0)return o;for(int i=0;i<v.size()-1;i++)o<<v[i]<<' ';return o<<v.last();}Vector<int>baseVector(int n,int b){Vector<int>v(64);for(int&e:v){e=n%b;n/=b;}return v;}int baseVectorValue(Vector<int>v,int b){int n=0,m=1;for(int&e:v){n+=e*m;m*=b;}return n;}

// Matrix class need Vector class
#define MatCalc(OP) Matrix<T>operator OP(const Matrix<T>&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Matrix<T>operator OP(const Vector<T>&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<T>operator OP(const T&r)const{Matrix<T>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<T>operator OP##=(const Matrix<T>&r){return *this=*this OP r;}Matrix<T>operator OP##=(const Vector<T>&r){return *this=*this OP r;}Matrix<T>operator OP##=(const T&r){return *this=*this OP r;}
#define MatComp(OP) Matrix<int>operator OP(const Matrix<T>&r)const{Matrix<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Matrix<int>operator OP(const Vector<T>&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<int>operator OP(const T&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}
template<typename T>class Matrix{Vector<Vector<T>>value;public:Matrix(int c=0,int r=0,T v=T()){if(c>=0&&r>=0)assign(c,r,v);else{assign(-c,-r,v);for(Vector<T>&e:value)std::cin>>e;}}Matrix(std::pair<int,int>p,T v=T()){if(p.first>=0&&p.second>=0)assign(p.first,p.second,v);else{resize(-p.first,-p.second);for(Vector<T>&e:value)std::cin>>e;}}Matrix(const std::initializer_list<std::initializer_list<T>>&l){value.resize(l.size());for(int i=0;i<size();i++)value[i]=*(l.begin()+i);rect();}template<typename U>Matrix(const Matrix<U>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];}Matrix(const Vector<Vector<T>>&v){value.resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];rect();}Matrix(const std::vector<std::vector<T>>&v){value.resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];rect();}void rect(){Vector<T>v(size());for(int i=0;i<size();i++)v[i]=value[i].size();resize(size(),v.max());}
int size()const{return value.size();}std::pair<int,int>shape()const{return std::make_pair(size(),size()==0?0:value[0].size());}Vector<T>operator[](int i)const{return value[i];}Vector<T>&operator[](int i){return value[i];}T operator[](std::pair<int,int>p)const{return value[p.first][p.second];}T&operator[](std::pair<int,int>p){return value[p.first][p.second];}Matrix<T>operator[](Slice p)const{return value[p];}Matrix<T>operator[](std::pair<Slice,Slice>p)const{p.first.last=(p.first.last<0?p.first.last+shape().first+1:p.first.last);p.second.last=(p.second.last<0?p.second.last+shape().second+1:p.second.last);Matrix<T>v;for(int i=p.first.first;i<p.first.last;i+=p.first.step){Vector<T>u;for(int j=p.second.first;j<p.second.last;j+=p.second.step)u.pub(value[i][j]);v.vstack(u);}return v;}Matrix<T>&operator=(const Matrix<T>&v){value.resize(size());for(int i=0;i<v.size();i++)value[i]=v[i];return *this;}Matrix<T>operator+()const{return *this;}Matrix<T>operator-()const{Matrix<T>v(value.size());for(int i=0;i<size();i++)v[i]=-value[i];return v;}Matrix<T>operator++(){for(Vector<T>&e:value)e++;return *this;}Matrix<T>operator--(){for(Vector<T>&e:value)e--;return *this;}Matrix<T>operator++(int32_t){Matrix<T>v=*this;for(Vector<T>&e:value)e++;return v;}Matrix<T>operator--(int32_t){Matrix<T>v=*this;for(Vector<T>&e:value)e--;return v;}std::vector<std::vector<T>>stdVector(){std::vector<std::vector<T>>v(size());for(int i=0;i<size();i++)v[i]=value[i].stdVector();return v;}void out(){for(const Vector<T>&e:value)std::cout<<e<<'\n';}Vector<Vector<T>>vectorVector(){return value;}Vector<T>last()const{return value[size()-1];}
Vector<T>&last(){return value[size()-1];}Vector<T>vector()const{Vector<T>v;for(const Vector<T>&e:value)v.pub(e);return v;}auto begin(){return value.begin();}auto end(){return value.end();}auto begin()const{return value.begin();}auto end()const{return value.end();}T sum(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T();cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v+=value[i].sum(rl,rr);return v;}T prod(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T()+1;cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v*=value[i].prod(rl,rr);return v;}T xorsum(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T();cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v^=value[i].xorsum(rl,rr);return v;}
std::pair<int,int>argmin()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].min();int m=v.argmin();return std::make_pair(m,value[m].argmin());}std::pair<int,int>argmax()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].max();int m=v.argmax();return std::make_pair(m,value[m].argmax());}T min()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].min();return v.min();}T max()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].max();return v.max();}void dot(Matrix<T>v){Matrix<T>m(value);assign(shape().first,v.shape().second,0);for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)for(int k=0;k<std::min(m.shape().second,v.shape().first);k++)value[i][j]+=m[i][k]*v[k][j];}void resize(int c,Vector<T>v=Vector<T>()){value.resize(c,v);}void resize(int c,int r,T v=T()){resize(c);for(Vector<T>&e:value)e.resize(r,v);}void resize(std::pair<int,int>p,T v=T()){resize(p.first,p.second,v);}void assign(int c,const Vector<T>&v){value.assign(c,v);}void assign(int c,int r,T v){assign(c,Vector<T>(r,v));}void assign(std::pair<int,int>p,const T&v){assign(p.first,p.second,v);}
void vstack(const Vector<T>&v){if(shape().second<v.size()&&size()>0){value.pub(v[{0,shape().second,1}]);}else{value.pub(v);value.last().resize(shape().second);}}void vstack(const Matrix<T>&v){Matrix<T>u(v[{{0,-1,1},{0,std::min(shape().second,v.shape().second),1}}]);for(const Vector<T>&e:u)vstack(e);}void hstack(const Vector<T>&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)value[i].pub(v[i]);resize(shape());}void hstack(const Matrix<T>&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)value[i].pub(v[i]);resize(shape());}void vpob(){value.pob();}void hpob(){for(Vector<T>&e:value)e.pob();}void verase(int i,int j=-1){if(j==-1)value.erase(i);else value.erase(i,j);}void herase(int i,int j=-1){for(Vector<T>&e:value)if(j==-1)e.erase(i);else e.erase(i,j);}void vinsert(int i,const Vector<T>&v){if(shape()==std::make_pair(int(0),int(0)))vstack(v);else value.insert(i,v[{0,shape().second,1}]);}void vinsert(int i,const Matrix<T>&v){if(shape()==std::make_pair(int(0),int(0)))vstack(v);else value.insert(i,v[{{0,-1,1},{0,std::min(shape().second,v.shape().second),1}}].vectorVector());}void hinsert(int i,const Vector<T>&v){if(shape()==std::make_pair(int(0),int(0)))hstack(v);else for(int j=0;j<std::min(size(),v.size());j++)value[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)value[j].insert(i,0);}void hinsert(int i,const Matrix<T>&v){if(shape()==std::make_pair(int(0),int(0)))hstack(v);else for(int j=0;j<std::min(size(),v.size());j++)value[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)value[j].resize(v.shape().second);}
void transpose(){std::pair<int,int>s=shape();if(s.first<s.second)for(int i=0;i<s.second-s.first;i++)value.pub(Vector<T>(s.first));else for(int i=0;i<s.second;i++)value[i].resize(s.first);for(int i=0;i<std::min(s.first,s.second);i++)for(int j=i+1;j<size();j++)std::swap(value[i][j],value[j][i]);resize(s.second,s.first);}void power(int n){Matrix<T>m(*this);assign(size(),size(),0);for(int i=0;i<size();i++)value[i][i]=1;while(n>0){if(n&1)dot(m);m.dot(m);n/=2;}}void cumsum(){value.cumsum();for(Vector<T>&e:value)e.cumsum();}void sumdiff(){value.sumdiff();for(Vector<T>&e:value)e.sumdiff();}T cumsumpart(int cl,int rl,int cr,int rr)const{return value[cr-1][rr-1]-(cl==0?0:value[cl-1][rr-1])-(rl==0?0:value[cr-1][rl-1])+((cl==0||rl==0)?0:value[cl-1][rl-1]);}void cumxorsum(){value.cumxorsum();for(Vector<T>&e:value)e.cumxorsum();}void xorsumdiff(){value.xorsumdiff();for(Vector<T>&e:value)e.xorsumdiff();}T cumxorsumpart(int cl,int rl,int cr,int rr)const{return value[cr-1][rr-1]^(cl==0?0:value[cl-1][rr-1])^(rl==0?0:value[cr-1][rl-1])^((cl==0||rl==0)?0:value[cl-1][rl-1]);}void compress(){Vector<T>u=vector();u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)value[i][j]=m[value[i][j]];}MatCalc(+)MatCalc(-)MatCalc(*)MatCalc(/)MatCalc(%)MatCalc(<<)MatCalc(>>)MatCalc(&)MatCalc(|)MatCalc(^)MatComp(==)MatComp(!=)MatComp(>=)MatComp(<=)MatComp(>)MatComp(<)
Matrix<T>vstacked(const Vector<T>&v)const{Matrix<T>r(*this);r.vstack(v);return r;}Matrix<T>vstacked(const Matrix<T>&v)const{Matrix<T>r(*this);r.vstack(v);return r;}Matrix<T>hstacked(const Vector<T>&v)const{Matrix<T>r(*this);r.hstack(v);return r;}Matrix<T>hstacked(const Matrix<T>&v)const{Matrix<T>r(*this);r.hstack(v);return r;}Matrix<T>vpobed()const{Matrix<T>r(*this);r.vpob();return r;}Matrix<T>hpobed()const{Matrix<T>r(*this);r.hpob();return r;}Matrix<T>verased(int i,int j=-1)const{Matrix<T>r(*this);r.verase(i,j);return r;}Matrix<T>herased(int i,int j=-1)const{Matrix<T>r(*this);r.herase(i,j);return r;}Matrix<T>vinserted(int i,const Vector<T>&v)const{Matrix<T>r(*this);r.vinsert(i,v);return r;}Matrix<T>vinserted(int i,const Matrix<T>&v)const{Matrix<T>r(*this);r.vinsert(i,v);return r;}Matrix<T>hinserted(int i,const Vector<T>&v)const{Matrix<T>r(*this);r.hinsert(i,v);return r;}Matrix<T>hinserted(int i,const Matrix<T>&v)const{Matrix<T>r(*this);r.hinsert(i,v);return r;}Matrix<T>transposed()const{Matrix<T>r(*this);r.transpose();return r;}Matrix<T>powered(int n)const{Matrix<T>r(*this);r.power(n);return r;}Matrix<T>cumsumed()const{Matrix<T>r(*this);r.cumsum();return r;}Matrix<T>sumdiffed()const{Matrix<T>r(*this);r.sumdiff();return r;}Matrix<T>cumxorsumed()const{Matrix<T>r(*this);r.cumxorsum();return r;}Matrix<T>xorsumdiffed()const{Matrix<T>r(*this);r.xorsumdiff();return r;}Matrix<T>compressed()const{Matrix<T>r(*this);r.compress();return r;}};

// String class need Vector class
#define DefOtherType(RTYPE,OP,CONST) RTYPE operator OP(const char*s)CONST{return operator OP(String(s));}RTYPE operator OP(const std::string&s)CONST{return operator OP(String(s));}RTYPE operator OP(char c)CONST{return operator OP(String(c));}
#define StrComp(OP) bool operator OP(const String&s)const{return str OP s.stdString();}DefOtherType(bool,OP,const)
class String{std::string str;public:String(){}String(const char*s):str(s){}String(char s):str(1,s){}String(int i,char c){str=std::string(i,c);}String(int32_t i):str(std::to_string(i)){}String(int64_t i):str(std::to_string(i)){}String(const std::string&s):str(s){}String(const Vector<char>&v){for(char c:v)pub(c);}char operator[](int i)const{return str[i];}char&operator[](int i){return str[i];}String operator[](Slice s)const{s.last=(s.last<0?s.last+size()+1:s.last);String r;for(int i=s.first;i<s.last;i+=s.step)r.pub(str[i]);return r;}void operator--(int32_t){pob();}String&operator=(const String&s){str=s.stdString();return *this;}DefOtherType(String&,=,)String&operator<<(const String&s){pub(s);return *this;}DefOtherType(String&,<<,)String operator+(const String&s)const{String r(*this);r.pub(s);return r;}DefOtherType(String,+,const)String operator+=(const String&s){pub(s);return *this;}DefOtherType(String,+=,)StrComp(==)StrComp(!=)StrComp(>=)StrComp(<=)StrComp(>)StrComp(<)std::string stdString()const{return str;}std::string&stdString(){return str;}char last()const{return str[size()-1];}Vector<char>toVector()const{Vector<char>v;for(char c:str)v.pub(c);return v;}char&last(){return str[size()-1];}auto begin(){return str.begin();}auto end(){return str.end();}auto begin()const{return str.begin();}auto end()const{return str.end();}
int size()const{return str.size();}String substr(int p,int s=-1)const{return operator[]({p,s<0?s:p+s,1});}int32_t toInt(){return std::stoi(str);}int64_t toLong(){return std::stol(str);}Vector<int>find(const String&s)const{Vector<int>v;auto i=str.find(s.stdString());while(i!=std::string::npos){v.pub(i);i=str.find(s.stdString(),i+s.size());}return v;}Vector<int>find_dup(const String&s)const{Vector<int>v;auto i=str.find(s.stdString());while(i!=std::string::npos){v.pub(i);i=str.find(s.stdString(),i+1);}return v;}void resize(int i,char c=0){str.resize(i,c);}void assign(int i,char c){str.assign(i,c);}void pub(const String&s){str+=s.stdString();}void pob(){str.pop_back();}void reverse(){std::reverse(begin(),end());}void insert(int i,const String&s){str.insert(i,s.stdString());}void erase(int i,int j=-1){if(j<0)str.erase(i,1);else str.erase(i,j-i);}void erase_unique(){str.erase(std::unique(begin(),end()),end());}void rotatedown(int i){std::rotate(begin(),begin()+i,end());}void rotateup(int i){std::rotate(str.rbegin(),str.rbegin()+i,str.rend());}void sortup(){int m=*std::min_element(begin(),end());int M=*std::max_element(begin(),end());Vector<char>b(M-m+1);for(char e:str)b[e-m]++;b.cumsum();for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)str[j]=m+i;}void sortdown(){sortup();reverse();}
String reversed()const{String r(*this);r.reverse();return r;}String inserted(int i,const String&s)const{String r(*this);r.insert(i,s);return r;}String erased(int i,int j=-1)const{String r(*this);r.erase(i,j);return r;}String erase_uniqued()const{String r(*this);r.erase_unique();return r;}String rotatedowned(int i)const{String r(*this);r.rotatedown(i);return r;}String rotateuped(int i)const{String r(*this);r.rotateup(i);return r;}String sortuped()const{String r(*this);r.sortup();return r;}String sortdowned()const{String r(*this);r.sortdown();return r;}};std::istream&operator>>(std::istream&i,String&s){i>>s.stdString();return i;}std::ostream&operator<<(std::ostream&o,const String&s){return o<<s.stdString();}

// Modulo class
#define ModCalc(OP) Modulo operator OP(const Modulo&l,const Modulo&r){return Modulo(l.val()OP r.val());}Modulo operator OP(const Modulo&l,const int64_t&r){return Modulo(l.val()OP Modulo(r));}Modulo operator OP(const int64_t&l,const Modulo&r){return Modulo(l)OP r.val();}Modulo operator OP##=(Modulo&l,const Modulo&r){return l=l OP r;}Modulo operator OP##=(Modulo&l,const int64_t&r){return l=l OP r;}int64_t operator OP##=(int64_t&l,const Modulo&r){return l=l OP r.val();}
#define ModComp(OP) bool operator OP(const Modulo&l,const Modulo&r){return l.val()OP r.val();}bool operator OP(const Modulo&l,const int64_t&r){return l.val()OP r;}bool operator OP(const int64_t&l,const Modulo&r){return l OP r.val();}
class Modulo{int64_t value;public:Modulo():value(0){}Modulo(const int64_t&v){value=v;normalize();}void normalize(){value=(value%mod()+mod())%mod();}Modulo(const Modulo&m):value(m.val()){}Modulo inv()const{int64_t a=value;int64_t b=mod(),u=0,v=1;while(a>1){u-=b/a*v;b%=a;std::swap(a,b);std::swap(u,v);}return Modulo(v);}int64_t val()const{return value;}int64_t&val(){return value;}Modulo&operator=(const Modulo&m){value=m.val();return *this;}int64_t mod()const{return MOD;}Modulo&operator=(const int64_t&v){value=v;return *this;}Modulo operator++(){return Modulo(++value);}Modulo operator--(){return Modulo(--value);}Modulo operator++(int32_t){return Modulo(value++);}Modulo operator--(int32_t){return Modulo(value--);}Modulo operator+()const{return *this;}Modulo operator-()const{return Modulo(-value);}Modulo power(int64_t i)const{int64_t x=value;int64_t r=1;while(i>0){if(i&1)r=r*x%mod();x=x*x%mod();i/=2;}return Modulo(r);}};std::ostream&operator<<(std::ostream&o,const Modulo&m){return o<<m.val();}std::istream&operator>>(std::istream&i,Modulo&m){i>>m.val();m.normalize();return i;}ModCalc(+)ModCalc(-)ModCalc(*)ModCalc(<<)ModCalc(>>)ModCalc(&)ModCalc(|)ModCalc(^)ModComp(==)ModComp(!=)ModComp(>=)ModComp(<=)ModComp(>)ModComp(<)Modulo operator/(const Modulo&l,const Modulo&r){return Modulo(l.val()*r.inv());}Modulo operator/(const Modulo&l,const int64_t&r){return Modulo(l.val()*Modulo(r).inv());}Modulo operator/(const int64_t&l,const Modulo&r){return Modulo(Modulo(l)*r.inv());}

// FFT, NNT need Vector Modulo class
std::unordered_map<int,int>MOD_ROOT={{1224736769,3},{1053818881,7},{1051721729,6},{1045430273,3},{1012924417,5},{1007681537,3},{1004535809,3},{998244353,3},{985661441,3},{976224257,3},{975175681,17},{962592769,7},{950009857,7},{943718401,7},{935329793,3},{924844033,5},{469762049,3},{167772161,3}};Vector<std::complex<double>>fft(Vector<std::complex<double>>a,bool inverse=false){int n=a.size(),h=std::log2(n);for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){for(int j=0;j<b;j++){std::complex<double>w=std::polar(1.0,(2*M_PI)/(2*b)*j*(inverse?1:-1));for(int k=0;k<n;k+=b*2){std::complex<double>s=a[j+k],t=a[j+k+b]*w;a[j+k]=s+t;a[j+k+b]=s-t;}}}a/=std::complex<double>(inverse?n:1);return a;}Vector<Modulo>ntt(Vector<Modulo>a,bool inverse=false){int n=a.size(),h=std::log2(n);Modulo root=MOD_ROOT[MOD];for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){Modulo w=root.power((a[0].mod()-1)/(b*2));if(inverse)w=w.inv();for(int j=0;j<n;j+=b*2){Modulo wn=1;for(int k=0;k<b;k++){Modulo s=a[j+k+0],t=a[j+k+b]*wn;a[j+k]=s+t;a[j+k+b]=s-t;wn=wn*w;}}}if(inverse){Modulo v=Modulo(n).inv();a*=v;}return a;}
Vector<double>convolve(Vector<double>a,Vector<double>b){if(a.size()==0||b.size()==0)return Vector<double>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<std::complex<double>>A=fft(a),B=fft(b);A*=B;A=fft(A,true);a.resize(s);for(int i=0;i<s;i++)a[i]=A[i].real();return a;}Vector<int>convolve(Vector<int>a,Vector<int>b){return convolve(Vector<double>(a),Vector<double>(b))+0.5;}Vector<Modulo>convolve(Vector<Modulo>a,Vector<Modulo>b){if(a.size()==0||b.size()==0)return Vector<Modulo>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<Modulo>A=ntt(a),B=ntt(b);A*=B;a=ntt(A,true);a.resize(s);return a;}

// MultipleVector class need Vector, Modulo class
class MultipleVector{Vector<Modulo>vfact,ifact,pows;Modulo p;public:MultipleVector(int n=0,int _p=1):vfact(Vector<Modulo>(1,1)),ifact(Vector<Modulo>(1,1)),pows(Vector<Modulo>(1,1)),p(_p){resize(n);}void resize(int n){if(vfact.size()>=n)return;int s=vfact.size();vfact.resize(n+1);for(int i=s;i<=n;i++)vfact[i]=i*vfact[i-1];ifact.resize(n+1);ifact[n]=vfact[n].inv();for(int i=n;i>s;i--)ifact[i-1]=i*ifact[i];pows.resize(n+1);for(int i=s;i<=n;i++)pows[i]=p*pows[i-1];}Modulo fact(Modulo n){resize(n.val());return vfact[n.val()];}Vector<Modulo>facts(Modulo n){resize(n.val());return vfact[{0,n.val(),1}];}Modulo factinv(Modulo n){resize(n.val());return ifact[n.val()];}Vector<Modulo>factinvs(Modulo n){resize(n.val());return ifact[{0,n.val(),1}];}Modulo power(Modulo n){resize(n.val());return pows[n.val()];}Vector<Modulo>powers(Modulo n){resize(n.val());return pows[{0,n.val(),1}];}Modulo parm(Modulo n,Modulo r){if(n<r)return Modulo();resize(n.val());return vfact[n.val()]*ifact[(n-r).val()];}Modulo comb(Modulo n,Modulo r){if(n<r)return Modulo();resize(n.val());return vfact[n.val()]*ifact[(n-r).val()]*ifact[r.val()];}Modulo homo(Modulo n,Modulo r){return comb(n+r-1,r);}};

// Eratos class need Vector class
class Eratos{Vector<int>divs,prms,ords;int order_max;public:Eratos(int n=0):order_max(0){resize(n);}int size()const{return divs.size();}void resize(int n){if(size()>=n)return;int m=size();divs.resize(n+1);for(int i=m;i<2;i++)if(i<size())divs[i]=-1;int r=std::sqrt(n-1)+1;for(int i=2;i<r;i++)if(divs[i]==0)for(int j=std::max((m-1)/i+1,(int)2)*i;j<=n;j+=i)divs[j]=(divs[j]==0?i:divs[j]);for(int i=m;i<=n;i++)if(divs[i]==0)prms.pub(i);ords.resize(n+1);for(int i=m;i<=n;i++)ords[i]=(divs[i]==0?++order_max:0);}Vector<int>divisors()const{return divs;}Vector<int>primes()const{return prms;}Vector<int>orders()const{return ords;}};

// Unionfind class need Vector class
template<typename T>class Unionfind{Vector<int>p;Vector<T>w;int sign(int x){return(x>0)-(x<0);}int get(int x){if(p[x]==(x+1))return x+1;else{int parent=sign(p[x])*get(abs(p[x])-1);w[x]+=w[abs(p[x])-1];return p[x]=parent;}}void get(int&x,int&y){x=get(x);y=get(y);}int weight(int x){get(x);return w[x];}public:Unionfind(int n=0){resize(n);}void resize(const int&n){p.resize(n);for(int i=w.size();i<p.size();i++)p[i]=i+1;w.resize(n);}int size()const{return p.size();}bool unite(int x,int y,T vv=T()){if(vv<0){std::swap(x,y);vv*=-1;}vv+=weight(x)-weight(y);get(x,y);if(abs(x)==abs(y))return vv==weight(x)-weight(y);p[abs(y)-1]=x*sign(y);w[abs(y)-1]=vv;return true;}bool separate(int x,int y,T vv=T()){if(vv<0){std::swap(x,y);vv*=-1;}vv+=weight(x)-weight(y);get(x,y);if(abs(x)==abs(y))return vv==weight(x)-weight(y);p[abs(y)-1]=-x*sign(y);w[abs(y)-1]=vv;return true;}int same(int x,int y){get(x,y);return (x==y)-(x==-y);}Vector<int>same(int x){Vector<int>v(size());for(int i=0;i<size();i++)v[i]=same(x,i);return v;}T diff(int x,int y){return sign(same(x,y))*(weight(y)-weight(x));}Vector<T>diff(int x){Vector<int>v(size());for(int i=0;i<size();i++)v[i]=diff(x,i);return v;}};

// Graph class need Vector class
template<typename T>struct Edge{int from,to;T cost;Edge(int f=0,int t=0,T c=T()):from(f),to(t),cost(c){}};template<typename T>std::istream&operator>>(std::istream&i,Edge<T>&e){i>>e.from>>e.to>>e.cost;return i;}template<typename T>std::ostream&operator<<(std::ostream&o,const Edge<T>&e){return o<<e.from<<' '<<e.to<<' '<<e.cost;}template<typename T>class Graph{public:Vector<Edge<T>>edge;Vector<Vector<int>>node;Graph(int n=0){resize(n);}void resize(int n){node.resize(n);}void clear(){edge=Vector<Edge<T>>();node=Vector<Vector<int>>(nodes());}int edges()const{return edge.size();}int nodes()const{return node.size();}virtual int add(int from,int to,T cost)=0;Vector<T>dijkstra(int start){Vector<T>d(nodes(),std::numeric_limits<T>::max());std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<std::pair<T,int>>>s;d[start]=0;s.emplace(d[start],start);while(!s.empty()){T dist=s.top().first;int from=s.top().second;s.pop();if(d[from]<dist)continue;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[from]+edge[id].cost<d[to]){d[to]=d[from]+edge[id].cost;s.emplace(d[to],to);}}}return d;}};


// Undigraph class need Vector, Graph class
template<typename T>class Undigraph:public Graph<T>{Vector<int>brgs,crus,lows,ords;bool lowlinked;int lowlink_dfs(int from,int k,int parent){ords[from]=lows[from]=k++;bool is_crunode=false;int cnt=0;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(ords[to]==-1){cnt++;k=lowlink_dfs(to,k,from);lows[from]=std::min(lows[from],lows[to]);is_crunode|=parent!=-1&&lows[to]>=ords[from];if(ords[from]<lows[to])brgs.pub(id);}else if(to!=parent)lows[from]=std::min(lows[from],lows[to]);}is_crunode|=parent==-1&&cnt>1;if(is_crunode)crus.pub(from);return k;}void lowlink(){brgs=Vector<int>();crus=Vector<int>();ords.assign(this->nodes(),-1),lows.assign(this->nodes(),-1);int k=0;for(int i=0;i<this->nodes();i++)if(ords[i]==-1)k=lowlink_dfs(i,k,-1);lowlinked=true;}public:using Graph<T>::edge;using Graph<T>::node;Undigraph(int n=0):Graph<T>(n){lowlinked=false;}int add(int from,int to,T cost=1){int id=this->edges();node[from].pub(id);node[to].pub(id);edge.pub(Edge<T>(from,to,cost));return id;}void reset_lowlink(){lowlink();}Vector<int>bridges(){if(!lowlinked)lowlink();return brgs;}Vector<int>crunodes(){if(!lowlinked)lowlink();return crus;}
T prim(int start=0){Vector<std::pair<T,std::pair<int,int>>>cft;T total = 0;Vector<int>used(this->nodes(),0);std::priority_queue<std::pair<T,std::pair<int,int>>,std::vector<std::pair<T,std::pair<int,int>>>,std::greater<std::pair<T,std::pair<int,int>>>>s;s.emplace(std::make_pair(0,std::make_pair(-1,start)));while(!s.empty()){T cost=s.top().first;int fromfrom=s.top().second.first,from=s.top().second.second;s.pop();if(used[from])continue;used[from]=true;total+=cost;if(fromfrom>-1)cft.pub(std::make_pair(cost,std::make_pair(fromfrom,from)));for(int id:node[from]){int to=edge[id].from^edge[id].to^from;s.emplace(std::make_pair(edge[id].cost,std::make_pair(from,to)));}}this->clear();for(std::pair<T,std::pair<int,int>>e:cft)add(e.second.first,e.second.second,e.first);return total;}};

// Forest class need Vector, Graph, Undigraph class
template<typename T>class Forest:public Undigraph<T>{public:Vector<int>root,parent,treesize,depth;Vector<T>dist;Vector<Vector<int>>children;using Undigraph<T>::edge;using Undigraph<T>::node;using Undigraph<T>::resize;using Undigraph<T>::edges;using Undigraph<T>::nodes;Forest(int n=0):Undigraph<T>(n){initialize();}void initialize(){root.assign(nodes(),-1);parent.assign(nodes(),-1);treesize.assign(nodes(),1);depth.assign(nodes(),0);dist.assign(nodes(),0);children.assign(nodes(),Vector<int>());}private:void dfs(int from){for(int&id:node[from]){if(from==edge[id].from)std::swap(edge[id].from,edge[id].to);int to=edge[id].from;if(root[to]!=-1)continue;root[to]=root[from];parent[to]=from;depth[to]=depth[from]+1;dist[to]=dist[from]+edge[id].cost;children[from].pub(to);dfs(to);treesize[from]+=treesize[to];}}public:void setTreeRoot(int n){initialize();root[n]=n;dfs(n);}void setForestRoot(){initialize();for(int n=0;n<nodes();n++)if(root[n]==-1){root[n]=n;dfs(n);};}T diameter(int n=0){setTreeRoot(n);int terminal=dist.argmax();setTreeRoot(terminal);return dist.max();}};


// Digraph class need Vector, Graph class
template<typename T>class Digraph:public Graph<T>{Vector<Vector<int>>rev_node;Vector<Edge<T>>rev_edge;Vector<int>strong_edgeid,weak_edgeid,strong_id,ords;bool scced;void scc_dfs(int from){if(strong_id[from]==-1)return;strong_id[from]=-1;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;scc_dfs(to);}ords.pub(from);}void scc_rdfs(int from,int cnt){if(strong_id[from]!=-1)return;strong_id[from]=cnt;for(int id:rev_node[from]){int to=rev_edge[id].from^rev_edge[id].to^from;if(strong_id[to]==-1){strong_edgeid.pub(id);scc_rdfs(to,cnt);}else if(strong_id[to]==cnt)strong_edgeid.pub(id);else if(strong_id[to]<cnt)weak_edgeid.pub(id);}}public:using Graph<T>::edge;using Graph<T>::node;Digraph(int n=0):Graph<T>(n),scced(false){}int add(int from,int to,T cost=1){int id=this->edges();node[from].pub(id);edge.pub(Edge<T>(from,to,cost));return id;}Digraph<T>reversed()const{Digraph<T>r(this->edges());for(Edge<T>e:edge)r.add(e.to,e.from,e.cost);return r;}
void scc(){strong_edgeid=Vector<int>();weak_edgeid=Vector<int>();strong_id.assign(this->nodes(),0);ords=Vector<int>(this->nodes());rev_node=Vector<Vector<int>>(this->nodes());rev_edge=Vector<Edge<T>>(this->edges());for(int id=0;id<this->edges();id++){rev_node[edge[id].to].pub(id);rev_edge[id]=Edge<T>(edge[id].to,edge[id].from,edge[id].cost);}for(int from=0;from<this->nodes();from++)scc_dfs(from);ords.reverse();int cnt=0;for(int from:ords)if(strong_id[from]==-1){scc_rdfs(from,cnt);cnt++;}Vector<Edge<T>>strong_edge;for(int id:strong_edgeid)strong_edge.pub(edge[id]);this->clear();for(Edge<T>e:strong_edge)add(e.from,e.to,e.cost);scced=true;}Vector<int>weakid(){if(!scced)scc();return weak_edgeid;};Vector<int>stronggroup(){if(!scced)scc();return strong_id;}
Vector<T>bellman(int start){Vector<T>d(this->nodes(),std::numeric_limits<T>::max());d[start]=0;bool negloop=false;Vector<int>updating(1,start);for(int i=0;i<this->nodes()&&updating.size()>0;i++){Vector<int>toUpdate;for(int from:updating){for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[to]>d[from]+edge[id].cost){d[to]=d[from]+edge[id].cost;toUpdate.pub(to);if(i==this->nodes()-1)d[to]=std::numeric_limits<T>::min();negloop=true;}}}updating=toUpdate;}if(negloop){for(int i=0;i<this->nodes()&&updating.size()>0;i++){Vector<int>toUpdate;for(int from:updating){for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[to]!=std::numeric_limits<T>::min()){d[to]=std::numeric_limits<T>::min();toUpdate.pub(to);}}}updating=toUpdate;}}return d;}Vector<int>topsort(){Vector<int>to_node(this->nodes(),0);for(Edge<T>e:edge)to_node[e.to]++;Vector<int>sorted;for(int i=0;i<this->nodes();i++)if(to_node[i]==0)sorted.pub(i);for(int i=0;i<sorted.size();i++)for(int id:node[sorted[i]]){if(--to_node[edge[id].to]==0)sorted.pub(edge[id].to);}if(sorted.size()!=this->nodes())return Vector<int>();return sorted;}};


// math function for Vector, Matrix, Modulo class
template<typename T>T sign(const T&x){return(x>0)-(x<0);}template<typename T>T abs(const T&x){return x*sign(x);}template<typename T>T power(T x,int y){T r=x*0+1;while(y>0){if(y&1)r*=x;x*=x;y/=2;}return r;}bool is_power(int n,int m){return n==power(llround(std::pow(n,(double)+1/m)),m);}int _gcd(const int&a,const int&b){return b?_gcd(b,a%b):a;}int gcd(const int&a,const int&b){return _gcd(std::max(a,b),std::min(a,b));}int lcm(const int&a,const int&b){return a/gcd(a,b)*b;}bool is_prime(int n){int m=std::sqrt(n-1)+1;for(int i=2;i<m+1;i++)if(n%i==0)return false;return n>1;}
int fact(int n){int v=1;for(int i=1;i<n+1;i++)v*=i;return v;}Modulo fact(Modulo n){Modulo v=1;for(int i=1;i<n+1;i++)v*=i;return v;}int parm(int n,int r){int v=1;for(int i=n-r+1;i<n+1;i++)v*=i;return v;}Modulo parm(Modulo n,Modulo r){Modulo v=1;for(int i=n.val()-r.val()+1;i<n.val()+1;i++)v*=i;return v;}int comb(int n,int r){int v=1;r=std::min(r,n-r);for(int i=0;i<r;i++){v*=n-i;v/=i+1;}return v;}Modulo comb(Modulo n,Modulo r){Modulo p=1,q=1;r=std::min(r,n-r);for(int i=0;i<r;i++){p*=n-i;q*=i+1;}return p/q;}int homo(int m,int n){return comb(m+n-1,n);}Modulo homo(Modulo m,Modulo n){return comb(m+n-1,n);}

// ex. function_find(fname,0,1024,'u',100,output)
#define function_find(FUNCTION_INT_TO_VALUE,INT_RANGE_MIN,INT_RANGE_MAX,CHAR_KIND,VALUE_TARGET,INT_AND_OUTPUT) {int left=INT_RANGE_MIN-1;int right=INT_RANGE_MAX+1;bool outleft=(CHAR_KIND=='d'||CHAR_KIND=='U');int getmin=(CHAR_KIND=='u'||CHAR_KIND=='d')?1:-1;while(right-left>1){int mid=left+(right-left)/2;bool OK=FUNCTION_INT_TO_VALUE(mid)*getmin>=VALUE_TARGET*getmin;if(outleft==OK)left=mid;else right=mid;}INT_AND_OUTPUT=outleft?left:right;}


// BinaryIndexedTree class need Vector class
#define BITCalc(OP) BinaryIndexedTree<T>operator OP##=(const T&v){if(range.first+1==range.second)for(int i=range.first;i<size();i|=(i+1))t1[i]OP##=v;else for(int i=range.first;i<size();i|=(i+1)){t1[i]OP##=-v*(range.first-1);t2[i]OP##=v;}for(int i=range.second;i<size();i|=(i+1)){t1[i]OP##=v*(range.second-1);t2[i]OP##=-v;}return *this;}
template<typename T>class BinaryIndexedTree{Vector<T>t1,t2;std::pair<int,int>range;public:T sum(int x){T v=T();for(int i=x;i>=0;i=(i&(i+1))-1){v+=t1[i]+t2[i]*x;}return v;}T sum(int l,int r){return sum(r-1)-sum(l-1);}T get(int x){return sum(x,x+1);}void resize(int n){t1.resize(n);t2.resize(n);}int size()const{return t1.size();}Vector<T>firstVector()const{return t1;}Vector<T>secondVector()const{return t2;}BinaryIndexedTree(int n=0):range(std::make_pair(0,0)){resize(n);}BinaryIndexedTree(const BinaryIndexedTree&bit):t1(bit.firstVector()),t2(bit.secondVector()),range(std::make_pair(0,-1)){resize(bit.size());}BinaryIndexedTree<T>&operator=(const BinaryIndexedTree<T>&bit){resize(bit.size());t1=bit.firstVector();t2=bit.secondVector();return *this;}T operator[](int i)const{return get(i);}BinaryIndexedTree<T>&operator[](std::initializer_list<int>l){if(l.size()==1){range.first=*l.begin();range.second=(*l.begin())+1;}if(l.size()==2){range.first=*l.begin();range.second=(*(l.begin()+1)<0?*(l.begin()+1)+size()+1:*(l.begin()+1));}return *this;}BITCalc(+)BITCalc(-)T sum(){return sum(range.first,range.second);}BinaryIndexedTree<T>operator=(const T&v){for(int i=range.first;i<range.second;i++){operator[]({i});operator+=(-get(i)+v);}return *this;}Vector<T>toVector(){Vector<T>v(size());for(int i=0;i<size();i++)v[i]=get(i);return v;}};



class Input{public:
  template<typename T>void input_integer(T&var){
      var=0;T sign=1;
      int c=getchar_unlocked();
      while(!(('0'<=c&&c<='9')||c=='-'))c=getchar_unlocked();
      if(c=='-'){sign=-1;c=getchar_unlocked();}
      while('0'<=c&&c<='9'){var=var*10+c-'0';c=getchar_unlocked();}
      var*=sign;
  }
  Input&operator>>(int32_t&var){input_integer<int32_t>(var);return *this;}
  Input&operator>>(int64_t&var){input_integer<int64_t>(var);return *this;}
  Input&operator>>(std::string& var){
    int c = getchar_unlocked();
    while(!(0x21<=c&&c<=0x7E))c=getchar_unlocked();
    while(0x21<=c&&c<=0x7E){var.push_back(c);c=getchar_unlocked();}
    return *this;
  }
};
Input input;



// BIT^2, graph
// argofsortup
// 10^5 -> NlogN, 3000 -> N^2, 200 -> N^3, 50 -> N^4, 20 -> 2^N 
WRITE_FUNCTION_UNDER_HERE




int32_t main(){INIT;
  in(int,n,m);
  VPII py(-m);

  VI order(m);
  order.iota();

  order=separate((unite(py,order)).sortuped()).se;
  py.sortup();

  py[0].se=1;
  fou(i,1,py.size()){
    if(py[i].fi==py[i-1].fi){
      py[i].se=py[i-1].se+1;
    }else{
      py[i].se=1;
    }
  }
  py=separate((unite(order,py)).sortuped()).se;

  fou(i,0,py.size()){
    String pref=py[i].fi;
    while(pref.size()<6)pref.insert(0,'0');
    String year=py[i].se;
    while(year.size()<6)year.insert(0,'0');
    out(pref+year);
  }

}

Measured memory_bytes: 12032