在算法竞赛的道路上，一套可靠、高效的代码模板能为我们节省宝贵的时间，让我们更专注于问题本身的逻辑。以下是我在学习和实践中，参考多位优秀选手的代码风格与优化技巧后，整理出的一套实用模板。它包含了竞赛中最常用的设置与工具函数，希望能为你的训练和比赛提供一份扎实的起点。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
// 优点：避免 std::endl 的缓冲区刷新，提升输出性能
// 使用条件：确保代码中不使用 std::endl，且不需要立即刷新缓冲区

// ====================== 常用常量定义 ======================
const int MOD = 1e9 + 7;                       // 标准模数，适用于大多数取模运算
const double PI = acos(-1.0);                  // 圆周率常量，几何计算时使用
const double eps = 1e-8;                       // 浮点数比较容差，用于判断相等
const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}; // 方向数组
const int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; // 上、下、左、右 + 对角线

// ====================== 数论基础 ======================
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } // 欧几里得算法

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } // a * b = gcd(a, b) * lcm(a, b)

ll mul(ll a, ll b, ll mod)
{
    // 防止溢出的乘法，使用快速加或 __int128（若环境支持）
    // 使用方法：mul(a, b, mod) 返回 (a*b)%mod
    // return (ll)((__int128)a * b % mod);  // 环境允许选择这一条语句
    a %= mod;
    b %= mod;
    ll res = 0;
    while (b > 0)
    {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

ll qpow(ll a, ll b, ll mod)
{
    // 快速幂，返回 a^b % mod
    ll res = 1;
    a %= mod;
    while (b)
    {
        if (b & 1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 素数测试
bool witness(ll a, ll n)
{
    ll u = n - 1;
    int t = 0;
    while ((u & 1) == 0) { u >>= 1; t++; }
    ll x1 = qpow(a, u, n);
    ll x2;
    for (int i = 1; i <= t; ++i)
    {
        x2 = mul(x1, x1, n);
        if (x2 == 1 && x1 != 1 && x1 != n - 1) return true;
        x1 = x2;
    }
    if (x1 != 1) return true;
    return false;
}

bool miller_rabin(ll n)
{
    // 判断 n 是否为素数（概率性，s=50 次测试）
    int s = 50;
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 0; i < s; ++i)
    {
        ll a = rand() % (n - 1) + 1;
        if (witness(a, n)) return false;
    }
    return true;
}

vector<ll> euler_sieve(ll n)
{
    // 欧拉线性筛，返回 [2, n] 内所有素数
    vector<bool> vis(n + 1, true);
    vector<ll> prime;
    for (ll i = 2; i <= n; ++i)
    {
        if (vis[i]) prime.push_back(i);
        for (ll j = 0; j < (ll)prime.size(); ++j)
        {
            if (i > n / prime[j]) break;
            vis[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
    return prime;
}

// ====================== 数论进阶 ======================

// 扩展欧几里得算法
// 使用方法：exgcd(a,b,x,y) 返回 gcd(a,b)，并得到一组解 x,y 满足 a*x + b*y = gcd(a,b)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 中国剩余定理（模数互质）
// 使用方法：crt(mod, rem) 返回最小非负解 x，满足 x ≡ rem[i] (mod mod[i])，模数两两互质
ll crt(const vector<ll>& mod, const vector<ll>& rem)
{
    ll M = 1, ans = 0;
    for (ll m : mod) M *= m;
    for (size_t i = 0; i < mod.size(); ++i)
    {
        ll Mi = M / mod[i];
        ll inv, y;
        exgcd(Mi, mod[i], inv, y);
        inv = (inv % mod[i] + mod[i]) % mod[i];
        ans = (ans + rem[i] * Mi % M * inv % M) % M;
    }
    return ans;
}

// 组合数预处理（阶乘+逆元，MOD 需为素数）
// 使用方法：声明 Comb comb(N); 然后 comb.C(n, k) 返回 C(n,k) % MOD
struct Comb
{
    int n;
    vector<ll> fact, invfact;
    Comb(int _n) : n(_n)
    {
        fact.resize(n+1);
        invfact.resize(n+1);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
        invfact[n] = qpow(fact[n], MOD-2, MOD);
        for (int i = n-1; i >= 0; --i) invfact[i] = invfact[i+1] * (i+1) % MOD;
    }
    ll C(int a, int b)
    {
        if (b < 0 || b > a) return 0;
        return fact[a] * invfact[b] % MOD * invfact[a-b] % MOD;
    }
};

// 矩阵快速幂（用于线性递推优化）
// 使用方法：Matrix mat(n); 赋值 mat.mat[i][j] = ...; 然后 mat.pow(p) 返回 mat^p
struct Matrix
{
    vector<vector<ll>> mat;
    int n;
    Matrix(int _n) : n(_n), mat(_n, vector<ll>(_n, 0)) {}
    Matrix operator*(const Matrix& other) const
    {
        Matrix res(n);
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < n; ++k)
                if (mat[i][k] != 0)
                    for (int j = 0; j < n; ++j)
                        res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
        return res;
    }
    Matrix pow(ll p) const
    {
        Matrix res(n), base = *this;
        for (int i = 0; i < n; ++i) res.mat[i][i] = 1;
        while (p)
        {
            if (p & 1) res = res * base;
            base = base * base;
            p >>= 1;
        }
        return res;
    }
};

// 欧拉函数（单个数）
// 使用方法：phi(n) 返回 φ(n)
ll phi(ll n)
{
    ll res = n;
    for (ll i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            while (n % i == 0) n /= i;
            res -= res / i;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

// 线性筛欧拉函数（前缀）
// 使用方法：vector<ll> phi_arr = eulerPhi(n); phi_arr[i] 为 φ(i)
vector<ll> eulerPhi(int n)
{
    vector<ll> phi(n+1);
    vector<int> primes;
    vector<bool> isComp(n+1, false);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!isComp[i]) { primes.push_back(i); phi[i] = i - 1; }
        for (int p : primes)
        {
            if (i * p > n) break;
            isComp[i*p] = true;
            if (i % p == 0) { phi[i*p] = phi[i] * p; break; }
            else phi[i*p] = phi[i] * (p - 1);
        }
    }
    return phi;
}

// ====================== 并查集 ======================
struct DSU
{
    vector<int> parent, rank_; // rank_ 记录树的高度（秩）
    // 使用方法：DSU dsu(n); dsu.unite(a,b); dsu.same(a,b); dsu.find(x);
    DSU(int n)
    {
        parent.resize(n + 1);
        rank_.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }

    int find(int x)
    {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    void unite(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        // 按秩合并
        if (rank_[rootX] < rank_[rootY]) parent[rootX] = rootY;
        else if (rank_[rootX] > rank_[rootY]) parent[rootY] = rootX;
        else { parent[rootY] = rootX; rank_[rootX]++; }
    }

    bool same(int x, int y) { return find(x) == find(y); }
};

// ====================== 图论 ======================

/**
 * Dijkstra 单源最短路（堆优化）
 * 使用方法：
 *   vector<vector<pair<int,ll>>> g(n+1); // g[u].push_back({v, w})
 *   vector<ll> dist = dijkstra(n, g, s);
 *   dist[i] 为从 s 到 i 的最短距离，不可达为 LLONG_MAX
 */
vector<ll> dijkstra(int n, const vector<vector<pair<int, ll>>> &g, int s)
{
    vector<ll> dist(n + 1, LLONG_MAX);
    vector<bool> vis(n + 1, false);
    dist[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, s});
    while (!pq.empty())
    {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : g[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

/**
 * Bellman-Ford 算法（可检测负环）
 * 使用方法：
 *   vector<tuple<int,int,ll>> edges; // edges.push_back({u,v,w})
 *   vector<ll> dist = bellmanFord(n, edges, s);
 *   若返回空 vector 则表示存在负环
 */
vector<ll> bellmanFord(int n, const vector<tuple<int, int, ll>> &edges, int s)
{
    vector<ll> dist(n + 1, LLONG_MAX);
    dist[s] = 0;
    for (int i = 1; i < n; ++i)
    {
        bool updated = false;
        for (auto [u, v, w] : edges)
        {
            if (dist[u] != LLONG_MAX && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    // 第 n 轮检查负环
    for (auto [u, v, w] : edges)
        if (dist[u] != LLONG_MAX && dist[v] > dist[u] + w)
            return {};
    return dist;
}

/**
 * Floyd-Warshall 多源最短路
 * 使用方法：
 *   vector<vector<ll>> g(n+1, vector<ll>(n+1, LLONG_MAX));
 *   设置 g[i][i] = 0, g[u][v] = w
 *   调用 floyd(n, g); 之后 g[i][j] 即为 i->j 最短路
 */
void floyd(int n, vector<vector<ll>> &g)
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (g[i][k] != LLONG_MAX && g[k][j] != LLONG_MAX)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

/**
 * 拓扑排序（Kahn 算法，基于 BFS）
 * 使用方法：
 *   vector<vector<int>> g(n+1); // 有向图邻接表
 *   vector<int> topo = topoSort(n, g);
 *   若存在环则返回空 vector，否则返回拓扑序（从 1 到 n 顺序）
 */
vector<int> topoSort(int n, const vector<vector<int>> &g)
{
    vector<int> indeg(n + 1, 0);
    for (int u = 1; u <= n; ++u)
        for (int v : g[u]) indeg[v]++;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);
    vector<int> topo;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    if ((int)topo.size() != n) return {}; // 有环
    return topo;
}

/**
 * 匈牙利算法（二分图最大匹配）
 * 使用方法：
 *   vector<vector<int>> g(n+1); // 左部点 u 可匹配的右部点列表（1-indexed）
 *   int match_count = hungarian(n, m, g); // n 为左部点数，m 为右部点数
 */
int hungarian(int n, int m, const vector<vector<int>> &g)
{
    vector<int> matchR(m + 1, 0);
    int res = 0;
    vector<bool> vis;

    function<bool(int)> dfs = [&](int u)
    {
        for (int v : g[u])
        {
            if (vis[v]) continue;
            vis[v] = true;
            if (matchR[v] == 0 || dfs(matchR[v]))
            {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    };

    for (int u = 1; u <= n; ++u)
    {
        vis.assign(m + 1, false);
        if (dfs(u)) res++;
    }
    return res;
}

/**
 * Tarjan 求强连通分量（缩点）
 * 使用方法：
 *   TarjanSCC scc(n, g); // 传入邻接表 g
 *   之后 scc.scc_id[u] 为 u 所属的 SCC 编号（1..scc_cnt），scc.scc_cnt 为总数
 */
struct TarjanSCC
{
    int n, timestamp, scc_cnt;
    vector<vector<int>> g;
    vector<int> dfn, low, stk, scc_id;
    vector<bool> in_stk;

    TarjanSCC(int _n, const vector<vector<int>> &_g) : n(_n), g(_g)
    {
        dfn.assign(n + 1, 0);
        low.assign(n + 1, 0);
        scc_id.assign(n + 1, 0);
        in_stk.assign(n + 1, false);
        timestamp = 0;
        scc_cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) dfs(i);
    }

    void dfs(int u)
    {
        dfn[u] = low[u] = ++timestamp;
        stk.push_back(u);
        in_stk[u] = true;
        for (int v : g[u])
        {
            if (!dfn[v])
            {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
            else if (in_stk[v])
            {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u])
        {
            scc_cnt++;
            int v;
            do
            {
                v = stk.back(); stk.pop_back();
                in_stk[v] = false;
                scc_id[v] = scc_cnt;
            } while (v != u);
        }
    }
};

/**
 * LCA 倍增法（预处理 O(n log n)，查询 O(log n)）
 * 使用方法：
 *   LCA lca(n, g); // g 为树的无向邻接表（1-indexed）
 *   lca.init(root);
 *   int anc = lca.lca(a, b);
 */
struct LCA
{
    int n, LOG;
    vector<vector<int>> g, up;
    vector<int> depth;
    LCA(int _n, const vector<vector<int>> &_g) : n(_n), g(_g)
    {
        LOG = __lg(n) + 1;
        up.assign(n + 1, vector<int>(LOG));
        depth.assign(n + 1, 0);
    }
    void dfs(int u, int p)
    {
        up[u][0] = p;
        for (int i = 1; i < LOG; ++i)
            up[u][i] = up[ up[u][i-1] ][i-1];
        for (int v : g[u])
        {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
    void init(int root)
    {
        depth[root] = 0;
        dfs(root, root);
    }
    int lca(int a, int b)
    {
        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];
        for (int i = 0; i < LOG; ++i)
            if (diff >> i & 1) a = up[a][i];
        if (a == b) return a;
        for (int i = LOG - 1; i >= 0; --i)
            if (up[a][i] != up[b][i])
                a = up[a][i], b = up[b][i];
        return up[a][0];
    }
};

/**
 * Prim 最小生成树（堆优化）
 * 使用方法：
 *   vector<vector<pair<int,ll>>> g(n+1); // 无向图邻接表，存入 {v, w}
 *   ll mst_w = prim(n, g); 若不连通返回 -1
 */
ll prim(int n, const vector<vector<pair<int, ll>>> &g)
{
    vector<bool> vis(n + 1, false);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 1}); // 从 1 开始
    ll ans = 0;
    int cnt = 0;
    while (!pq.empty() && cnt < n)
    {
        auto [w, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        ans += w;
        cnt++;
        for (auto [v, c] : g[u])
            if (!vis[v]) pq.push({c, v});
    }
    return (cnt == n) ? ans : -1;
}

// Kruskal 算法
struct Edge
{
    int u, v, w;
    bool operator<(const Edge &other) const { return w < other.w; }
};
int kruskal(int n, const vector<Edge> &edges)
{
    vector<Edge> sortedEdges = edges;
    sort(sortedEdges.begin(), sortedEdges.end());
    DSU dsu(n);
    int mst_weight = 0, cnt = 0;
    for (const auto &e : sortedEdges)
    {
        if (!dsu.same(e.u, e.v))
        {
            dsu.unite(e.u, e.v);
            mst_weight += e.w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return (cnt == n - 1) ? mst_weight : -1;
}

// ====================== 数据结构 ======================

/**
 * 树状数组（Fenwick Tree） 1-indexed
 * 使用方法：
 *   BIT bit(n);
 *   bit.add(idx, delta);
 *   ll sum = bit.sum(idx);    // [1, idx]
 *   ll range = bit.rangeSum(l, r);
 */
struct BIT
{
    int n;
    vector<ll> tree;
    BIT(int _n) : n(_n), tree(_n + 2, 0) {}
    void add(int idx, ll delta)
    {
        while (idx <= n)
        {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    ll sum(int idx) // [1, idx]
    {
        ll res = 0;
        while (idx > 0)
        {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
    ll rangeSum(int l, int r) { return sum(r) - sum(l - 1); }
};

/**
 * 线段树（区间加、区间求和，带懒标记）
 * 使用方法：
 *   SegTree seg(n);
 *   seg.rangeAdd(l, r, val);
 *   ll sum = seg.rangeSum(l, r);
 */
struct SegTree
{
    int n;
    vector<ll> sum, lazy;
    SegTree(int _n) : n(_n), sum(4 * _n + 5), lazy(4 * _n + 5) {}

    void push(int p, int l, int r)
    {
        if (lazy[p] != 0)
        {
            int mid = (l + r) >> 1;
            sum[p<<1] += lazy[p] * (mid - l + 1);
            sum[p<<1|1] += lazy[p] * (r - mid);
            lazy[p<<1] += lazy[p];
            lazy[p<<1|1] += lazy[p];
            lazy[p] = 0;
        }
    }

    void update(int p, int l, int r, int ql, int qr, ll val)
    {
        if (ql <= l && r <= qr)
        {
            sum[p] += val * (r - l + 1);
            lazy[p] += val;
            return;
        }
        push(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(p<<1, l, mid, ql, qr, val);
        if (qr > mid) update(p<<1|1, mid+1, r, ql, qr, val);
        sum[p] = sum[p<<1] + sum[p<<1|1];
    }

    ll query(int p, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr) return sum[p];
        push(p, l, r);
        int mid = (l + r) >> 1;
        ll res = 0;
        if (ql <= mid) res += query(p<<1, l, mid, ql, qr);
        if (qr > mid) res += query(p<<1|1, mid+1, r, ql, qr);
        return res;
    }

    void rangeAdd(int l, int r, ll val) { update(1, 1, n, l, r, val); }
    ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }
};

/**
 * ST 表（静态区间最大值，不支持修改）
 * 使用方法：
 *   vector<ll> a(n+1); a[1..n]
 *   SparseTable st(a);
 *   ll mx = st.query(l, r); // 闭区间 [l, r] 最大值
 */
struct SparseTable
{
    vector<vector<ll>> st;
    vector<int> log;
    SparseTable(const vector<ll>& a)
    {
        int n = a.size() - 1; // a[1..n]
        log.resize(n + 2);
        log[1] = 0;
        for (int i = 2; i <= n + 1; ++i) log[i] = log[i/2] + 1;
        int K = log[n] + 1;
        st.assign(n + 1, vector<ll>(K));
        for (int i = 1; i <= n; ++i) st[i][0] = a[i];
        for (int j = 1; j < K; ++j)
            for (int i = 1; i + (1<<j) - 1 <= n; ++i)
                st[i][j] = max(st[i][j-1], st[i + (1<<(j-1))][j-1]);
    }
    ll query(int l, int r)
    {
        int j = log[r - l + 1];
        return max(st[l][j], st[r - (1<<j) + 1][j]);
    }
};

// 单调栈：求每个位置左边第一个更小的元素的下标（示例）
// 使用方法：auto left = leftSmaller(a);  left[i] 为下标，若无则为 -1
vector<int> leftSmaller(const vector<int>& a)
{
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; ++i)
    {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        res[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    return res;
}

// 单调队列：滑动窗口最大值
// 使用方法：auto mx = slidingWindowMax(a, k); 返回每个窗口最大值的列表
vector<int> slidingWindowMax(const vector<int>& a, int k)
{
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < (int)a.size(); ++i)
    {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

// ====================== 字符串 ======================

/**
 * KMP 算法：返回模式串 pat 在文本串 txt 中的所有出现位置（0-indexed）
 * 使用方法：auto occ = kmpSearch(txt, pat); 返回起始下标列表
 */
vector<int> kmpSearch(const string& txt, const string& pat)
{
    string s = pat + "#" + txt;
    int n = s.size(), m = pat.size();
    vector<int> nxt(n, 0);
    for (int i = 1; i < n; ++i)
    {
        int j = nxt[i-1];
        while (j > 0 && s[i] != s[j]) j = nxt[j-1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    vector<int> res;
    for (int i = m+1; i < n; ++i)
        if (nxt[i] == m) res.push_back(i - 2*m);
    return res;
}

/**
 * Manacher 算法：求最长回文子串长度
 * 使用方法：int len = manacher(s); 返回最长回文子串的长度
 */
int manacher(const string& s)
{
    string t = "#";
    for (char c : s) t += c, t += '#';
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    for (int i = 0; i < n; ++i)
    {
        int mirror = 2 * center - i;
        if (i < right) p[i] = min(right - i, p[mirror]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i-p[i]-1] == t[i+p[i]+1]) p[i]++;
        if (i + p[i] > right)
        {
            center = i;
            right = i + p[i];
        }
    }
    return *max_element(p.begin(), p.end());
}

/**
 * 双哈希字符串哈希（防碰撞）
 * 使用方法：
 *   DoubleHash dh(s);
 *   auto [h1, h2] = dh.getHash(l, r); // 0-indexed 闭区间 [l, r]
 *   可直接比较两个子串哈希是否相等
 */
struct DoubleHash
{
    static const ll base = 91138233;
    static const ll mod1 = 1e9+7, mod2 = 1e9+9;
    vector<ll> h1, h2, pow1, pow2;
    DoubleHash(const string& s)
    {
        int n = s.size();
        h1.resize(n+1); h2.resize(n+1);
        pow1.resize(n+1); pow2.resize(n+1);
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            pow1[i] = pow1[i-1] * base % mod1;
            pow2[i] = pow2[i-1] * base % mod2;
        }
        for (int i = 1; i <= n; ++i)
        {
            h1[i] = (h1[i-1] * base + s[i-1]) % mod1;
            h2[i] = (h2[i-1] * base + s[i-1]) % mod2;
        }
    }
    pair<ll,ll> getHash(int l, int r) // 0-indexed, [l, r]
    {
        ll v1 = (h1[r+1] - h1[l] * pow1[r-l+1] % mod1 + mod1) % mod1;
        ll v2 = (h2[r+1] - h2[l] * pow2[r-l+1] % mod2 + mod2) % mod2;
        return {v1, v2};
    }
};

// ====================== 计算几何 ======================

struct Point
{
    double x, y;
    Point(double x=0, double y=0) : x(x), y(y) {}
    Point operator+(const Point& p) const { return {x+p.x, y+p.y}; }
    Point operator-(const Point& p) const { return {x-p.x, y-p.y}; }
    double dot(const Point& p) const { return x*p.x + y*p.y; }
    double cross(const Point& p) const { return x*p.y - y*p.x; }
    double len2() const { return x*x + y*y; }
    double len() const { return sqrt(len2()); }
    bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }
};

/**
 * Andrew 凸包算法
 * 使用方法：
 *   vector<Point> pts;
 *   vector<Point> hull = convexHull(pts);
 *   返回逆时针凸包点集（不含重复端点，最后一点不与起点重复）
 */
vector<Point> convexHull(vector<Point> pts)
{
    int n = pts.size();
    if (n <= 1) return pts;
    sort(pts.begin(), pts.end());
    vector<Point> hull;
    // 下凸包
    for (int i = 0; i < n; ++i)
    {
        while (hull.size() >= 2 && (hull.back() - hull[hull.size()-2]).cross(pts[i] - hull.back()) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    int lower = hull.size();
    // 上凸包
    for (int i = n-2; i >= 0; --i)
    {
        while (hull.size() > lower && (hull.back() - hull[hull.size()-2]).cross(pts[i] - hull.back()) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    if (hull.size() > 1) hull.pop_back(); // 移除起点重复
    return hull;
}

// ====================== DP 优化（示例） ======================

/**
 * 单调队列优化 DP 框架
 * 问题：dp[i] = min_{j∈[i-m, i-1]} (dp[j] + (a[i]-a[j])^2)
 * 使用方法：根据具体题目修改转移方程，此处仅展示框架
 */
ll monotoneQueueDP(const vector<ll>& a, int m)
{
    int n = a.size();
    vector<ll> dp(n, 0);
    deque<int> dq;
    for (int i = 0; i < n; ++i)
    {
        while (!dq.empty() && dq.front() < i - m) dq.pop_front();
        if (!dq.empty())
            dp[i] = dp[dq.front()] + (a[i] - a[dq.front()]) * (a[i] - a[dq.front()]);
        else
            dp[i] = (i == 0 ? 0 : LLONG_MAX/2);
        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    return dp[n-1];
}

// ====================== 搜索与状态压缩 ======================

/**
 * 双向 BFS（示例：状态为整数）
 * 使用方法：
 *   auto getNext = [&](int state) -> vector<int> { ... };
 *   int steps = bidirectionalBFS(start, target, getNext);
 *   返回最少步数，若无法到达则返回 -1
 */
int bidirectionalBFS(int start, int target, function<vector<int>(int)> getNext)
{
    if (start == target) return 0;
    queue<int> q1, q2;
    unordered_map<int, int> dist1, dist2;
    q1.push(start); dist1[start] = 0;
    q2.push(target); dist2[target] = 0;

    auto extend = [&](queue<int>& q, unordered_map<int,int>& dist, unordered_map<int,int>& distOther) -> int
    {
        int u = q.front(); q.pop();
        int d = dist[u];
        for (int v : getNext(u))
        {
            if (dist.count(v)) continue;
            if (distOther.count(v)) return d + 1 + distOther[v];
            dist[v] = d + 1;
            q.push(v);
        }
        return -1;
    };

    while (!q1.empty() && !q2.empty())
    {
        int res;
        if (q1.size() <= q2.size()) res = extend(q1, dist1, dist2);
        else res = extend(q2, dist2, dist1);
        if (res != -1) return res;
    }
    return -1;
}

/**
 * 状态压缩 DP 示例：TSP（旅行商问题）
 * 使用方法：
 *   vector<vector<ll>> dist(n, vector<ll>(n)); // dist[u][v] 距离
 *   ll ans = tsp(dist); 返回从 0 出发、遍历所有点并返回 0 的最短路径长度
 */
ll tsp(const vector<vector<ll>>& dist)
{
    int n = dist.size();
    vector<vector<ll>> dp(1 << n, vector<ll>(n, LLONG_MAX/2));
    dp[1][0] = 0; // 起点 0
    for (int mask = 1; mask < (1 << n); ++mask)
    {
        for (int u = 0; u < n; ++u)
        {
            if (!(mask >> u & 1)) continue;
            for (int v = 0; v < n; ++v)
            {
                if (mask >> v & 1) continue;
                int nxt = mask | (1 << v);
                dp[nxt][v] = min(dp[nxt][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    ll ans = LLONG_MAX/2;
    int all = (1 << n) - 1;
    for (int u = 0; u < n; ++u)
        ans = min(ans, dp[all][u] + dist[u][0]);
    return ans;
}

// ====================== 进制转换与二分查找 ======================

// 将字符转换成数值 (0~35)
int charToVal(char c)
{
    if (c >= '0' && c <= '9') return c - '0';
    return toupper(c) - 'A' + 10; // 支持大小写
}

// 将数值转换成字符 (0~35)
char valToChar(int v)
{
    if (v < 10) return '0' + v;
    return 'A' + v - 10;
}

// 进制转换核心函数
string convertBase(const string &s, int fromBase, int toBase)
{
    if (s.empty()) return "0";
    vector<int> num;
    for (char c : s) num.push_back(charToVal(c));

    string result;
    while (!num.empty())
    {
        int remainder = 0;
        vector<int> newNum;
        for (size_t i = 0; i < num.size(); ++i)
        {
            int cur = remainder * fromBase + num[i];
            int q = cur / toBase;
            remainder = cur % toBase;
            if (!newNum.empty() || q != 0) newNum.push_back(q);
        }
        result.push_back(valToChar(remainder));
        num = newNum;
    }
    reverse(result.begin(), result.end());
    return result.empty() ? "0" : result;
}

bool check(ll mid) 
{ 
    // 根据实际问题修改判断条件
    return mid; 
}

ll binarySearch(ll l, ll r, bool findFirst = true)
{
    // findFirst = true: 左边界查找（第一个满足条件的）
    // findFirst = false: 右边界查找（最后一个满足条件的）
    if (findFirst)
    {
        while (l < r)
        {
            ll mid = l + ((r - l) >> 1);
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return check(l) ? l : r + 1;
    }
    else
    {
        while (l < r)
        {
            ll mid = l + ((r - l + 1) >> 1);
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return check(l) ? l : -1;
    }
}

// ====================== 主函数与 solve 框架 ======================
void solve()
{
    // 在此编写题目求解逻辑
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    // cin >> T; // 多组测试数据时取消注释
    while (T--)
    {
        solve();
    }
    return 0;
}

关于模板的学习与使用建议：

1. 理解优先于记忆：在使用任何模板前，务必理解其实现原理和适用场景。例如，理解快速幂的二进制分解思想，比单纯背诵代码更重要。
2. 刻意练习形成肌肉记忆：对于常用模板（如快速幂、并查集、二分查找），应通过反复敲打直至熟练，使其在比赛时能快速、准确地写出。
3. 根据比赛需求灵活裁剪：在ICPC、CCPC等团队赛中，可以指派一名队员提前准备好包含更全算法的“板子”。但具体到每道题，应只保留必要的部分，保持代码清晰。
4. 保持更新与迭代：随着学习的深入，你会遇到更优的实现或更适合自己习惯的写法。定期回顾并优化自己的模板库，是持续进步的重要一环。

模板是工具，能帮你提高效率，但不能替代思考。扎实的基础、清晰的逻辑和稳定的心态，才是解决难题的根本。

下面算法心传系列会对常用的算法模板一一讲解，深度剖析，帮助大家可以灵活使用，更深刻的理解算法竞赛模板的运用。

我会持续优化这份模板，并在我的博客中更新。祝愿各位在算法之路上不断精进，在比赛中取得理想的成绩！！！