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

using ll = long long;

// =====================================================================
// This file provides a collection of ready‑to‑use segment tree
// implementations.  Each class is a "black box" – you only need to
// know what it does, how to call its methods, and what to expect.
// All comments above each class/method explain exactly that.
// =====================================================================

// ---------------------------------------------------------------------
// 1) Basic Iterative Segment Tree – Range Sum with Point Updates
//    Use when you need to:
//      - change one element in the array (point update)
//      - ask for the sum of any interval [l, r]
//    Very fast and simple.
// ---------------------------------------------------------------------

struct SegTreeSum {
    // -----------------------------------------------------------------
    // Purpose:
    //   Maintains an array of numbers.  Supports:
    //     - point update: set arr[pos] = new_value
    //     - range sum  : sum of arr[l] + ... + arr[r]
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create object: SegTreeSum st(my_vector);
    //   2) st.update(pos, value)  – pos is 0‑indexed
    //   3) st.query(l, r)         – inclusive, 0‑indexed; returns sum
    // -----------------------------------------------------------------
    // Time Complexity:
    //   Both update and query run in O(log n), where n is array size.
    // -----------------------------------------------------------------
    // Constraints:
    //   - array size is fixed after construction.
    //   - values fit in long long (64‑bit).
    // -----------------------------------------------------------------
    int n;
    vector<ll> tree;
    SegTreeSum() {}
    SegTreeSum(const vector<ll>& a) { build(a); }
    void build(const vector<ll>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;
        tree.assign(2*n, 0);
        for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
        for (int i = n-1; i > 0; i--) tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update(int pos, ll val) {
        pos += n;
        tree[pos] = val;
        for (pos >>= 1; pos; pos >>= 1) tree[pos] = tree[pos<<1] + tree[pos<<1|1];
    }
    ll query(int l, int r) { // inclusive
        l += n; r += n;
        ll res = 0;
        while (l <= r) {
            if (l & 1) res += tree[l++];
            if (!(r & 1)) res += tree[r--];
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

// ---------------------------------------------------------------------
// 2) Basic Iterative Segment Tree – Range Minimum with Point Updates
//    Same as above but query returns the minimum value on the interval.
// ---------------------------------------------------------------------

struct SegTreeMin {
    // -----------------------------------------------------------------
    // Purpose:
    //   Maintains an array of numbers.  Supports:
    //     - point update: set arr[pos] = new_value
    //     - range minimum: min(arr[l..r])
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create object: SegTreeMin st(my_vector);
    //   2) st.update(pos, value)  – pos is 0‑indexed
    //   3) st.query(l, r)         – inclusive, 0‑indexed; returns minimum
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per operation.
    // Constraints: values fit in long long.
    // -----------------------------------------------------------------
    int n;
    vector<ll> tree;
    SegTreeMin() {}
    SegTreeMin(const vector<ll>& a) { build(a); }
    void build(const vector<ll>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;
        tree.assign(2*n, LLONG_MAX);
        for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
        for (int i = n-1; i > 0; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update(int pos, ll val) {
        pos += n;
        tree[pos] = val;
        for (pos >>= 1; pos; pos >>= 1) tree[pos] = min(tree[pos<<1], tree[pos<<1|1]);
    }
    ll query(int l, int r) {
        l += n; r += n;
        ll res = LLONG_MAX;
        while (l <= r) {
            if (l & 1) res = min(res, tree[l++]);
            if (!(r & 1)) res = min(res, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

// (Range Maximum is analogous – you can copy and change min to max.)

// ---------------------------------------------------------------------
// 3) Lazy Segment Tree – Range Add & Range Sum (recursive)
//    Use when you need to add a value to all elements in an interval
//    and also query the sum of any interval.
// ---------------------------------------------------------------------

struct LazySegTreeSum {
    // -----------------------------------------------------------------
    // Purpose:
    //   Maintains an array.  Supports two operations on a range:
    //     - range add: increase every element in [l, r] by a given value
    //     - range sum: compute sum of elements in [l, r]
    //   Both are O(log n).
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: LazySegTreeSum st(my_vector);
    //   2) st.range_add(l, r, delta)   – add delta to indices [l, r]
    //   3) st.range_sum(l, r)          – return sum on [l, r]
    //   All indices are 0‑based and inclusive.
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per range_add and range_sum.
    // Constraints: n >= 1; values fit in long long.
    // Note: This is a recursive implementation, recursion depth is O(log n).
    // -----------------------------------------------------------------
    int n;
    vector<ll> tree, lazy;
    LazySegTreeSum(const vector<ll>& a) {
        n = a.size();
        tree.assign(4*n, 0);
        lazy.assign(4*n, 0);
        build(1, 0, n-1, a);
    }
    void build(int node, int l, int r, const vector<ll>& a) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int mid = (l+r)/2;
        build(node*2, l, mid, a);
        build(node*2+1, mid+1, r, a);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    void apply(int node, int l, int r, ll val) {
        tree[node] += val * (r - l + 1);
        lazy[node] += val;
    }
    void push(int node, int l, int r) {
        if (lazy[node] != 0 && l != r) {
            int mid = (l+r)/2;
            apply(node*2, l, mid, lazy[node]);
            apply(node*2+1, mid+1, r, lazy[node]);
            lazy[node] = 0;
        }
    }
    void range_add(int L, int R, ll val) { range_add(1, 0, n-1, L, R, val); }
    void range_add(int node, int l, int r, int L, int R, ll val) {
        if (L > r || R < l) return;
        if (L <= l && r <= R) {
            apply(node, l, r, val);
            return;
        }
        push(node, l, r);
        int mid = (l+r)/2;
        range_add(node*2, l, mid, L, R, val);
        range_add(node*2+1, mid+1, r, L, R, val);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    ll range_sum(int L, int R) { return range_sum(1, 0, n-1, L, R); }
    ll range_sum(int node, int l, int r, int L, int R) {
        if (L > r || R < l) return 0;
        if (L <= l && r <= R) return tree[node];
        push(node, l, r);
        int mid = (l+r)/2;
        return range_sum(node*2, l, mid, L, R) +
               range_sum(node*2+1, mid+1, r, L, R);
    }
};

// ---------------------------------------------------------------------
// 4) Lazy Segment Tree – Range Assignment & Range Sum
//    Similar to above but the operation is "set all elements in [l, r]
//    to a given value" (not add).
// ---------------------------------------------------------------------

struct LazySegTreeAssign {
    // -----------------------------------------------------------------
    // Purpose:
    //   Maintains an array.  Supports:
    //     - range assign: set all elements in [l, r] to a given value
    //     - range sum   : sum of elements in [l, r]
    //   Both O(log n).
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: LazySegTreeAssign st(my_vector);
    //   2) st.range_set(l, r, value)   – assigns [l, r] to 'value'
    //   3) st.range_sum(l, r)          – returns sum on [l, r]
    //   Indices are 0‑based and inclusive.
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per operation.
    // Constraints: n >= 1; values fit in long long.
    // Note: The lazy tag indicates an assignment; it overrides any previous
    //       additions (but this implementation only does assignment).
    // -----------------------------------------------------------------
    int n;
    vector<ll> tree, lazy;
    vector<bool> hasLazy; // true if lazy holds a pending assignment
    LazySegTreeAssign(const vector<ll>& a) {
        n = a.size();
        tree.assign(4*n, 0);
        lazy.assign(4*n, 0);
        hasLazy.assign(4*n, false);
        build(1, 0, n-1, a);
    }
    void build(int node, int l, int r, const vector<ll>& a) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int mid = (l+r)/2;
        build(node*2, l, mid, a);
        build(node*2+1, mid+1, r, a);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    void apply(int node, int l, int r, ll val) {
        tree[node] = val * (r - l + 1);
        lazy[node] = val;
        hasLazy[node] = true;
    }
    void push(int node, int l, int r) {
        if (hasLazy[node] && l != r) {
            int mid = (l+r)/2;
            apply(node*2, l, mid, lazy[node]);
            apply(node*2+1, mid+1, r, lazy[node]);
            hasLazy[node] = false;
        }
    }
    void range_set(int L, int R, ll val) { range_set(1, 0, n-1, L, R, val); }
    void range_set(int node, int l, int r, int L, int R, ll val) {
        if (L > r || R < l) return;
        if (L <= l && r <= R) {
            apply(node, l, r, val);
            return;
        }
        push(node, l, r);
        int mid = (l+r)/2;
        range_set(node*2, l, mid, L, R, val);
        range_set(node*2+1, mid+1, r, L, R, val);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    ll range_sum(int L, int R) { return range_sum(1, 0, n-1, L, R); }
    ll range_sum(int node, int l, int r, int L, int R) {
        if (L > r || R < l) return 0;
        if (L <= l && r <= R) return tree[node];
        push(node, l, r);
        int mid = (l+r)/2;
        return range_sum(node*2, l, mid, L, R) +
               range_sum(node*2+1, mid+1, r, L, R);
    }
};

// ---------------------------------------------------------------------
// 5) Segment Tree with Custom Monoid (template)
//    This is a generic iterative segment tree that works for any
//    associative operation (like sum, min, max, gcd, xor, etc.).
// ---------------------------------------------------------------------

template<typename T, T (*combine)(T, T), T (*identity)()>
struct SegTreeMonoid {
    // -----------------------------------------------------------------
    // Purpose:
    //   A generic segment tree that can answer range queries for any
    //   associative binary operation (e.g., sum, max, gcd).
    //   The operation must be associative and have an identity element.
    //   Supports point updates and range queries.
    // -----------------------------------------------------------------
    // How to use:
    //   1) Define a combine function: T my_combine(T a, T b) { ... }
    //   2) Define an identity function: T my_identity() { return ...; }
    //   3) Create: SegTreeMonoid<T, my_combine, my_identity> st(vec);
    //   4) st.update(pos, new_value)
    //   5) st.query(l, r) returns combine over [l, r] (inclusive).
    //   Indices are 0‑based.
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per update and query.
    // Constraints:
    //   - The operation must be associative.
    //   - The identity must be a true identity: combine(x, identity) = x.
    //   - The tree stores values of type T.
    // -----------------------------------------------------------------
    // Note: For non‑commutative operations (e.g., matrix multiplication),
    //       the order of combination is preserved correctly.
    // -----------------------------------------------------------------
    int n;
    vector<T> tree;
    SegTreeMonoid(const vector<T>& a) { build(a); }
    void build(const vector<T>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;
        tree.assign(2*n, identity());
        for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
        for (int i = n-1; i > 0; i--) tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    void update(int pos, T val) {
        pos += n;
        tree[pos] = val;
        for (pos >>= 1; pos; pos >>= 1) tree[pos] = combine(tree[pos<<1], tree[pos<<1|1]);
    }
    T query(int l, int r) {
        l += n; r += n;
        T resL = identity(), resR = identity();
        while (l <= r) {
            if (l & 1) resL = combine(resL, tree[l++]);
            if (!(r & 1)) resR = combine(tree[r--], resR);
            l >>= 1; r >>= 1;
        }
        return combine(resL, resR);
    }
};

// Example: sum monoid
ll sum_ll(ll a, ll b) { return a + b; }
ll zero_ll() { return 0; }
using SegTreeSumMonoid = SegTreeMonoid<ll, sum_ll, zero_ll>;

// Example: max monoid
ll max_ll(ll a, ll b) { return max(a, b); }
ll neg_inf() { return LLONG_MIN; }
using SegTreeMax = SegTreeMonoid<ll, max_ll, neg_inf>;

// ---------------------------------------------------------------------
// 6) Merge Sort Tree
//    Each node stores a sorted vector of its segment.  Allows counting
//    how many numbers in a range are ≤ a given value, and finding the
//    k‑th smallest in a range (with binary search).
// ---------------------------------------------------------------------

struct MergeSortTree {
    // -----------------------------------------------------------------
    // Purpose:
    //   Builds a segment tree where every node contains a sorted list
    //   of the elements in its segment.  Enables:
    //     - count of elements ≤ x in [l, r]
    //     - k‑th smallest element in [l, r] (via binary search)
    //   All operations are O(log² n) (the count query) or O(log n * log V)
    //   for k‑th (where V is value range).
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: MergeSortTree mst(my_int_vector);
    //   2) mst.query_le(l, r, x)   – returns count of values ≤ x in [l, r]
    //   3) mst.query_kth(l, r, k)  – returns the k‑th smallest (1‑indexed)
    //   Indices are 0‑based, inclusive.
    // -----------------------------------------------------------------
    // Time Complexity:
    //   - query_le: O(log² n) (each level does a binary search)
    //   - query_kth: O(log n * log V) where V is the value range (1e9)
    //     because it binary searches the answer and calls query_le each time.
    // -----------------------------------------------------------------
    // Constraints:
    //   - Values must be in the range [-1e9, 1e9] (adjustable in query_kth).
    //   - n up to ~1e5 (memory ~ n log n).
    // -----------------------------------------------------------------
    // Note: The tree stores ints; for long long adapt accordingly.
    // -----------------------------------------------------------------
    int n;
    vector<vector<int>> tree;
    MergeSortTree(const vector<int>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;
        tree.resize(2*n);
        for (int i = 0; i < (int)a.size(); i++) tree[n+i] = {a[i]};
        for (int i = n-1; i > 0; i--) {
            tree[i].resize(tree[i<<1].size() + tree[i<<1|1].size());
            merge(tree[i<<1].begin(), tree[i<<1].end(),
                  tree[i<<1|1].begin(), tree[i<<1|1].end(),
                  tree[i].begin());
        }
    }
    int query_le(int l, int r, int x) {
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += upper_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
                l++;
            }
            if (!(r & 1)) {
                res += upper_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
                r--;
            }
            l >>= 1; r >>= 1;
        }
        return res;
    }
    int query_kth(int l, int r, int k) {
        int low = -1e9, high = 1e9;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (query_le(l, r, mid) >= k) high = mid;
            else low = mid + 1;
        }
        return low;
    }
};

// ---------------------------------------------------------------------
// 7) Fenwick Tree (Binary Indexed Tree)
//    Often used for frequency counting after coordinate compression.
//    Supports point updates and prefix sums, plus finding k‑th element.
// ---------------------------------------------------------------------

struct Fenwick {
    // -----------------------------------------------------------------
    // Purpose:
    //   A Fenwick tree (BIT) for 1‑indexed arrays.  Supports:
    //     - add value delta at position idx
    //     - prefix sum up to idx
    //     - range sum [l, r]
    //     - find smallest idx with prefix sum >= k (k‑th order statistic)
    //   Very efficient and simple.
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: Fenwick fw(n)  – where n is the maximum index (1‑based)
    //   2) fw.add(idx, delta)     – idx is 1‑based
    //   3) fw.sum(idx)            – returns sum of positions 1..idx
    //   4) fw.range_sum(l, r)     – sum on [l, r] (1‑based, inclusive)
    //   5) fw.kth(k)              – returns smallest idx with prefix sum ≥ k
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per operation.
    // Constraints: n >= 1; all internal values fit in int (or long long).
    // Note: The kth method uses binary lifting and requires that all
    //       values are non‑negative and the total sum >= k.
    // -----------------------------------------------------------------
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n+1, 0) {}
    void add(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    int range_sum(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l-1);
    }
    int kth(int k) {
        int idx = 0;
        int mask = 1 << (31 - __builtin_clz(n));
        while (mask) {
            int nxt = idx + mask;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
            mask >>= 1;
        }
        return idx + 1;
    }
};

// ---------------------------------------------------------------------
// 8) Dynamic Segment Tree (point update, range sum over large coordinates)
//    Creates nodes only when needed, so you can use it even if the
//    coordinate range is huge (e.g., up to 1e9).
// ---------------------------------------------------------------------

struct DynamicSegTree {
    // -----------------------------------------------------------------
    // Purpose:
    //   A segment tree that does not pre‑allocate a full array.
    //   It builds nodes on demand, so it can work with very large
    //   index ranges (e.g., n up to 1e9) while using memory proportional
    //   to the number of updates.
    //   Supports point updates (set value) and range sum queries.
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: DynamicSegTree dseg(n)  – where n is the size (0..n-1)
    //   2) dseg.update(pos, value)         – pos is 0‑based
    //   3) dseg.query(L, R)                – returns sum on [L, R]
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per update/query (but log n is based on
    //   the coordinate range, not number of elements).
    // -----------------------------------------------------------------
    // Constraints:
    //   - n can be as large as 1e9 (or even more, if memory allows).
    //   - Number of updates should not be too large (e.g., ≤ 1e5) to keep
    //     memory reasonable.
    //   - Values fit in long long.
    // -----------------------------------------------------------------
    // Note: The tree is implemented with a vector of nodes; each node has
    //       left child, right child, and sum.  Node 0 is a null node.
    // -----------------------------------------------------------------
    struct Node {
        ll sum;
        int left, right;
        Node() : sum(0), left(-1), right(-1) {}
    };
    vector<Node> st;
    int n; // range [0, n-1]
    DynamicSegTree(int n) : n(n) {
        st.reserve(4 * 100000); // reserve some space
        st.emplace_back(); // node 0 = null
        st.emplace_back(); // node 1 = root (this was missing in the original)
    }
    void update(int pos, ll val) { update(1, 0, n-1, pos, val); }
    void update(int node, int l, int r, int pos, ll val) {
        if (l == r) {
            st[node].sum = val;
            return;
        }
        int mid = (l+r)/2;
        if (pos <= mid) {
            if (st[node].left == -1) {
                st[node].left = st.size();
                st.emplace_back();
            }
            update(st[node].left, l, mid, pos, val);
        } else {
            if (st[node].right == -1) {
                st[node].right = st.size();
                st.emplace_back();
            }
            update(st[node].right, mid+1, r, pos, val);
        }
        st[node].sum = (st[node].left != -1 ? st[st[node].left].sum : 0) +
                       (st[node].right != -1 ? st[st[node].right].sum : 0);
    }
    ll query(int L, int R) { return query(1, 0, n-1, L, R); }
    ll query(int node, int l, int r, int L, int R) {
        if (node == -1) return 0;
        if (L <= l && r <= R) return st[node].sum;
        int mid = (l+r)/2;
        ll res = 0;
        if (L <= mid) res += query(st[node].left, l, mid, L, R);
        if (R > mid) res += query(st[node].right, mid+1, r, L, R);
        return res;
    }
};

// ---------------------------------------------------------------------
// 9) Persistent Segment Tree (Chairman Tree)
//    Maintains multiple versions of a segment tree after point updates.
//    Often used for static range k‑th smallest queries.
// ---------------------------------------------------------------------

struct PersistentSegTree {
    // -----------------------------------------------------------------
    // Purpose:
    //   Builds a persistent segment tree (also called Chairman tree)
    //   that can answer k‑th smallest queries on any subarray of a
    //   static array in O(log n).
    //   Each version corresponds to a prefix of the array.
    // -----------------------------------------------------------------
    // How to use:
    //   1) Compress the array values to the range [1, m].
    //   2) Create: PersistentSegTree pst(m);
    //   3) pst.build(compressed_vector)  – where compressed_vector
    //      contains the compressed values for the whole array.
    //   4) pst.query_kth(l, r, k)        – returns the compressed value
    //      of the k‑th smallest in the subarray [l, r] (both 1‑based).
    //   5) Convert back using the original value array.
    // -----------------------------------------------------------------
    // Time Complexity: O(log m) per query.
    //   Build: O(n log m).
    // -----------------------------------------------------------------
    // Constraints:
    //   - Array size n and value range m up to ~1e5.
    //   - Memory: O(n log m) nodes, reserve enough.
    //   - l and r are 1‑based positions in the original array.
    // -----------------------------------------------------------------
    // Note: The class stores roots for each prefix.  roots[0] = empty tree.
    //       query_kth(l, r, k) uses roots[l-1] and roots[r].
    // -----------------------------------------------------------------
    struct Node {
        int left, right, sum;
        Node(int l=0, int r=0, int s=0) : left(l), right(r), sum(s) {}
    };
    vector<Node> tree;
    vector<int> roots;
    int n; // range of values (1..n)
    PersistentSegTree(int n) : n(n) {
        tree.reserve( (n+5) * 20 );
        tree.emplace_back(0,0,0); // node 0 = null
        roots.push_back(0);
    }
    int update(int prev, int l, int r, int pos) {
        int cur = tree.size();
        tree.push_back(tree[prev]);
        tree[cur].sum++;
        if (l != r) {
            int mid = (l+r)/2;
            if (pos <= mid) {
                int newLeft = update(tree[prev].left, l, mid, pos);
                tree[cur].left = newLeft;
            } else {
                int newRight = update(tree[prev].right, mid+1, r, pos);
                tree[cur].right = newRight;
            }
        }
        return cur;
    }
    void build(const vector<int>& arr) {
        for (int val : arr) {
            int newRoot = update(roots.back(), 1, n, val);
            roots.push_back(newRoot);
        }
    }
    int query_kth(int l, int r, int k) {
        return query_kth(roots[l-1], roots[r], 1, n, k);
    }
    int query_kth(int u, int v, int l, int r, int k) {
        if (l == r) return l;
        int mid = (l+r)/2;
        int leftCount = tree[tree[v].left].sum - tree[tree[u].left].sum;
        if (leftCount >= k)
            return query_kth(tree[u].left, tree[v].left, l, mid, k);
        else
            return query_kth(tree[u].right, tree[v].right, mid+1, r, k - leftCount);
    }
};

// ---------------------------------------------------------------------
// 10) Segment Tree Beats (incomplete – NOT IMPLEMENTED)
//     This was meant to support range chmin, chmax, add, sum, etc.
//     However, the original code is incomplete and contains syntax errors.
//     I have removed it to avoid confusion.
//     If you need a working Segment Tree Beats, please look for a
//     complete implementation elsewhere.
// ---------------------------------------------------------------------

// ---------------------------------------------------------------------
// 11) Lazy Segment Tree for Range Affine Transformations
//     Applies transformations of the form: a[i] = a[i] * mul + add
//     on a range, and supports range sum queries.
// ---------------------------------------------------------------------

struct LazyAffine {
    // -----------------------------------------------------------------
    // Purpose:
    //   Maintains an array and supports range updates of the form
    //     for each i in [l, r]: a[i] = a[i] * m + a
    //   (where m and a are given constants) and also range sum queries.
    //   This is a combination of multiplication and addition (affine).
    // -----------------------------------------------------------------
    // How to use:
    //   1) Create: LazyAffine la(my_vector);
    //   2) la.range_affine(l, r, mul, add) – applies transformation
    //   3) la.range_sum(l, r)              – returns sum on [l, r]
    //   Indices are 0‑based, inclusive.
    // -----------------------------------------------------------------
    // Time Complexity: O(log n) per operation.
    // Constraints:
    //   - Values fit in long long.
    //   - The operations are applied in the order: first multiply then add.
    //   - The lazy tags compose correctly.
    // -----------------------------------------------------------------
    // Note: This implementation only maintains the sum; it does not
    //       maintain min/max.  For more advanced queries, extend it.
    // -----------------------------------------------------------------
    int n;
    vector<ll> sum, mul, add;
    LazyAffine(const vector<ll>& a) {
        n = a.size();
        sum.assign(4*n, 0);
        mul.assign(4*n, 1);
        add.assign(4*n, 0);
        build(1, 0, n-1, a);
    }
    void build(int node, int l, int r, const vector<ll>& a) {
        if (l == r) { sum[node] = a[l]; return; }
        int mid = (l+r)/2;
        build(node*2, l, mid, a);
        build(node*2+1, mid+1, r, a);
        sum[node] = sum[node*2] + sum[node*2+1];
    }
    void apply(int node, int l, int r, ll m, ll a) {
        sum[node] = sum[node] * m + a * (r - l + 1);
        mul[node] *= m;
        add[node] = add[node] * m + a;
    }
    void push(int node, int l, int r) {
        if (mul[node] != 1 || add[node] != 0) {
            int mid = (l+r)/2;
            apply(node*2, l, mid, mul[node], add[node]);
            apply(node*2+1, mid+1, r, mul[node], add[node]);
            mul[node] = 1; add[node] = 0;
        }
    }
    void range_affine(int L, int R, ll m, ll a) {
        range_affine(1, 0, n-1, L, R, m, a);
    }
    void range_affine(int node, int l, int r, int L, int R, ll m, ll a) {
        if (L > r || R < l) return;
        if (L <= l && r <= R) {
            apply(node, l, r, m, a);
            return;
        }
        push(node, l, r);
        int mid = (l+r)/2;
        range_affine(node*2, l, mid, L, R, m, a);
        range_affine(node*2+1, mid+1, r, L, R, m, a);
        sum[node] = sum[node*2] + sum[node*2+1];
    }
    ll range_sum(int L, int R) {
        return range_sum(1, 0, n-1, L, R);
    }
    ll range_sum(int node, int l, int r, int L, int R) {
        if (L > r || R < l) return 0;
        if (L <= l && r <= R) return sum[node];
        push(node, l, r);
        int mid = (l+r)/2;
        return range_sum(node*2, l, mid, L, R) +
               range_sum(node*2+1, mid+1, r, L, R);
    }
};

// =====================================================================
// Additional notes on common tricks (not code):
//   - Use a segment tree to find the first index where prefix sum >= K
//     by traversing the tree.
//   - For 2D queries, you can use a Fenwick tree of Fenwick trees or
//     a segment tree of vectors.
//   - For maximum subarray sum, store total, max prefix, max suffix,
//     and max subarray.
//   - Offline queries can be handled by segment tree over time.
// =====================================================================

// ---------------------------------------------------------------------
// Example usage in main()
// ---------------------------------------------------------------------

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

    // Example: basic sum segtree
    vector<ll> arr = {1, 2, 3, 4, 5};
    SegTreeSum st(arr);
    cout << st.query(1, 3) << '\n'; // 2+3+4 = 9
    st.update(2, 10); // arr[2] = 10
    cout << st.query(1, 3) << '\n'; // 2+10+4 = 16

    // Example: lazy add + sum
    LazySegTreeSum lazy(arr);
    lazy.range_add(1, 3, 5); // add 5 to indices 1..3
    cout << lazy.range_sum(0, 4) << '\n'; // sum all = 1+7+8+9+5 = 30

    // Example: merge sort tree
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    MergeSortTree mst(a);
    cout << mst.query_le(1, 5, 4) << '\n'; // in subarray [1,4,1,5,9] count <=4 => 3 (1,4,1)
    cout << mst.query_kth(1, 5, 3) << '\n'; // 3rd smallest in that range -> sorted: 1,1,4,5,9 => 4

    // Example: persistent segment tree (k-th smallest in subarray)
    vector<int> vals = {3, 1, 4, 1, 5, 9, 2, 6};
    vector<int> comp = vals;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    vector<int> compressed;
    for (int x : vals) {
        compressed.push_back(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
    }
    PersistentSegTree pst(comp.size());
    pst.build(compressed);
    // k-th smallest in range [l, r] (1‑based positions)
    cout << comp[pst.query_kth(2, 5, 2) - 1] << '\n'; // subarray indices 1..4 (0-based) => vals[1..4] = {1,4,1,5}, 2nd smallest = 1

    return 0;
}