int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}

ll read_ll() {
    char c;
    ll ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}