$rt$

#include <iostream>
#include <ctime>
#include <random>
#include <cstring>
namespace IO
{
	int min(int,int);
	long long minl(long long x,long long y);
	long double minlb(long double x,long double y);
	int max(int x,int y);
	long long maxl(long long x,long long y);
	long double maxlb(long double x,long double y);
	int ceil(double x);
	long long ceill(double x);
	int floor(double x);
	long long floorl(double x);
	int abs(int x);
	double fabs(double x);
	long long labs(long long x);
	long double lbabs(long double x);
	void read(int &x);
	void readl(long long &x);
	void write(int x);
	void writel(long long x);
	double sqrt(double x);
	long double sqrtl(long double x);
	double pow(double x,long long y);
	long double powl(double x,long long y);
	double cbrt(double x);
	long double cbrtl(long double x);
	double gh(double x,long long c);
	long double ghl(long double x,long long c);
	long long fastpow(long long a,long long n,long long mod);
	static const int mod1=998244353;
	static const int mod2=1e9+7;
	static const int INF1=0x3f3f3f;
	static const int INF2=0x7ffffff/3;
	static const int INF3=1e9+7;
	using std::cin;
	using std::cout;
	std::mt19937 rnd(time(nullptr));
	inline long double ffastpow(long double a,long long n,long long mod)
	{
		long double ans=1;
		while(n)
		{
			if(n&1)
			{
				ans=ans*a;
				while(ans>=mod)
				{
					ans-=mod;
				}
			}
			a=a*a;
			while(a>=mod)
			{
				a-=mod;
			}
			n>>=1;
		}
		return ans;
	}
	inline void swap(int &a,int &b)
	{
		a=a xor b;
		b=b xor a;
		a=a xor b;
	}
	inline int min(int x,int y)
	{
		return x<y?x:y;
	}
	inline long long minl(long long x,long long y)
	{
		return x<y?x:y;
	}
	inline long double minlb(long double x,long double y)
	{
		return x<y?x:y;
	}
	inline int max(int x,int y)
	{
		return x>y?x:y;
	}
	inline long long maxl(long long x,long long y)
	{
		return x>y?x:y;
	}
	inline long double maxlb(long double x,long double y)
	{
		return x>y?x:y;
	}
	inline int ceil(double x)
	{
		return (x!=(int)x?(int)x+1:x);
	}
	inline long long ceill(double x)
	{
		return (x!=(long long)x?(long long)x+1:x);
	}
	inline int floor(double x)
	{
		return (x!=(int)x?(int)x:x);
	}
	inline long long floorl(double x)
	{
		return (x!=(long long)x?(long long)x:x);
	}
	inline int abs(int x)
	{
		return x<0?-x:x;
	}
	inline double fabs(double x)
	{
		return x<0?-x:x;
	}
	inline long long labs(long long x)
	{
		return x<0?-x:x;
	}
	inline long double lbabs(long double x)
	{
		return x<0?-x:x;
	}
	inline void read(int &x)
	{
		int f=1;
		x=0;
		char s=getchar();
		while(s<'0'||s>'9')
		{
			if (s=='-') f=-1;
			s=getchar();
		}
		while(s>='0'&&s<='9')
		{
			x=x*10+s-'0';
			s=getchar();
		}
		x*=f;
	}
	inline void readl(long long &x)
	{
		int f=1;
		x=0;
		char s=getchar();
		while(s<'0'||s>'9')
		{
			if (s=='-') f=-1;
			s=getchar();
		}
		while(s>='0'&&s<='9')
		{
			x=x*10+s^48;
			s=getchar();
		}
		x*=f;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
	inline void writel(long long x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
	inline double sqrt(double x)
	{
		double exp(1e-10);
		double l(0),r(x),mid;
		while(l<r)
		{
			mid=(l+r)/2;
			double t(mid*mid);
			if(fabs(x-t)<=exp)
			{
				return mid;
			}
			t>x?r=mid:l=mid+exp;
		}
		return mid;
	}
	inline long double sqrtl(long double x)
	{
		long double exp(1e-10);
		long double l(0),r(x),mid;
		while(l<r)
		{
			mid=(l+r)/2;
			long double t(mid*mid);
			if(lbabs(x-t)<=exp)
			{
				return mid;
			}
			t>x?r=mid:l=mid+exp;
		}
		return mid;
	}
	inline double pow(double x,long long y)
	{
		long double sum(1);
		for(register int i(1); i<=y; ++i)
		{
			sum*=x;
		}
		return sum;
	}
	inline long double powl(double x,long long y)
	{
		long double sum(1);
		for(register int i(1); i<=y; ++i)
		{
			sum*=x;
		}
		return sum;
	}
	inline double gh(double x)
	{
		double exp=1e-10;
		double l=0,r=x,mid;
		while(l<r)
		{
			mid=(l+r)/2;
			long double t=mid*mid;
			if(fabs(x-t)<=exp)
			{
				return mid;
			}
			t>x?r=mid:l=mid+exp;
		}
		return mid;
	}
	inline long double ghl(long double x,long long c)
	{
		long double exp=1e-18;
		long double l=0,r=x,mid;
		while(l<r)
		{
			mid=(l+r)/2;
			long double t=pow(mid,c);
			if(lbabs(x-t)<=exp)
			{
				return mid;
			}
			t>x?r=mid:l=mid+exp;
		}
		return mid;
	}
	inline long long fastpow(long long a,long long n,long long mod)
	{
		long long ans=1;
		a%=mod;
		while(n)
		{
			if(n&1)
			{
				ans=(ans*a)%mod;
			}
			a=(a*a)%mod;
			n>>=1;
		}
		return ans;
	}
	template <typename T>
	class stack
	{
		private:
			int cnt=0;
			struct node
			{
				T x;
				node *next;
			};
			node *head;
		public:
			stack()
			{
				head=new node;
				head->next=nullptr;
			}
			inline void push(T x)
			{
				cnt++;
				node *p=new node;
				p->x=x;
				p->next=head;
				head=p;
			}
			inline T front()
			{
				return head->x;
			}
			inline void pop()
			{
				cnt--;
				head=head->next;
			}
			inline int size()
			{
				return cnt;
			}
			inline bool empty()
			{
				return cnt==0;
			}
	};
	template <typename T>
	class queue
	{
		private:
			int cnt=0;
			struct node
			{
				T x;
				node *next;
			};
			node *head,*tail;
		public:
			queue()
			{
				head=new node;
				tail=new node;
			}
			inline void push(T x)
			{
				cnt++;
				node *p=new node;
				p->x=x;
				p->next=nullptr;
				tail->next=p;
				tail=p;
			}
			inline T front()
			{
				return head->x;
			}
			inline void pop()
			{
				cnt--;
				head=head->next;
			}
			inline int size()
			{
				return cnt;
			}
			inline bool empty()
			{
				return cnt==0;
			}
	};
	template <typename T>
	class deque
	{
		private:
			int cnt=0;
			struct node
			{
				T x;
				node *next,*pre;
			};
			node *head,*tail;
		public:
			deque()
			{
				head=new node;
				tail=new node;
			}
			inline void push_back(T x)
			{
				cnt++;
				node *p=new node;
				p->x=x;
				p->next=nullptr;
				p->pre=tail;
				tail->next=p;
				tail=p;
			}
			inline void push_front(T x)
			{
				cnt++;
				node *p=new node;
				p->x=x;
				p->next=head;
				p->pre=nullptr;
				head->pre=p;
				head=p;
			}
			inline T front()
			{
				return head->x;
			}
			inline T back()
			{
				return tail->x;
			}
			inline void pop_front()
			{
				cnt--;
				head=head->next;
				delete head->pre;
				head->pre=nullptr;
			}
			inline void pop_back()
			{
				cnt--;
				tail=tail->pre;
				delete tail->next;
				tail->next=nullptr;
			}
			inline int size()
			{
				return cnt;
			}
			inline bool empty()
			{
				return cnt==0;
			}
	};
//	template <typename T>
//	class priority_queue
//	{
//		private:
//			struct node
//			{
//				T x;
//				node *ls,*rs,*fa;
//			};
//			priority_queue()
//			{
//				node *root=new node;
//			}
//			int n=0;
//			inline void up(node a)
//			{
//				if(a->fa=nullptr)
//				{
//					return ;
//				}
//				if(a->fa->x>a->x)
//				{
//					swap(a->fa,a);
//					up(a->fa);
//				}
//			}
//			inline void down(int x)
//			{
//				if(x<<1>n) return ;
//				if(x<<1==n)
//				{
//					if(a[x]>a[x<<1])
//					{
//						swap(a[x],a[x<<1]);
//					}
//					return;
//				}
//				if(a[x]<a[x<<1] && a[x]<a[x<<1|1])
//				{
//					return ;
//				}
//				if(a[x<<1]<a[x<<1|1])
//				{
//					swap(a[x<<1],a[x]);
//					down(x<<1);
//				}
//				else
//				{
//					swap(a[x<<1|1],a[x]);
//					down(x<<1|1);
//				}
//			}
//		public:
//			inline void push(T x)
//			{
//				++n;
//				a[n]=x;
//				up(n);
//			}
//			inline void del(T x)
//			{
//				a[x]=a[n];
//				--n;
//				up(x);
//				down(x);
//			}
//			inline void pop()
//			{
//				a[1]=a[n];
//				n--;
//				down(1);
//			}
//			inline T front()
//			{
//				return root;
//			}
//			inline int size()
//			{
//				return n;
//			}
//	};
	template <typename T>
	class FHQ
	{
			static const int N = 1e6 + 10;
		private:
			struct fhq
			{
				int l, r;
				int key;
				T val;
				int siz, tag;
			} tr[N];
			inline void push_down(int p)
			{
				if (tr[p].tag)
				{
					swap(tr[p].l, tr[p].r);
					tr[tr[p].l].tag ^= 1;
					tr[tr[p].r].tag ^= 1;
					tr[p].tag = 0;
				}
			}
			inline void push_up(int p)
			{
				tr[p].siz = tr[tr[p].l].siz + tr[tr[p].r].siz + 1;
			}
		public:
			inline void add(T x)
			{
				tr[x].val = x;
				tr[x].siz = 1;
				tr[x].key = rnd();
				tr[x].l = tr[x].r = 0;
			}
			inline void split(int p, T x, int &l, int &r)
			{
				if (!p)
				{
					l = r = 0;
					return;
				}
				push_down(p);
				if (tr[tr[p].l].siz + 1 <= x)
				{
					l = p;
					split(tr[p].r, x - tr[tr[p].l].siz - 1, tr[p].r, r);
				}
				else
				{
					r = p;
					split(tr[p].l, x, l, tr[p].l);
				}
				push_up(p);
			}
			inline int merge(int l, int r)
			{
				if (!l or !r)
				{
					return l + r;
				}
				if (tr[l].key < tr[r].key)
				{
					push_down(l);
					tr[l].r = merge(tr[l].r, r);
					push_up(l);
					return l;
				}
				else
				{
					push_down(r);
					tr[r].l = merge(l, tr[r].l);
					push_up(r);
					return r;
				}
			}
			inline void print(int u)
			{
				push_down(u);
				if (tr[u].l)
				{
					print(tr[u].l);
				}
				write(tr[u].val);
				putchar('\n');
				if (tr[u].r)
				{
					print(tr[u].r);
				}
			}
			inline void distag(int x)
			{
				tr[x].tag = tr[x].tag xor 1;
			}
	};
	template<typename T>
	class szsz
	{
			int n=0;
			T a[1000001],tr[1000001];
			inline void insert(T x)
			{
				a[++n]=x;
			}
			inline void push(int x,T v)
			{
				while(x<=n)
				{
					tr[x]+=v;
					x+=x&(-x);
				}
			}
			inline T query(int x)
			{
				T sum=0;
				while(x>0)
				{
					sum+=tr[x];
					x-=x&(-x);
				}
				return sum;
			}
	};
	template <typename T>
	class LCT
	{
			int len=0;
		private:
			struct node
			{
				int val,ch[2],fa,lazy,sum;
			} tree[500005];
			int sz,stk[500005],topp;
			inline void access(int x)
			{
				for(int y = 0; x; y=x,x=tree[x].fa)
				{
					splay(x),tree[x].ch[1]=y,update(x);
				}
				return;
			}
			inline void makeroot(int x)
			{
				access(x);
				splay(x);
				tree[x].lazy^=1;
				swap(tree[x].ch[0],tree[x].ch[1]);
				return;
			}
			inline int findroot(int x)
			{
				access(x);
				splay(x);
				while(tree[x].ch[0])
				{
					pushdown(x);
					x=tree[x].ch[0];
				}
				access(x);
				splay(x);
				return x;
			}
			inline void pushdown(int nod)
			{
				if(tree[nod].lazy)
				{
					tree[nod].lazy^=1;
					tree[tree[nod].ch[0]].lazy^=1;
					tree[tree[nod].ch[1]].lazy^=1;
					swap(tree[tree[nod].ch[0]].ch[0],tree[tree[nod].ch[0]].ch[1]);
					swap(tree[tree[nod].ch[1]].ch[0],tree[tree[nod].ch[1]].ch[1]);
				}
			}
			inline void update(int nod)
			{
				tree[nod].sum=tree[nod].val xor tree[tree[nod].ch[0]].sum xor tree[tree[nod].ch[1]].sum;
				return;
			}
			inline bool root(int x)
			{
				if(x==tree[tree[x].fa].ch[0])
				{
					return true;
				}
				if(x==tree[tree[x].fa].ch[1])
				{
					return true;
				}
				return false;
			}
			inline bool get(int p)
			{
				return p==tree[tree[p].fa].ch[1];
			}
			inline void rotate(int nod)
			{
				int f=tree[nod].fa,z=tree[f].fa,ck=get(nod),sec=tree[nod].ch[1-ck],getf=get(f);
				tree[sec].fa=f;
				tree[f].ch[ck]=sec;
				tree[nod].fa=z;
				if(root(f))
				{
					tree[z].ch[getf]=nod;
				}
				tree[f].fa=nod;
				tree[nod].ch[1-ck]=f;
				update(f);
				update(nod);
				return;
			}
		public:
			inline void splay(int x)
			{
				int y=x;
				topp=0;
				while(root(y))
				{
					stk[++topp]=y;
					y=tree[y].fa;
				}
				stk[++topp]=y;
				while(topp)
				{
					pushdown(stk[topp]);
					topp--;
				}
				while(root(x))
				{
					int f=tree[x].fa;
					if(root(f))
					{
						if(get(x)!=get(f))
						{
							rotate(x);
						}
						else
						{
							rotate(f);
						}
					}
					rotate(x);
				}
				update(x);
				return;
			}
			inline void split(int x,int y)
			{
				makeroot(x);
				access(y);
				splay(y);
				return;
			}
			inline void link(int x,int y)
			{
				makeroot(x);
				if(x!=findroot(y))
				{
					tree[x].fa=y;
				}
				return;
			}
			inline void cut(int x,int y)
			{
				makeroot(x);
				if(x!=findroot(y))
				{
					return;
				}
				if(tree[y].fa!=x||tree[y].ch[0])
				{
					return;
				}
				tree[x].ch[1]=0,tree[y].fa=0;
				update(x);
				return;
			}
			inline void push_back(T x)
			{
				tree[++len].val=x;
				tree[len].sum=x;
			}
			inline void modify(int x,T y)
			{
				tree[x].val=y;
			}
	};
	template <typename T>
	class unionn
	{
			static const int M=1e6+7;
			int n, m;
			int pre[M];
			int ans;
			inline int find(int t)
			{
				return t == pre[t] ? t : pre[t] = find(pre[t]);
			}
			inline void merge(int u, int v)
			{
				int a = find(u), b = find(v);
				if (a != b)
				{
					pre[a] = b;
				}
			}
			inline bool isJudge(int u, int v)
			{
				return find(u)==find(v);
			}
	};
	inline long long fm_ny(long long a,long long b)
	{
		return fastpow(a,b-2,b)%b;
	}
	inline long long ex_gcd(long long a,long long b,long long &x,long long &y)
	{
		if(b==0)
		{
			x=1;
			y=0;
			return a;
		}
		long long ans=ex_gcd(b,a%b,x,y);
		long long temp=x;
		x=y;
		y=temp-a/b*y;
		return ans;
	}
	inline long long ex_ny(long long a,long long b,long long c)
	{
		long long x,y;
		long long gcd=ex_gcd(a,b,x,y);
		if(c%gcd!=0) return -1;
		x*=c/gcd;
		b/=gcd;
		if(b<0) b=-b;
		long long ans=x%b;
		if(ans<=0) ans+=b;
		return ans;
	}
	template<typename T>
	class vector
	{
		private:
			T* vec;
			int size;
			int c;
		public:
			inline void clear()
			{
				if(vec!=nullptr)
				{
					delete[]vec;
				}
				size=0;
				c=1;
				vec=nullptr;
			}
			vector():vec(new T),size(0),c(1) {}
			~vector()
			{
				if(vec!=nullptr)
				{
					delete [] vec;
				}
				size=0;
				c=0;
				vec=nullptr;
			}
			inline int Size()
			{
				return size;
			}
			inline bool empty()
			{
				return !size;
			}
			inline void push_back(register const T &x)
			{
				if(-~size==c)
				{
					register T* temp=new T[c<<=1];
					for(register int i=0; i<size; ++i)
					{
						temp[i]=vec[i];
					}
					if(vec!=nullptr)
					{
						delete []vec;
					}
					vec=temp;
				}
				vec[size++]=x;
			}
			inline void pop_back()
			{
				if(size)
				{
					--size;
				}
			}
			inline T* begin()
			{
				return vec;
			}
			inline T* end()
			{
				return vec+size;
			}
			inline int maxsize()
			{
				return c;
			}
			inline const T &front()
			{
				return vec[0];
			}
			inline const T &back()
			{
				return vec[size-1];
			}
			inline void erase(register T *x)
			{
				for(register T *i(x+1); i<end(); ++i)
				{
					*(i-1)=*i;
				}
				--size;
			}
			inline void erase(register T *l,register T *r)
			{
				for(register T *i=l; i+(r-l-1)<end(); ++i)
				{
					*i=*(i+(r-l-1)+1);
				}
				size-=(r-l);
			}
			inline void insert(register T *p,register const T &x,register const int &n=1)
			{
				register int t=p-vec;
				if(size+n>=c)
				{
					while(size+n>=c)
					{
						c<<=1;
					}
					register T* temp=new T[c];
					for(register int i=0; i<size; ++i)
					{
						temp[i]=vec[i];
					}
					if(vec!=nullptr)
					{
						delete []vec;
					}
					vec=temp;
					p=vec+t;
				}
				for(register int i=size-1; i>=t; --i)
				{
					vec[i+n]=vec[i];
				}
				for(register T *i=p; i-p<n; ++i)
				{
					*i=x;
				}
				size+=n;
			}
			inline void resize(register const int &x)
			{
				size=x;
				c=x;
				if(vec!=nullptr)
				{
					delete[]vec;
				}
				vec=new T[x];
			}
			inline T& operator[](register const int &x)
			{
				return vec[x];
			}
			inline vector& operator=(register const vector<T>&x)
			{
				if(this==&x)
				{
					return *this;
				}
				register T* temp=new T[x.c];
				for(register int i=0; i<size; ++i)
				{
					temp[i]=x.vec[i];
				}
				if(vec!=nullptr)
				{
					delete []vec;
				}
				vec=temp;
				size=x.size;
				c=x.c;
				return *this;
			}
			inline bool operator<(register const vector<T>&x)const
			{
				register int l=min(size,x.Size());
				for(register int i=0; i<l; i=-~i)
				{
					if(vec[i]!=x[i])
					{
						return vec[i]<x[i];
					}
				}
				if(size^x.Size())
				{
					return size<x.Size();
				}
				return 0;
			}
			inline bool operator>(register const vector<T>&x)const
			{
				return x<*this;
			}
			inline bool operator<=(register const vector<T>&x)const
			{
				return!(x<*this);
			}
			inline bool operator>=(register const vector<T>&x)const
			{
				return!(*this<x);
			}
			inline bool operator!=(register const vector<T>&x)const
			{
				return *this<x or x<*this;
			}
			inline bool operator==(register const vector<T>&x)const
			{
				return!( *this<x or x<*this);
			}
	};
	template<typename T>
	struct less
	{
		inline bool operator()(register const T &a,register const T &b)
		{
			return a<b;
		}
	};
	template<typename T>
	struct Greater
	{
		inline bool operator()(register const T &a,register const T &b)
		{
			return b<a;
		}
	};
	template<typename T,typename Comper=less<T> >
	class Tree
	{
		private:
			struct node
			{
				node *ls,*rs;
				int pri,size;
				T k;
			}*root,*null;
			std::mt19937 random;
			Comper cmp;
			inline void Clear(register node *&x)
			{
				if(x==nullptr)return;
				Clear(x->ls);
				Clear(x->rs);
				delete x;
			}
			inline node* newnode(register const T &k)
			{
				register node *p(new node);
				p->ls=p->rs=nullptr;
				p->k=k;
				p->pri=random();
				p->size=1;
				return p;
			}
			inline void update(register node *u)
			{
				u->size=u->ls->size+u->rs->size+1;
			}
			inline void split(register node *u,register const T &x,register node *&l,register node *&r)
			{
				if(u==nullptr)
				{
					l=r=nullptr;
					return;
				}
				if(!cmp(x,u->k))
				{
					l=u;
					split(l->rs,x,l->rs,r);
					update(l);
				}
				else
				{
					r=u;
					split(r->ls,x,l,r->ls);
					update(r);
				}
			}
			inline node* merge(register node *l,register node *r)
			{
				if(l==nullptr)
				{
					return r;
				}
				if(r==nullptr)
				{
					return l;
				}
				if(l->pri>r->pri)
				{
					l->rs=merge(l->rs,r);
					update(l);
					return l;
				}
				else
				{
					r->ls=merge(l,r->ls);
					update(r);
					return r;
				}
			}
			inline void Erase(register node *&x,register const T &k)
			{
				if(x==nullptr)return;
				--x->size;
				if(x->k==k)
				{
					register node *temp(x);
					x=merge(x->ls,x->rs);
					delete temp;
					return;
				}
				if(cmp(k,x->k))
				{
					Erase(x->ls,k);
				}
				else
				{
					Erase(x->rs,k);
				}
			}
			inline int Rank(register node *x,register const T &k)
			{
				if(x==nullptr)
				{
					return 1;
				}
				if(cmp(x->k,k))
				{
					return Rank(x->rs,k)+x->ls->size+1;
				}
				return Rank(x->ls,k);
			}
			inline T kth(register node* now,register int x)
			{
				for(;;)
				{
					if(x<=now->ls->size)now=now->ls;
					else if(x==now->ls->size+1)return now->k;
					else x-=now->ls->size+1,now=now->rs;
				}
			}
			inline T lower__bound(register node *x,register const T &k)
			{
				if(x==nullptr)
				{
					return T();
				}
				if(cmp(x->k,k))
				{
					return lower__bound(x->rs,k);
				}
				register T _(lower__bound(x->ls,k));
				if(_==T())
				{
					return x->k;
				}
				return _;
			}
			inline T upper__bound(register node *x,register const T &k)
			{
				if(x==nullptr)
				{
					return T();
				}
				if(!(cmp(k,x->k)))
				{
					return upper__bound(x->rs,k);
				}
				register T _(upper__bound(x->ls,k));
				if(_==T())
				{
					return x->k;
				}
				return _;
			}
			inline T Pre(register node *x,register const T &k)
			{
				if(x==nullptr)
				{
					return T();
				}
				if(!cmp(x->k,k))
				{
					return Pre(x->ls,k);
				}
				register T _(Pre(x->rs,k));
				if(_==T())
				{
					return x->k;
				}
				return _;
			}
			inline node* find(register node *x,register const T &k)
			{
				if(x==nullptr)
				{
					return nullptr;
				}
				if(x->k==k)
				{
					return x;
				}
				if(x->k>k)
				{
					return find(x->ls,k);
				}
				return find(x->rs,k);
			}
			inline void Printf(register node *x)
			{
				Printf(x->ls);
				cout<<x->k<<' ';
				Printf(x->rs);
			}
		public:
			Tree()
			{
				random.seed((unsigned)time(nullptr));
				root=null=new node;
				null->ls=null->rs=nullptr;
				null->k=T();
				null->pri=null->size=0;
			}
			~Tree()
			{
				Clear(root);
			}
			inline void clear()
			{
				Clear(root);
				root=nullptr;
			}
			inline void insert(register const T &k)
			{
				register node *l,*r;
				split(root,k,l,r);
				root=merge(merge(l,newnode(k)),r);
			}
			inline void erase(register const T &k)
			{
				Erase(root,k);
			}
			inline int order_of_key(register const T &k)
			{
				return Rank(root,k);
			}
			inline T find_by_order(register const int &r)
			{
				return kth(root,r);
			}
			inline T lower_bound(register const T &k)
			{
				return lower__bound(root,k);
			}
			inline T upper_bound(register const T &k)
			{
				return upper__bound(root,k);
			}
			inline T next(register const T &k)
			{
				return upper__bound(root,k);
			}
			inline T pre(register const T &k)
			{
				return Pre(root,k);
			}
			inline node* find(register const T &k)
			{
				return find(root,k);
			}
			inline int count(register const T &k)
			{
				register node *l,*r,*p;
				register  T temp(pre(k));
				spilt(root,k,l,r),split(l,temp,l,p);
				register int ans(p->size);
				return root=merge(merge(l,p),r),ans;
			}
			inline int size()
			{
				return root->size;
			}
			inline bool empty()
			{
				return root==nullptr;
			}
			inline void print()
			{
				Printf(root);
			}
	};
	template <typename T>
	class list
	{
		private:
			struct node
			{
				T x;
				node *pre,*next;
			};
			node *it,*head,*tail;
		public:
			list()
			{
				head=new node;
				tail=new node;
				it=new node;
				it->next=nullptr;
				it->pre=nullptr;
				head=tail=it;
			}
			void del(int x)
			{
				node *now;
				now=it;
				for(int i=1; i<x; i++)
				{
					now=now->next;
				}
				if(x==1)
				{
					head=now->next;
				}
				if(now==tail)
				{
					tail=now->pre;
				}
				now->pre->next=now->next;
				now->next->pre=now->pre;
				it=now;
				delete now;
			}
			void b_head()
			{
				it=head;
			}
			void b_tail()
			{
				it=tail;
			}
			void insert(int x,T data)
			{
				node *now,*p;
				now=it;
				p=new node;
				p->x=data;
				p->next=nullptr;
				p->pre=nullptr;
				for(int i=1; i<x; i++)
				{
					now=now->next;
				}
				p->next=now->next;
				it=now;
				now->next->pre=p;
				now->next=p;
				p->pre=now;
				if(p->next=nullptr)
				{
					tail=p;
				}
				if(p->pre=nullptr)
				{
					head=p;
				}
			}
			void print()
			{
				node *p=head;
				while(p->next!=nullptr)
				{
					cout<<p->x<<'\n';
					p=p->next;
				}
			}
	};
	template<typename X,typename Y>
	struct pair
	{
		X first;
		Y second;
		bool operator<(const pair<X,Y>&i)const
		{
			return (first!=i.first)?(first<i.first):(second<i.second);
		}
		bool operator>(const pair<X,Y>&i)const
		{
			return i<*this;
		}
		bool operator<=(const pair<X,Y>&i)const
		{
			return !(i<*this);
		}
		bool operator>=(const pair<X,Y>&i)const
		{
			return !(*this<i);
		}
		bool operator!=(const pair<X,Y>&i)const
		{
			return i<*this||*this<i;
		}
		bool operator==(const pair<X,Y>&i)const
		{
			return !(i<*this||*this<i);
		}
	};
	template<typename T,typename mapped>
	class map
	{
		private:
			struct node
			{
				node *ls,*rs;
				T key;
				mapped mp;
				int pri;
			};
			node *root;
			std::mt19937 random;
			inline void newnode(node* &p,const T &k,const mapped &m)
			{
				p=new node;
				p->ls=p->rs=nullptr;
				p->key=k;
				p->mp=m;
				p->pri=random();
			}
			inline void split(node* &u,const T &x,node* &l,node* &r)
			{
				if(u==nullptr)
				{
					l=r=nullptr;
					return;
				}
				if(!(x<u->key))
				{
					l=u;
					split(u->rs,x,u->rs,r);
				}
				else
				{
					r=u;
					split(u->ls,x,l,u->ls);
				}
			}
			inline node*& merge(node* &l,node* &r)
			{
				if(l==nullptr)
				{
					return r;
				}
				if(r==nullptr)
				{
					return l;
				}
				if(l->pri>r->pri)
				{
					l->rs=merge(l->rs,r);
					return l;
				}
				else
				{
					r->ls=merge(l,r->ls);
					return r;
				}
			}
			inline void insert(const T &x,const mapped &m)
			{
				node *l,*r,*p;
				split(root,x,l,r);
				newnode(p,x,m);
				root=merge(merge(l,p),r);
			}
			inline node* find(const T &x,node* now)
			{
				if(now==nullptr)
				{
					return nullptr;
				}
				if(x==now->key)
				{
					return now;
				}
				if(x<now->key)
				{
					return find(x,now->ls);
				}
				else
				{
					return find(x,now->rs);
				}
			}
			inline void clear(node* x)
			{
				if(x==nullptr)
				{
					return;
				}
				clear(x->ls);
				clear(x->rs);
				delete x;
			}
			inline void del(node* &x,const T &key)
			{
				if(x==nullptr)
				{
					return;
				}
				if(x->key==key)
				{
					node *X(x);
					x=merge(x->ls,x->rs);
					delete X;
					return;
				}
				if(x->key>key)
				{
					del(x->ls,key);
				}
				else
				{
					del(x->rs,key);
				}
			}
		public:
			inline map()
			{
				random.seed((unsigned)time(nullptr));
			}
			inline ~map()
			{
				clear();
			}
			inline mapped &operator[](const T &x)
			{
				node *p=find(x,root);
				if(p==nullptr)
				{
					insert(x,mapped());
					return find(x,root)->mp;
				}
				return p->mp;
			}
			inline void insert(const pair<T,mapped>&p)
			{
				insert(p.first,p.second);
			}
			inline node* find(const T &x)
			{
				return find(x,root);
			}
			inline void erase(const T &x)
			{
				del(root,x);
			}
			inline void clear()
			{
				clear(root);
				root=nullptr;
			}
	};
	template <typename T>
	class Segmenttree
	{
		private:
			static const int N = 1000005;
			int cnt = 0;
			T s[N << 2], f[N << 2], a[N];
			void add(int k, int l, int r, T v)
			{
				f[k] += v;
				s[k] += (T)v * (r - l + 1);
				return;
			}
			void push_down(int k, int l, int r, int mid)
			{
				if (!f[k]) return;
				add(k << 1, l, mid, f[k]);
				add(k << 1 | 1, mid + 1, r, f[k]);
				f[k] = 0;
				return;
			}
		public:
			int r_cnt()
			{
				return cnt;
			}
			void push_back(T x)
			{
				a[++cnt] = x;
			}
			void xuigai(T x,int y)
			{
				a[y]=x;
			}
			void build(int k, int l, int r)
			{
				if (l == r)
				{
					s[k] = a[l];
					return;
				}
				int mid = l + r >> 1;
				build(k << 1, l, mid);
				build(k << 1 | 1, mid + 1, r);
				s[k] = s[k << 1] + s[k << 1 | 1];
				return;
			}
			void modify(int k, int l, int r, int x, int y, T v)
			{
				if (x <= l and r <= y)
				{
					return add(k, l, r, v);
				}
				int mid = l + r >> 1;
				push_down(k, l, r, mid);
				if (x <= mid)
				{
					modify(k << 1, l, mid, x, y, v);
				}
				if (y > mid)
				{
					modify(k << 1 | 1, mid + 1, r, x, y, v);
				}
				s[k] = s[k << 1] + s[k << 1 | 1];
				return;
			}
			T query(int k, int l, int r, int x, int y)
			{
				if (x <= l and r <= y)
				{
					return s[k];
				}
				int mid = (l + r) >> 1;
				T res = 0;
				push_down(k, l, r, mid);
				if (x <= mid)
				{
					res += query(k << 1, l, mid, x, y);
				}
				if (y > mid)
				{
					res += query(k << 1 | 1, mid + 1, r, x, y);
				}
				return res;
			}
	};
}
using namespace IO;
queue<int>q;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==1)
		{
			int y;
			scanf("%d",&y);
			q.push(y);
		}
		else if(x==2)
		{
			if(q.empty())
			{
				printf("ERR_CANNOT_POP\n");
			}
			else q.pop();
		}
		else if(x==3)
		{
			if(q.empty())
			{
				printf("ERR_CANNOT_QUERY\n");
			}
			else printf("%d\n",q.front());
		}
		else if(x==4)
		{
			printf("%d\n",q.size());
		}
	}
	return 0;
}