inline char get(void) {
    static char buf[1000000], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, 1000000, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
inline void read(ll &x) {
    static char c; x = 0; int sgn = 0;
    for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
    for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}