template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();} while(isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f; return; } template <typename T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); return; }