#include <cstdio>
#include <cctype>

class BufferedFastIO {
public:
    static const size_t bufsize = 1 << 20;

protected:
    char buf[bufsize], *p1, *p2;
    char outbuf[bufsize], *po;

    char readchar() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, bufsize, stdin);
        return p1 == p2 ? EOF : *p1++;
    }


public:
    BufferedFastIO() { p1 = p2 = buf; po = outbuf; }
    virtual ~BufferedFastIO() { this->flush(); }

    template <typename T>
    int readint(T& val) {
        char ch;
        bool neg = false;

        for (ch = readchar(); !isdigit(ch); ch = readchar()) {
            if (ch == '-') neg = !neg;
            if (ch == EOF) return EOF;
        }

        for (; isdigit(ch); ch = readchar())
            val = val * 10 + (ch - '0');

        if (neg)
            val = -val;

        return 1;
    }

    void printchar(char ch) {
        if (po - outbuf == bufsize) fwrite(outbuf, 1, bufsize, stdout);
        *po++ = ch;
    }

    template <typename T>
    void printint(T val) {
        if (val < 0) {
            printchar('-');
            val = -val;
        }

        static int stk[40];
        int top = 0;

        do {
            stk[top++] = val % 10;
            val /= 10;
        } while (val);

        while (top) printchar(stk[--top] + '0');
    }

    void flush() { fwrite(outbuf, 1, bufsize, stdout); }
};