#define gc getchar
#define pc putchar
template < typename Type >
void read(Type &x){
    x = 0;
    bool f = 1;
    char ch = gc();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = !f;
        ch = gc();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = gc();
    }
    x = (f ? x : -x);
}
template < typename Type , typename... Args >
void read(Type &x,Args&..._x){
    read(x);
    read(_x...);
}
template < typename Type>
void write(Type x,bool f){
    if(x < 0)
        x = -x,putchar('-');
    static short sta[50] , top(0);
    do
        sta[++top] = x % 10 , x /= 10;
    while(x);
    while(top) putchar(sta[top--] | 48);
    f ? pc('\n') : pc(' ');
}