namespace fastio {
const int BUFFER_SIZE = 1 << 20;
char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE], *p1 = ibuf, *p2 = ibuf;
int pos;
int get() {
if (p1 == p2) {
p1 = ibuf;
p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
}
if (p1 == p2) return EOF;
return *p1++;
}
void flush() {
fwrite(obuf, 1, pos, stdout);
pos = 0;
}
template<typename T>
void readInt(T &obj) {
bool flag = false;
char ch = get();
while (ch < '0' || ch > '9') {
if (ch == '-') {
flag = true;
}
ch = get();
}
T x = 0;
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = get();
}
obj = (flag ? -1 : 1) * x;
}
void put(char ch) {
if (pos + 1 == BUFFER_SIZE) {
flush();
}
obuf[pos++] = ch;
}
template<typename T>
void writeInt(T x) {
if (x < 0) put('-'), x = -x;
if (x > 9) writeInt(x / 10);
put(x % 10 + '0');
}
struct _Cin {
template<typename T>
_Cin& operator>>(T &obj);
} Cin;
template<>
_Cin& _Cin::operator>>(int &obj) {
readInt(obj);
return *this;
}
template<>
_Cin& _Cin::operator>>(long long &obj) {
readInt(obj);
return *this;
}
template<>
_Cin& _Cin::operator>>(__int128 &obj) {
readInt(obj);
return *this;
}
struct _Cout {
_Cout() {
pos = 0;
}
~_Cout() {
flush();
}
template<typename T>
_Cout& operator<<(const T obj);
} Cout;
template<>
_Cout& _Cout::operator<<(const int obj) {
writeInt(obj);
return *this;
}
template<>
_Cout& _Cout::operator<<(const long long obj) {
writeInt(obj);
return *this;
}
template<>
_Cout& _Cout::operator<<(const __int128 obj) {
writeInt(obj);
return *this;
}
template<>
_Cout& _Cout::operator<<(const char* str) {
int len = strlen(str);
if (pos + len >= BUFFER_SIZE) {
flush();
}
memcpy(obuf + pos, str, len);
pos += len;
return *this;
}
template<>
_Cout& _Cout::operator<<(const string str) {
int len = str.size();
if (pos + len >= BUFFER_SIZE) {
flush();
}
memcpy(obuf + pos, str.c_str(), len);
pos += len;
return *this;
}
};
using fastio::Cin;
using fastio::Cout;