233333333333

inline int () {
    static const int L = 1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

inline int re() 
{ 
    static int ch=0; 
    bool f=0; 
    while(!isdigit(ch=getc())) if(ch==’-‘) f=1; 
    int num=ch-‘0’; 
    while(isdigit(ch=getc())) num=(num<<3)+(num<<1)+ch-‘0’; 
    return f?-num:num; 
}

#define reg register
#define fok (ch!=EOF)
#define sep (ch==' '||ch=='n'||ch=='t')
#define dsep !isdigit(ch)
#define neq(a,b) ((a)-(b)>1e-6)
using namespace std;
struct FastIO{
    char rbuf[1000002],wbuf[1000002],b,*p1,*p2;
    int rs,ws,S;
    FastIO(){p1=rbuf,p2=wbuf,S=1000000,rs=1000000,ws=-1,b=1;}
    inline void go(){fwrite(wbuf,1,ws+1,stdout)?ws=-1:0;}
    inline char getch(){
        return rs==S&&
        (p1=rbuf,rs=-1,(S=fread(rbuf,1,S+1,stdin)-1)==-1)?
        (b=0,EOF):(++rs,*p1++);
    }
    inline void putch(int x){
        ws==1000000&&
        (p2=wbuf,ws=-1,fwrite(wbuf,1,1000001,stdout)),++ws,*p2++=x;
    }
    inline void puts(char str[]){
        for(reg int i=0;str[i]!='