Fast Read and Write

char buf[1 << 20], *p1, *p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
// Don't use this with file IO!
//#define getchar gc

template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    T f = 1;
    while (ch < 48 || ch > 57) {
        if (ch == 45) {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) {
        x = (x << 1) + (x << 3) + (ch ^ 48); // 此处因为每个字符对应的数字都小于 10 所以可以用异或
        ch = getchar();
    }
    x *= f;
}

template<typename T, typename ...Ts>
void read(T &x, Ts &...args) {
    read(x);
    read(args...);
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar(45);
        x = -x;
    }
    static int sta[40];
    int top = 0;
    do {
        sta[top++] = x % 10;
        x /= 10;
    }
    while (x);
    while (top) {
        putchar(sta[--top] | 48); // 此处因为每个数字都小于 10 所以可以用或
    }
}

template<typename T, typename ...Ts>
void write(T arg, Ts ...args) {
    write(arg);
    if (sizeof...(args)) {
        putchar(32);
        write(args...);
    }
}