// NOTE: arguments to functions like `putnum` and `putch` must be a throwaway variable
#define INPUT_SZ  (1 << 22)
#define OUTPUT_SZ (1 << 20)
char _i[INPUT_SZ], _o[OUTPUT_SZ], __[20], _, _c; int _i0, _o0, _n;
#define readio() { fread(_i, 1, INPUT_SZ, stdin); }
#define writeio() { fwrite(_o, 1, _o0, stdout); }
#define scan(x) { x = (_c = _i[_i0++]) != 45 ? _c : _i[_i0++]; for (x &= 15; 47 < (_ = _i[_i0++]); x = x * 10 + (_ & 15)); if (_c < 46) x = -x; }
#define scanu(x) { for (x = _i[_i0++] & 15; 47 < (_ = _i[_i0++]); x = x * 10 + (_ & 15)); }
#define putnum(x) { if (x < 0) { _o[_o0++] = '-'; x = -x; } _ = 0; do __[_++] = x % 10 | '0'; while (x /= 10); while (_--) _o[_o0++] = __[_]; }
#define putnumu(x) { _ = 0; do __[_++] = x % 10 | '0'; while (x /= 10); while (_--) _o[_o0++] = __[_]; }
#define putstr(x) { _n = strlen(x); memcpy(_o + _o0, x, _n), _o0 += _n; }
#define putch(x) { _o[_o0++] = x; }

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(); 
    } 
}