#include <cstdio>
#include <string>
using namespace std;
char buf;
int signbuf;
/* Read a non-space char. */
inline char xchar() { while (buf = getchar(), isspace(buf)); return buf; }
/* Read an SIGNED int. */
inline int xint() { while (buf = getchar(), (buf < '0' || buf > '9') && buf != '-'); int x = (buf == '-' ? 0 : buf - '0'); signbuf = (buf == '-' ? -1 : 1); for (; buf = getchar(), buf >= '0' && buf <= '9'; x = x * 10 + buf - '0'); return signbuf * x; }
/* Read an int IGNORING THE SIGN. */
inline int xuint() { while (buf = getchar(), buf < '0' || buf > '9'); int x = buf - '0'; for (; buf = getchar(), buf >= '0' && buf <= '9'; x = x * 10 + buf - '0'); return x; }
/* Read an SIGNED int64. */
inline long long xll() { while (buf = getchar(), (buf < '0' || buf > '9') && buf != '-'); long long x = (buf == '-' ? 0 : buf - '0'); signbuf = (buf == '-'); for (; buf = getchar(), buf >= '0' && buf <= '9'; x = x * 10 + buf - '0'); return signbuf * x; }
/* Read an int64 IGNORING THE SIGN. */
inline long long xull() { while (buf = getchar(), buf < '0' || buf > '9'); long long x = buf - '0'; for (; buf = getchar(), buf >= '0' && buf <= '9'; x = x * 10 + buf - '0'); return x; }
/* Read a string separated by SPACE, or NEWLINE. */
inline string xstring() { while (buf = getchar(), buf == ' ' || buf == '\n'); string x = ""; for (x += buf; buf = getchar(), buf != ' ' && buf != '\n' && buf != '\r'; x += buf); return x; }
/* Read a single line IGNORING LEADING SPACES. */
inline string xline() { while (buf = getchar(), buf == ' ' || buf == '\n'); string x = ""; for (x += buf; buf = getchar(), buf != '\n' && buf != '\r'; x += buf); return x; }