Contest Template

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)4e18;

// ---------- modular arithmetic (prime modulus arithmetic, @matrices/recurrences) ----------
struct Mod {
    static const ll P = 998244353;
    static ll powm(ll a, ll e = P - 2) { ll r = 1; for (; e; e >>= 1, a = a * a % P) if (e & 1) r = r * a % P; return r; }
};
inline void add(ll &a, ll b) { a += b; if (a >= Mod::P) a -= Mod::P; }

// ---------- DSU with size, no path compression when rollback is needed (@structures/dsu) ----------
struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) { reset(n); }
    void reset(int n) { p.resize(n); sz.assign(n, 1); iota(p.begin(), p.end(), 0); }
    int find(int v) { return p[v] == v ? v : p[v] = find(p[v]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; return true;
    }
    int size(int v) { return sz[find(v)]; }
};

// ---------- Fenwick over int or ll (1-indexed) (@structures/fenwick) ----------
struct BIT {
    vector<ll> t; int n;
    BIT(int n = 0) : t(n + 1, 0), n(n) {}
    void add(int i, ll v) { for (; i <= n; i += i & -i) t[i] += v; }
    ll sum(int i) { ll r = 0; for (; i > 0; i -= i & -i) r += t[i]; return r; }
    ll range(int l, int r) { return sum(r) - sum(l - 1); }
    int kth(ll k) { int i = 0; for (int b = 31 - __builtin_clz(n); b >= 0; b--) if (i + (1 << b) <= n && t[i + (1 << b)] < k) { i += 1 << b; k -= t[i]; } return i + 1; }
};

// ---------- Segment tree, iterative, any associative op (@structures/segment-tree) ----------
template <class T, T (*F)(T, T)>
struct Seg {
    int n; vector<T> t;
    Seg(const vector<T> &a) : n(a.size()), t(2 * n) {
        copy(a.begin(), a.end(), t.begin() + n);
        for (int i = n - 1; i > 0; i--) t[i] = F(t[2*i], t[2*i+1]);
    }
    void setp(int i, T v) { for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = F(t[i], t[i ^ 1]); }
    T query(int l, int r) { T L{}, R{}; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) L = F(L, t[l++]); if (r & 1) R = F(t[--r], R); } return F(L, R); }
};

// ---------- binary lifting + LCA (@lca/binary-lifting) ----------
// ---------- Dinic (@flow/maxflow) ----------
// ---------- Kuhn / Hopcroft-Karp (@matching/bipartite) ----------
// ... deliberately not repeated here: copy the version from the page you are using.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    // cin >> tc;                       // uncomment for multi-test cases
    while (tc--) {
    }
    return 0;
}