struct IO{
    char inbuf[30*1048576]; int p;
    char outbuf[10*1048576]; int q;
    void init(){ fread(inbuf,1,sizeof(inbuf),stdin); }
    void done(){ fwrite(outbuf,1,q,stdout); }
    template<typename T> T getint(){
        T r=0;
        while(inbuf[p]<'0'||inbuf[p]>'9') p++;
        while(inbuf[p]>='0'&&inbuf[p]<='9') r=r*10+inbuf[p]-'0',p++;
        return r;
    }
    IO& operator>>(int& x) { x=getint<int>();  return *this; }
    IO& operator>>(long& x){ x=getint<long>(); return *this; }
    template<typename T> void putint(T x){
        char tmp[20]; int i=0;
        if(!x) tmp[i++]='0';
        else{
            while(x) tmp[i++]=x%10+'0',x/=10;
        }
        reverse(tmp,tmp+i);
        copy_n(tmp,i,outbuf+q),q+=i;
    }
    void putchar(char c){ outbuf[q++]=c; }
    IO& operator<<(int x) { putint(x); return *this; }
    IO& operator<<(long x){ putint(x); return *this; }
    IO& operator<<(char c){ putchar(c); return *this; }
} io;