#ifdef __cpp_if_constexpr
template <typename T, typename... Args>
void read(T& x, Args&... r) {
if constexpr (is_integral_v<T> && !is_same_v<decay_t<T>, char>) {
x = 0;
lli f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
} else if constexpr (is_same_v<decay_t<T>, string>) {
x.resize(buf);
char* ptr = x.data();
read(ptr);
x.resize(strlen(x.data()));
} else if constexpr (is_same_v<decay_t<T>, char*>) {
scanf("%s", x);
} else if constexpr (is_same_v<decay_t<T>, char>) {
x = getchar();
while (isspace(x)) x = getchar();
} else cin >> x;
if constexpr (sizeof...(r) > 0) read(r...);
}
#else
template<typename T>
void read(T& x) {
cin >> x;
}
template <typename T, typename... Args>
void read(T& x, Args&... r) {
read(x); read(r...);
}
#endif
template <typename T>
void read_vec(vector<T>& vec, lli n, lli offset = 1) {
vec.resize(n + offset);
for (lli i = offset; i < n + offset; ++i)
read(vec[i]);
}
#define input(...) lli __VA_ARGS__; read(__VA_ARGS__)
#define input_vec(vec, ...) vector<lli> vec; read_vec(vec, __VA_ARGS__)
#ifdef __cpp_if_constexpr
template <typename T, typename ...Args>
void write(const T& x, const Args&... r) {
if constexpr (is_integral_v<T> && !is_same_v<decay_t<T>, char>) {
lli y = x;
if (y < 0) {
putchar('-');
y = -y;
}
if (y > 9) write(y / 10);
putchar(y % 10 + '0');
} else if constexpr (is_same_v<decay_t<T>, string>) {
write(x.c_str());
} else if constexpr (is_same_v<decay_t<T>, char*>) {
fputs(x, stdout);
} else if constexpr (is_same_v<decay_t<T>, char>) {
putchar(x);
} else if constexpr (is_same_v<decay_t<T>, bool>) {
putchar(x ? 'T' : 'F');
}
else cout << x;
if constexpr (sizeof...(r) > 0) write(r...);
}
#else
template<typename T>
void write(const T& x) {
cout << x;
}
template <typename T, typename... Args>
void write(const T& x, const Args&... r) {
write(x); write(r...);
}
#endif
template <typename T>
void write_vec(const vector<T>& vec, lli n, lli offset = 1) {
for (lli i = offset; i < n + offset; ++i)
write(vec[i], ' ');
write('\n');
}
#ifdef _DEBUG
# define debug(...) write(__VA_ARGS__)
# define debug_vec(...) write_vec(__VA_ARGS__)
# define debug_code(...) do __VA_ARGS__ while (false)
#else
# define debug(...)
# define debug_vec(...)
# define debug_code(...)
#endif