inline void read (register int &x) { x = 0; register bool f = 0; register char ch = getchar(); while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); x = f ? ~x + 1 : x; }
inline void write (register int x) { static char c[11]; register unsigned p = 0; if (x < 0) putchar ('-'), x = ~x + 1; if (!x) { putchar ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) putchar (c[p]), --p; }
template <class T, class... U> inline void read (register T &x, register U &...t) { read (x), read (t...); }
template <class T, class... U> inline void write (register T x, register U ...t) { write (x), write (t...); }