#define INPUT_SIZE 1<<22
#define OUTPUT_SIZE 1<<22
int _i0=0, _o0=0;
char _, _n, __[20], _i[INPUT_SIZE],_o[OUTPUT_SIZE];
#define readin fread(_i, 1, INPUT_SIZE, stdin)
#define writeout fwrite(_o, 1, _o0, stdout)
#define scanu(x) do{while((_=_i[_i0++])<48);for(x=_-48;47<(_=_i[_i0++]);x=x*10+_-48);}while(0)
#define scan(x) do{while((_n=_i[_i0++])<45);if(_n-45)x=_n;else x=_i[_i0++];for(x-=48;47<(_=_i[_i0++]);x=x*10+_-48);if(_n<46)x=-x;}while(0)
#define scanch(x) do{x=_i[_i0++];}while(0)
#define scanch2(x) do{while((_=_i[_i0++])<33);x=_;}while(0)
#define scanstr(s) do{while((_=_i[_i0++])<33);s=_;while(32<(_=_i[_i0++]))s+=_;}while(0)
inline void putnumu(int x) {_=0;do __[_++]=x%10;while(x/=10);while(_--)_o[_o0++]=__[_]+'0';}
inline void putnum(int x) {if(x<0){_o[_o0++]='-';x=-x;}_=0;do __[_++]=x%10;while(x/=10);while(_--)_o[_o0++]=__[_]+'0';}
inline void putnumll(long long x) {if(x<0){_o[_o0++]='-';x=-x;}_=0;do __[_++]=x%10;while(x/=10);while(_--)_o[_o0++]=__[_]+'0';}
inline void putnumull(long long x) {_=0;do __[_++]=x%10;while(x/=10);while(_--)_o[_o0++]=__[_]+'0';}
inline void putstr(std::string s) {for(int i=0;i<int(s.size());i++)_o[_o0++]=s[i];}
inline void putch(char c) {_o[_o0++]=c;}
#define putnl _o[_o0++]='\n'

static class Reader { 
    final private int BUFFER_SIZE = 1 << 16; 
    private DataInputStream din; 
    private byte[] buffer; 
    private int bufferPointer, bytesRead; 

    public Reader() { 
        din = new DataInputStream(System.in); 
        buffer = new byte[BUFFER_SIZE]; 
        bufferPointer = bytesRead = 0; 
    } 

    public Reader(String file_name) throws IOException { 
        din = new DataInputStream(new FileInputStream(file_name)); 
        buffer = new byte[BUFFER_SIZE]; 
        bufferPointer = bytesRead = 0; 
    } 

    public String read() throws IOException {
        byte[] ret = new byte[64];
        int idx = 0;
        byte c = Read();
        while (c <= ' ') {
            c = Read();
        }
        do {
            ret[idx++] = c;
            c = Read();
        } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
        return new String(ret, 0, idx);
    }

    public String readLine() throws IOException { 
        byte[] buf = new byte[64];
        int cnt = 0, c; 
        while ((c = Read()) != -1) { 
            if (c == '\n') 
                break; 
            buf[cnt++] = (byte) c; 
        } 
        return new String(buf, 0, cnt); 
    } 

    public int nextInt() throws IOException { 
        int ret = 0; 
        byte c = Read(); 
        while (c <= ' ') 
            c = Read(); 
        boolean neg = (c == '-'); 
        if (neg) 
            c = Read(); 
        do { 
            ret = ret * 10 + c - '0'; 
        }  while ((c = Read()) >= '0' && c <= '9'); 
        return neg ? -ret : ret;
    } 

    public long nextLong() throws IOException { 
        long ret = 0; 
        byte c = Read(); 
        while (c <= ' ') 
            c = Read(); 
        boolean neg = (c == '-'); 
        if (neg) 
            c = Read(); 
        do { 
            ret = ret * 10 + c - '0'; 
        } while ((c = Read()) >= '0' && c <= '9'); 
        return neg ? -ret : ret;
    } 

    public double nextDouble() throws IOException {
        double ret = 0, div = 1; 
        byte c = Read(); 
        while (c <= ' ') 
            c = Read(); 

        boolean neg = (c == '-'); 
        if (neg) 
            c = Read(); 

        do { 
            ret = ret * 10 + c - '0'; 
        } while ((c = Read()) >= '0' && c <= '9'); 

        if (c == '.')
            while ((c = Read()) >= '0' && c <= '9')
                ret += (c - '0') / (div *= 10); 

        return neg ? -ret : ret;
    } 

    private void fillBuffer() throws IOException {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
        if (bytesRead == -1) 
            buffer[0] = -1; 
    } 

    private byte Read() throws IOException {
        if (bufferPointer == bytesRead) 
            fillBuffer(); 
        return buffer[bufferPointer++]; 
    } 

    public void close() throws IOException { 
        if (din == null) 
            return; 
        din.close(); 
    } 
}