#include<cstdio>
#include<cstdlib>
#include<utility>
/**
 * 匿名的namespace一般是define
 * Base_Tools是常用板子
 * Math_Tools是偏数学的板子
 * IO是读写优化
 * Graph_Tools是图论工具，目前只有图的链式前向星形式（而且是指针的捏）（常数极大，不建议使用）
 * rel_ops其实跟标准库的基本一个用法，但是模板参传了俩
 * 现在这份缺省源已经接近20kb了……
 * （慢得要死）
*/
namespace QL{
	namespace{
#ifndef _GLIBCXX_CMATH
	#define sqrt __builtin_sqrt
	#define sqrtf __builtin_sqrtf
	#define sqrtl __builtin_sqrtl
	#define ceil __builtin_ceil
	#define ceilf __builtin_ceilf
	#define ceill __builtin_ceill
	#define floor __builtin_floor
	#define floorf __builtin_floorf
	#define floorl __builtin_floorl
#endif
#ifndef _GLIBCXX_CSTRING
	#define memset __builtin_memset
	#define memcpy __builtin_memcpy
	#define strlen __builtin_strlen
	#define strcmp __builtin_strcmp
#endif
	}
	namespace Base_Tools{
#if _GLIBCXX_NUMERIC&&__cplusplus>=201703L
		template<typename _Tp>
		constexpr _Tp Inf=std::numeric_limits<_Tp>::max()/2;
#else
		constexpr int Inf=0x3f3f3f3f;
		constexpr long long llInf=0x3f3f3f3f3f3f3f3f;
		constexpr double dbInf=1e17;
#endif
		using ll=long long;
		using ull=unsigned long long;
		using ui=unsigned int;
#if _GLIBCXX_USE_INT128
		using lll=__int128;
		using ulll=unsigned __int128;
#else
		using lll=long long;
		using ulll=unsigned long long;
#endif
		template<typename _Tp1,typename _Tp2>
		auto min(const _Tp1 &x,const _Tp2 &y){
			return x<y?x:y;
		}
		template<typename _Tp,typename ...Args>
		auto min(const _Tp &x,const Args &...args){
			return min(x,min(args...));
		}
		template<typename _Tp1,typename _Tp2>
		auto max(const _Tp1 &x,const _Tp2 &y){
			return y<x?x:y;
		}
		template<typename _Tp,typename ...Args>
		auto max(const _Tp &x,const Args &...args){
			return max(x,max(args...));
		}
		template<typename _Tp1,typename _Tp2>
		bool chkmin(_Tp1 &x,const _Tp2 &y){
			return y<x?(x=y,true):false;
		}
		template<typename _Tp1,typename _Tp2,typename...Args>
		bool chkmin(_Tp1 &x,const _Tp2 &y,const Args &...args){
			return chkmin(x,y)|chkmin(x,args...);
		}
		template<typename _Tp1,typename _Tp2>
		bool chkmax(_Tp1 &x,const _Tp2 &y){
			return x<y?(x=y,true):false;
		}
		template<typename _Tp1,typename _Tp2,typename...Args>
		bool chkmax(_Tp1 &x,const _Tp2 &y,const Args &...args){
			return chkmax(x,y)|chkmax(x,args...);
		}
		template<typename _Tp>
		void swap(_Tp &x,_Tp &y){
			static _Tp tmp;
			tmp=x,x=y,y=tmp;
		}
		template<>
		void swap(int &x,int &y){
			x!=y&&(x^=y^=x^=y);
		}
		template<typename _Tp1,typename _Tp2=_Tp1>
		int digit_length(_Tp1 x,_Tp2 p=10){
			int ret=0;
			while(x>0) x/=p,++ret;
			return ret;
		}
		template<typename _Tp>
		const _Tp abs(const _Tp&x){
			return x<0?-x:x;
		}
	}
	/*
	gcd和lcm会把非整数的gcd当作1
	frac未经正经测试，慎用
	exgcd和excrt还不能过excrt的板子题（但能过crt的……）慎用
	Math_Tools_Base是实现，有些地方接口改了一下，就多套了一层
	*/
	namespace Math_Tools{
		namespace Math_Tools_base{
			template<typename _Tp,typename _Used>
			_Tp qpow(Base_Tools::ll x,_Used p,_Tp mod){
				_Tp ret=1;
				for(;p;p>>=1,x=x*x%mod) if(p&1) ret=ret*x%mod;
				return ret;
			}
		}
		template<typename _Tp,typename _Used>
		_Tp qpow(_Tp x,_Used p,_Tp mod){
			return Math_Tools_base::qpow(x,p,mod);
		}
		template<typename _Tp>
		_Tp inv(_Tp x,_Tp mod){
			return Math_Tools_base::qpow(x,mod-2,mod);
		}
		namespace Math_Tools_base{
			template<typename _Tp>
			int calc_phi(_Tp x){
				_Tp ret=x;
				for(Base_Tools::ll i=2;i*i<=x;++i){
					if(x%i==0){
						while(x%i==0) x/=i;
						ret=ret/i*(i-1);
					}
				}
				if(x!=1) ret=ret/x*(x-1);
				return ret;
			}
		}
		template<typename _Tp>
		int calc_phi(_Tp x){
			return Math_Tools_base::calc_phi(x);
		}
		template<typename _Tp>
		const _Tp gcd(const _Tp &a,const _Tp &b){
			return b?gcd(b,a%b):a;
		}
#define __gcd__(_Tp) \
		template<> \
		const _Tp gcd(const _Tp &a,const _Tp &b){ \
			return 1; \
		}
		__gcd__(double)
		__gcd__(float)
		__gcd__(long double)
#undef __gcd__
		template<typename _Tp>
		const _Tp lcm(const _Tp &a,const _Tp &b){
			return a/gcd(a,b)*b;
		}
		/**
		 * 本实现的亮点是支持不定模数（不用遍历地进行初始化）
		 * 需要实现一个类，重载const类型的()运算符返回模数
		 * 实现可参考QL::ModNumber::Moder
		 * 模数有问题可以重载inv
		 * 其他的不知道了，似乎不是很快，要卡常的可以套约减器
		 * （用这玩意儿也就图个方便）
		 * upd：塞进去了个barrett约减，更慢了（乐
		 * 跑不过编译器优化，它是蒙哥马利吗……
		 */
		namespace ModNumber{
			using QL::Base_Tools::ll;
			using QL::Base_Tools::ulll;
			template<typename _Tp>
			struct Barrett{
				_Tp mod;
				ulll used;
				Barrett(){}
				Barrett(_Tp _mod):mod{_mod},used{(ulll(1)<<63)/mod}{}
				_Tp calc(ll x){
					return (x=x-mod*((x*used)>>63))<mod?x:x-mod;
				}
			};
			template<typename _Tp>
			struct Moder{
				template<typename _Tp_>
				void chk_val(_Tp_ &val)const{
					val<0?(val+=getmod()):(val<getmod()?0:val-=getmod());
				}
				virtual const _Tp getmod(void)const{
					return _Tp(998244353);
				}
				virtual const _Tp operator()(void)const{
					return getmod();
				}
				virtual const _Tp calc(ll x)const{
					return x%getmod();
				}
				template<typename _Tp1,typename _Tp2>
				_Tp plus(const _Tp1 &x,const _Tp2 &y)const{
					return calc(x+y);
				}
				template<typename _Tp1,typename _Tp2>
				_Tp mul(const _Tp1 &x,const _Tp2 &y)const{
					return calc(ll(x)*y);
				}
				_Tp qpow(ll a,int x)const{
					_Tp ret=1;
					for(;x;x>>=1,a=calc(a*a)) if(x&1) ret=calc(ret*a);
					return ret;
				}
				template<typename _Tp_>
				_Tp inv(const _Tp_ &x)const{
					return qpow(x,getmod()-2);
				}
			};
			template<typename _Moder>
			class modInt{
			protected:
				static _Moder mod;
				int v;
			public:
				modInt():v{}{}
				template<typename _Tp_>
				modInt(const _Tp_ &_v):v(_v%mod()){mod.chk_val(v);}
				template<typename _Tp_>
				explicit operator _Tp_()const{
					return _Tp_(v);
				}
				modInt operator-()const{
					return modInt(mod()-v);
				}
				modInt operator+(const modInt &y)const{
					return mod.plus(v,y.v);
				}
				modInt operator-(const modInt &y)const{
					return *this+(-y);
				}
				modInt operator*(const modInt &y)const{
					return mod.mul(v,y.v);
				}
				modInt operator/(const modInt &y)const{
					return mod.mul(v,mod.inv(y.v));
				}
				template<typename _Tp_>
				modInt operator^(const modInt<_Tp_> &y)const{
					return mod.qpow(v,int(y));
				}
				template<typename _Tp_>
				friend modInt operator+(const _Tp_ &x,const modInt &y){
					return mod.plus(x,y.v);
				}
				template<typename _Tp_>
				friend modInt operator+(const modInt &x,const _Tp_ &y){
					return mod.plus(x.v,y);
				}
				template<typename _Tp_>
				friend modInt operator-(const _Tp_ &x,const modInt &y){
					return x+(-y);
				}
				template<typename _Tp_>
				friend modInt operator-(const modInt &x,const _Tp_ &y){
					return x+(-y);
				}
				template<typename _Tp_>
				friend modInt operator*(const _Tp_ &x,const modInt &y){
					return mod.mul(x,y.v);
				}
				template<typename _Tp_>
				friend modInt operator*(const modInt &x,const _Tp_ &y){
					return mod.mul(x.v,y);
				}
				template<typename _Tp_>
				friend modInt operator/(const _Tp_ &x,const modInt &y){
					return mod.mul(x,mod.inv(y.v));
				}
				template<typename _Tp_>
				friend modInt operator/(const modInt &x,const _Tp_ &y){
					return mod.mul(x.v,mod.inv(y));
				}
				template<typename _Tp_>
				friend modInt operator^(const modInt &x,const _Tp_ &y){
					return mod.qpow(x.v,y);
				}
				template<typename _Tp_>
				friend bool operator<(const _Tp_ &x,const modInt &y){
					return x<y.v;
				}
				template<typename _Tp_>
				bool operator<(const _Tp_ &y)const{
					return v<y;
				}
				template<typename _Tp_>
				friend bool operator==(const _Tp_ &x,const modInt &y){
					return x==y.v;
				}
				template<typename _Tp_>
				bool operator==(const _Tp_ &y)const{
					return v==y;
				}
				modInt &operator++(){
					mod.chk_val(++v);
					return *this;
				}
				modInt operator++(int){
					modInt ret=*this;
					mod.chk_val(++v);
					return ret;
				}
				modInt &operator--(){
					mod.chk_val(--v);
					return *this;
				}
				modInt operator--(int){
					modInt ret=*this;
					mod.chk_val(--v);
					return ret;
				}
			};
			template<typename _Moder>
			_Moder modInt<_Moder>::mod;
		}
		namespace Math_Tools_base{
#ifdef _GLIBCXX_TUPLE
		template<typename _Tp>
		_Tp exgcd(long long a,long long b,_Tp &x,_Tp &y){
			long long x1=1,x2=0,x3=0,x4=1;
			while(b){
				long long c=a/b;
				std::tie(x1,x2,x3,x4,a,b)=std::make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
			}
			x=x1,y=x2;
			return a;
		}
#else
			template<typename _Tp>
			_Tp exgcd(const long long &a,const long long &b,_Tp &x,_Tp &y){
				if(!b){
					x=1,y=0;
					return a;
				}
				_Tp _gcd_=exgcd(b,a%b,y,x);
				y-=a/b*x;
				return _gcd_;
			}
#endif
		}
		template<typename _Tp>
		_Tp exgcd(const _Tp &a,const _Tp &b,_Tp &x,_Tp &y){
			return Math_Tools_base::exgcd(a,b,x,y);
		}
		namespace Math_Tools_base{
			template<typename _Tp_ptr>
			auto excrt(_Tp_ptr a,_Tp_ptr m,int st,int ed){
				long long A=a[ed],M=m[ed];
				for(int i=st;i<ed;++i){
					auto p=A,q=A,t=a[i]-A;
					long long _gcd_=exgcd(M,m[i],p,q),pos=m[i]/_gcd_;
					if(t%_gcd_!=0) return A=-114514;
					A+=((p/_gcd_*t%pos+pos)%pos)*M,M*=pos,A=(A%M+M)%M;
				}
				return (A=(A%M+M)%M)==0?M:A;
			}
		}
		template<typename _Tp_ptr>
		auto excrt(_Tp_ptr a,_Tp_ptr m,int st,int ed){
			return Math_Tools_base::excrt(a,m,st,ed);
		}
	}
	namespace Graph_Tools{
		/**
		 * 后面会重写
		*/
		class Graph{
		public:
			struct edge{
				int ver;
				edge*nxt,*rev;
				edge():ver{},nxt{nullptr},rev{nullptr}{}
				edge(int _ver,edge*_nxt,edge*_rev):ver{_ver},nxt{_nxt},rev{_rev}{}
				~edge(){
					if(nxt) nxt->~edge();
				}
			};
		protected:
			int node;
			edge *head;
			edge *pools,*pool_pos;
			edge *get_new_edge(void){
				if(pool_pos==pools) pool_pos=(pools=new edge[node])+node-1;
				return pool_pos--;
			}
		public:
			void link(int u,int v){
				if(u<1||node<u||v<1||node<v) return;
				edge *p=get_new_edge();
				edge *q=get_new_edge();
				*p=edge(v,head[u].nxt,q);
				*q=edge(u,head[v].nxt,p);
				head[u].nxt=p;
				head[v].nxt=q;
			}
			edge*operator[](int x){
				return x<1||node<x?nullptr:head[x].nxt;
			}
			Graph():head{nullptr}{}
			Graph(int n):head{new edge[(node=n)+1]{}}{}
			void clear(){this->~Graph();}
			void resize(int n){
				clear();
				head=new edge[(node=n)+1]{};
			}
			~Graph(){
				delete[] head;
				delete[] pools;
			}
		};
	}
	/**
	 * 多项式，占坑
	 * 以后会尽量补全的
	 */
	namespace Poly_Tools{
		/**
		 * 暴力乘法
		 */
		template<typename _Tp>
		class Poly{
		protected:
			_Tp *p;
			int n;
		public:
			int length(void)const{return n;}
			Poly():p{},n{}{}
			Poly(const int &_n):p{new _Tp[(n=_n)+1]{}}{}
			Poly(const std::initializer_list<_Tp> &L){
				p=new _Tp[L.size()+1];
				n=-1;
				for(auto it:L) p[++n]=it;
			}
			Poly(const Poly &it):n{it.n}{
				for(int i=0;i<=n;++i) p[i]=it[i];
			}
			_Tp &operator[](const int &x){
				if(x<0||x>n) std::exit(114514);
				return p[x];
			}
			const _Tp &operator[](const int &x)const{
				if(x<0||x>n) std::exit(114514);
				return p[x];
			}
			Poly operator*(const Poly &it)const{
				Poly ret(n+it.n);
				for(int i=0;i<=n;++i)
					for(int j=0;j<=it.n;++j)
						ret[i+j]=ret[i+j]+p[i]*it[j];
				return ret;
			}
		};
	}
	namespace rel_ops{
		namespace Calc{
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator+=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs+rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator-=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs-rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator*=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs*rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator/=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs/rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator%=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs%rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator&=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs&rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator|=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs|rhs);
			}
			template<typename _Tp1,typename _Tp2>
			_Tp1 operator^=(_Tp1 &lhs,const _Tp2 &rhs){
				return lhs=(lhs^rhs);
			}
		}
		namespace Compare{
			template<typename _Tp1,typename _Tp2>
			bool operator!=(const _Tp1 &lhs,const _Tp2 &rhs){
				return !(lhs==rhs);
			}
			template<typename _Tp1,typename _Tp2>
			bool operator<=(const _Tp1 &lhs,const _Tp2 &rhs){
				return (lhs==rhs)||(lhs<rhs);
			}
			template<typename _Tp1,typename _Tp2>
			bool operator>(const _Tp1 &lhs,const _Tp2 &rhs){
				return !((lhs==rhs)||(lhs<rhs));
			}
			template<typename _Tp1,typename _Tp2>
			bool operator>=(const _Tp1 &lhs,const _Tp2 &rhs){
				return !(lhs<rhs);
			}
		}
	}
	/**
	 * 字符串的工具
	 * 主要是各种算法（KMP，SA，ACAM……都在考虑内）
	 * 计划是算法类C风格参数
	 */
	namespace String_Tools{
		namespace SA{
			template<int M=128,int N>
			void calc_sa(char (&str)[N],int sa[],int rk[],int n){
				int m=M-1;
				static int cnt[N<M?M:N],id[N],oldrk[N<<1],key[N];
				for(int i=1;i<=n;++i) ++cnt[rk[i]=str[i]];
				for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
				for(int i=n;i;--i) sa[cnt[rk[i]]--]=i;
				for(int k=1,p;;k<<=1,m=p){
					p=0;
					for(int i=n;i>n-k;--i) id[++p]=i;
					for(int i=1;i<=n;++i) if(sa[i]>k) id[++p]=sa[i]-k;
					memset(cnt,0,sizeof(int)*(m+1));
					for(int i=1;i<=n;++i) ++cnt[key[i]=rk[id[i]]];
					for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
					for(int i=n;i;--i) sa[cnt[key[i]]--]=id[i];
					memcpy(oldrk,rk,sizeof(int)*(n+1));
					p=0;
					for(int i=1;i<=n;++i){
						static auto cmp=[&k](int x,int y){
							return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
						};
						rk[sa[i]]=cmp(sa[i],sa[i-1])?p:++p;
					}
					if(p==n) return;
				}
			}
			template<int N>
			void calc_height(char (&str)[N],int sa[],int rk[],int height[],int n){
				for(int i=1,k=0;i<=n;++i){
					if(!rk[i]) continue;
					k&&--k;
					for(;str[i+k]==str[sa[rk[i]-1]+k];++k);
					height[rk[i]]=k;
				}
			}
		}
	}
	/**
	 * 占坑
	 */
	namespace Data_Structure{}
}
namespace QL{
	namespace Base_Tools{
		template<typename _Tp>
		static constexpr std::size_t integral_length=sizeof(_Tp)*10/sizeof(int);
	}
	namespace IO{
		using Base_Tools::integral_length;
		/**
		 *  -DLOCAL后能使用错误流，并关掉fread/fwrite
		 * 然而使用错误流时VScode会假CE，还不能解决
		 * 此外，这套IO跟C的一样，不是很方便扩展
		 * 正在考虑怎么改一下，大概是通过友元
		 * 扩充了浮点数的输出，借助了C库的sprintf，写得还有点丑，之后改
		 * 浮点输入咕
 		*/
		class IO{
		protected:
#ifdef _INITIALIZER_LIST
			using LIST=std::initializer_list<int>;
#endif
#ifndef LOCAL
			FILE *IN;
			FILE *OUT;
			static constexpr int SIZE=1<<15;
			char buf[SIZE]{},*p1{buf},*p2{buf},obuf[SIZE]{},*p3{obuf};
			char pull(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,IN),p1==p2)?EOF:*p1++;}
			void push(char ch){((p3-obuf)==SIZE&&(flush(false),0)),*p3++=ch;}
			template<std::size_t L>
			FILE*set_in(const char(&name)[L]){
				static char in[L+5]={};
				memcpy(in,name,sizeof in);
				in[L-1]='.',in[L]='i',in[L+1]='n',in[L+2]='\0';
				return std::fopen(in,"r");
			}
			template<std::size_t L>
			FILE*set_out(const char(&name)[L]){
				static char out[L+5];
				memcpy(out,name,sizeof out);
				out[L-1]='.',out[L]='o',out[L+1]='u',out[L+2]='t',out[L+3]='\0';
				return std::fopen(out,"w");
			}
#else
			char pull(){return std::getchar();}
			void push(char ch){std::putchar(ch);}
			void errchar(char ch){std::fputc(ch,stderr);}
			template<std::size_t L>
			void reset_stdin(const char(&name)[L]){
				static char in[L+5]={};
				__builtin_memcpy(in,name,sizeof in);
				in[L-1]='.',in[L]='i',in[L+1]='n',in[L+2]='\0';
				freopen(in,"r",stdin);
			}
			template<std::size_t L>
			void reset_stdout(const char(&name)[L]){
				static char out[L+5];
				__builtin_memcpy(out,name,sizeof out);
				out[L-1]='.',out[L]='o',out[L+1]='u',out[L+2]='t',out[L+3]='\0';
				freopen(out,"w",stdout);
			}
#endif
		public:
#ifndef LOCAL
			IO():IN{stdin},OUT{stdout},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&QL::IO::IO::push}{}
			template<std::size_t L>
			IO(const char(&name)[L]):IN{set_in(name)},OUT{set_out(name)},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&QL::IO::IO::push}{}
			template<std::size_t L>
			IO(const char(&name)[L],bool in,bool out):IN{in?set_in(name):stdin},OUT{out?set_out(name):stdout},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&QL::IO::IO::push}{}
			~IO(){flush();}
			void flush(bool _flush_=false){
				__builtin_fwrite(obuf,1,p3-obuf,OUT),p3=obuf;
				if(_flush_) std::fflush(stdout);
			}
#else
			IO(){}
			template<std::size_t L>
			IO(const char(&name)[L]):Ch{'\n'}{reset_stdin(name),reset_stdout(name);}
			template<std::size_t L>
			IO(const char(&name)[L],bool in,bool out):Ch{'\n'}{in&&(reset_stdin(name),0),out&&(reset_stdout(name),0);}
			void flush(){std::fflush(stdout);}
#endif
			template<typename T>
			T read(){
				T x;
				read(x);
				return x;
			}
protected:
			char Ch='\n';
public:
			template<typename T>
			void read(T &&x){
				x=0;bool flag=0;char ch=Ch;
				for(;ch<'0'||ch>'9';ch=pull()) if(ch=='-') flag=1;
				if(flag) for(;ch>='0'&&ch<='9';ch=pull()) x=(x<<1)+(x<<3)-(ch&15);
				else for(;ch>='0'&&ch<='9';ch=pull()) x=(x<<1)+(x<<3)+(ch&15);
			}
			void read(char *str){
				char ch=Ch;
				for(;(ch==' '||ch=='\n'||ch=='\r')&&ch!=EOF;ch=pull());
				if(ch==EOF) return (void)(*str='\0');
				for(;ch!=' '&&ch!='\n'&&ch!='\r'&&ch!=EOF;ch=pull()) *str++=ch;
				*str='\0';
				Ch=ch;
			}
			void read(char &c){
				char ch=Ch;
				for(;ch==' '||ch=='\n';ch=pull());
				c=ch;
				Ch=pull();
			}
			void read(bool &x){
				char ch=Ch;
				for(;ch!='0'&&ch!='1';ch=pull());
				x=ch=='1';
				Ch=pull();
			}
			template<typename T>
			void read(T &x){read(std::move(x));}
		protected:
			void(IO::*outchar)(char)=&QL::IO::IO::push;
			template<typename T>
			void out(T x){
				static char sta[integral_length<T>];
				int top=0;
				if(x<0){
					(this->*outchar)('-');
					do sta[top++]=((-x)%10)|48,x/=10;
					while(x);
				}
				else{
					do sta[top++]=(x%10)|48,x/=10;
					while(x);
				}
				while(top) (this->*outchar)(sta[--top]);
			}
			void out(bool x){(this->*outchar)(x?'1':'0');}
			void out(char x){(this->*outchar)(x);}
			void out(char *str){while(*str!='\0') (this->*outchar)(*str++);}
			void out(const char *str){while(*str!='\0') (this->*outchar)(*str++);}
			void out(float x){
				static char str[114];
				std::sprintf(str,"%.17f",x);
				out(str);
			}
			void out(double x){
				static char str[114];
				std::sprintf(str,"%.17f",x);
				out(str);
			}
			void out(long double x){
				static char str[114];
				std::sprintf(str,"%.17Lf",x);
				out(str);
			}
			void out(std::pair<int,float> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%df",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void out(std::pair<int,double> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%df",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void out(std::pair<int,long double> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%dLf",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void set_std_out(){outchar=&QL::IO::IO::push;}
#ifdef LOCAL
			void set_err_out(){outchar=&QL::IO::IO::errchar;}
#endif
		public:
			template<typename...Args>
			void read(Args &&...args){(void)LIST{(read(args),0)...};}
			template<typename...Args>
			void write(Args...args){set_std_out(),(void)LIST{(out(args),0)...};}
			template<typename...Args>
			void writeln(Args...args){write(args...),push('\n');}
#ifdef LOCAL
			template<typename...Args>
			void error(Args...args){set_err_out(),(void)LIST{(out(args),0)...};}
			template<typename...Args>
			void errorln(Args...args){error(args...),errchar('\n');}
#endif
		};
	}
}
namespace MAIN{
	QL::IO::IO lq;
	void radix_sort(int *x,int n){
		static const int mask=(1<<16)-1;
		static int *cnt=new int[mask+1],*y=new int[n+5];
		for(int k=0;k<32;k+=16){
			for(int i=0;i<=mask;++i) cnt[i]=0;
			for(int i=1;i<=n;++i) ++cnt[(x[i]>>k)&mask];
			for(int sum=0,i=0;i<=mask;++i)
				sum+=cnt[i],cnt[i]=sum-cnt[i];
			for(int i=1;i<=n;++i) y[++cnt[(x[i]>>k)&mask]]=x[i];
			int *tmp=x;
			x=y,y=tmp;
		}
	}
	constexpr int N=1e5+5;
	int n,a[N];
	int _main_(void){
		lq.read(n);
		for(int i=1;i<=n;++i) lq.read(a[i]);
		radix_sort(a,n);
		for(int i=1;i<=n;++i) lq.write(a[i],' ');
		return 0;
	}
}
signed main(){
	return MAIN::_main_();
}