inline char readchar(){
    static const int bufsize = 1 << 16;
    static int p = 0, end = 0;
    static char buf[bufsize];
    if (p == end)
        end = fread_unlocked(buf, sizeof(char), bufsize, stdin), p = 0;
    return p == end ? EOF : buf[p++];
}
template<typename T> inline void read(T& a){
    static char p;
    static bool b;
    while (!isdigit(p = readchar()))
        b = p == '-'; a = p ^ '0';
    while (isdigit(p = readchar()))
        a *= 10, a += p ^ '0';
    (b ? a *= -1 : 0);
    b = p == '-';
}
inline void R(){} template<class T1, class... T2> inline void R(T1 &h, T2 &... e){read(h), R(e...);}