#ifndef VERY_FAST_IO3
#define VERY_FAST_IO3
#include <unistd.h>
#include<bits/stdc++.h>
 
namespace MTL{
	using namespace std;
	//getchar_unlocked/putchar_unlocked貌似快一点? 
	#define likely(x) __builtin_expect(!!(x), 1)
	#define unlikely(x) __builtin_expect(!!(x), 0)
	class fast_ios{//out普通操作0~9,in普通操作10~19,格式操作30~39,流修改50~59 
		long long Key_,seting;
		public:
			fast_ios(long long k,long long setin=0){
				Key_=k;seting=setin;
			}
			friend fast_ios operator|(fast_ios a,fast_ios b);
			long long operator&(long long b){
				return Key_&b;
			}
			long long get_seting(){return seting;}
	}; 
	fast_ios operator|(fast_ios a,fast_ios b){
		return fast_ios(a.Key_|b.Key_);
	}
	namespace fast_ios_base{
		const fast_ios fast_ends(1ll),fast_flush(1ll<<1),fast_endl(3ll),fast_lock(1ll<<50),fast_unlock(1ll<<51),fast_ws(1<<10),fast_out(1<<9),fast_in(1<<19),fast_append((1<<8)|(1<<9));
	} 
	const fast_ios fast_setf(long long k){//设置double精度 
		return fast_ios(1ll<<30,k);
	}
	namespace const_val{
		const long long buf_len=998732;
		//const long long buf_len=1<<16;
		//const long long fast_ios_len=2;//fast_ios的有效位数 
	}
	class fast_io{
		#define buf_len const_val::buf_len
		bool is_lock=1;
		char buf_i[buf_len],buf_o[buf_len];
		long long in_i=0,out_i=0,double_out_len=9;
		bool IO_OK=1;
		double double_out_min=1E-10,double_out_mlen=100000000;
		FILE *fastin=NULL,*fastout=NULL;
		public:
			fast_io(){
				fastin=stdin,fastout=stdout;
				in_i=buf_len;
				
			}
			fast_io(string file_name,fast_ios f=fast_ios((1<<9)|(1<<19))){
				if(f&(1<<9)){
					if(f&(1<<8))fastout=fopen((file_name+string(".out")).c_str(),"ab");
					else fastout=fopen((file_name+string(".out")).c_str(),"wb");
				}
				if(f&(1<<19))fastin=fopen((file_name+string(".in")).c_str(),"rb");
				in_i=buf_len;
			} 
			fast_io(string in_file_name,string out_file_name,fast_ios f=fast_ios((1<<9)|(1<<19))){
				if(f&(1<<9)){
					if(f&(1<<8))fastout=fopen(out_file_name.c_str(),"ab");
					else fastout=fopen((out_file_name+string(".out")).c_str(),"wb");
				}
				if(f&(1<<19))fastin=fopen(in_file_name.c_str(),"rb");
				in_i=buf_len;
			} 
			~fast_io(){
				if(fastout!=NULL)fwrite(buf_o,1,out_i,fastout);
			}
			void open(string file_name,fast_ios f){
				close(f);
				if(f&(1<<9)){
					if(f&(1<<8))fastout=fopen(file_name.c_str(),"ab");
					else fastout=fopen((file_name+string(".out")).c_str(),"wb");
				}
				if(f&(1<<19))IO_OK=1,fastin=fopen(file_name.c_str(),"rb");
			}
			void close(fast_ios f){
				if(f&(1<<9)){fflush();if(fastout!=stdout){fclose(fastout);}fastout=NULL;}
				if(f&(1<<19)){in_i=buf_len;if(fastin!=stdin){fclose(fastin);}fastin=NULL;}
			}
			void clear(fast_ios f){
				if((f&(1<<9))&&fastout!=NULL)fflush(),fseek(fastout,0,SEEK_SET);
				if((f&(1<<19))&&fastin!=NULL)IO_OK=1,in_i=buf_len,fseek(fastin,0,SEEK_SET);
			}
			void to_stdio(){
				fflush();
				fclose(fastout);
				fclose(fastin);
				fastin=stdin,fastout=stdout;
				in_i=buf_len;
				IO_OK=1;
			}
			inline void fflush(){
				if(fastout!=NULL)fwrite(buf_o,1,out_i,fastout),out_i=0;
			}
			operator bool(){
				return IO_OK;
			}
			bool eof(){
				return !IO_OK;
			}

			inline char getchar(){
				if(likely(IO_OK)&&unlikely(fastin!=NULL)){
					if(unlikely(in_i==buf_len)){
						memset(buf_i,-1,buf_len);
							fread(buf_i,1,buf_len,fastin);
							in_i=0;
					}
					if(unlikely(buf_i[in_i]==EOF||buf_i[in_i]==0)){
						IO_OK=0;	
						return EOF;
					}
					return buf_i[in_i++];
				}
				return EOF;
			}
			inline void putchar(char _Ch){
				if(unlikely(fastout==NULL))return;
					if(unlikely(out_i==buf_len))fflush();
					buf_o[out_i++]=_Ch;
				
				
			}
			char peekchar(){
				if(unlikely(!IO_OK))return EOF;
				if(unlikely(in_i==buf_len)){
					fread(buf_i,1,buf_len,fastin);
					in_i=0;	
				}
				if(unlikely(buf_i[in_i]==EOF))IO_OK=0;
				return buf_i[in_i];
			}

			template<typename T>
			fast_io& operator>>(T& x){
				char c=getchar();x=0;bool h=0;
				while((c>'9'||c<'0')&&c!=EOF)(c=='-'?h^=1:h),c=getchar();
				while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
				x=(h?-x:x);
				return *this;
			}
			template<typename T>
			fast_io& operator<<(T x){
				if(x==0){
					putchar('0');
					return *this;
				}
				if(x<0)putchar('-'),x=-x;
				T x2=0;int kk=0;
				while(x%10==0)kk++,x/=10;
				while(x)x2=(x2<<1)+(x2<<3)+x%10,x/=10;
				while(x2)putchar((x2%10)^'0'),x2/=10;
				while(kk--)putchar('0');
				return *this;
			}

			fast_io& operator>>(string& x){
				char c=getchar();x.clear();
				while((c==' '||c=='\n')&&c!=EOF)c=getchar();
				while(c!=' '&&c!='\n'&&c!=EOF)x+=c,c=getchar();
				return *this;
			}
			fast_io& operator<<(string x){
				for(int i=0;i<x.size();i++)putchar(x[i]);
				return *this;
			}
			fast_io& operator>>(char* x){
				char c=getchar();int len=strlen(x);
				memset(x,0,len);
				while((c==' '||c=='\n')&&c!=EOF)c=getchar();
				while(c!=' '&&c!='\n'&&c!=EOF)*(x++)=c,c=getchar();
				return *this;
			}
			fast_io& operator<<(const char* x){
				int len=strlen(x);
				for(int i=0;i<len;i++)putchar(x[i]);
				return *this;
			}
			fast_io& operator>>(char& c){
				c=getchar();
				while((c==' '||c=='\n')&&c!=EOF)c=getchar();
				return *this;
			}
			fast_io& operator<<(char x){
				putchar(x);
				return *this;
			}

			fast_io& operator<<(fast_ios x){
				if(x&1){putchar('\n');}
				if(x&2){fflush();}
				//if(x&(1ll<<50)){is_lock=1;}//开同步
				//if(x&(1ll<<51)){fflush(),is_lock=0;}//异步模式 
				if(x&(1ll<<30)){
					double_out_len=x.get_seting();
					double_out_mlen=pow((double)10,double(double_out_len-1));
					double_out_min=(double)(1)/double_out_mlen*0.01;
				}
				return *this;
			}
			fast_io& operator>>(fast_ios x){
				if(x&(1<<10)){
					while((peekchar()==' '||peekchar()=='\n')&&peekchar()!=EOF){getchar();}
				}
				return *this;
			}

			fast_io& operator>>(double& x){
				char c=getchar();x=0;bool h=0;long long b=0;
				while((c>'9'||c<'0')&&c!=EOF)(c=='-'?h^=1:h),c=getchar();
				while(c>='0'&&c<='9')b=(b<<3)+(b<<1)+(c^'0'),c=getchar();
				x=(h?-b:b);
				long long bb=10;
				if(c!='.')return *this;
				c=getchar();
				while(c>='0'&&c<='9'){
					x+=(h?-1:1)*(c^'0')/(double)bb;
					bb*=10;
					c=getchar();
				}
				return *this;
			}
			fast_io& operator<<(double x){
				x+=5*double_out_min;
				if(x<0)putchar('-'),x=-x;
				double x2=1;
				while(x2*x>10){
					x2/=10;
				}
				for(;x2<=1.1;x2*=10){
					putchar(char(x2*x)^'0');
					x-=int(x2*x)/x2;
				}
				
				if(fabs(x)>=double_out_min*10&&double_out_len>0)putchar('.');
				else return *this; 
				
				for(double i=0,i2=double_out_mlen;i<double_out_len;i++,i2/=10){
					x*=10;
					if(x*i2<=1)return *this;///#########################
					putchar(char(x)^'0');
					x-=int(x);
				}
				
				return *this;
			}			
	}fio;
	#undef buf_len
	#undef unlikely
	#undef likely
} 
using MTL::fast_ios_base::fast_ends;
using MTL::fast_ios_base::fast_endl;
using MTL::fast_ios_base::fast_flush;
using MTL::fast_ios_base::fast_lock;
using MTL::fast_ios_base::fast_unlock;
using MTL::fast_ios_base::fast_ws;
using MTL::fast_setf;
using MTL::fio;
using MTL::fast_io;
#define fast_ios_base MTL::fast_ios_base
#endif
04-19 08:32