#include <iostream>
namespace IO{
    #define BUFSIZE 20000000
    #define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++)
    #define putchar(c) (p1==p2?fwrite(buf,1,p1-buf,stdout),p1=buf:0,*p1++=c)
    struct read{
        char buf[BUFSIZE],*p1,*p2,c,f;
        read():p1(buf),p2(buf){}
        read&operator>>(int&x){
            for(c=getchar(),x=f=0;c!=EOF&&!isdigit(c);c=getchar())if(c=='-')f=1;
            for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
            return x=f?-x:x,*this;
        }
        read&operator>>(char*s){
            while(isspace(*s=getchar()));
            while(!isspace(*++s=getchar())&&*s!=EOF);
            return *s='\0',*this;
        }
    }in;
    struct write{
        char buf[BUFSIZE],*p1,*p2,st[50];
        int tp;
        write():p1(buf),p2(buf+BUFSIZE){}
        ~write(){fwrite(buf,1,p1-buf,stdout),p1=buf;}
        write&operator<<(int x){
            if(x<0)putchar('-'),x=-x;
            do st[tp++]=x%10^48,x/=10;while(x);
            while(tp)putchar(st[--tp]);
            return *this;
        }
        write&operator<<(char x){return putchar(x),*this;}
        write&operator<<(char*s){
            while(!iscntrl(*s))putchar(*s++);
            if(*s=='\n')putchar(*s);
            return *this;
        }
    }out;
}
using IO::in;
using IO::out;