char buf[1<<20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? 0 : *p1 ++ )
template<typename T>
inline void readT(T &x){
    bool f = 1;
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = !f;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x = (f ? x : -x);
    return;
}
inline void read128(__int128 &x){
    bool f = 1;
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = !f;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x = (f ? x : -x);
    return;
}

namespace IO {
    const int MAX = 1 << 20;
    char buf[MAX], *p1, *p2;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAX, stdin), p1 == p2) ? EOF : *p1++)

    int read() {
        int x = 0, f = 1;
        char c = gc();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = gc();
        }
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        return f * x;
    }

    char pbuf[MAX];
    int p2 = -1;

    inline void flush() {
        fwrite(pbuf, 1, p2 + 1, stdout);
        p2 = -1;
    }

    inline void write(int x) {
        if (p2 > 1 << 20) flush();
        if (x < 0) pbuf[++p2] = '-', x = -x;
        int p = 0;
        char a[20];
        do {
            a[++p] = x % 10 + '0';
        } while (x /= 10);
        do {
            pbuf[++p2] = a[p];
        } while (--p);
        pbuf[++p2] = '\n';  // 根据需要修改
    }
} // namespace IO

namespace IO {
    const int MAX = 1 << 20;
    char buf[MAX], *p1, *p2;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAX, stdin), p1 == p2) ? EOF : *p1++)

    int read() {
        int x = 0, f = 1;
        char c = gc();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = gc();
        }
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        return f * x;
    }

    char pbuf[MAX];
    int p2 = -1;

    inline void write(int x) {
        if (x < 0) pbuf[++p2] = '-', x = -x;
        int p = 0;
        char a[20];
        do {
            a[++p] = x % 10 + '0';
        } while (x /= 10);
        do {
            pbuf[++p2] = a[p];
        } while (--p);
        // pbuf[++p2] = '\n';  // 根据需要添加换行符

        if (p2 > MAX - 32) {  // 留出一些空间以防溢出
            fwrite(pbuf, 1, p2 + 1, stdout);
            p2 = -1;
        }
    }
} // namespace IO

namespace IO {
    const int MAX = 1 << 20;
    char buf[MAX], *p1, *p2;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAX, stdin), p1 == p2) ? EOF : *p1++)

    int read() {
        int x = 0, f = 1;
        char c = gc();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = gc();
        }
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        return f * x;
    }

    char pbuf[MAX];
    int p2 = -1;

    inline void flush() {
        fwrite(pbuf, 1, p2 + 1, stdout);
        p2 = -1;
    }

    inline void write(int x) {
        if (x < 0) pbuf[++p2] = '-', x = -x;
        int p = 0;
        char a[20];
        do {
            a[++p] = x % 10 + '0';
        } while (x /= 10);
        while (p) pbuf[++p2] = a[p--];
        // pbuf[++p2] = '\n';  // 根据需要添加换行符

        if (p2 > MAX - 32) {  // 留出一些空间以防溢出
            flush();
        }
    }
} // namespace IO

namespace IO {
    const int MAX = 1 << 20;
    char buf[MAX], *p1 = buf, *p2 = buf;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAX, stdin), p1 == p2) ? EOF : *p1++)

    int read() {
        int x = 0, f = 1;
        char c = gc();
        while (!isdigit(c)) {
            if (c == '-') f = -1;
            c = gc();
        }
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        return f * x;
    }

    char pbuf[MAX];
    int p2 = -1;

    inline void flush() {
        fwrite(pbuf, 1, p2 + 1, stdout);
        p2 = -1;
    }

    inline void write(int x) {
        if (x < 0) pbuf[++p2] = '-', x = -x;
        char *start = pbuf + p2 + 1;
        do {
            *++p2 = x % 10 + '0';
        } while (x /= 10);
        std::reverse(start, pbuf + p2 + 1);
        // pbuf[++p2] = '\n';  // 根据需要添加换行符

        if (p2 > MAX - 32) {  // 留出一些空间以防溢出
            flush();
        }
    }
} // namespace IO