inline int read() {
int x = 0, w = 0;
char ch = getchar();
while (ch > '9' || ch < '0') {
w |= ch == '-';
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -x : x;
}