int inv(int a) {

    if(a == 1) return 1;

    return ((MOD - MOD / a) * inv(MOD % a)) % MOD;

}

int cmp(int a) {if (!a) return 0; return a < 0 ? -1 : 1;}

int cmp(int a) {return (a >> 31) + (-a >> 31 & 1);}

int abs(int x) {return x > 0 ? x : -x;}

int abs(int x) {int y = x >> 31; return (x + y) ^ y;}

x = (x == a ? b : a)

x ^ = a ^ b

//等于0返回0，大于0返回1，小于0返回-1

int sgn(double x) {

    if(fabs(x) < EPS) return 0;

    return x > 0 ? 1 : -1;

}

int sgn(double x) {

    return (x > EPS) - (x < -EPS);

}

int fastMax(int x, int y) {return (((y-x)>>(32-1))&(x^y))^y;}

int fastMin(int x, int y) {return (((y-x)>>(32-1))&(x^y))^x;}

#pragma comment(linker, "/STACK:1024000000,1024000000")

struct Reader {

    static const int MSIZE = 65536;

    char buffer[MSIZE], c;

    int l = 0, r = 0;

    char readchar() {

        if(l == r) {

            l = 0;

            r = fread(buffer, 1, MSIZE, stdin);

        }

        return buffer[l++];

    }

    int readint() {

        c = readchar();

        while(!isdigit(c)) c = readchar();

        int res = 0;

        while(isdigit(c)) res = res * 10 + c - '0', c = readchar();

        return res;

    }

} reader;