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

// ===================================================================
// This file contains a collection of 2D Segment Tree algorithms.
// Each function/class 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
//   - Any extra notes
// ===================================================================

// ===================================================================
// 1) STATIC 2D SEGMENT TREE FOR SUM
//    (Point Update, Rectangle Sum Query)
// ===================================================================

// -------------------------------------------------------------------
// CLASS: SegTree2DSum
// -------------------------------------------------------------------
// WHAT IT DOES:
//   Builds a 2D segment tree over a grid of integers (N rows x M columns).
//   It supports:
//     - Point update: add a value (delta) to a single cell.
//     - Rectangle sum: compute the sum of all cells inside a given
//       rectangle [x1..x2] × [y1..y2].
//
// INPUT:
//   - The grid is given as a 2D vector (N x M) in the `build` function.
//   - Coordinates are 0‑based (row and column indices start from 0).
//
// OUTPUT:
//   - `querySum` returns an integer – the sum of the rectangle.
//   - `updatePoint` does not return anything; it modifies the tree.
//
// TIME COMPLEXITY:
//   - Build: O(N * M)  (actually O(4*N * 4*M) but practically O(N*M)).
//   - Update: O(log N * log M).
//   - Query:  O(log N * log M).
//
// MEMORY:
//   - O(N * M)  (stored as a 2D array of size 4*N × 4*M).
//
// CONSTRAINTS / ASSUMPTIONS:
//   - N and M must be known at construction time.
//   - The grid values are integers (int).
//   - The grid size (N × M) should be reasonable (e.g., N, M <= 1000)
//     because memory grows quadratically.
//   - Updates add a delta; they do not set a value (use negative delta
//     to subtract).
//
// NOTES:
//   - This implementation uses 0‑based indices everywhere.
//   - It is a "static" tree because the grid size is fixed after build.
//   - The class allocates a full 4*N × 4*M array, so it may be heavy
//     for large grids.
//   - If you need to handle sparse data or very large coordinates,
//     see the Fenwick2D class below (coordinate compression).
// -------------------------------------------------------------------

class SegTree2DSum {
    int n, m;
    vector<vector<int>> tree;  // tree[4*n][4*m]

    // Build the column segment tree for a single row (leaf row node).
    void buildColTree(int rowNode, int colNode, int l, int r, const vector<int>& row) {
        if (l == r) {
            tree[rowNode][colNode] = row[l];
            return;
        }
        int mid = (l + r) / 2;
        buildColTree(rowNode, colNode*2, l, mid, row);
        buildColTree(rowNode, colNode*2+1, mid+1, r, row);
        tree[rowNode][colNode] = tree[rowNode][colNode*2] + tree[rowNode][colNode*2+1];
    }

    // Merge the column trees of two child row nodes into the parent row node.
    void mergeColTrees(int rowNode, int colNode, int l, int r) {
        if (l == r) {
            tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
            return;
        }
        int mid = (l + r) / 2;
        mergeColTrees(rowNode, colNode*2, l, mid);
        mergeColTrees(rowNode, colNode*2+1, mid+1, r);
        tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
    }

    // Build the row segment tree recursively.
    void buildRow(int node, int l, int r, const vector<vector<int>>& grid) {
        if (l == r) {
            // Leaf row: build its column tree from the grid row.
            buildColTree(node, 1, 0, m-1, grid[l]);
            return;
        }
        int mid = (l + r) / 2;
        buildRow(node*2, l, mid, grid);
        buildRow(node*2+1, mid+1, r, grid);
        // Merge the column trees of the two children.
        mergeColTrees(node, 1, 0, m-1);
    }

    // Update a single column in a leaf row node.
    void updateCol(int rowNode, int colNode, int l, int r, int y, int delta) {
        if (l == r) {
            tree[rowNode][colNode] += delta;
            return;
        }
        int mid = (l + r) / 2;
        if (y <= mid) updateCol(rowNode, colNode*2, l, mid, y, delta);
        else updateCol(rowNode, colNode*2+1, mid+1, r, y, delta);
        tree[rowNode][colNode] = tree[rowNode][colNode*2] + tree[rowNode][colNode*2+1];
    }

    // After updating one child row, recompute the current row node's
    // column tree for the affected column.
    void updateColMerge(int rowNode, int colNode, int l, int r, int y, int delta) {
        if (l == r) {
            tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
            return;
        }
        int mid = (l + r) / 2;
        if (y <= mid) updateColMerge(rowNode, colNode*2, l, mid, y, delta);
        else updateColMerge(rowNode, colNode*2+1, mid+1, r, y, delta);
        tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
    }

    // Update a cell (x,y) by adding delta, traversing the row tree.
    void updateRow(int node, int l, int r, int x, int y, int delta) {
        if (l == r) {
            updateCol(node, 1, 0, m-1, y, delta);
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) updateRow(node*2, l, mid, x, y, delta);
        else updateRow(node*2+1, mid+1, r, x, y, delta);
        // After child is updated, update the current node's column tree.
        updateColMerge(node, 1, 0, m-1, y, delta);
    }

    // Query the column tree of a given row node for a range of columns.
    int queryCol(int rowNode, int colNode, int l, int r, int y1, int y2) {
        if (y1 <= l && r <= y2) {
            return tree[rowNode][colNode];
        }
        int mid = (l + r) / 2;
        int res = 0;
        if (y1 <= mid) res += queryCol(rowNode, colNode*2, l, mid, y1, y2);
        if (y2 > mid) res += queryCol(rowNode, colNode*2+1, mid+1, r, y1, y2);
        return res;
    }

    // Query the row tree for a rectangle [x1..x2] × [y1..y2].
    int queryRow(int node, int l, int r, int x1, int x2, int y1, int y2) {
        if (x1 <= l && r <= x2) {
            return queryCol(node, 1, 0, m-1, y1, y2);
        }
        int mid = (l + r) / 2;
        int res = 0;
        if (x1 <= mid) res += queryRow(node*2, l, mid, x1, x2, y1, y2);
        if (x2 > mid) res += queryRow(node*2+1, mid+1, r, x1, x2, y1, y2);
        return res;
    }

public:
    // Constructor: prepares the tree with given dimensions.
    // Input: number of rows (n) and columns (m).
    SegTree2DSum(int n, int m) : n(n), m(m) {
        tree.assign(4*n, vector<int>(4*m, 0));
    }

    // Build the 2D segment tree from the grid.
    // Input: a 2D vector grid of size n x m (must match the constructor dimensions).
    // Time: O(n*m).
    void build(const vector<vector<int>>& grid) {
        buildRow(1, 0, n-1, grid);
    }

    // Point update: add 'delta' to cell (x,y).
    // Input: x (row), y (column), delta (value to add, can be negative).
    // Time: O(log n * log m).
    void updatePoint(int x, int y, int delta) {
        updateRow(1, 0, n-1, x, y, delta);
    }

    // Rectangle sum query: sum of cells in [x1..x2] × [y1..y2].
    // Input: x1, y1, x2, y2 (all 0‑based indices, inclusive).
    // Returns: the sum as an integer.
    // Time: O(log n * log m).
    int querySum(int x1, int y1, int x2, int y2) {
        return queryRow(1, 0, n-1, x1, x2, y1, y2);
    }
};

// ===================================================================
// 2) STATIC 2D SEGMENT TREE FOR MIN / MAX
//    (Point Update, Rectangle Query)
// ===================================================================

// -------------------------------------------------------------------
// CLASS: SegTree2DMinMax
// -------------------------------------------------------------------
// WHAT IT DOES:
//   Same structure as the sum version, but instead of summing,
//   it combines values using a custom merge function (e.g., min or max).
//   It supports point updates (set a cell to a value) and rectangle
//   queries (get the min or max over a rectangle).
//
// INPUT:
//   - Template parameter T: the data type (e.g., int, long long).
//   - Template parameter mergeFunc: a function pointer T (*)(T,T) that
//     combines two values (e.g., minFunc or maxFunc).
//   - The constructor also takes an 'identity' value – the neutral element
//     for the merge operation (e.g., INF for min, -INF for max).
//   - The grid is given as a 2D vector of T.
//   - Coordinates are 0‑based.
//
// OUTPUT:
//   - `query` returns a value of type T – the result of the merge over
//     the rectangle (min or max).
//   - `updatePoint` sets a cell to a new value (not an addition).
//
// TIME COMPLEXITY:
//   - Build: O(N * M).
//   - Update: O(log N * log M).
//   - Query:  O(log N * log M).
//
// MEMORY:
//   - O(N * M).
//
// CONSTRAINTS / ASSUMPTIONS:
//   - N and M must be known at construction.
//   - The grid values and the identity must be of type T.
//   - The merge function must be associative (like min, max).
//   - Use INT_MAX / INT_MIN for int, or LLONG_MAX / LLONG_MIN for long long.
//   - Point update sets the cell to the given value (overwrites).
//
// NOTES:
//   - The class is generic, so you need to instantiate it with a merge
//     function. Two helper functions (minFunc, maxFunc) are provided below.
//   - Example usage: SegTree2DMinMax<int, minFunc> segMin(n, m, INT_MAX);
//   - Because it's a static tree, it allocates full memory; use only for
//     moderate grid sizes.
// -------------------------------------------------------------------

template<typename T, T (*mergeFunc)(T, T)>
class SegTree2DMinMax {
    int n, m;
    vector<vector<T>> tree;
    T identity;

    // Build column tree for a single row.
    void buildColTree(int rowNode, int colNode, int l, int r, const vector<T>& row) {
        if (l == r) {
            tree[rowNode][colNode] = row[l];
            return;
        }
        int mid = (l + r) / 2;
        buildColTree(rowNode, colNode*2, l, mid, row);
        buildColTree(rowNode, colNode*2+1, mid+1, r, row);
        tree[rowNode][colNode] = mergeFunc(tree[rowNode][colNode*2], tree[rowNode][colNode*2+1]);
    }

    // Merge two child row nodes' column trees into the parent.
    void mergeColTrees(int rowNode, int colNode, int l, int r) {
        if (l == r) {
            tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
            return;
        }
        int mid = (l + r) / 2;
        mergeColTrees(rowNode, colNode*2, l, mid);
        mergeColTrees(rowNode, colNode*2+1, mid+1, r);
        tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
    }

    void buildRow(int node, int l, int r, const vector<vector<T>>& grid) {
        if (l == r) {
            buildColTree(node, 1, 0, m-1, grid[l]);
            return;
        }
        int mid = (l + r) / 2;
        buildRow(node*2, l, mid, grid);
        buildRow(node*2+1, mid+1, r, grid);
        mergeColTrees(node, 1, 0, m-1);
    }

    void updateCol(int rowNode, int colNode, int l, int r, int y, T val) {
        if (l == r) {
            tree[rowNode][colNode] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (y <= mid) updateCol(rowNode, colNode*2, l, mid, y, val);
        else updateCol(rowNode, colNode*2+1, mid+1, r, y, val);
        tree[rowNode][colNode] = mergeFunc(tree[rowNode][colNode*2], tree[rowNode][colNode*2+1]);
    }

    // Recompute current row node's column tree after a child row update.
    void updateColMerge(int rowNode, int colNode, int l, int r, int y, T val) {
        if (l == r) {
            tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
            return;
        }
        int mid = (l + r) / 2;
        if (y <= mid) updateColMerge(rowNode, colNode*2, l, mid, y, val);
        else updateColMerge(rowNode, colNode*2+1, mid+1, r, y, val);
        tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
    }

    void updateRow(int node, int l, int r, int x, int y, T val) {
        if (l == r) {
            updateCol(node, 1, 0, m-1, y, val);
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) updateRow(node*2, l, mid, x, y, val);
        else updateRow(node*2+1, mid+1, r, x, y, val);
        updateColMerge(node, 1, 0, m-1, y, val);
    }

    T queryCol(int rowNode, int colNode, int l, int r, int y1, int y2) {
        if (y1 <= l && r <= y2) {
            return tree[rowNode][colNode];
        }
        int mid = (l + r) / 2;
        T res = identity;
        if (y1 <= mid) res = mergeFunc(res, queryCol(rowNode, colNode*2, l, mid, y1, y2));
        if (y2 > mid) res = mergeFunc(res, queryCol(rowNode, colNode*2+1, mid+1, r, y1, y2));
        return res;
    }

    T queryRow(int node, int l, int r, int x1, int x2, int y1, int y2) {
        if (x1 <= l && r <= x2) {
            return queryCol(node, 1, 0, m-1, y1, y2);
        }
        int mid = (l + r) / 2;
        T res = identity;
        if (x1 <= mid) res = mergeFunc(res, queryRow(node*2, l, mid, x1, x2, y1, y2));
        if (x2 > mid) res = mergeFunc(res, queryRow(node*2+1, mid+1, r, x1, x2, y1, y2));
        return res;
    }

public:
    // Constructor: pass grid dimensions and the identity value for the merge.
    // Input: n (rows), m (columns), identity (e.g., INF for min, -INF for max).
    SegTree2DMinMax(int n, int m, T identity) : n(n), m(m), identity(identity) {
        tree.assign(4*n, vector<T>(4*m, identity));
    }

    // Build the tree from the grid.
    // Input: 2D vector grid of size n x m.
    // Time: O(n*m).
    void build(const vector<vector<T>>& grid) {
        buildRow(1, 0, n-1, grid);
    }

    // Point update: set cell (x,y) to value 'val' (overwrites previous value).
    // Input: x, y, val.
    // Time: O(log n * log m).
    void updatePoint(int x, int y, T val) {
        updateRow(1, 0, n-1, x, y, val);
    }

    // Rectangle query: returns the merge result over [x1..x2] × [y1..y2].
    // Input: x1, y1, x2, y2 (inclusive, 0‑based).
    // Returns: the min or max (depending on mergeFunc) as type T.
    // Time: O(log n * log m).
    T query(int x1, int y1, int x2, int y2) {
        return queryRow(1, 0, n-1, x1, x2, y1, y2);
    }
};

// -------------------------------------------------------------------
// Helper merge functions for min and max (to use with SegTree2DMinMax)
// -------------------------------------------------------------------
// minFunc: returns the smaller of two values.
// maxFunc: returns the larger of two values.
// These are simple functions that you can pass as template arguments.
int minFunc(int a, int b) { return min(a, b); }
int maxFunc(int a, int b) { return max(a, b); }

// ===================================================================
// 3) 2D FENWICK TREE WITH COORDINATE COMPRESSION (SPARSE POINTS)
//    (Point Update, Prefix Sum, Rectangle Sum)
// ===================================================================

// -------------------------------------------------------------------
// CLASS: Fenwick2D
// -------------------------------------------------------------------
// WHAT IT DOES:
//   This is a 2D Fenwick tree (also called Binary Indexed Tree) that
//   works with sparse points. It is useful when the grid is huge
//   (coordinates up to 1e9) but the number of points that will ever
//   be updated is relatively small (K points).
//   It supports:
//     - Point update: add a value (delta) to a point (x, y).
//     - Prefix sum: sum of all points with X <= x and Y <= y.
//     - Rectangle sum: sum over a rectangle using inclusion‑exclusion
//       from prefix sums.
//
// INPUT:
//   - Constructor: a list of all points (x, y) that will ever be updated.
//     This is used to compress the coordinates.
//   - Updates and queries use the same coordinate values (they must be
//     among those initially provided, otherwise the update will fail
//     or produce wrong results).
//   - Coordinates can be negative or large; they are stored as ints.
//
// OUTPUT:
//   - `add` modifies the internal structure (no return).
//   - `prefixSum(x, y)` returns the sum of points with X <= x and Y <= y.
//   - `rectangleSum(x1, y1, x2, y2)` returns the sum in that rectangle.
//
// TIME COMPLEXITY:
//   - Build (constructor): O(K log K) roughly, where K is the number of
//     unique points (or the number of points provided).
//   - Update: O(log K) in both dimensions.
//   - Prefix sum: O(log K) in both dimensions.
//
// MEMORY:
//   - O(K log K) in the worst case, because each point is inserted into
//     O(log K) Fenwick nodes. In practice, it is manageable for K up to
//     a few hundred thousand.
//
// CONSTRAINTS / ASSUMPTIONS:
//   - All points that will be updated must be passed to the constructor
//     beforehand. If you try to update a point that was not in the list,
//     the internal `ys` vector for that x will not contain that y, and
//     the update will access out‑of‑bounds (or silently fail).
//   - Coordinates are integer values.
//   - The class uses 1‑based indexing internally for the Fenwick tree,
//     but the public interface uses the original coordinates (0‑based or
//     any integer).
//   - Rectangle queries use the standard inclusion‑exclusion formula
//     with prefix sums.
//
// NOTES:
//   - "Fenwick tree" is a data structure that efficiently supports
//     prefix sums and point updates. It is also called a Binary Indexed
//     Tree (BIT).
//   - "Coordinate compression" means we map large coordinate values to
//     small indices (1..K) so that we can store arrays of manageable size.
//   - This implementation is offline: it needs all update points in
//     advance. If you have dynamic additions of new points, you need a
//     different approach (e.g., a dynamic 2D segment tree).
//   - The `prefixSum` method returns the sum for all points with X <= x
//     and Y <= y. If x or y is smaller than all provided coordinates,
//     it returns 0.
// -------------------------------------------------------------------

class Fenwick2D {
    int n; // number of compressed x coordinates
    vector<vector<int>> ys; // compressed y coordinates per x node
    vector<vector<int>> bit; // BIT values (2D)
    vector<int> xs; // all unique x coordinates

public:
    // Constructor: takes a list of all points that will ever be updated.
    // Input: vector of pairs (x, y). Duplicates are allowed (they are handled).
    // Time: O(K log K) where K is the number of points.
    Fenwick2D(const vector<pair<int,int>>& points) {
        // Collect all unique x coordinates.
        vector<int> allX;
        for (auto &p : points) allX.push_back(p.first);
        sort(allX.begin(), allX.end());
        allX.erase(unique(allX.begin(), allX.end()), allX.end());
        xs = allX;
        n = xs.size();
        ys.resize(n+1);
        // For each point, add its y to all Fenwick nodes that cover its x.
        for (auto &p : points) {
            int x = p.first;
            int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1; // 1-indexed
            for (int i = idx; i <= n; i += i & -i) {
                ys[i].push_back(p.second);
            }
        }
        // Compress each y list and allocate the BIT array.
        bit.resize(n+1);
        for (int i = 1; i <= n; i++) {
            sort(ys[i].begin(), ys[i].end());
            ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
            bit[i].assign(ys[i].size()+1, 0);
        }
    }

    // Point update: add 'delta' to point (x, y).
    // Input: x, y (coordinates), delta (value to add).
    // Time: O(log K) where K is the number of points.
    // IMPORTANT: (x,y) must have been included in the constructor's point list.
    void add(int x, int y, int delta) {
        int xi = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
        for (int i = xi; i <= n; i += i & -i) {
            int yi = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1;
            for (int j = yi; j < (int)bit[i].size(); j += j & -j) {
                bit[i][j] += delta;
            }
        }
    }

    // Prefix sum: sum of all points with X <= x and Y <= y.
    // Input: x, y (coordinates).
    // Returns: integer sum.
    // Time: O(log K).
    int prefixSum(int x, int y) {
        int xi = upper_bound(xs.begin(), xs.end(), x) - xs.begin(); // number of xs <= x
        int res = 0;
        for (int i = xi; i > 0; i -= i & -i) {
            int yi = upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
            for (int j = yi; j > 0; j -= j & -j) {
                res += bit[i][j];
            }
        }
        return res;
    }

    // Rectangle sum: sum of points inside [x1..x2] × [y1..y2].
    // Input: x1, y1, x2, y2 (inclusive, any order).
    // Returns: integer sum.
    // Time: O(log K) (four prefixSum calls).
    int rectangleSum(int x1, int y1, int x2, int y2) {
        return prefixSum(x2, y2) - prefixSum(x1-1, y2) - prefixSum(x2, y1-1) + prefixSum(x1-1, y1-1);
    }
};

// ===================================================================
// 4) 2D SEGMENT TREE WITH LAZY PROPAGATION (RANGE UPDATES)
//    (Concept only – not implemented)
// ===================================================================
// This section is kept as a placeholder. Lazy propagation in 2D is
// advanced and rarely needed. For most problems, a 2D BIT or offline
// sweepline is sufficient. No implementation is provided here.
// ===================================================================

// ===================================================================
// 5) COMMON TRICKS & PATTERNS FOR ECPC/ACPC
// ===================================================================
// The following notes are for your reference:
//
// 5.1) Offline queries with sweepline:
//      For static 2D points, you can answer rectangle sum queries by
//      sorting points by x, queries by x2, and using a 1D BIT on y.
//      This avoids 2D segment trees entirely.
//
// 5.2) Dynamic 2D Segment Tree using pointers:
//      When the grid is huge and updates/queries are few, you can
//      create nodes on demand. This is not implemented here because
//      it is complex; the Fenwick2D class is usually enough for sparse data.
//
// 5.3) Using 2D Segment Tree for range maximum with point updates:
//      The SegTree2DMinMax class above does exactly that.
//
// 5.4) Combining with Binary Search on answer:
//      If you need to find the smallest rectangle containing a certain
//      number of points, you can binary search the size and use a
//      2D segment tree to count points in a rectangle.
//
// 5.5) Negative coordinates or large ranges:
//      Always use coordinate compression (Fenwick2D) for such cases.
// ===================================================================

// ===================================================================
// 6) SPARSE 2D SEGMENT TREE (DYNAMIC ALLOCATION) – NOT IMPLEMENTED
// ===================================================================
// A fully dynamic 2D segment tree would allocate nodes only when
// needed. Because of its complexity, we recommend using Fenwick2D
// with coordinate compression instead.
// ===================================================================

// ===================================================================
// 7) EXAMPLE USAGE
// ===================================================================
// The main() function below demonstrates how to use the three main
// classes. Read the comments inside to see each step.
// ===================================================================

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

    // ---------- Example 1: Sum 2D Segment Tree ----------
    vector<vector<int>> grid = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int n = 3, m = 3;
    SegTree2DSum seg(n, m);
    seg.build(grid);

    cout << "Sum of entire grid: " << seg.querySum(0,0,2,2) << '\n'; // 45
    cout << "Sum of subrectangle (1,1)-(2,2): " << seg.querySum(1,1,2,2) << '\n'; // 5+6+8+9=28

    seg.updatePoint(1,1, 10); // add 10 to cell (1,1) which was 5 -> now 15
    cout << "After update, sum of subrectangle (1,1)-(2,2): " << seg.querySum(1,1,2,2) << '\n'; // 15+6+8+9=38

    // ---------- Example 2: Min 2D Segment Tree ----------
    SegTree2DMinMax<int, minFunc> segMin(n, m, INT_MAX);
    segMin.build(grid);
    cout << "Min in entire grid: " << segMin.query(0,0,2,2) << '\n'; // 1
    segMin.updatePoint(0,0, 0); // set (0,0) to 0
    cout << "Min after update: " << segMin.query(0,0,2,2) << '\n'; // 0

    // ---------- Example 3: 2D Fenwick with coordinate compression ----------
    vector<pair<int,int>> points = {{1,1}, {2,3}, {5,7}};
    Fenwick2D fw(points);
    fw.add(1,1, 5);
    fw.add(2,3, 10);
    cout << "Prefix sum up to (2,3): " << fw.prefixSum(2,3) << '\n'; // 15
    cout << "Prefix sum up to (5,7): " << fw.prefixSum(5,7) << '\n'; // 15
    fw.add(5,7, 3);
    cout << "After add: " << fw.prefixSum(5,7) << '\n'; // 18

    return 0;
}

// ===================================================================
// ADDITIONAL NOTES FOR ECPC/ACPC COMPETITORS:
// - 2D Segment Trees are memory heavy; use them only when N and M are
//   small (<= 1000) or when coordinates are compressed.
// - For dynamic updates and large coordinates, prefer Fenwick2D with
//   compression (offline).
// - For offline static queries, a sweepline + 1D BIT is often simpler
//   and faster.
// - When implementing your own 2D segment tree, watch out for recursion
//   depth and memory consumption.
// - Always test edge cases: N=1, M=1, empty rectangles, negative
//   coordinates (Fenwick2D handles them if you provide them).
// ===================================================================