自用。
#include <bits/stdc++.h>
#include <chrono>
std::mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return std::uniform_int_distribution<int>(l, r)(eng); }
namespace FastIO {
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
inline char rChar() { char ch = getchar(); while (!isalpha(ch)) ch = getchar(); return ch; }
}; using namespace FastIO;
using ll = long long;
namespace Maths {
const int MAXN = 1;
constexpr ll MOD = 1000000007;
ll qpow(ll a, ll x) { ll ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; }
ll qpow(ll a, ll x, ll p) { ll ans = 1; while (x) (x & 1) && (ans = ans * a % p), a = a * a % p, x >>= 1; return ans; }
ll frac[MAXN], prac[MAXN];
inline void inis(int V) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; }
inline long long C(int N, int M) { return N < 0 || M < 0 || N < M ? 0ll : frac[N] * prac[M] % MOD * prac[N - M] % MOD; }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
inline ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
std::pair<ll, ll> exgcd(ll x, ll y) { if (!y) return std::make_pair(1ll, 0ll); auto k = exgcd(y, x % y); return std::make_pair(k.second, k.first - k.second * (x / y)); }
ll inv(ll a, ll p) { return (exgcd(a, p).first % p + p) % p; }
struct modulo { ll p, v; modulo (ll P = 1, ll V = 0) : p(P), v(V) {} };
modulo operator + (modulo a, modulo b) {
if ((b.v - a.v) % gcd(a.p, b.p) != 0) return modulo(-1, -1);
ll d = (b.v - a.v) / gcd(a.p, b.p);
auto k = exgcd(a.p, b.p);
ll q = (k.first * d * a.p + a.v) % lcm(a.p, b.p);
return modulo(lcm(a.p, b.p), (q + lcm(a.p, b.p)) % lcm(a.p, b.p));
}
modulo operator += (modulo a, modulo b) { return a = a + b; }
};
namespace Matrix {
const int SIZE = 3;
struct matrix { int a[SIZE][SIZE], n, m; matrix () { memset(a, 0, sizeof(a)); } matrix (int N, int M) : n(N), m(M) { memset(a, 0, sizeof(a)); } inline void debug() { for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) print<int>(a[i][j], " \n"[j == m]); } };
const matrix unit(int N) { matrix ans = matrix(N, N); for (int i = 1; i <= N; ++i) ans.a[i][i] = 1; return ans; }
matrix operator * (const matrix& a, const matrix& b) { assert(a.m == b.n); matrix c(a.n, b.m); for (int k = 1; k <= a.m; ++k) for (int i = 1; i <= a.n; ++i) for (int j = 1; j <= b.m; ++j) c.a[i][j] = (1ll * a.a[i][k] * b.a[k][j] + c.a[i][j]) % Maths::MOD; return c; }
matrix operator ^ (matrix a, long long x) { assert(a.m == a.n); matrix c = unit(a.n); while (x) { if (x & 1) c = c * a; a = a * a, x >>= 1; } return c; }
}; // for optimization, try delay-modulo in operation *
namespace Gauss /* Require C++17 */ {
// constexpr double eps = 1e-7;
// using vd = std::vector<double>;
// std::variant<bool, vd> Gauss(std::vector<vd>& a, const int& N) {
// for (int i = 0, max = 0; i < N; max = ++i) {
// for (int j = i + 1; j < N; ++j) std::abs(a[j][i]) > std::abs(a[max][i]) && (max = j);
// for (int j = 0; j <= N; ++j) std::swap(a[i][j], a[max][j]);
// if (std::abs(a[i][i]) <= eps) return false;
// for (int j = 0; j < N; ++j) if (i != j) {
// double f = a[j][i] / a[i][i];
// for (int k = i + 1; k <= N; ++k) a[j][k] -= a[i][k] * f;
// }
// }
// vd res(N); for (int i = 0; i < N; ++i) res[i] = a[i][N] / a[i][i];
// return res;
// }
// usage :
// std::vector<double> g;
// try {
// g = std::get<std::vector<double>>(Gauss(funcs, N));
// // ......
// } catch (const std::bad_variant_access& ex) {
// // 这里是无解或者无数解情况
// }
};
namespace DSU {
const int MAXN = 1;
int det[MAXN], fa[MAXN]; std::stack<std::pair<int, int>> s;
void inis(int N) { for (int i = 1; i <= N; ++i) det[i] = 1, fa[i] = i; while (!s.empty()) s.pop(); }
inline int find(int x) { while (x != fa[x]) x = fa[x]; return x; }
inline void merge(int x, int y) { x = find(x), y = find(y); if (det[x] > det[y]) std::swap(x, y); fa[x] = y, det[y] += (det[x] == det[y]); s.push({x, y}); }
inline void split(int x, int y) { fa[x] = x, det[y] -= (det[x] == det[y]); }
}; // delete undos if you dont want
namespace String {
const int MAXN = 1;
int rk[MAXN << 1], sa[MAXN << 1], cnt[MAXN], tmp[MAXN], height[MAXN];
void suffixA(std::string S, int N) {
// rk[i]：第 i 个后缀的排名
// sa[i]：排名为 i 的后缀的开始位置
if (N == 1) return (void)(sa[1] = rk[1] = 1);
for (int i = 1; i <= N; ++i) sa[i] = i, rk[i] = S[i - 1];
for (int w = 1, m = std::max(128, N); w < N; w <<= 1) {
std::fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= N; ++i) ++cnt[rk[i + w]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = N; i; --i) tmp[cnt[rk[sa[i] + w]]--] = sa[i];
std::fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= N; ++i) ++cnt[rk[tmp[i]]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = N; i; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
auto rp = [&](int x) { return std::make_pair(rk[x], rk[x + w]); };
for (int i = 1, p = 0; i <= N; ++i)
tmp[sa[i]] = rp(sa[i - 1]) == rp(sa[i]) ? p : ++p;
std::copy(tmp + 1, tmp + N + 1, rk + 1);
}
for (int i = 1, k = 0; i <= N; ++i) { if (k > 0) --k; while (S[i + k - 1] == S[sa[rk[i] - 1] + k - 1]) ++k; height[rk[i]] = k; }
}
};
namespace Graph {
const int MAXN = 1, MAXM = 5;
struct graph {
int head[MAXN], cnt = 0;
struct Edge { int to, nxt; Edge () {} Edge (int T, int N) : to(T), nxt(N) {} } e[MAXM << 1];
inline void clear(int N, int M) { cnt = 0, memset(head, 0, sizeof(int) * (N + 5)), memset(e, 0, sizeof(Edge) * (M + 5)); }
inline void addEdge(int u, int v) { e[++cnt] = Edge(v, head[u]), head[u] = cnt; }
inline void addEdges(int u, int v) { e[++cnt] = Edge(v, head[u]), head[u] = cnt; e[++cnt] = Edge(u, head[v]), head[v] = cnt; }
};
};
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
template <uint32_t MOD> struct mint {
static constexpr u32 get_r() {
u32 ret = MOD;
for (i32 i = 0; i < 4; ++i) ret *= 2 - MOD * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(MOD) % MOD;
static_assert(r * MOD == 1, "invalid, r * MOD != 1");
static_assert(MOD < (1 << 30), "invalid, MOD >= 2 ^ 30");
static_assert((MOD & 1) == 1, "invalid, MOD % 2 == 0");
u32 a;
constexpr mint() : a(0) {}
constexpr mint(const int64_t &b) : a(reduce(u64(b % MOD + MOD) * n2)){};
static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * MOD) >> 32; }
constexpr mint &operator += (const mint &b) { if (i32(a += b.a - 2 * MOD) < 0) a += 2 * MOD; return *this; }
constexpr mint &operator -= (const mint &b) { if (i32(a -= b.a) < 0) a += 2 * MOD; return *this; }
constexpr mint &operator *= (const mint &b) { a = reduce(u64(a) * b.a); return *this; }
constexpr mint &operator /= (const mint &b) { *this *= b.inverse(); return *this; }
constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }
constexpr bool operator == (const mint &b) const { return (a >= MOD ? a - MOD : a) == (b.a >= MOD ? b.a - MOD : b.a); }
constexpr bool operator != (const mint &b) const { return (a >= MOD ? a - MOD : a) != (b.a >= MOD ? b.a - MOD : b.a); }
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; }
constexpr mint inverse() const { return pow(MOD - 2); }
friend std::ostream &operator<< (std::ostream &os, const mint &b) { return os << b.get(); }
friend std::istream &operator>> (std::istream &is, mint &b) { int64_t t; is >> t; b = mint<MOD>(t); return (is); }
constexpr u32 get() const { u32 ret = reduce(a); return ret >= MOD ? ret - MOD : ret; }
static constexpr u32 get_MOD() { return MOD; }
explicit operator u32() const { return get(); }
};
using modint = mint<Maths::MOD>;
namespace Balance {
const int MAXN = 1, X = 200000000;
struct FhqTreap {
int lc[MAXN], rc[MAXN], sz[MAXN], val[MAXN], c[MAXN], cnt = 0, root = 0;
inline int szup(int id) { sz[id] = sz[lc[id]] + sz[rc[id]] + 1; return id; }
inline int newNode(int v) { sz[++cnt] = 1, val[cnt] = v, c[cnt] = rnd(1, X); return cnt; }
void split(int id, int s, int& x, int& y) { if (!id) return (void)(x = y = 0); if (val[id] <= s) x = id, split(rc[id], s, rc[id], y); else y = id, split(lc[id], s, x, lc[id]); szup(id); }
int merge(int x, int y) { if (!x || !y) return x | y; if (c[x] > c[y]) { rc[x] = merge(rc[x], y); return szup(x); } else { lc[y] = merge(x, lc[y]); return szup(y); } }
void insert(int v) { static int x, y; split(root, v, x, y); root = merge(merge(x, newNode(v)), y); }
void erase(int v) { static int x, y, z; split(root, v, x, z), split(x, v - 1, x, y); root = merge(merge(x, lc[y]), merge(rc[y], z)); }
int rnk(int v) { static int x, y, tmp; split(root, v - 1, x, y); tmp = sz[x] + 1, root = merge(x, y); return tmp; }
int queryN(int v, bool l, int *ch) { static int x, y, tmp; split(root, v, x, y); tmp = (l ? x : y); while (ch[tmp]) tmp = ch[tmp]; root = merge(x, y); return val[tmp]; }
int pre(int v) { return queryN(v - 1, true, rc); }
int nxt(int v) { return queryN(v, false, lc); }
int kth(int k) { int p = root; while (true) { if (sz[lc[p]] + 1 == k) return val[p]; if (sz[lc[p]] >= k) p = lc[p]; else k -= sz[lc[p]] + 1, p = rc[p]; } }
};
// powered by rui_er. 如果想要不换根版本，可以见 luogu P9201:
// void link(int u, int v) { int t = findroot(v); makeroot(u), fa[u] = v; makeroot(t); }
// void cut(int u, int v) { int t = findroot(v); makeroot(u), access(v), splay(v); fa[u] = son[v][0] = 0, pushup(v); makeroot(u), makeroot(t); }
// int query(int u, int v) { int t = findroot(u); makeroot(u), access(v), splay(v); int z = maxv[v]; makeroot(t); return z; }
// 需要根据题意更改的有 pushup .
struct LinkCutTree {
int fa[MAXN], val[MAXN], maxv[MAXN], tag[MAXN], son[MAXN][2];
void clearAll() { memset(fa, 0, sizeof(fa)); memset(maxv, 0, sizeof(maxv)); memset(tag, 0, sizeof(tag)); memset(son, 0, sizeof(son)); }
int get(int u) { if (son[fa[u]][0] == u) return 0; if (son[fa[u]][1] == u) return 1; return -1; }
void connect(int u, int f, int tp) { fa[u] = f; if (~tp) son[f][tp] = u; }
void pushup(int u) { maxv[u] = std::max({maxv[son[u][0]], maxv[son[u][1]], val[u]}); }
void reverse(int u) { std::swap(son[u][0], son[u][1]), tag[u] ^= 1; }
void pushdown(int u) { if (!tag[u]) return; if (son[u][0]) reverse(son[u][0]); if (son[u][1]) reverse(son[u][1]); tag[u] = 0; }
void pushall(int u) { if (~get(u)) pushall(fa[u]); pushdown(u); }
void rotate(int u) { int v = fa[u], w = fa[v], p = get(u), q = get(v), c = son[u][p ^ 1]; connect(c, v, p), connect(v, u, p ^ 1), connect(u, w, q); pushup(v), pushup(u); }
int splay(int u) { pushall(u); if (get(u) == -1) return u; for (int f; true; ) { f = fa[u]; if (get(f) == -1) { rotate(u); return f; } else rotate(get(u) == get(f) ? f : u); f = fa[u]; if (get(f) == -1) { rotate(u); return f; } else rotate(u); } }
void access(int u) { for (int v = 0; u; v = u, u = fa[u]) splay(u), son[u][1] = v, pushup(u); }
void makeroot(int u) { access(u), splay(u), reverse(u); }
int findroot(int u) { access(u), splay(u), pushdown(u); for (; son[u][0]; u = son[u][0]) pushdown(u); splay(u); return u; }
void link(int u, int v) { makeroot(u), fa[u] = v; }
void cut(int u, int v) { makeroot(u), access(v), splay(v); fa[u] = son[v][0] = 0, pushup(v); }
int query(int u, int v) { int t = findroot(u); makeroot(u), access(v), splay(v); return maxv[v]; }
};
};
namespace Bits {
const int V = 10944, B = 64, R = 63, T = 6;
struct bitset {
private : unsigned long long a[V];
public :
bitset () { memset(a, 0, sizeof(a)); }
inline int operator [] (const int& i) { return (a[i >> T] >> (i & R)) & 1; }
inline unsigned long long get(const int& i) { return a[i]; }
inline void set(int v, unsigned long long x = 1) { a[v >> T] ^= ((x ^ (*this)[v]) << (v & R)); }
bitset (const std::string& S) { memset(a, 0, sizeof(a)); for (int i = 0, n = (int)S.size(); i < n; ++i) if (S[i] ^ '0') this -> set(i); }
bitset operator & (const bitset& k) const { bitset t; for (int i = 0; i < V; i += 4) t.a[i] = a[i] & k.a[i], t.a[i | 1] = a[i | 1] & k.a[i | 1], t.a[i | 2] = a[i | 2] & k.a[i | 2], t.a[i | 3] = a[i | 3] & k.a[i | 3]; return t; }
bitset operator &= (const bitset& k) { for (int i = 0; i < V; i += 4) a[i] &= k.a[i], a[i | 1] &= k.a[i | 1], a[i | 2] &= k.a[i | 2], a[i | 3] &= k.a[i | 3]; return *this; }
bitset operator | (const bitset& k) const { bitset t; for (int i = 0; i < V; i += 4) t.a[i] = a[i] | k.a[i], t.a[i | 1] = a[i | 1] | k.a[i | 1], t.a[i | 2] = a[i | 2] | k.a[i | 2], t.a[i | 3] = a[i | 3] | k.a[i | 3]; return t; }
bitset operator |= (const bitset& k) { for (int i = 0; i < V; i += 4) a[i] |= k.a[i], a[i | 1] |= k.a[i | 1], a[i | 2] |= k.a[i | 2], a[i | 3] |= k.a[i | 3]; return *this; }
bitset operator ^ (const bitset& k) const { bitset t; for (int i = 0; i < V; i += 4) t.a[i] = a[i] ^ k.a[i], t.a[i | 1] = a[i | 1] ^ k.a[i | 1], t.a[i | 2] = a[i | 2] ^ k.a[i | 2], t.a[i | 3] = a[i | 3] ^ k.a[i | 3]; return t; }
bitset operator ^= (const bitset& k) { for (int i = 0; i < V; i += 4) a[i] ^= k.a[i], a[i | 1] ^= k.a[i | 1], a[i | 2] ^= k.a[i | 2], a[i | 3] ^= k.a[i | 3]; return *this; }
bitset operator <<= (int k) { if (k >= B) { int s = k >> T; for (int i = V - 1; ~i; --i) a[i] = (i + 1 > s ? a[i - s] : 0ull); k &= R; } if (!k) return *this; unsigned long long o = 0, t; for (int i = 0; i < V; ++i) t = a[i] >> (B - k), a[i] = (a[i] << k) | o, o = t; return *this; }
bitset operator << (int k) const { bitset t = *this; return t <<= k; }
bitset operator >>= (int k) { if (k >= B) { int s = k >> T; for (int i = 0; i < V; ++i) a[i] = (i + s < V ? a[i + s] : 0ull); k &= R; } if (!k) return *this; unsigned long long o = 0, t; for (int i = V - 1; ~i; --i) t = a[i] << (B - k), a[i] = (a[i] >> k) | o, o = t; return *this; }
bitset operator >> (int k) const { bitset t = *this; return t >>= k; }
const int count(int N) const { int ans = 0; for (int i = 0; i <= (N >> T); ++i) ans += __builtin_popcountll(a[i]); return ans; }
const void debug(int N) { for (int i = 0; i < N; ++i) putchar(48 + (*this)[i]); puts(""); }
};
};
namespace Basis {
const int V = 62;
struct base {
private :
long long f[V + 1], g[V + 1]; int cnt = 0; bool flag = false;
public :
void add(long long x) { for (int i = V; ~i; --i) if ((x >> i) & 1) { if (f[i]) x ^= f[i]; else { f[i] = x; break; } } }
void inis() { flag = true; for (int i = 0; i <= V; ++i) { for (int j = i - 1; ~j; --j) if ((f[i] >> j) & 1) f[i] ^= f[j]; if (f[i]) g[cnt++] = f[i]; } }
long long kth(long long K) { if (!flag) inis(); long long ans = 0; for (int i = 0; i < cnt; ++i) if ((K >> i) & 1) ans ^= g[i]; return ans; }
long long lgn() { long long ans = 0; for (int i = V; ~i; --i) if (!((ans >> i) & 1)) ans ^= f[i]; return ans; }
};
};
void solve() {
}
int main() { int T = read<int>(); while (T--) solve(); return 0; }