C++ Competitive Programming Template - Everything in One Place

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

#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(int i = a; i < b; i++)

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int LG = 20;

int n, m;

void solve() {
    // solution here
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

struct DSU {
    int connected;
    int par[N], sz[N];

    DSU() {}

    DSU(int n) {
        for(int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
        connected = n;
    }

    int getPar(int k) {
        while(k != par[k]) {
            par[k] = par[par[k]]; // path compression (halving)
            k = par[k];
        }
        return k;
    }

    bool same(int u, int v) {
        return getPar(u) == getPar(v);
    }

    int getSize(int k) {
        return sz[getPar(k)];
    }

    // returns false if already connected
    bool unite(int u, int v) {
        int p1 = getPar(u), p2 = getPar(v);
        if(p1 == p2) return false;
        connected--;
        if(sz[p1] > sz[p2]) swap(p1, p2);
        sz[p2] += sz[p1];
        sz[p1] = 0;
        par[p1] = p2;
        return true;
    }
};
// DSU dsu(n);
// dsu.unite(u, v);
// dsu.same(u, v);
// dsu.connected — number of connected components

struct node {
    int mn;
    node() : mn(1e9) {}
};

struct SegTree {
    int N;
    vector<node> st;
    vector<bool> hasLazy;
    vector<int> lazy;

    void init(int n) {
        N = n;
        st.resize(4 * N + 5);
        hasLazy.assign(4 * N + 5, false);
        lazy.assign(4 * N + 5, 0);
    }

    void merge(node &cur, node &l, node &r) {
        cur.mn = min(l.mn, r.mn);
    }

    void applyLazy(int node, int L, int R) {
        st[node].mn = lazy[node];
        if(L != R) {
            hasLazy[2*node] = hasLazy[2*node+1] = true;
            lazy[2*node] = lazy[2*node+1] = lazy[node];
        }
        hasLazy[node] = false;
    }

    void push(int node, int L, int R) {
        if(hasLazy[node]) applyLazy(node, L, R);
    }

    void build(int node, int L, int R, vector<int> &a) {
        if(L == R) { st[node].mn = a[L]; return; }
        int M = (L + R) / 2;
        build(2*node, L, M, a);
        build(2*node+1, M+1, R, a);
        merge(st[node], st[2*node], st[2*node+1]);
    }

    node query(int node, int L, int R, int l, int r) {
        push(node, L, R);
        if(r < L || R < l) return node{}; // identity
        if(l <= L && R <= r) return st[node];
        int M = (L + R) / 2;
        node left  = query(2*node, L, M, l, r);
        node right = query(2*node+1, M+1, R, l, r);
        node cur;
        merge(cur, left, right);
        return cur;
    }

    void update(int node, int L, int R, int l, int r, int val) {
        push(node, L, R);
        if(r < L || R < l) return;
        if(l <= L && R <= r) {
            hasLazy[node] = true;
            lazy[node] = val;
            applyLazy(node, L, R);
            return;
        }
        int M = (L + R) / 2;
        update(2*node, L, M, l, r, val);
        update(2*node+1, M+1, R, l, r, val);
        merge(st[node], st[2*node], st[2*node+1]);
    }

    // public interface
    void build(vector<int> &a)       { build(1, 1, N, a); }
    node query(int l, int r)          { return query(1, 1, N, l, r); }
    void update(int l, int r, int v)  { update(1, 1, N, l, r, v); }
    void update(int pos, int v)       { update(1, 1, N, pos, pos, v); }
};
// SegTree seg; seg.init(n); seg.build(a);
// seg.query(l, r).mn
// seg.update(l, r, val)   — range assign
// seg.update(pos, val)    — point assign

struct SegTreeSum {
    int N;
    vector<long long> st, lazy;

    void init(int n) {
        N = n;
        st.assign(4 * N + 5, 0);
        lazy.assign(4 * N + 5, 0);
    }

    void push(int node, int L, int R) {
        if(lazy[node]) {
            int M = (L + R) / 2;
            st[2*node]   += lazy[node] * (M - L + 1);
            st[2*node+1] += lazy[node] * (R - M);
            lazy[2*node]   += lazy[node];
            lazy[2*node+1] += lazy[node];
            lazy[node] = 0;
        }
    }

    void build(int node, int L, int R, vector<int> &a) {
        if(L == R) { st[node] = a[L]; return; }
        int M = (L + R) / 2;
        build(2*node, L, M, a);
        build(2*node+1, M+1, R, a);
        st[node] = st[2*node] + st[2*node+1];
    }

    long long query(int node, int L, int R, int l, int r) {
        if(r < L || R < l) return 0;
        if(l <= L && R <= r) return st[node];
        push(node, L, R);
        int M = (L + R) / 2;
        return query(2*node, L, M, l, r) + query(2*node+1, M+1, R, l, r);
    }

    void update(int node, int L, int R, int l, int r, long long val) {
        if(r < L || R < l) return;
        if(l <= L && R <= r) {
            st[node] += val * (R - L + 1);
            lazy[node] += val;
            return;
        }
        push(node, L, R);
        int M = (L + R) / 2;
        update(2*node, L, M, l, r, val);
        update(2*node+1, M+1, R, l, r, val);
        st[node] = st[2*node] + st[2*node+1];
    }

    void build(vector<int> &a)              { build(1, 1, N, a); }
    long long query(int l, int r)           { return query(1, 1, N, l, r); }
    void update(int l, int r, long long v)  { update(1, 1, N, l, r, v); }
    void update(int pos, long long v)       { update(1, 1, N, pos, pos, v); }
};
// SegTreeSum seg; seg.init(n); seg.build(a);
// seg.query(l, r)          — range sum
// seg.update(l, r, val)   — range add
// seg.update(pos, val)    — point add

struct BIT {
    int N;
    vector<int> bit;

    void init(int n) {
        N = n;
        bit.assign(n + 1, 0);
    }

    void update(int idx, int val) {
        for(; idx <= N; idx += idx & -idx)
            bit[idx] += val;
    }

    int pref(int idx) {
        int ans = 0;
        for(; idx > 0; idx -= idx & -idx)
            ans += bit[idx];
        return ans;
    }

    int query(int l, int r) {
        return pref(r) - pref(l - 1);
    }

    // point update, then range min/max (non-reversible — use only for prefix max)
    void updateMax(int idx, int val) {
        for(; idx <= N; idx += idx & -idx)
            bit[idx] = max(bit[idx], val);
    }

    int prefMax(int idx) {
        int ans = -2e9;
        for(; idx > 0; idx -= idx & -idx)
            ans = max(ans, bit[idx]);
        return ans;
    }
};
// BIT bit; bit.init(n);
// bit.update(i, val); bit.query(l, r);

struct BITDiff {
    int N;
    vector<long long> bit;

    void init(int n) { N = n; bit.assign(n + 2, 0); }

    void update(int idx, long long val) {
        for(; idx <= N; idx += idx & -idx)
            bit[idx] += val;
    }

    long long pref(int idx) {
        long long ans = 0;
        for(; idx > 0; idx -= idx & -idx)
            ans += bit[idx];
        return ans;
    }

    void rangeAdd(int l, int r, long long val) {
        update(l, val);
        update(r + 1, -val);
    }

    long long pointQuery(int i) { return pref(i); }
};
// BITDiff bit; bit.init(n);
// bit.rangeAdd(l, r, val); bit.pointQuery(i);

int floorlog[N];
int sparse[20][N]; // sparse[j][i] = min of [i, i + 2^j - 1]

void buildSparse(vector<int> &a, int n) {
    for(int i = 2; i <= n; i++)
        floorlog[i] = floorlog[i/2] + 1;
    for(int i = 1; i <= n; i++) sparse[0][i] = a[i];
    for(int j = 1; (1 << j) <= n; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            sparse[j][i] = min(sparse[j-1][i], sparse[j-1][i + (1 << (j-1))]);
}

int rmq(int l, int r) {
    int k = floorlog[r - l + 1];
    return min(sparse[k][l], sparse[k][r - (1 << k) + 1]);
}
// Change min -> max for range max. O(n log n) build, O(1) query, no updates.

vector<pii> g[N]; // g[u] = {v, weight}
int dist[N];

void dijkstra(int src) {
    fill(dist + 1, dist + n + 1, INF);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : g[u]) {
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
// dist[v] = INF means unreachable

int par[N];

void dijkstra(int src) {
    fill(dist+1, dist+n+1, INF);
    fill(par+1, par+n+1, -1);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : g[u]) {
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                par[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

vector<int> getPath(int t) {
    vector<int> path;
    for(int v = t; v != -1; v = par[v]) path.pb(v);
    reverse(all(path));
    return path;
}

int bfsDist[N];
int bfsPar[N];

void bfs(int src) {
    fill(bfsDist+1, bfsDist+n+1, -1);
    fill(bfsPar+1, bfsPar+n+1, -1);
    queue<int> q;
    bfsDist[src] = 0;
    q.push(src);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto v : g[u]) {
            if(bfsDist[v] == -1) {
                bfsDist[v] = bfsDist[u] + 1;
                bfsPar[v] = u;
                q.push(v);
            }
        }
    }
}

void bfs01(int src) {
    fill(dist+1, dist+n+1, INF);
    dist[src] = 0;
    deque<int> dq;
    dq.push_front(src);
    while(!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for(auto [v, w] : g[u]) {
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if(w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}

int dist[505][505];

void floydWarshall(int n) {
    // init: dist[i][i] = 0, dist[i][j] = edge weight or INF
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
// After: if dist[i][i] < 0, there is a negative cycle reachable from i.
// Use n <= 500 only.

struct Edge { int u, v, w; };
vector<Edge> edges;
int dist[N];

bool bellmanFord(int src, int n) { // returns true if negative cycle exists
    fill(dist+1, dist+n+1, INF);
    dist[src] = 0;
    for(int i = 0; i < n - 1; i++)
        for(auto &[u, v, w] : edges)
            if(dist[u] < INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    // nth iteration — if any update, negative cycle exists
    for(auto &[u, v, w] : edges)
        if(dist[u] < INF && dist[u] + w < dist[v])
            return true;
    return false;
}

int indeg[N];
vector<int> g[N];

vector<int> topoSort(int n) {
    for(int u = 1; u <= n; u++)
        for(auto v : g[u]) indeg[v]++;
    priority_queue<int, vi, greater<int>> pq; // min-heap for lex smallest
    for(int i = 1; i <= n; i++)
        if(!indeg[i]) pq.push(i);
    vector<int> order;
    while(!pq.empty()) {
        int u = pq.top(); pq.pop();
        order.pb(u);
        for(auto v : g[u])
            if(--indeg[v] == 0) pq.push(v);
    }
    if(sz(order) < n) return {}; // cycle exists
    return order;
}

struct Edge { int u, v, w; };

int kruskalMST(int n, vector<Edge> &edges) {
    sort(all(edges), [](auto &a, auto &b){ return a.w < b.w; });
    DSU dsu(n);
    int cost = 0, cnt = 0;
    for(auto &[u, v, w] : edges) {
        if(dsu.unite(u, v)) {
            cost += w;
            if(++cnt == n - 1) break;
        }
    }
    return (cnt == n - 1) ? cost : -1; // -1 if not connected
}

vector<int> g[N], rg[N];
bool vis[N];
vector<int> order;
int comp[N];
int numSCC;

void dfs1(int u) {
    vis[u] = true;
    for(auto v : g[u]) if(!vis[v]) dfs1(v);
    order.pb(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    for(auto v : rg[u]) if(comp[v] == -1) dfs2(v, c);
}

void scc(int n) {
    for(int i = 1; i <= n; i++) if(!vis[i]) dfs1(i);
    fill(comp+1, comp+n+1, -1);
    numSCC = 0;
    for(int i = n - 1; i >= 0; i--) // process in reverse finish order
        if(comp[order[i]] == -1) dfs2(order[i], numSCC++);
}

void addEdge(int u, int v) {
    g[u].pb(v);
    rg[v].pb(u);
}
// comp[u] = SCC id of u (0-indexed). numSCC = total SCCs.
// nodes in same SCC have same comp value.

int tin[N], low[N], timer_ap;
bool vis[N], isAP[N];
vector<int> g[N];
vector<pii> bridges; // {u, v}

void dfs(int u, int par) {
    vis[u] = true;
    tin[u] = low[u] = ++timer_ap;
    int children = 0;
    for(auto v : g[u]) {
        if(v == par) continue;
        if(vis[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= tin[u] && par != -1) isAP[u] = true;
            if(low[v] > tin[u]) bridges.pb({u, v}); // bridge
            children++;
        }
    }
    if(par == -1 && children > 1) isAP[u] = true;
}

void findAPBridges(int n) {
    timer_ap = 0;
    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i, -1);
}
// Note: for multigraphs, track edge index instead of parent node to avoid
// treating parallel edges as back edges.

int par[LG][N], tin[N], tout[N], level[N], lca_timer;
vector<int> g[N];

void dfs(int u, int p, int lvl) {
    tin[u] = ++lca_timer;
    par[0][u] = p;
    level[u] = lvl;
    for(auto v : g[u]) if(v != p) dfs(v, u, lvl + 1);
    tout[u] = lca_timer;
}

void buildLCA(int root, int n) {
    lca_timer = 0;
    dfs(root, root, 0);
    for(int i = 1; i < LG; i++)
        for(int j = 1; j <= n; j++)
            par[i][j] = par[i-1][par[i-1][j]];
}

bool isAnc(int u, int v) { // is u an ancestor of v?
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if(isAnc(u, v)) return u;
    if(isAnc(v, u)) return v;
    for(int i = LG-1; i >= 0; i--)
        if(!isAnc(par[i][u], v)) u = par[i][u];
    return par[0][u];
}

int kthAncestor(int u, int k) { // k-th ancestor of u
    for(int i = LG-1; i >= 0; i--)
        if((k >> i) & 1) u = par[i][u];
    return u;
}

int dist(int u, int v) {
    return level[u] + level[v] - 2 * level[lca(u, v)];
}
// buildLCA(1, n) — call once after building the tree in g[]

vector<int> prefixFunction(const string &s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for(int i = 1; i < n; i++) {
        int j = pi[i-1];
        while(j > 0 && s[i] != s[j]) j = pi[j-1];
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// returns 0-indexed positions in text where pattern starts
vector<int> kmpSearch(const string &text, const string &pattern) {
    string s = pattern + '#' + text;
    auto pi = prefixFunction(s);
    vector<int> matches;
    int p = pattern.size();
    for(int i = p + 1; i < (int)s.size(); i++)
        if(pi[i] == p) matches.pb(i - 2 * p);
    return matches;
}

// period of string s: if (n % (n - pi[n-1])) == 0, period = n - pi[n-1]

vector<int> zFunction(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;
    for(int i = 1, l = 0, r = 0; i < n; i++) {
        if(i <= r) z[i] = min(r - i + 1, z[i - l]);
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

// Pattern matching: s = pattern + '#' + text
// positions i in text where z[i] == |pattern|

struct Hash {
    static const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
    static const int B1 = 131, B2 = 137;
    vector<long long> h1, h2, p1, p2;

    void build(const string &s) {
        int n = s.size();
        h1.resize(n+1, 0); h2.resize(n+1, 0);
        p1.resize(n+1, 1); p2.resize(n+1, 1);
        for(int i = 0; i < n; i++) {
            h1[i+1] = (h1[i] * B1 + s[i]) % MOD1;
            h2[i+1] = (h2[i] * B2 + s[i]) % MOD2;
            p1[i+1] = p1[i] * B1 % MOD1;
            p2[i+1] = p2[i] * B2 % MOD2;
        }
    }

    pair<long long,long long> get(int l, int r) { // 0-indexed [l, r]
        long long v1 = (h1[r+1] - h1[l] * p1[r-l+1] % MOD1 + MOD1 * 2) % MOD1;
        long long v2 = (h2[r+1] - h2[l] * p2[r-l+1] % MOD2 + MOD2 * 2) % MOD2;
        return {v1, v2};
    }
};
// Hash h; h.build(s); h.get(l, r) == h.get(l2, r2) → substrings equal

struct Trie {
    struct Node {
        int ch[2] = {0, 0};
        int cnt = 0;
    };
    vector<Node> t;
    int root;

    Trie() { t.push_back(Node()); root = 0; }

    void insert(int x, int BITS = 30) {
        int cur = root;
        for(int i = BITS; i >= 0; i--) {
            int b = (x >> i) & 1;
            if(!t[cur].ch[b]) {
                t[cur].ch[b] = t.size();
                t.push_back(Node());
            }
            cur = t[cur].ch[b];
            t[cur].cnt++;
        }
    }

    void remove(int x, int BITS = 30) {
        int cur = root;
        for(int i = BITS; i >= 0; i--) {
            cur = t[cur].ch[(x >> i) & 1];
            t[cur].cnt--;
        }
    }

    int maxXor(int x, int BITS = 30) {
        int cur = root, ans = 0;
        for(int i = BITS; i >= 0; i--) {
            int b = (x >> i) & 1;
            int want = 1 - b;
            if(t[cur].ch[want] && t[t[cur].ch[want]].cnt > 0) {
                ans |= (1 << i);
                cur = t[cur].ch[want];
            } else {
                cur = t[cur].ch[b];
            }
        }
        return ans;
    }

    int minXor(int x, int BITS = 30) {
        int cur = root, ans = 0;
        for(int i = BITS; i >= 0; i--) {
            int b = (x >> i) & 1;
            if(t[cur].ch[b] && t[t[cur].ch[b]].cnt > 0)
                cur = t[cur].ch[b];
            else {
                ans |= (1 << i);
                cur = t[cur].ch[1-b];
            }
        }
        return ans;
    }
};

const int MOD = 1e9 + 7;

int pw(long long a, long long b, long long mod = MOD) {
    int ans = 1;
    a %= mod;
    while(b > 0) {
        if(b & 1) ans = (__int128)ans * a % mod;
        a = (__int128)a * a % mod;
        b >>= 1;
    }
    return ans;
}

int modinv(int a, int mod = MOD) {
    return pw(a, mod - 2, mod); // only for prime mod
}

int add(int a, int b, int mod = MOD) { return (a + b) % mod; }
int sub(int a, int b, int mod = MOD) { return ((a - b) % mod + mod) % mod; }
int mul(int a, int b, int mod = MOD) { return (long long)a * b % mod; }

// --- nCr precomputation ---
int fact[N], inv_fact[N];

void precompFact(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = mul(fact[i-1], i);
    inv_fact[n] = modinv(fact[n]);
    for(int i = n-1; i >= 0; i--) inv_fact[i] = mul(inv_fact[i+1], i+1);
}

int nCr(int n, int r) {
    if(r < 0 || r > n) return 0;
    return mul(fact[n], mul(inv_fact[r], inv_fact[n-r]));
}
// precompFact(N-1) once in main, then nCr(n, r) in O(1)

const int SZ = 2; // matrix dimension — change per problem

struct Matrix {
    long long a[SZ][SZ];
    Matrix() { memset(a, 0, sizeof(a)); }

    Matrix operator*(const Matrix &o) const {
        Matrix res;
        for(int i = 0; i < SZ; i++)
            for(int k = 0; k < SZ; k++) if(a[i][k])
                for(int j = 0; j < SZ; j++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return res;
    }
};

Matrix identity() {
    Matrix I;
    for(int i = 0; i < SZ; i++) I.a[i][i] = 1;
    return I;
}

Matrix matpow(Matrix M, long long p) {
    Matrix res = identity();
    while(p > 0) {
        if(p & 1) res = res * M;
        M = M * M;
        p >>= 1;
    }
    return res;
}
// Use: encode F(n) = M * F(n-1), then F(n) = matpow(M, n) * F(0)
// Fibonacci: M = [[1,1],[1,0]], F(0) = [1, 0]

// Count integers in [0, R] satisfying property P.
// For [L, R]: f(R) - f(L-1).
// State: (position, tight, ...property-specific state)

// Example: count numbers in [0, R] with at most 3 non-zero digits
// Adapt state dimensions to the problem (here: pos, tight, nonzero_count)
int digits[20], sz;
int cache[20][2][11]; // [pos][tight][nonzero_count], adjust last dim per problem

int dp(int idx, bool tight, int nonzero) {
    if(nonzero > 3) return 0;
    if(idx == sz) return 1;
    int &ans = cache[idx][tight][nonzero];
    if(ans != -1) return ans;
    ans = 0;
    int hi = tight ? digits[idx] : 9;
    for(int d = 0; d <= hi; d++)
        ans += dp(idx + 1, tight && (d == hi), nonzero + (d > 0));
    return ans;
}

int f(long long R) {
    if(R < 0) return 0;
    sz = 0;
    while(R > 0) { digits[sz++] = R % 10; R /= 10; }
    reverse(digits, digits + sz);
    memset(cache, -1, sizeof(cache));
    return dp(0, true, 0);
}
// answer for [L, R] = f(R) - f(L - 1)

// Next Greater Element (to the right)
vector<int> nextGreater(vector<int> &a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st; // stores indices
    for(int i = 0; i < n; i++) {
        while(!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = i; // or a[i] for the value
            st.pop();
        }
        st.push(i);
    }
    return ans; // ans[i] = index of next greater element, -1 if none
}

// Previous Smaller Element (to the left) — iterate right-to-left and flip condition
// Largest rectangle in histogram uses two monotone stack passes (or one pass)

int largestRectangle(vector<int> &h) {
    int n = h.size();
    stack<int> st;
    int ans = 0;
    h.pb(0); // sentinel
    for(int i = 0; i <= n; i++) {
        while(!st.empty() && h[st.top()] > h[i]) {
            int height = h[st.top()]; st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            ans = max(ans, height * width);
        }
        st.push(i);
    }
    return ans;
}

vector<int> slidingMax(vector<int> &a, int k) {
    deque<int> dq; // stores indices, front = current max
    vector<int> ans;
    for(int i = 0; i < (int)a.size(); i++) {
        while(!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if(i >= k - 1) ans.pb(a[dq.front()]);
    }
    return ans;
}

int lis(vector<int> &a) {
    vector<int> dp; // dp[i] = smallest tail of IS of length i+1
    for(int x : a) {
        auto it = lower_bound(all(dp), x); // use upper_bound for non-strict
        if(it == dp.end()) dp.pb(x);
        else *it = x;
    }
    return dp.size();
}

// n items, capacity W, weights w[], values v[]
vector<int> knapsack(int n, int W, vector<int> &w, vector<int> &v) {
    vector<int> dp(W + 1, 0);
    for(int i = 0; i < n; i++)
        for(int j = W; j >= w[i]; j--)  // iterate down for 0/1
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp; // dp[W] = max value with capacity W
}
// Unbounded knapsack: iterate j upward

// dp[mask][i] = min cost to visit exactly nodes in mask, ending at i
int tsp(int n, vector<vector<int>> &cost) {
    int FULL = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0; // start at node 0
    for(int mask = 1; mask <= FULL; mask++) {
        for(int u = 0; u < n; u++) {
            if(!(mask & (1 << u)) || dp[mask][u] == INF) continue;
            for(int v = 0; v < n; v++) {
                if(mask & (1 << v)) continue;
                int nmask = mask | (1 << v);
                dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + cost[u][v]);
            }
        }
    }
    int ans = INF;
    for(int u = 1; u < n; u++)
        ans = min(ans, dp[FULL][u] + cost[u][0]);
    return ans;
}

// dp[mask] = sum of f[sub] for all sub ⊆ mask
// init dp[mask] = f[mask], then:
void sos(vector<int> &dp, int n) {
    for(int i = 0; i < n; i++)
        for(int mask = 0; mask < (1 << n); mask++)
            if(mask >> i & 1)
                dp[mask] += dp[mask ^ (1 << i)];
}
// O(n * 2^n)

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; (long long)i * i <= n; i++)
        if(is_prime[i])
            for(int j = i * i; j <= n; j += i)
                is_prime[j] = false;
    return is_prime;
}

// Linear sieve + smallest prime factor (for O(log n) factorization)
int spf[N]; // smallest prime factor
void linearSieve(int n) {
    vector<int> primes;
    iota(spf, spf + n + 1, 0);
    for(int i = 2; i <= n; i++) {
        if(spf[i] == i) primes.pb(i); // i is prime
        for(int j = 0; j < (int)primes.size() && primes[j] <= spf[i] && (long long)i * primes[j] <= n; j++)
            spf[i * primes[j]] = primes[j];
    }
}

vector<int> factorize(int x) {
    vector<int> f;
    while(x > 1) { f.pb(spf[x]); x /= spf[x]; }
    return f;
}

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

// Extended GCD: returns gcd, sets x, y such that ax + by = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if(!b) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}
// modinv via extgcd (works for non-prime mod too):
// long long inv = ((x % mod) + mod) % mod;

// "minimum value such that check(mid) is true"
// check(mid) must be monotone: false...false...true...true

auto bsearch = [&](long long lo, long long hi) {
    while(lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if(check(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo; // first value where check is true
};

// "maximum value such that check(mid) is true"
auto bsearchMax = [&](long long lo, long long hi) {
    while(lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if(check(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
};

// Count subarrays with sum exactly k (non-negative array: use two pointers)
// For general arrays: prefix sum + hashmap
int countSubarraysSum(vector<int> &a, int k) {
    unordered_map<int,int> freq;
    freq[0] = 1;
    int psum = 0, ans = 0;
    for(int x : a) {
        psum += x;
        ans += freq[psum - k];
        freq[psum]++;
    }
    return ans;
}

// Longest subarray with sum <= k (non-negative values)
int longestSubarray(vector<int> &a, int k) {
    int l = 0, sum = 0, ans = 0;
    for(int r = 0; r < (int)a.size(); r++) {
        sum += a[r];
        while(sum > k) sum -= a[l++];
        ans = max(ans, r - l + 1);
    }
    return ans;
}

// Check if bit k is set
bool bitSet(int x, int k) { return (x >> k) & 1; }

// Set bit k
int setBit(int x, int k) { return x | (1 << k); }

// Clear bit k
int clearBit(int x, int k) { return x & ~(1 << k); }

// Lowest set bit
int lsb(int x) { return x & (-x); }

// Count set bits
int popcount(int x) { return __builtin_popcount(x); }     // int
int popcount(ll x)  { return __builtin_popcountll(x); }   // long long

// Enumerate all subsets of mask (including empty)
for(int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process sub
}
// Add sub == 0 case separately if needed

// Next permutation of bits (same popcount, next larger value)
int nextPerm(int x) {
    int c = x & -x, r = x + c;
    return (((r ^ x) >> 2) / c) | r;
}

// Check power of 2
bool isPow2(int x) { return x > 0 && !(x & (x - 1)); }

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>,
             rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// ordered_set s;
// s.insert(x);
// s.find_by_order(k) → iterator to k-th element (0-indexed)
// s.order_of_key(x)  → number of elements strictly less than x
// For duplicates: use pair<int,int> with unique IDs as second element

struct Query { int l, r, idx; };

// Block size = sqrt(n)
void mo(vector<int> &a, vector<Query> &queries) {
    int n = a.size(), q = queries.size();
    int block = max(1, (int)sqrt(n));

    sort(queries.begin(), queries.end(), [&](auto &a, auto &b) {
        int ba = a.l / block, bb = b.l / block;
        if(ba != bb) return ba < bb;
        return (ba & 1) ? (a.r > b.r) : (a.r < b.r); // alternating for speed
    });

    vector<int> ans(q);
    int curL = 0, curR = -1; // current window

    auto add = [&](int pos) { /* add a[pos] to current window */ };
    auto rem = [&](int pos) { /* remove a[pos] from current window */ };

    for(auto &[l, r, idx] : queries) {
        while(curR < r) add(++curR);
        while(curL > l) add(--curL);
        while(curR > r) rem(curR--);
        while(curL < l) rem(curL++);
        ans[idx] = /* current answer */;
    }
}
// O((n + q) * sqrt(n))

// Variables: 1..n. Literal x = x, negation = x + n.
// Clause (a OR b): add edges ~a -> b and ~b -> a.

struct TwoSat {
    int n;
    vector<int> g[2*N], rg[2*N];
    bool vis[2*N];
    vector<int> order;
    int comp[2*N];
    int numSCC;

    void init(int _n) { n = _n; }

    int neg(int x) { return x <= n ? x + n : x - n; }

    void addClause(int a, int b) { // a OR b
        g[neg(a)].pb(b);  g[neg(b)].pb(a);
        rg[b].pb(neg(a)); rg[a].pb(neg(b));
    }

    void dfs1(int u) { vis[u]=1; for(auto v:g[u]) if(!vis[v]) dfs1(v); order.pb(u); }
    void dfs2(int u, int c) { comp[u]=c; for(auto v:rg[u]) if(comp[v]==-1) dfs2(v,c); }

    // returns true if satisfiable, fills vals[]
    bool solve(vector<bool> &vals) {
        for(int i=1;i<=2*n;i++) if(!vis[i]) dfs1(i);
        fill(comp+1, comp+2*n+1, -1);
        numSCC = 0;
        for(int i=2*n-1;i>=0;i--)
            if(comp[order[i]]==-1) dfs2(order[i], numSCC++);
        vals.resize(n+1);
        for(int i=1;i<=n;i++) {
            if(comp[i] == comp[i+n]) return false;
            vals[i] = comp[i] > comp[i+n];
        }
        return true;
    }
};
// addClause(a, b): variable a is literal a (true) or a+n (false), same for b

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randInt(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

// Shuffle
shuffle(all(v), rng);

// Random hash base (anti-hack)
const int BASE = uniform_int_distribution<int>(200, 1e9)(rng);

// In a separate file or toggle with #define
// brute.cpp and sol.cpp compiled separately
// stress.sh:
// while true; do
//   python3 gen.py > inp.txt
//   ./brute < inp.txt > out_brute.txt
//   ./sol < inp.txt > out_sol.txt
//   if ! diff -q out_brute.txt out_sol.txt; then echo "DIFF!"; break; fi
// done