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

// ===================================================================
// PERSISTENT SEGMENT TREE LIBRARY
//
// Contains:
//   1) Persistent Segment Tree with lazy propagation
//      - Range add / range sum queries
//      - Also provides "first index with prefix sum > target"
//   2) Persistent Segment Tree for range assignment (set)
//      - Range set / range sum queries
//   3) Persistent Segment Tree for point updates and k‑th smallest
//      - (no lazy, count‑based, classic for subarray order statistics)
//
// All classes are self‑contained, ready to use as black boxes.
// Time complexities: O(log N) per operation, O(N + Q log N) memory.
// ===================================================================

// ===================================================================
// 1) PERSISTENT SEGMENT TREE – RANGE ADD, RANGE SUM
// ===================================================================

class PersistentSegTreeLazy {
private:
    struct Node {
        int left = 0, right = 0;
        ll sum = 0, lazy = 0;
        Node() {}
        Node(int l, int r, ll s, ll la) : left(l), right(r), sum(s), lazy(la) {}
    };

    vector<Node> tree;          // node pool (index 0 = dummy)
    int N;                      // size of the underlying array
    vector<int> roots;          // roots[version] = root node index

    // Creates a copy of an existing node. Returns the new node's index.
    int cloneNode(int node) {
        tree.push_back(tree[node]);
        return (int)tree.size() - 1;
    }

    // Applies an addition to a node's whole segment (persistent – call on a cloned node).
    void apply(int node, int l, int r, ll val) {
        tree[node].sum += val * (r - l + 1);
        tree[node].lazy += val;
    }

    // Pushes the lazy value down to children (clones children to keep persistence).
    int push(int node, int l, int r) {
        if (l == r || tree[node].lazy == 0) return node;
        int mid = (l + r) / 2;
        int leftChild = cloneNode(tree[node].left);
        int rightChild = cloneNode(tree[node].right);
        apply(leftChild, l, mid, tree[node].lazy);
        apply(rightChild, mid + 1, r, tree[node].lazy);
        tree[node].left = leftChild;
        tree[node].right = rightChild;
        tree[node].lazy = 0;
        return node;
    }

    // Builds the initial tree from the array.
    int build(const vector<ll>& arr, int l, int r) {
        int node = (int)tree.size();
        tree.push_back(Node());
        if (l == r) {
            tree[node].sum = arr[l];
            return node;
        }
        int mid = (l + r) / 2;
        int leftChild = build(arr, l, mid);
        int rightChild = build(arr, mid + 1, r);
        tree[node].left = leftChild;
        tree[node].right = rightChild;
        tree[node].sum = tree[leftChild].sum + tree[rightChild].sum;
        return node;
    }

    // Recursive range add – returns new root after the update.
    int updateRangeAddRec(int node, int l, int r, int ql, int qr, ll val) {
        int newNode = cloneNode(node);
        if (ql <= l && r <= qr) {
            apply(newNode, l, r, val);
            return newNode;
        }
        newNode = push(newNode, l, r);
        int mid = (l + r) / 2;
        if (ql <= mid) {
            int newLeft = updateRangeAddRec(tree[newNode].left, l, mid, ql, qr, val);
            tree[newNode].left = newLeft;
        }
        if (qr > mid) {
            int newRight = updateRangeAddRec(tree[newNode].right, mid + 1, r, ql, qr, val);
            tree[newNode].right = newRight;
        }
        tree[newNode].sum = tree[tree[newNode].left].sum + tree[tree[newNode].right].sum;
        return newNode;
    }

    // Recursive range sum – does NOT modify the tree.
    ll queryRangeSumRec(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[node].sum;
        }
        int mid = (l + r) / 2;
        ll res = 0;
        if (ql <= mid) {
            res += queryRangeSumRec(tree[node].left, l, mid, ql, qr);
        }
        if (qr > mid) {
            res += queryRangeSumRec(tree[node].right, mid + 1, r, ql, qr);
        }
        // Add the contribution of the lazy value stored in this node.
        int overlapL = max(ql, l);
        int overlapR = min(qr, r);
        if (overlapL <= overlapR) {
            res += tree[node].lazy * (overlapR - overlapL + 1);
        }
        return res;
    }

    // Recursive search for the first index where prefix sum > target.
    // accLazy = sum of lazy values from ancestors (not yet applied to this node).
    int findFirstPrefixGreaterRec(int node, int l, int r, ll target, ll accLazy) {
        // Total sum of this segment if ancestor lazy were applied.
        ll total = tree[node].sum + accLazy * (r - l + 1);
        if (total <= target) return -1;
        if (l == r) return l;

        int mid = (l + r) / 2;
        ll newAccLazy = accLazy + tree[node].lazy;   // passed to children
        int leftChild = tree[node].left;
        ll leftSum = tree[leftChild].sum + newAccLazy * (mid - l + 1);

        if (leftSum > target) {
            return findFirstPrefixGreaterRec(leftChild, l, mid, target, newAccLazy);
        } else {
            return findFirstPrefixGreaterRec(tree[node].right, mid + 1, r,
                                             target - leftSum, newAccLazy);
        }
    }

public:
    // Constructor: builds the tree from the initial array.
    // Version 0 is created automatically.
    PersistentSegTreeLazy(const vector<ll>& arr) {
        N = (int)arr.size();
        tree.clear();
        tree.reserve(2000000);      // adjust size for your problem
        tree.push_back(Node());    // dummy node at index 0
        int root = build(arr, 0, N - 1);
        roots.clear();
        roots.push_back(root);
    }

    // Returns the root index of a given version.
    int getRoot(int version) const {
        return roots[version];
    }

    // Returns the number of the latest version.
    int getCurrentVersion() const {
        return (int)roots.size() - 1;
    }

    // Stores a new root as a new version.
    void addVersion(int root) {
        roots.push_back(root);
    }

    // Applies a range add to the given version root.
    // Returns the new root (caller should use addVersion() to save it).
    int updateRangeAdd(int root, int ql, int qr, ll val) {
        return updateRangeAddRec(root, 0, N - 1, ql, qr, val);
    }

    // Queries the sum on [ql, qr] for the given version root.
    ll queryRangeSum(int root, int ql, int qr) {
        return queryRangeSumRec(root, 0, N - 1, ql, qr);
    }

    // Finds the smallest index i (0‑based) such that sum(a[0..i]) > target.
    // If none, returns -1.
    int findFirstPrefixGreater(int root, ll target) {
        return findFirstPrefixGreaterRec(root, 0, N - 1, target, 0);
    }
};

// ===================================================================
// 2) PERSISTENT SEGMENT TREE – RANGE ASSIGNMENT (SET), RANGE SUM
// ===================================================================

class PersistentSegTreeSet {
private:
    struct Node {
        int left = 0, right = 0;
        ll sum = 0;
        ll lazy = 0;
        bool hasLazy = false;   // true if there is a pending assignment
        Node() {}
        Node(int l, int r, ll s, ll la, bool hl)
            : left(l), right(r), sum(s), lazy(la), hasLazy(hl) {}
    };

    vector<Node> tree;
    int N;
    vector<int> roots;

    int cloneNode(int node) {
        tree.push_back(tree[node]);
        return (int)tree.size() - 1;
    }

    void applySet(int node, int l, int r, ll val) {
        tree[node].sum = val * (r - l + 1);
        tree[node].lazy = val;
        tree[node].hasLazy = true;
    }

    int push(int node, int l, int r) {
        if (l == r || !tree[node].hasLazy) return node;
        int mid = (l + r) / 2;
        int leftChild = cloneNode(tree[node].left);
        int rightChild = cloneNode(tree[node].right);
        applySet(leftChild, l, mid, tree[node].lazy);
        applySet(rightChild, mid + 1, r, tree[node].lazy);
        tree[node].left = leftChild;
        tree[node].right = rightChild;
        tree[node].hasLazy = false;
        return node;
    }

    int build(const vector<ll>& arr, int l, int r) {
        int node = (int)tree.size();
        tree.push_back(Node());
        if (l == r) {
            tree[node].sum = arr[l];
            return node;
        }
        int mid = (l + r) / 2;
        int leftChild = build(arr, l, mid);
        int rightChild = build(arr, mid + 1, r);
        tree[node].left = leftChild;
        tree[node].right = rightChild;
        tree[node].sum = tree[leftChild].sum + tree[rightChild].sum;
        return node;
    }

    int updateRangeSetRec(int node, int l, int r, int ql, int qr, ll val) {
        int newNode = cloneNode(node);
        if (ql <= l && r <= qr) {
            applySet(newNode, l, r, val);
            return newNode;
        }
        newNode = push(newNode, l, r);
        int mid = (l + r) / 2;
        if (ql <= mid) {
            int newLeft = updateRangeSetRec(tree[newNode].left, l, mid, ql, qr, val);
            tree[newNode].left = newLeft;
        }
        if (qr > mid) {
            int newRight = updateRangeSetRec(tree[newNode].right, mid + 1, r, ql, qr, val);
            tree[newNode].right = newRight;
        }
        tree[newNode].sum = tree[tree[newNode].left].sum + tree[tree[newNode].right].sum;
        return newNode;
    }

    ll queryRangeSumRec(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[node].sum;
        }
        int mid = (l + r) / 2;
        ll res = 0;
        if (ql <= mid)
            res += queryRangeSumRec(tree[node].left, l, mid, ql, qr);
        if (qr > mid)
            res += queryRangeSumRec(tree[node].right, mid + 1, r, ql, qr);

        // If this node has a pending assignment, it covers the whole segment.
        int overlapL = max(ql, l);
        int overlapR = min(qr, r);
        if (overlapL <= overlapR && tree[node].hasLazy) {
            res += tree[node].lazy * (overlapR - overlapL + 1);
        }
        return res;
    }

public:
    PersistentSegTreeSet(const vector<ll>& arr) {
        N = (int)arr.size();
        tree.clear();
        tree.reserve(2000000);
        tree.push_back(Node());
        int root = build(arr, 0, N - 1);
        roots.clear();
        roots.push_back(root);
    }

    int getRoot(int version) const { return roots[version]; }
    int getCurrentVersion() const { return (int)roots.size() - 1; }
    void addVersion(int root) { roots.push_back(root); }

    // Range assignment: sets every element in [ql, qr] to val.
    int updateRangeSet(int root, int ql, int qr, ll val) {
        return updateRangeSetRec(root, 0, N - 1, ql, qr, val);
    }

    // Range sum query.
    ll queryRangeSum(int root, int ql, int qr) {
        return queryRangeSumRec(root, 0, N - 1, ql, qr);
    }
};

// ===================================================================
// 3) PERSISTENT SEGMENT TREE FOR K‑TH SMALLEST (COUNT TREE)
//    No lazy – point updates, frequency based.
// ===================================================================

class PersistentSegTreeCount {
private:
    struct Node {
        int left = 0, right = 0;
        int cnt = 0;   // number of elements in this segment
        Node() {}
        Node(int l, int r, int c) : left(l), right(r), cnt(c) {}
    };

    vector<Node> tree;
    int N;               // number of distinct values (coordinates)
    vector<int> roots;   // roots[0] = empty tree, roots[i] = after first i elements

    int build(int l, int r) {
        int node = (int)tree.size();
        tree.push_back(Node());
        if (l == r) return node;
        int mid = (l + r) / 2;
        int leftChild = build(l, mid);
        int rightChild = build(mid + 1, r);
        tree[node].left = leftChild;
        tree[node].right = rightChild;
        return node;
    }

    int updatePointRec(int node, int l, int r, int pos, int delta) {
        int newNode = (int)tree.size();
        tree.push_back(tree[node]);
        tree[newNode].cnt += delta;
        if (l == r) return newNode;
        int mid = (l + r) / 2;
        if (pos <= mid) {
            int newLeft = updatePointRec(tree[node].left, l, mid, pos, delta);
            tree[newNode].left = newLeft;
        } else {
            int newRight = updatePointRec(tree[node].right, mid + 1, r, pos, delta);
            tree[newNode].right = newRight;
        }
        return newNode;
    }

    // k is 1‑indexed. nodeL = earlier root, nodeR = later root.
    int queryKthRec(int nodeL, int nodeR, int l, int r, int k) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        int leftCount = tree[tree[nodeR].left].cnt - tree[tree[nodeL].left].cnt;
        if (k <= leftCount) {
            return queryKthRec(tree[nodeL].left, tree[nodeR].left, l, mid, k);
        } else {
            return queryKthRec(tree[nodeL].right, tree[nodeR].right,
                               mid + 1, r, k - leftCount);
        }
    }

public:
    // distinctValues = number of different compressed coordinates.
    PersistentSegTreeCount(int distinctValues) {
        N = distinctValues;
        tree.clear();
        tree.reserve(2000000);
        tree.push_back(Node());      // dummy node 0
        int root = build(1, N);      // 1‑indexed for easier handling
        roots.clear();
        roots.push_back(root);       // version 0 : empty
    }

    // Returns the root of the given version.
    int getRoot(int version) const {
        return roots[version];
    }

    // Adds a new version by applying a point update (+delta) to the previous root.
    int updatePoint(int previousRoot, int pos, int delta) {
        return updatePointRec(previousRoot, 1, N, pos, delta);
    }

    // Appends a new version (root) to the internal list.
    void addVersion(int root) {
        roots.push_back(root);
    }

    // Query the k‑th smallest (1‑indexed) in the subarray [l, r] (0‑based indices).
    // Version indices correspond to prefix lengths:
    //    versionL = l        (prefix before the subarray)
    //    versionR = r + 1    (prefix up to r)
    // For example, to query a[l..r], call queryKth(l, r+1, k).
    int queryKth(int versionL, int versionR, int k) {
        int rootL = roots[versionL];
        int rootR = roots[versionR];
        return queryKthRec(rootL, rootR, 1, N, k);
    }
};

// ===================================================================
// EXAMPLE USAGE
// ===================================================================

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

    // ---------------------------------------------------------------
    // Demo 1: Persistent tree with range add and sum
    // ---------------------------------------------------------------
    vector<ll> arr = {1, 2, 3, 4, 5};
    PersistentSegTreeLazy pst(arr);

    int root0 = pst.getRoot(0);
    cout << "Initial sum [1,3] = " << pst.queryRangeSum(root0, 1, 3) << "\n"; // 9

    int root1 = pst.updateRangeAdd(root0, 1, 3, 10);   // add 10 to indices 1..3
    pst.addVersion(root1);
    cout << "After add, sum [1,3] = " << pst.queryRangeSum(root1, 1, 3) << "\n"; // 39

    // Find the first index where prefix sum > 25
    int idx = pst.findFirstPrefixGreater(root1, 25);
    cout << "First index with prefix > 25 = " << idx << "\n"; // 2 (prefix up to 2 = 26)

    // ---------------------------------------------------------------
    // Demo 2: Persistent tree with range set (assignment)
    // ---------------------------------------------------------------
    PersistentSegTreeSet pstSet(arr);
    int r0 = pstSet.getRoot(0);
    cout << "Initial sum [0,4] = " << pstSet.queryRangeSum(r0, 0, 4) << "\n"; // 15

    int r1 = pstSet.updateRangeSet(r0, 0, 2, 100); // set first three to 100
    pstSet.addVersion(r1);
    cout << "After setting [0,2] to 100, sum all = " << pstSet.queryRangeSum(r1, 0, 4) << "\n"; // 100+100+100+4+5 = 309

    // ---------------------------------------------------------------
    // Demo 3: K‑th smallest using the count tree
    // ---------------------------------------------------------------
    vector<int> values = {5, 2, 8, 2, 9};
    // Coordinate compression
    vector<int> sortedVals = values;
    sort(sortedVals.begin(), sortedVals.end());
    sortedVals.erase(unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());

    PersistentSegTreeCount pstCount((int)sortedVals.size());
    int emptyRoot = pstCount.getRoot(0);
    vector<int> countRoots = {emptyRoot};   // root[0] = empty prefix

    for (int x : values) {
        int pos = lower_bound(sortedVals.begin(), sortedVals.end(), x) - sortedVals.begin() + 1; // 1‑indexed
        int newRoot = pstCount.updatePoint(countRoots.back(), pos, 1);
        countRoots.push_back(newRoot);
    }

    // Query 2nd smallest in subarray [1, 3] (0‑based) -> values {2,8,2} -> sorted {2,2,8}
    // We need versions: L = 1 (prefix before index 1), R = 4 (prefix up to index 3).
    int kthIdx = pstCount.queryKth(1, 4, 2);
    cout << "2nd smallest in [1,3] = " << sortedVals[kthIdx - 1] << "\n"; // should be 2

    return 0;
}