#ifndef VERY_FAST_IO3
#define VERY_FAST_IO3
#include <unistd.h>
#include<bits/stdc++.h>
namespace MTL{
using namespace std;
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
class fast_ios{
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){
return fast_ios(1ll<<30,k);
}
namespace const_val{
const long long buf_len=998732;
}
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<<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
