namespace FastIO{
    const int BUF_COUNT=1000000,BUF_SIZ=1<<25;
    char in_buf[BUF_SIZ],*got_pos=in_buf,*read_pos=in_buf,out_buf[BUF_SIZ],*write_pos=out_buf;
    char get_next_char(){if(read_pos==got_pos){got_pos+=fread(got_pos,sizeof(char),BUF_COUNT,stdin);}return*(read_pos++);}
    void put_char(char ch){*(write_pos++)=ch;}
    void flush_output(){fwrite(out_buf,sizeof(char),write_pos-out_buf,stdout);}
    template<typename T>void read(T& res){char ch;while(!isdigit(ch=get_next_char()));res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');}
    template<typename T>void write(T x){if(!x){put_char('0');return;}static int lis[25],*lp=lis;while(x){*(++lp)=x%10;x/=10;}while(lp!=lis)put_char((*(lp--))+'0');}
    template<typename T>void writeln(const T& x){write(x);put_char('\n');}
    template<typename T>void writesp(const T& x){write(x);put_char(' ');}
    class _IO_Flusher{public:~_IO_Flusher(){flush_output();}}__Flusher;
    class IStream{public:
        template<typename T>IStream& operator>>(T& x){read(x);return *this;}
        IStream& operator>>(char* str){char ch;while(isspace(ch=get_next_char()));(*(str++))=ch;while(!isspace(ch=get_next_char())){if(ch==EOF)break;(*(str++))=ch;}return *this;}
    }Cin;
    class OStream{public:
        OStream& operator<< (const int& x){write(x);return *this;}
        OStream& operator<< (const long long& x){write(x);return *this;}
        OStream& operator<< (const char& ch){put_char(ch);return *this;}
        OStream& operator<< (const char* str){for(const char* p=str;*p;put_char(*(p++)));return *this;}
    }Cout;
}
using namespace FastIO;
#define cin Cin
#define cout Cout