// < Global Header >
// <    ver 1.0    >
#include<bits/stdc++.h>
namespace globalhead{
	typedef unsigned long long size_t;
	
	namespace algo{
		template<typename T>lowbit(T a){return a&(-a);}
	}
	
	namespace structs{
		template<typename T>class exarr{
		private:
			size_t sz;
			size_t allsz;
			T* tag;
		protected:
			void fill(size_t putsz){
				sz=putsz;
			}
		public:
			exarr(size_t sz){
				resize(sz);
				fill(sz);
			}
			
			T& operator [](int idx){
				if(idx>(int)sz)return *(tag+sz);
				return *(tag+idx);
			}
			
			void resize(size_t nwsz){
				allsz=nwsz;
				T* tmp=new T[nwsz];
				for(int i=0;i<sz;i++){
					*(tmp+i)=*(tag+i);
				}
				delete[] tag;
				tag=tmp;
			}
			
			size_t size(){return sz;}
			
			bool empty(){return sz==0;}
			
			size_t length(){return sz;}
			
			size_t maxsize(){return allsz;}
			
			size_t maxlength(){return allsz;}
			
			void push_back(T thing){
				if(sz>=allsz){
					resize(allsz==0?1:allsz*2);
				}
				*(tag+(++sz)-1)=thing;
			}
			
			void pop_back(){
				if(sz>1)sz--;
			}
			
			T* begin(){return tag;}
			
			T* end(){return tag+sz;}
		};
		
		template<typename T>class liststack{
		private:
			size_t sz;
			struct node{
				T thing;
				node* prv;
			}bottom;
			node* tp;
		public:
			size_t size(){return sz;}
			
			size_t length(){return sz;}
			
			bool empty(){return sz==0;}
			
			void push(T thing){
				node tmp=new node;
				tmp.prv=tp;
				tmp.thing=thing;
				tp=*tmp;
			}
			
			void pop(){
				if(sz<=0)return;
				node* tmp=tp->prv;
				delete tp;
				tp=tmp;
			}
			
			T top(){
				return tp->thing;
			}
		};
	
		template<typename T>class arrstack{
		private:
			size_t sz;
			size_t allsz;
			T* tag;
		protected:
			void resize(size_t nwsz){
				T* tmp=new T[nwsz];
				for(int i=0;i<sz;i++){
					*(tmp+i)=*(tag+i);
				}
				delete[] tag;
				allsz=nwsz;
				tag=tmp;
			}
		public:
			size_t size(){return sz;}
			
			size_t length(){return sz;}
			
			bool empty(){return sz==0;}
			
			void push(T thing){
				if(sz>=allsz){
					resize(allsz==0?1:allsz*2);
				}
				*(tag+(++sz)-1)=thing;
			}
			
			void pop(){
				if(sz>0)sz--;
			}
			
			T top(){
				return *(tag+sz-1);
			}
		};
	
		template<typename T>class dearr{
			// wait to do
		};
	}
}