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

// ===================================================================
// This file contains a collection of Sqrt Decomposition and MO's
// Algorithm templates. Each function/struct is ready to be used as a
// "black box". Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================

// ===================================================================
// 1) Sqrt Decomposition (Static / Point Updates)
//    Block decomposition splits the array into blocks of size ~sqrt(n).
//    Precompute aggregate values per block.
// ===================================================================

// -------------------------------------------------------------------
// SqrtDecompSum: Range Sum with Point Updates
// -------------------------------------------------------------------
// What it does: Maintains an array and supports:
//   - Point update: change value at a given index.
//   - Range sum query: sum of elements in [l, r] (inclusive).
// How to use:
//   - Create object: SqrtDecompSum<T> ds(vector<T> a) where T is numeric.
//   - update(pos, new_val): O(1) amortized? Actually O(1) per block update.
//   - query(l, r): O(sqrt(n)) time.
// Time complexity:
//   - Build: O(n)
//   - Update: O(1)
//   - Query: O(sqrt(n))
// Constraints:
//   - Array size n can be up to ~1e5-1e6.
//   - Works for any numeric type (int, long long, etc.).
// Notes:
//   - The array is 0-indexed.
//   - Range is inclusive on both ends.
// -------------------------------------------------------------------
template<typename T>
struct SqrtDecompSum {
    int n, block_size, num_blocks;
    vector<T> arr, block_sum;

    SqrtDecompSum(const vector<T>& a = {}) { init(a); }

    void init(const vector<T>& a) {
        arr = a;
        n = (int)arr.size();
        block_size = max(1, (int)sqrt(n));
        num_blocks = (n + block_size - 1) / block_size;
        block_sum.assign(num_blocks, 0);
        for (int i = 0; i < n; ++i) {
            block_sum[i / block_size] += arr[i];
        }
    }

    // Point update: set arr[pos] = new_val
    void update(int pos, T new_val) {
        int b = pos / block_size;
        block_sum[b] += (new_val - arr[pos]);
        arr[pos] = new_val;
    }

    // Range sum [l, r] inclusive
    T query(int l, int r) {
        T res = 0;
        int bl = l / block_size, br = r / block_size;
        if (bl == br) {
            for (int i = l; i <= r; ++i) res += arr[i];
        } else {
            for (int i = l; i < (bl + 1) * block_size; ++i) res += arr[i];
            for (int b = bl + 1; b < br; ++b) res += block_sum[b];
            for (int i = br * block_size; i <= r; ++i) res += arr[i];
        }
        return res;
    }
};

// -------------------------------------------------------------------
// SqrtDecompMinMax: Range Minimum/Maximum (static, no updates)
// -------------------------------------------------------------------
// What it does: Precomputes block-wise min and max for static array.
//   - queryMin(l, r): returns minimum value in range.
//   - queryMax(l, r): returns maximum value in range.
// How to use:
//   - Create object with array: SqrtDecompMinMax<T> ds(vector<T> a)
//   - Call queryMin(l, r) or queryMax(l, r).
// Time complexity:
//   - Build: O(n)
//   - Each query: O(sqrt(n))
// Constraints:
//   - Array is static; updates are not supported (if you update, you must rebuild).
//   - Works for any comparable type (int, long long, etc.).
// Notes:
//   - 0-indexed, inclusive range.
//   - For updates, you would need to rebuild the block (O(block_size)) or rebuild whole structure.
// -------------------------------------------------------------------
template<typename T>
struct SqrtDecompMinMax {
    int n, block_size, num_blocks;
    vector<T> arr;
    vector<T> block_min, block_max;

    SqrtDecompMinMax(const vector<T>& a = {}) { init(a); }

    void init(const vector<T>& a) {
        arr = a;
        n = (int)arr.size();
        block_size = max(1, (int)sqrt(n));
        num_blocks = (n + block_size - 1) / block_size;
        block_min.assign(num_blocks, numeric_limits<T>::max());
        block_max.assign(num_blocks, numeric_limits<T>::min());
        for (int i = 0; i < n; ++i) {
            int b = i / block_size;
            block_min[b] = min(block_min[b], arr[i]);
            block_max[b] = max(block_max[b], arr[i]);
        }
    }

    // Range minimum [l, r]
    T queryMin(int l, int r) {
        T res = numeric_limits<T>::max();
        int bl = l / block_size, br = r / block_size;
        if (bl == br) {
            for (int i = l; i <= r; ++i) res = min(res, arr[i]);
        } else {
            for (int i = l; i < (bl + 1) * block_size; ++i) res = min(res, arr[i]);
            for (int b = bl + 1; b < br; ++b) res = min(res, block_min[b]);
            for (int i = br * block_size; i <= r; ++i) res = min(res, arr[i]);
        }
        return res;
    }

    // Range maximum [l, r]
    T queryMax(int l, int r) {
        T res = numeric_limits<T>::min();
        int bl = l / block_size, br = r / block_size;
        if (bl == br) {
            for (int i = l; i <= r; ++i) res = max(res, arr[i]);
        } else {
            for (int i = l; i < (bl + 1) * block_size; ++i) res = max(res, arr[i]);
            for (int b = bl + 1; b < br; ++b) res = max(res, block_max[b]);
            for (int i = br * block_size; i <= r; ++i) res = max(res, arr[i]);
        }
        return res;
    }
};

// ===================================================================
// 2) MO's Algorithm (Offline Range Queries)
//    Sorts queries by (L/block_size) and R, then maintains current
//    range [curL, curR] by adding/removing elements.
//    Complexity: O((N+Q)*sqrt(N)) for basic MO.
// ===================================================================

// -------------------------------------------------------------------
// MO: Generic MO structure (base class)
// -------------------------------------------------------------------
// What it does: Provides a framework for answering many range queries offline.
//   You must derive a class and override add(), remove(), getAnswer().
// How to use:
//   - Create a derived class, implement the three virtual functions.
//   - Call addQuery(L, R, idx) for each query.
//   - Call process() to compute answers.
// Time complexity: O((N+Q)*sqrt(N)) plus cost of add/remove (each O(1) ideally).
// Constraints:
//   - All queries must be known beforehand (offline).
//   - Array indices are 0-based.
// Notes:
//   - The sorting uses odd-even block ordering to reduce pointer movement.
//   - The array 'arr' is stored; your add/remove functions can access it.
//   - Answers are stored as long long to accommodate large sums.
// -------------------------------------------------------------------
struct MO {
    int n, block_size;
    vector<int> arr;          // input array (0-indexed)
    vector<long long> ans;    // answer for each query (long long for safety)
    vector<tuple<int,int,int>> queries; // {L, R, idx} 0-indexed inclusive

    MO(const vector<int>& a) : arr(a) {
        n = arr.size();
        block_size = max(1, (int)sqrt(n));
    }

    void addQuery(int L, int R, int idx) {
        queries.emplace_back(L, R, idx);
    }

    // Override these in a derived class
    virtual void add(int pos) { /* add arr[pos] to current state */ }
    virtual void remove(int pos) { /* remove arr[pos] from current state */ }
    virtual long long getAnswer() { /* return current answer */ return 0; }

    void process() {
        int q = queries.size();
        ans.assign(q, 0);
        sort(queries.begin(), queries.end(), [&](const auto& a, const auto& b) {
            int blockA = get<0>(a) / block_size;
            int blockB = get<0>(b) / block_size;
            if (blockA != blockB) return blockA < blockB;
            // For odd blocks, sort R descending to reduce movement
            if (blockA & 1) return get<1>(a) > get<1>(b);
            return get<1>(a) < get<1>(b);
        });

        int curL = 0, curR = -1;
        for (auto [L, R, idx] : queries) {
            while (curL > L) add(--curL);
            while (curR < R) add(++curR);
            while (curL < L) remove(curL++);
            while (curR > R) remove(curR--);
            ans[idx] = getAnswer();
        }
    }
};

// -------------------------------------------------------------------
// MO_Distinct: Count distinct numbers in range (example)
// -------------------------------------------------------------------
// What it does: Answers queries for number of distinct values in [l, r].
// How to use:
//   - Create object: MO_Distinct mo(array)
//   - Add queries with addQuery(l, r, idx)
//   - Call process(), then read answers from mo.ans.
// Time complexity: O((N+Q)*sqrt(N))
// Constraints:
//   - Array values must be <= 1,000,000 (frequency array size).
//   - If values are larger, compress them first.
// Notes:
//   - This is a concrete implementation of the generic MO.
// -------------------------------------------------------------------
class MO_Distinct : public MO {
public:
    vector<int> freq;
    int distinct;

    MO_Distinct(const vector<int>& a) : MO(a) {
        freq.assign(1000005, 0); // assuming max value <= 1e6
        distinct = 0;
    }

    void add(int pos) override {
        int x = arr[pos];
        if (freq[x] == 0) ++distinct;
        ++freq[x];
    }

    void remove(int pos) override {
        int x = arr[pos];
        --freq[x];
        if (freq[x] == 0) --distinct;
    }

    long long getAnswer() override {
        return distinct;
    }
};

// -------------------------------------------------------------------
// MO_Sum: Sum of elements in range (example)
// -------------------------------------------------------------------
// What it does: Answers range sum queries.
// How to use: Similar to MO_Distinct.
// Time complexity: O((N+Q)*sqrt(N))
// Constraints: Works for int values; sum may overflow int, but we use long long.
// Notes: trivial implementation.
// -------------------------------------------------------------------
class MO_Sum : public MO {
public:
    ll current_sum;

    MO_Sum(const vector<int>& a) : MO(a) { current_sum = 0; }

    void add(int pos) override { current_sum += arr[pos]; }
    void remove(int pos) override { current_sum -= arr[pos]; }
    long long getAnswer() override { return current_sum; }
};

// -------------------------------------------------------------------
// MO_Mode: Find frequency of the mode (most frequent element) in range
// -------------------------------------------------------------------
// What it does: For each query, returns the maximum frequency among values in range.
// How to use: Similar to above.
// Time complexity: O((N+Q)*sqrt(N))
// Constraints: Values must fit in frequency array (<=1e6). 
// Notes: Maintains freq of each value and freqOfFreq (frequency of frequencies).
// -------------------------------------------------------------------
class MO_Mode : public MO {
public:
    vector<int> freq, freqOfFreq;
    int modeFreq;

    MO_Mode(const vector<int>& a) : MO(a) {
        freq.assign(1000005, 0);
        freqOfFreq.assign(1000005, 0);
        modeFreq = 0;
    }

    void add(int pos) override {
        int x = arr[pos];
        if (freq[x] > 0) --freqOfFreq[freq[x]];
        ++freq[x];
        ++freqOfFreq[freq[x]];
        modeFreq = max(modeFreq, freq[x]);
    }

    void remove(int pos) override {
        int x = arr[pos];
        --freqOfFreq[freq[x]];
        if (freq[x] == modeFreq && freqOfFreq[freq[x]] == 0) {
            // The mode frequency may decrease if no other element has that frequency
            while (modeFreq > 0 && freqOfFreq[modeFreq] == 0) --modeFreq;
        }
        --freq[x];
        if (freq[x] > 0) ++freqOfFreq[freq[x]];
    }

    long long getAnswer() override {
        return modeFreq;
    }
};

// ===================================================================
// 3) MO with Updates (MO's Algorithm with Modifications)
//    Handles point updates interleaved with queries.
//    Complexity: O( (N+Q)^(5/3) ) ~ O( (N+Q)*N^(2/3) ) with block size N^(2/3).
// ===================================================================

// -------------------------------------------------------------------
// MOWithUpdates: MO algorithm that supports point updates.
// -------------------------------------------------------------------
// What it does: Processes queries with updates in between.
//   It supports two operations:
//     1. Point update: change value at position pos to new_val.
//     2. Range query: e.g., count distinct numbers in [l, r].
// How to use:
//   - Create object with initial array.
//   - Add queries with addQuery(l, r, idx) and updates with addUpdate(pos, new_val).
//   - Call process() to compute answers.
// Time complexity: O( (N+Q)^(5/3) ) ~ O( (N+Q)*N^(2/3) )
// Constraints:
//   - Array values must fit in frequency array (size 1e6+5).
//   - All queries and updates must be known beforehand.
// Notes:
//   - The block size is chosen as N^(2/3) for optimal performance.
//   - The implementation here counts distinct numbers; you can adapt the lambda functions.
//   - The internal array 'arr' is modified during processing, but original is preserved.
// -------------------------------------------------------------------
struct MOWithUpdates {
    struct Query {
        int l, r, t, idx;
    };
    struct Update {
        int pos, old_val, new_val;
    };

    int n, q, u; // u = number of updates
    vector<int> arr;          // This will hold the array state while reading updates (for old_val)
    vector<int> initial_arr;  // Original array (copied from constructor) for processing
    vector<Query> queries;
    vector<Update> updates;
    vector<int> ans;

    MOWithUpdates(const vector<int>& a) : arr(a), initial_arr(a) {
        n = arr.size();
        q = u = 0;
    }

    void addQuery(int l, int r, int idx) {
        queries.push_back({l, r, (int)updates.size(), idx});
    }

    // Add a point update: set arr[pos] = new_val.
    // IMPORTANT: This modifies the internal array 'arr' to compute the correct old_val for later updates.
    // The original array is preserved in 'initial_arr' for processing.
    void addUpdate(int pos, int new_val) {
        int old_val = arr[pos];
        updates.push_back({pos, old_val, new_val});
        arr[pos] = new_val; // Update the current state for subsequent updates
    }

    void process() {
        q = queries.size();
        ans.assign(q, 0);
        int block_size = pow(n, 2.0/3.0); // typical block size for MO with updates
        sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
            int blockL_a = a.l / block_size;
            int blockL_b = b.l / block_size;
            if (blockL_a != blockL_b) return blockL_a < blockL_b;
            int blockR_a = a.r / block_size;
            int blockR_b = b.r / block_size;
            if (blockR_a != blockR_b) return blockR_a < blockR_b;
            return a.t < b.t;
        });

        vector<int> curArr = initial_arr; // start with the original array
        int curL = 0, curR = -1, curT = 0;

        // For this example we count distinct numbers. 
        // Frequency array size fixed to 1e6+5; ensure values are within that range.
        vector<int> freq(1000005, 0);
        int distinct = 0;

        auto addPos = [&](int pos) {
            int x = curArr[pos];
            if (freq[x] == 0) ++distinct;
            ++freq[x];
        };
        auto removePos = [&](int pos) {
            int x = curArr[pos];
            --freq[x];
            if (freq[x] == 0) --distinct;
        };
        auto applyUpdate = [&](int t, bool forward) {
            // forward = true: apply update t (change from old_val to new_val)
            // forward = false: rollback update t (change from new_val back to old_val)
            Update& upd = updates[t];
            int pos = upd.pos;
            int oldVal = upd.old_val;
            int newVal = upd.new_val;
            bool inRange = (curL <= pos && pos <= curR);
            if (inRange) {
                // Remove the current value (oldVal if forward, newVal if rollback)
                int currentVal = curArr[pos];
                --freq[currentVal];
                if (freq[currentVal] == 0) --distinct;
            }
            // Apply the change to the array
            if (forward) {
                curArr[pos] = newVal;
            } else {
                curArr[pos] = oldVal;
            }
            if (inRange) {
                // Add the new value
                int newCurrent = curArr[pos];
                if (freq[newCurrent] == 0) ++distinct;
                ++freq[newCurrent];
            }
        };

        for (auto& qu : queries) {
            // Adjust L and R
            while (curL > qu.l) addPos(--curL);
            while (curR < qu.r) addPos(++curR);
            while (curL < qu.l) removePos(curL++);
            while (curR > qu.r) removePos(curR--);
            // Adjust time
            while (curT < qu.t) {
                applyUpdate(curT, true);
                ++curT;
            }
            while (curT > qu.t) {
                --curT;
                applyUpdate(curT, false);
            }
            ans[qu.idx] = distinct;
        }
    }
};

// ===================================================================
// 4) MO on Trees (Path Queries)
//    For tree path queries, we flatten the tree using Euler tour.
//    For each node, we store first occurrence and last occurrence in Euler tour.
//    Then path queries become range queries on the Euler array.
//    Need to handle LCA to avoid double counting.
// ===================================================================

// -------------------------------------------------------------------
// MOOnTree: MO algorithm for path queries on a tree.
// -------------------------------------------------------------------
// What it does: Answers queries about a path between two nodes in a tree.
//   For example, count distinct values on the path.
// How to use:
//   - Create object with number of nodes N.
//   - Add edges with addEdge(u, v).
//   - Set values for each node in 'value' array.
//   - Call preprocessLCA(root) to build Euler tour and LCA table.
//   - Add queries with addQuery(u, v, idx).
//   - Call process() to compute answers.
// Time complexity:
//   - Preprocessing: O(N log N) for LCA.
//   - Query processing: O((N+Q)*sqrt(N)) where N is number of nodes (Euler length 2N).
// Constraints:
//   - Tree is 0-indexed.
//   - Values must fit in frequency array (1e6+5).
//   - The tree is static; no updates.
// Notes:
//   - The Euler tour length is 2N.
//   - For each query, we compute the range [l, r] and possibly add LCA separately.
//   - The current implementation counts distinct values on path (you can modify toggle function).
//   - The LCA is computed using binary lifting.
// -------------------------------------------------------------------
struct MOOnTree {
    int n, q;
    vector<vector<int>> adj;
    vector<int> value;   // value of each node
    vector<int> euler;   // Euler tour of length 2n
    vector<int> first, last; // first and last occurrence in Euler
    vector<int> depth, parent, lg;
    vector<vector<int>> up; // binary lifting for LCA

    MOOnTree(int n) : n(n) {
        adj.assign(n, {});
        value.assign(n, 0);
        first.assign(n, -1);
        last.assign(n, -1);
        depth.assign(n, 0);
        parent.assign(n, 0);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int p) {
        parent[u] = p;
        first[u] = euler.size();
        euler.push_back(u);
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
        last[u] = euler.size();
        euler.push_back(u);
    }

    // LCA preprocessing
    void preprocessLCA(int root = 0) {
        dfs(root, root);
        int LOG = 1;
        while ((1 << LOG) <= n) ++LOG;
        up.assign(LOG, vector<int>(n));
        up[0] = parent;
        for (int j = 1; j < LOG; ++j) {
            for (int i = 0; i < n; ++i) {
                up[j][i] = up[j-1][ up[j-1][i] ];
            }
        }
    }

    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; diff; ++j, diff >>= 1) {
            if (diff & 1) u = up[j][u];
        }
        if (u == v) return u;
        for (int j = up.size() - 1; j >= 0; --j) {
            if (up[j][u] != up[j][v]) {
                u = up[j][u];
                v = up[j][v];
            }
        }
        return parent[u];
    }

    struct Query {
        int l, r, idx, lcaNode;
        bool addLca;
    };

    vector<Query> queries;
    vector<int> ans;

    void addQuery(int u, int v, int idx) {
        if (first[u] > first[v]) swap(u, v);
        int w = lca(u, v);
        Query q;
        q.idx = idx;
        q.addLca = false;
        q.lcaNode = w;
        if (w == u) {
            q.l = first[u];
            q.r = first[v];
        } else {
            q.l = last[u];
            q.r = first[v];
            q.addLca = true;
        }
        queries.push_back(q);
    }

    void process() {
        q = queries.size();
        ans.assign(q, 0);
        int block_size = max(1, (int)sqrt(2 * n));
        sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
            int blockA = a.l / block_size;
            int blockB = b.l / block_size;
            if (blockA != blockB) return blockA < blockB;
            if (blockA & 1) return a.r > b.r;
            return a.r < b.r;
        });

        vector<bool> vis(n, false);
        vector<int> freq(1000005, 0); // assuming values range
        int distinct = 0;

        auto toggle = [&](int node) {
            if (vis[node]) {
                // remove
                int x = value[node];
                --freq[x];
                if (freq[x] == 0) --distinct;
                vis[node] = false;
            } else {
                // add
                int x = value[node];
                if (freq[x] == 0) ++distinct;
                ++freq[x];
                vis[node] = true;
            }
        };

        int curL = 0, curR = -1;
        for (auto& q : queries) {
            while (curL > q.l) toggle(euler[--curL]);
            while (curR < q.r) toggle(euler[++curR]);
            while (curL < q.l) toggle(euler[curL++]);
            while (curR > q.r) toggle(euler[curR--]);
            int curAns = distinct;
            if (q.addLca) {
                // add LCA temporarily
                int x = value[q.lcaNode];
                if (freq[x] == 0) ++curAns;
                // Note: we do not modify freq permanently; just compute answer
            }
            ans[q.idx] = curAns;
        }
    }
};

// ===================================================================
// 5) Advanced Tricks & Patterns
// ===================================================================

// -------------------------------------------------------------------
// Hilbert Order for MO (improved cache performance)
// -------------------------------------------------------------------
// What it does: Computes a Hilbert curve order for a point (x, y).
//   Using this order for sorting MO queries can reduce pointer movement.
// How to use:
//   - In your MO processing, sort queries using hilbertOrder(l, r, pow, 0)
//     where pow is such that 2^pow > max(N, Q). Typically pow=21 for 2e6.
//   - Example: sort by hilbertOrder(a.l, a.r, 21, 0) < hilbertOrder(b.l, b.r, 21, 0)
// Time complexity: O(1) per call (recursive depth ~pow).
// Constraints: x and y should be non-negative and less than 2^pow.
// Notes: This is an alternative to odd-even block sorting; often faster.
// -------------------------------------------------------------------
long long hilbertOrder(int x, int y, int pow, int rotate) {
    if (pow == 0) return 0;
    int hpow = 1 << (pow - 1);
    int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
    seg = (seg + rotate) & 3;
    static const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    long long subSquareSize = 1LL << (2 * pow - 2);
    long long ord = seg * subSquareSize;
    long long add = hilbertOrder(nx, ny, pow - 1, nrot);
    ord += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ord;
}

// -------------------------------------------------------------------
// SqrtQueryDecomp: Process queries in blocks of sqrt(Q)
// -------------------------------------------------------------------
// What it does: Handles a mix of updates and queries by processing them in blocks.
//   At the start of each block, we have a snapshot of the array.
//   Within the block, we apply updates sequentially and answer queries on the fly.
// How to use:
//   - Create object with initial array.
//   - Add updates with addUpdate(pos, new_val) and queries with addQuery(l, r, idx).
//   - Call process() to get answers.
// Time complexity: O( (updates + queries) * sqrt(queries) * cost of query answer )
//   Here query answer is O(range length) in this naive implementation (which is slow).
//   For a proper implementation, you'd optimize query answering.
// Constraints:
//   - All operations are known offline.
//   - The current implementation answers sum queries in O(r-l+1) which defeats the purpose.
//     It is just a demonstration of the block decomposition concept.
// Notes: This is a different approach from MO; it's useful when updates are frequent.
// -------------------------------------------------------------------
struct SqrtQueryDecomp {
    int n, q;
    vector<int> arr;
    vector<tuple<int,int,int,int>> queries; // type, l, r, idx (type=0 update, type=1 query)
    int block_size;

    SqrtQueryDecomp(const vector<int>& a) : arr(a) {
        n = arr.size();
        q = 0;
        block_size = max(1, (int)sqrt(1)); // will set later
    }

    void addUpdate(int pos, int new_val) {
        queries.emplace_back(0, pos, new_val, -1);
    }
    void addQuery(int l, int r, int idx) {
        queries.emplace_back(1, l, r, idx);
    }

    vector<int> ans;

    void process() {
        q = queries.size();
        ans.assign(q, 0);
        block_size = max(1, (int)sqrt(q));
        // Process each block of queries
        for (int b = 0; b < q; b += block_size) {
            int end = min(q, b + block_size);
            vector<int> cur = arr;
            for (int i = b; i < end; ++i) {
                auto& qu = queries[i];
                int type = get<0>(qu);
                if (type == 0) { // update
                    int pos = get<1>(qu);
                    int new_val = get<2>(qu);
                    cur[pos] = new_val;
                } else { // query
                    int l = get<1>(qu);
                    int r = get<2>(qu);
                    int idx = get<3>(qu);
                    long long sum = 0;
                    for (int j = l; j <= r; ++j) sum += cur[j];
                    ans[idx] = sum;
                }
            }
            arr = cur; // apply all updates in this block for next block
        }
    }
};

// -------------------------------------------------------------------
// SqrtBitset: Use bitsets with sqrt decomposition
// -------------------------------------------------------------------
// What it does: Stores a bitset of values present in each block.
//   Allows fast set operations (union, intersection) on ranges.
// How to use:
//   - Create object with array: SqrtBitset sb(arr)
//   - Call queryBitset(l, r) to get a bitset of distinct values in range.
//   - Use countDistinct(l, r) for count, contains(l, r, x) to test presence.
// Time complexity:
//   - Build: O(n)
//   - queryBitset: O(sqrt(n) * (bitset_size / word_size))? Actually O(blocks + partial) but bitset OR is fast.
//   - For each range, we OR block bitsets and set individual elements.
// Constraints:
//   - Maximum value must be less than MAXV (here 100000). Adjust constant as needed.
//   - Array is static.
// Notes: Bitset is a data structure that represents a set of bits (booleans) efficiently.
//   A bitset of size MAXV uses MAXV/8 bytes of memory.
//   The OR operation combines bitsets quickly.
// -------------------------------------------------------------------
#include <bitset>
const int MAXV = 100000; // maximum value

struct SqrtBitset {
    int n, block_size, num_blocks;
    vector<int> arr;
    vector< bitset<MAXV> > block_bits; // bitset per block

    SqrtBitset(const vector<int>& a) {
        arr = a;
        n = arr.size();
        block_size = max(1, (int)sqrt(n));
        num_blocks = (n + block_size - 1) / block_size;
        block_bits.resize(num_blocks);
        for (int i = 0; i < n; ++i) {
            block_bits[i / block_size].set(arr[i]);
        }
    }

    // Query: return bitset of distinct values in range [l,r]
    bitset<MAXV> queryBitset(int l, int r) {
        bitset<MAXV> res;
        int bl = l / block_size, br = r / block_size;
        if (bl == br) {
            for (int i = l; i <= r; ++i) res.set(arr[i]);
        } else {
            for (int i = l; i < (bl+1)*block_size; ++i) res.set(arr[i]);
            for (int b = bl+1; b < br; ++b) res |= block_bits[b];
            for (int i = br*block_size; i <= r; ++i) res.set(arr[i]);
        }
        return res;
    }

    // Count distinct values in range
    int countDistinct(int l, int r) {
        return queryBitset(l, r).count();
    }

    // Check if range contains value x
    bool contains(int l, int r, int x) {
        return queryBitset(l, r).test(x);
    }

    // Union of two ranges: bitset OR
    bitset<MAXV> unionRanges(int l1, int r1, int l2, int r2) {
        return queryBitset(l1, r1) | queryBitset(l2, r2);
    }
};

// -------------------------------------------------------------------
// Coordinate compression for array values
// -------------------------------------------------------------------
// What it does: Maps large values to a smaller range [0, m-1].
//   Useful for MO when values are large and need to fit in frequency arrays.
// How to use:
//   - Pass your array to compressArray().
//   - It returns a new array with compressed values.
// Time complexity: O(n log n) due to sorting.
// Constraints: None.
// Notes: The original values are sorted and each gets a unique id.
//   The compressed values preserve order.
// -------------------------------------------------------------------
vector<int> compressArray(const vector<int>& a) {
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    vector<int> res(a.size());
    for (int i = 0; i < (int)a.size(); ++i) {
        res[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    }
    return res;
}

// ===================================================================
// 6) Example usage (commented)
// ===================================================================

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

    // Sqrt Decomposition Sum
    vector<int> arr = {1, 2, 3, 4, 5};
    SqrtDecompSum<int> sd(arr);
    cout << sd.query(1, 3) << '\n'; // 2+3+4=9
    sd.update(2, 10);
    cout << sd.query(1, 3) << '\n'; // 2+10+4=16

    // MO Distinct
    vector<int> a = {1, 2, 3, 2, 1, 4};
    MO_Distinct mo(a);
    mo.addQuery(0, 2, 0);
    mo.addQuery(1, 4, 1);
    mo.addQuery(2, 5, 2);
    mo.process();
    for (long long x : mo.ans) cout << x << ' '; // 3, 2, 3
    cout << '\n';

    // MO with Updates (example)
    vector<int> b = {1, 2, 3, 4};
    MOWithUpdates mow(b);
    mow.addQuery(0, 2, 0);
    mow.addUpdate(1, 5); // index 1 becomes 5
    mow.addQuery(0, 2, 1);
    mow.process();
    // answers: distinct in [0,2] initially: 1,2,3 => 3; after update: 1,5,3 => 3
    for (int x : mow.ans) cout << x << ' ';
    cout << '\n';

    // MO on Tree (example tree with 5 nodes)
    MOOnTree mot(5);
    mot.addEdge(0, 1);
    mot.addEdge(0, 2);
    mot.addEdge(1, 3);
    mot.addEdge(1, 4);
    mot.value = {1, 2, 3, 4, 5};
    mot.preprocessLCA(0);
    mot.addQuery(2, 3, 0); // path 2-0-1-3: values 3,1,2,4 => distinct 4
    mot.addQuery(3, 4, 1); // path 3-1-4: values 4,2,5 => distinct 3
    mot.process();
    for (int x : mot.ans) cout << x << ' ';
    cout << '\n';

    return 0;
}

// ===================================================================
// End of template
// ===================================================================