Fast IO
新的
#include<algorithm>
#include<cassert>
#include<complex>
#include<cstring>
#include<memory>
#include<string>
#include<vector> // need to include
using namespace std;template<class T>struct is_iterator{template<class U,typename enable_if<!is_convertible<U,const char*>::value,int>::type=0>constexpr static auto has_indirection(int)->decltype(*declval<U>(),bool()){return true;}template<class>constexpr static bool has_indirection(long){return false;}constexpr static bool value=has_indirection<T>(0);};using uint=unsigned int;const uint BUFFER_SIZE=1<<12;const uint MAX_LENGTH=1<<7;namespace Detail{struct Width{uint value;};struct Fill{char value;};struct Base{uint value;};struct Precision{uint value;};struct Delimiter{const char*value;};}Detail::Width setWidth(uint value=0){return{value};}Detail::Fill setFill(char value=' '){return{value};}Detail::Base setBase(uint value=10){assert(2<=value&&value<=36);return{value};}Detail::Precision setPrecision(uint value=9){assert(value<MAX_LENGTH);return{value};}Detail::Delimiter setDelimiter(const char*value=" "){return{value};}class InputDevice{protected:const char*head;const char*tail;InputDevice(const char*head,const char*tail):head(head),tail(tail),base(setBase().value){}virtual void fillInput()=0;inline char nextChar(){if(__builtin_expect(head>=tail,false))fillInput();return*head++;}template<class I>int readUnsignedIntGeneral(I&arg,char c){I value=0;int length=0;for(;;++length,c=nextChar()){if(isDigit(c))c-='0';else if(isUpper(c))c-='A'-10;else if(isLower(c))c-='a'-10;else c=base;if(c>=base)break;value=base*value+c;}arg=value;return--head,length;}template<class I>inline int readUnsignedInt(I&arg,char c){if(__builtin_expect(base>10,false))return readUnsignedIntGeneral(arg,c);I value=0;int length=0;for(;static_cast<unsigned char>(c-'0')<base;++length,c=nextChar())value=base*value+c-'0';arg=value;return--head,length;}template<class I>inline bool readSignedInt(I&arg,char c){bool negative=c=='-';if(negative)c=nextChar();typename make_unsigned<I>::type unsignedArg;if(readUnsignedInt(unsignedArg,c)==0)return false;arg=negative?~static_cast<I>(unsignedArg-1):static_cast<I>(unsignedArg);return true;}template<class F>bool readFloatingPoint(F&arg,char c){bool negative=c=='-';if(negative)c=nextChar();unsigned long long integerPart;if(readUnsignedInt(integerPart,c)==0)return false;arg=static_cast<F>(integerPart);if(nextChar()=='.'){unsigned long long fractionalPart=0;int fractionalLength=readUnsignedInt(fractionalPart,nextChar());if(fractionalLength>0){unsigned long long basePower=1;for(;fractionalLength;--fractionalLength)basePower*=base;arg+=static_cast<F>(fractionalPart)/basePower;}}else--head;if(negative)arg=-arg;return true;}public:uint base;InputDevice(InputDevice const&)=delete;InputDevice&operator=(InputDevice const&)=delete;static inline bool isSpace(char c){return static_cast<unsigned char>(c-'\t')<5||c==' ';}static inline bool isDigit(char c){return static_cast<unsigned char>(c-'0')<10;}static inline bool isUpper(char c){return static_cast<unsigned char>(c-'A')<26;}static inline bool isLower(char c){return static_cast<unsigned char>(c-'a')<26;}static inline bool isOneOf(char c,const char*str){return strchr(str,c)!=nullptr;}void putBack(){--head;}inline bool readChar(char&arg){if(__builtin_expect(head>=tail,false)){fillInput();if(__builtin_expect(head>=tail,false))return arg='\0',false;}return arg=*head++,true;}template<class UnaryPredicate>inline char skipCharacters(UnaryPredicate isSkipped){char c;do{c=nextChar();}while(isSkipped(c));return c;}inline char skipCharacters(){return skipCharacters(isSpace);}template<class UnaryPredicate>inline int readString(char*arg,int limit,UnaryPredicate isTerminator){skipCharacters(isTerminator);int charsRead=0;for(--head,--limit;head<tail;fillInput()){ptrdiff_t chunkSize=find_if(head,min(tail,head+limit-charsRead),isTerminator)-head;arg=copy_n(head,chunkSize,arg);head+=chunkSize;charsRead+=chunkSize;if(chunkSize==0||head<tail)break;}return*arg='\0',charsRead;}inline int readString(char*arg,int limit,const char*terminators){if(!*terminators)return readString(arg,limit,InputDevice::isSpace);return readString(arg,limit,[terminators](char c){return InputDevice::isOneOf(c,terminators);});}inline bool read(Detail::Base newBase){base=newBase.value;return true;}inline bool read(){return true;}inline bool read(char&arg){return readChar(arg);}template<class I>inline typename enable_if<is_integral<I>::value&&is_unsigned<I>::value,bool>::type read(I&arg){return readUnsignedInt(arg,skipCharacters())>0;}template<class I>inline typename enable_if<is_integral<I>::value&&is_signed<I>::value,bool>::type read(I&arg){return readSignedInt(arg,skipCharacters());}template<class F>inline typename enable_if<is_floating_point<F>::value,bool>::type read(F&arg){return readFloatingPoint(arg,skipCharacters());}inline bool read(const char&arg){skipCharacters([arg](char c){return arg!=c;});return true;}inline bool read(const char*arg){if(*arg)skipCharacters([arg](char c){return InputDevice::isOneOf(c,arg);});else skipCharacters();return putBack(),true;}inline bool read(bool(*isSkipped)(char)){skipCharacters(isSkipped);putBack();return true;}template<class I,class Terminator,class...Ts>inline typename enable_if<is_integral<I>::value,bool>::type read(char*arg,I limit,Terminator terminator,Ts&&...args){readString(arg,static_cast<int>(limit),terminator);return read(forward<Ts>(args)...);}template<class I>inline typename enable_if<is_integral<I>::value,bool>::type read(char*arg,I limit){return read(arg,limit,"");}template<class...Ts>inline bool read(char*first,char*last,Ts&&...args){return read(first,static_cast<int>(last-first),forward<Ts>(args)...);}template<int N,class...Ts>inline bool read(char(&arg)[N],Ts&&...args){return read(static_cast<char*>(arg),N,forward<Ts>(args)...);}template<class Terminator,class...Ts>inline bool read(string&arg,Terminator terminator,Ts&&...args){for(int length=16,last=0;;last+=length,length<<=1){arg.resize(last+length);int charsRead=readString(&arg[last],length+1,terminator);if(charsRead<length){arg.resize(last+charsRead);return read(forward<Ts>(args)...);}}}inline bool read(string&arg){return read(arg,"");}template<class T1,class T2>inline bool read(pair<T1,T2>&arg){return read(arg.first,arg.second);}template<class T>inline bool read(complex<T>&arg){T real,imag;if(!read(real,imag))return false;arg.real(real),arg.imag(imag);return true;}template<class T>inline bool read(vector<T>&arg){uint n;if(!read(n))return false;arg.resize(n);return read(arg.begin(),arg.end());}template<class Iterator,class...Ts>inline typename enable_if<is_iterator<Iterator>::value,bool>::type read(Iterator first,Iterator last,Ts&&...args){for(;first!=last;++first)if(!read(*first))return false;return read(forward<Ts>(args)...);}template<class Iterator,class I,class...Ts>inline typename enable_if<is_iterator<Iterator>::value&&is_integral<I>::value,bool>::type read(Iterator first,I count,Ts&&...args){return read(first,first+count,forward<Ts>(args)...);}template<class T>inline auto read(T&arg)->decltype(arg.read(*this)){return arg.read(*this);}template<class T0,class T1,class...Ts>inline typename enable_if<!is_iterator<T0>::value&&!is_convertible<T0,char*>::value,bool>::type read(T0&&arg0,T1&&arg1,Ts&&...args){return read(forward<T0>(arg0))&&read(forward<T1>(arg1),forward<Ts>(args)...);}};class InputFile:public InputDevice{FILE*file;bool lineBuffered;bool owner;char buffer[BUFFER_SIZE];void fillInput()override{head=buffer;*buffer='\0';if(__builtin_expect(!lineBuffered,true)){tail=head+fread(buffer,1,BUFFER_SIZE,file);}else{tail=head;if(fgets(buffer,BUFFER_SIZE,file))while(*tail)++tail;}}public:InputFile(FILE*file=stdin,bool lineBuffered=true,bool takeOwnership=false):InputDevice(buffer,buffer),file(file),lineBuffered(lineBuffered),owner(takeOwnership){}InputFile(const char*fileName):InputFile(fopen(fileName,"r"),false,true){}~InputFile(){if(owner)fclose(file);}};class InputString:public InputDevice{void fillInput()override{while(*tail)++tail;}public:InputString(const string&s):InputDevice(s.data(),s.data()+s.size()){}InputString(const char*s):InputDevice(s,s+strlen(s)){}};class OutputDevice{protected:char buffer[BUFFER_SIZE+MAX_LENGTH];char*output;char*end;bool separate;OutputDevice():output(buffer),end(buffer+BUFFER_SIZE+MAX_LENGTH),separate(false),width(setWidth().value),fill(setFill().value),base(setBase().value),precision(setPrecision().value),delimiter(setDelimiter().value){computeBasePower();}virtual void writeToDevice(uint count)=0;inline void flushMaybe(){if(__builtin_expect(output>=buffer+BUFFER_SIZE,false)){writeToDevice(BUFFER_SIZE);output=copy(buffer+BUFFER_SIZE,output,buffer);}}void computeBasePower(){basePower=1;for(uint i=0;i<precision;++i)basePower*=base;}template<class I>inline char*writeUnsignedInt(I arg,char*last){if(__builtin_expect(arg==0,false))*--last='0';if(__builtin_expect(base==10,true)){for(;arg;arg/=10)*--last='0'+arg%10;}else for(;arg;arg/=base){I digit=arg%base;*--last=digit<10?'0'+digit:'A'-10+digit;}return last;}template<class I>inline char*writeSignedInt(I arg,char*last){auto unsignedArg=static_cast<typename make_unsigned<I>::type>(arg);if(arg<0){last=writeUnsignedInt(~unsignedArg+1,last);*--last='-';return last;}return writeUnsignedInt(unsignedArg,last);}template<class F>char*writeFloatingPoint(F arg,char*last){bool negative=signbit(arg);if(negative)arg=-arg;if(isnan(arg))for(int i=0;i<3;++i)*--last=i["NaN"];else if(isinf(arg))for(int i=0;i<3;++i)*--last=i["fnI"];else{auto integerPart=static_cast<unsigned long long>(arg);auto fractionalPart=static_cast<unsigned long long>((arg-integerPart)*basePower+F(0.5));if(fractionalPart>=basePower)++integerPart,fractionalPart=0;char*point=last-precision;if(precision>0){::fill(point,writeUnsignedInt(fractionalPart,last),'0');*--point='.';}last=writeUnsignedInt(integerPart,point);}if(negative)*--last='-';return last;}inline int writeT(char*first){int delimiterLenght=separate?writeDelimiter():0;separate=true;uint charsWritten=static_cast<uint>(end-first);if(__builtin_expect(charsWritten<width,false))charsWritten+=writeFill(width-charsWritten);output=copy(first,end,output);flushMaybe();return delimiterLenght+static_cast<int>(charsWritten);}inline int writeFill(uint count){int charsWritten=static_cast<int>(count);if(__builtin_expect(output+count+MAX_LENGTH<end,true)){if(count==1)*output++=fill;else output=fill_n(output,count,fill);}else for(uint chunkSize=static_cast<uint>(buffer+BUFFER_SIZE-output);;chunkSize=BUFFER_SIZE){if(chunkSize>count)chunkSize=count;output=fill_n(output,chunkSize,fill);flushMaybe();if((count-=chunkSize)==0)break;}return charsWritten;}public:uint width;char fill;uint base;uint precision;unsigned long long basePower;string delimiter;OutputDevice(OutputDevice const&)=delete;OutputDevice&operator=(OutputDevice const&)=delete;virtual~OutputDevice(){};inline int writeChar(char arg){separate=false;*output++=arg;flushMaybe();return 1;}inline int writeString(const char*arg,size_t length,bool checkWidth=true){separate=false;uint count=static_cast<uint>(length);int charsWritten=static_cast<int>(count)+(checkWidth&&count<width?writeFill(width-count):0);if(__builtin_expect(output+count+MAX_LENGTH<end,true)){if(count==1)*output++=*arg;else output=copy_n(arg,count,output);}else for(uint chunkSize=static_cast<uint>(buffer+BUFFER_SIZE-output);;chunkSize=BUFFER_SIZE){if(chunkSize>count)chunkSize=count;output=copy_n(arg,chunkSize,output);flushMaybe();if((count-=chunkSize)==0)break;arg+=chunkSize;}return charsWritten;}inline int writeDelimiter(){return writeString(delimiter.c_str(),delimiter.size(),false);}inline void flush(){writeToDevice(static_cast<uint>(output-buffer));output=buffer;}inline int write(Detail::Width newWidth){width=newWidth.value;return 0;}inline int write(Detail::Fill newFill){fill=newFill.value;return 0;}inline int write(Detail::Base newBase){base=newBase.value;computeBasePower();return 0;}inline int write(Detail::Precision newPrecision){precision=newPrecision.value;computeBasePower();return 0;}inline int write(Detail::Delimiter newDelimiter){delimiter=newDelimiter.value;return 0;}inline int write(){return 0;}inline int write(char arg){return writeChar(arg);}template<class I>inline typename enable_if<is_integral<I>::value&&is_unsigned<I>::value,int>::type write(I arg){return writeT(writeUnsignedInt(arg,end));}template<class I>inline typename enable_if<is_integral<I>::value&&is_signed<I>::value,int>::type write(I arg){return writeT(writeSignedInt(arg,end));}template<class F>inline typename enable_if<is_floating_point<F>::value,int>::type write(F arg){return writeT(writeFloatingPoint(arg,end));}inline int write(const char*arg){return writeString(arg,strlen(arg));}template<int N>inline int write(char(&arg)[N]){return writeString(arg,strlen(arg));}inline int write(const string&arg){return writeString(arg.c_str(),arg.size());}template<class T1,class T2>inline int write(const pair<T1,T2>&arg){int charsWritten=write(arg.first);charsWritten+=writeDelimiter();return charsWritten+write(arg.second);}template<class T>inline int write(const complex<T>&arg){return write(real(arg),imag(arg));}template<class Iterator,class...Ts>inline typename enable_if<is_iterator<Iterator>::value,int>::type write(Iterator first,Iterator last,Ts&&...args){int charsWritten=0;for(;first!=last;charsWritten+=++first==last?0:writeDelimiter())charsWritten+=write(*first);return charsWritten+write(forward<Ts>(args)...);}template<class Iterator,class I,class...Ts>inline typename enable_if<is_iterator<Iterator>::value&&is_integral<I>::value,int>::type write(Iterator first,I count,Ts&&...args){return write(first,first+count,forward<Ts>(args)...);}template<class T>inline auto write(const T&arg)->decltype(arg.write(*this)){return arg.write(*this);}template<class T0,class T1,class...Ts>inline typename enable_if<!is_iterator<T0>::value,int>::type write(T0&&arg0,T1&&arg1,Ts&&...args){int charsWritten=write(forward<T0>(arg0));return charsWritten+write(forward<T1>(arg1),forward<Ts>(args)...);}};class OutputFile:public OutputDevice{FILE*file;bool owner;void writeToDevice(uint count)override{fwrite(buffer,1,count,file);fflush(file);}public:OutputFile(FILE*file=stdout,bool takeOwnership=false):file(file),owner(takeOwnership){}OutputFile(const char*fileName):OutputFile(fopen(fileName,"w"),true){}~OutputFile()override{flush();if(owner)fclose(file);}};class OutputString:public OutputDevice{string&str;void writeToDevice(uint count)override{str.append(buffer,count);}public:OutputString(string&str):OutputDevice(),str(str){}~OutputString()override{flush();}};unique_ptr<InputDevice>input;unique_ptr<OutputDevice>output;template<class...Ts>inline bool read(Ts&&...args){return input->read(forward<Ts>(args)...);}template<class...Ts>inline int write(Ts&&...args){return output->write(forward<Ts>(args)...);}template<class...Ts>inline int writeln(Ts&&...args){return write(forward<Ts>(args)...,'\n');}void flush(){output->flush();}
#ifdef ONLINE_JUDGE
input.reset(new InputFile(stdin, false)); // usual problem
input.reset(new InputFile()); // interactive problem
output.reset(new OutputFile());
#else
input.reset(new InputFile()); // local testing using a console
input.reset(new InputFile("input.txt")); // local testing using a file
output.reset(new OutputFile()); // output to console
output.reset(new OutputFile("output.txt")); // output to a file
#endif
how to use
压个行
namespace Fread { const int SIZE = (1 << 18); char buf[SIZE], *p1 = buf, *p2 = buf; inline char getchar() {return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);} }
namespace Fwrite { const int SIZE = (1 << 18); char buf[SIZE], *S = buf, *T = buf+SIZE; inline void flush(){ fwrite(buf, 1, S-buf, stdout), S = buf; } struct NTR{ ~NTR() { flush(); } }ztr;inline void putchar(char c){ *S++ = c; if(S == T) flush(); } }
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{ template <typename T> Reader & operator >> (T & x) {char c = getchar(); bool f = false;while (c < '0' or c > '9') { if (c == '-') f = true;c = getchar();} x = 0;while(c >= '0' and c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} if (f) x = -x;return *this;}Reader&operator>>(char&c){ c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){ int len=0;char c=getchar(); while(c=='\n'||c==' '||c=='\r')c=getchar(); while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar(); str[len]='\0'; return *this;}Reader & operator >> (float & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader & operator >> (double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}Reader(){}}cin;
struct Writer{ template <typename T> Writer & operator << (T x) {if(x == 0) return putchar('0'), *this;if(x < 0) putchar('-'), x = -x;static int sta[60], top = 0; while (x) sta[++top] = x %10, x /= 10; while (top) putchar(sta[top] + '0'), --top; return *this;} Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;} typedef unsigned long long mxdouble; int precision = 6; Writer set_precision(int val) { precision = val; return *this; }template <typename T> T deal_precision(T x) {__float128 tmp = x;for(int i=0;i<=precision;i++)tmp*=10;tmp+=5;for(int i=0;i<=precision;i++) tmp/=10;return (T)tmp;}Writer&operator<<(float x){if(x<0)putchar('-'),x=-x; x=deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<=precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(double)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer(){}}cout;
} const char * endl = "\n"; const char * space = " ";
#define cin Fastio :: cin
#define cout Fastio :: cout全类型读入
/* --------------- fast io --------------- */
#includ <bits/stdc++.h>
using namespace std;
namespace Fread{
const int SIZE = (1 << 18);
char buf[SIZE],*S,*T;
inline char getchar() {
if(S==T) {
T = (S = buf) + fread(buf,1,SIZE,stdin);
if(S==T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = (1 << 18);
char buf[SIZE],*S=buf,*T=buf+SIZE;
inline void flush(){
fwrite(buf,1,S-buf,stdout), S=buf;
}
inline void putchar(char c){
*S++=c;
if(S==T)flush();
}
struct NTR{
~NTR() { flush(); }
}ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader & operator >> (T&x) {
char c = getchar(); bool f = false;
while (c<'0'||c>'9') {
if(c == '-')f = true;
c=getchar();
} x=0;
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
} if (f) x = -x; return *this;
}
Reader & operator >> (double & x) {
char c=getchar();short f=1,s=0;x=0;double t=0;
while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();
if(c=='.')c=getchar();else return x*=f,*this;
while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();
while(s--)t/=10.0;x=(x+t)*f;return*this;
}
Reader&operator>>(long double&x){
char c=getchar();short f=1,s=0;x=0;long double t=0;
while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();
if(c=='.')c=getchar();else return x*=f,*this;
while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();
while(s--)t/=10.0;x=(x+t)*f;return*this;
}
Reader&operator>>(__float128&x){
char c=getchar();short f=1,s=0;x=0;__float128 t=0;
while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();
if(c=='.') c = getchar();
else return x*=f, *this;
while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();
while(s--)t/=10.0;x=(x+t)*f;
return *this;
}
Reader&operator>>(char&c){
c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();
return *this;
}
Reader&operator>>(char*str){
int len=0;char c=getchar();
while(c=='\n'||c==' '||c=='\r')c=getchar();
while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();
str[len]='\0';
return *this;
}
Reader&operator>>(string&str){
char c=getchar();str.clear();
while(c=='\n'||c==' '||c=='\r')c=getchar();
while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();
return *this;
}
template<class _Tp>
Reader&operator>>(vector<_Tp>&vec){
for(unsigned i=0;i<vec.size();i++)
cin>>vec[i];
return *this;
}
template<class _Tp,class _tp>
Reader&operator>>(pair<_Tp,_tp>&a){
cin>>a.first>>a.second;
return *this;
}
Reader(){}
}cin;
const char endl='\n';
struct Writer{
static const int set_precision = 6;
typedef int mxdouble;
template<typename T>
Writer&operator<<(T x){
if(x==0)return putchar('0'),*this;
if(x<0)putchar('-'),x=-x;
static int sta[45];int top=0;
while(x)sta[++top]=x%10,x/=10;
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
Writer&operator<<(double x){
if(x<0)putchar('-'),x=-x;
mxdouble _=x;x-=(double)_;static int sta[45];int top=0;
while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');
while(top)putchar(sta[top]+'0'),--top;putchar('.');
for(int i=0;i<set_precision;i++)x*=10;
_=x;while(_)sta[++top]=_%10,_/=10;
for(int i=0;i<set_precision-top;i++)putchar('0');
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
Writer&operator<<(long double x){
if(x<0)putchar('-'),x=-x;
mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;
while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');
while(top)putchar(sta[top]+'0'),--top;putchar('.');
for(int i=0;i<set_precision;i++)x*=10;
_=x;while(_)sta[++top]=_%10,_/=10;
for(int i=0;i<set_precision-top;i++)putchar('0');
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
Writer&operator<<(__float128 x){
if(x<0)putchar('-'),x=-x;
mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;
while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');
while(top)putchar(sta[top]+'0'),--top;putchar('.');
for(int i=0;i<set_precision;i++)x*=10;
_=x;while(_)sta[++top]=_%10,_/=10;
for(int i=0;i<set_precision-top;i++)putchar('0');
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
Writer&operator<<(char c){
putchar(c);
return*this;
}
Writer& operator<<(char*str){
int cur=0;while(str[cur])putchar(str[cur++]);
return *this;
}
Writer&operator<<(const char*str){
int cur=0;while(str[cur])putchar(str[cur++]);
return *this;
}
Writer&operator<<(string str){
int st=0,ed=str.size();
while(st<ed) putchar(str[st++]);
return *this;
}
template<class _Tp>
Writer&operator<<(vector<_Tp>vec){
for(unsigned i=0;i<vec.size()-1;i++)
cout<<vec[i]<<" ";cout<<vec[vec.size()-1];
return *this;
}
template<class _Tp,class _tp>
Writer&operator<<(pair<_Tp,_tp>a){
cout<<a.first<<" "<<a.second;
return *this;
}
Writer(){}
}cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
/* --------------- fast io --------------- */如果你嫌太长
#include <bits/stdc++.h>
using namespace std;
namespace Fread{
const int SIZE = (1 << 18);
char buf[SIZE], *S, *T;
inline char getchar() {
if(S==T) {
T = (S = buf) + fread(buf,1,SIZE,stdin);
if(S==T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = (1 << 18);
char buf[SIZE], *S = buf, *T = buf+SIZE;
inline void flush(){
fwrite(buf,1,S-buf,stdout), S=buf;
}
inline void putchar(char c){
*S++=c;
if(S==T)flush();
}
struct NTR{
~NTR() { flush(); }
}ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader & operator >> (T&x) {
char c = getchar(); bool f = false;
while (c<'0'||c>'9') {
if(c == '-')f = true;
c=getchar();
} x=0;
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
} if (f) x = -x; return *this;
}
Reader&operator>>(char&c){
c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();
return *this;
}
Reader&operator>>(char*str){
int len=0;char c=getchar();
while(c=='\n'||c==' '||c=='\r')c=getchar();
while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();
str[len]='\0';
return *this;
}
Reader&operator>>(string&str){
char c=getchar();str.clear();
while(c=='\n'||c==' '||c=='\r')c=getchar();
while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();
return *this;
}
Reader(){}
}cin;
const char endl='\n';
struct Writer{
template<typename T>
Writer&operator<<(T x){
if(x==0)return putchar('0'),*this;
if(x<0)putchar('-'),x=-x;
static int sta[45];int top=0;
while(x)sta[++top]=x%10,x/=10;
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
Writer&operator<<(char c){
putchar(c);
return*this;
}
Writer&operator<<(const char*str){
int cur=0;while(str[cur])putchar(str[cur++]);
return *this;
}
Writer&operator<<(string str){
int st=0,ed=str.size();
while(st<ed) putchar(str[st++]);
return *this;
}
Writer(){}
}cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))你要是啥都不想要
#include <bits/stdc++.h>
using namespace std;
namespace Fread{
const int SIZE = (1 << 18);
char buf[SIZE], *p1 = buf, *p2 = buf;
inline char getchar() {
return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);
}
} // namespace Fread
namespace Fwrite {
const int SIZE = (1 << 18);
char buf[SIZE], *S = buf, *T = buf+SIZE;
inline void flush(){
fwrite(buf, 1, S-buf, stdout), S = buf;
}
inline void putchar(char c){
*S++ = c;
if(S == T) flush();
}
struct NTR{
~NTR() { flush(); }
}ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader & operator >> (T & x) {
char c = getchar(); bool f = false;
while (c < '0' or c > '9') {
if (c == '-') f = true;
c = getchar();
} x = 0;
while(c >= '0' and c <= '9'){
x = (x<<1)+(x<<3)+(c^48);
c = getchar();
} if (f) x = -x;
return *this;
}
Reader(){}
}cin;
const char endl='\n';
struct Writer{
template<typename T>
Writer & operator << (T x) {
if(x == 0) return putchar('0'), *this;
if(x < 0) putchar('-'), x = -x;
static int sta[45], top = 0;
while (x)
sta[++top] = x %10, x /= 10;
while (top)
putchar(sta[top] + '0'), --top;
return *this;
}
Writer(){}
}cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))