[ Bonus ] Fenwick 2D ; main: explained monotonic stack
Let me help you complete the solution explanation:\n\n# Intuition\nWe process queries by sorting both the input array indices and query indices by X values in d
Let me help you complete the solution explanation:\n\n# Intuition\nWe process queries by sorting both the input array indices and query indices by X values in descending order. This allows us to maintain a monotonic stack of Y-values and their corresponding sums that will be valid for each query.\n\n# Approach\n1. Sort indices of input arrays by X values (descending)\n2. Sort query indices by X requirement (descending) \n3. Process queries sequentially, maintaining a stack of (Y, sum) pairs where:\n   - Y values are strictly ascending\n   - Sum values are strictly descending\n4. For each query:\n   - Add all array elements with X \u2265 query.X to the stack\n   - Use binary search to find first Y value \u2265 query.Y\n   - The corresponding sum is our answer (or -1 if not found)\n\n# Complexity\n- Time complexity: O((N + Q) log N) where N is array length and Q is number of queries\n- Space complexity: O(N)\n\n# Bonus Solution Note: \nThe alternative solution uses a 2D Fenwick tree (Binary Indexed Tree) to maintain prefix maximums. While theoretically elegant with O(log\xB2N) query time, it\'s less practical due to:\n1. Memory overhead\n2. More complex coordinate compression needed\n3. Slower actual performance\n\n\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(\n            const vector<int>& Xs, const vector<int>& Ys, const vector<vector<int>>& queries) {\n        vector<int> asX(Xs.size());\n        iota(asX.begin(), asX.end(), 0);\n        sort(asX.begin(), asX.end(), [&Xs](int a, int b) { return Xs[a] > Xs[b]; });\n        vector<int> asQ(queries.size());\n        iota(asQ.begin(), asQ.end(), 0);\n        sort(asQ.begin(), asQ.end(), [&queries](int a, int b) { return queries[a][0] > queries[b][0]; });\n\n        vector<int> res(queries.size(), -1);\n\n        vector<pair<int, int>> s_y_sum;\n        for (int i = 0, j = 0; i < asQ.size(); ++i) {\n            int qx = queries[asQ[i]][0];\n            int qy = queries[asQ[i]][1];\n            for (; j < asX.size() && Xs[asX[j]] >= qx; ++j) {\n                int dy = Ys[asX[j]];\n                int dsum = Xs[asX[j]] + Ys[asX[j]];\n                if (!s_y_sum.empty() && s_y_sum.back().first >= dy) continue;\n                while (!s_y_sum.empty() && s_y_sum.back().second < dsum)\n                    s_y_sum.pop_back();\n                s_y_sum.emplace_back(dy, dsum);\n            }\n            auto it = lower_bound(\n                s_y_sum.begin(), s_y_sum.end(), qy,\n                [](const pair<int, int> y_sum, int _qy) { return y_sum.first < _qy; });\n            if (it != s_y_sum.end())\n                res[asQ[i]] = it->second;\n            //\n            // Due to presumable lack of test, non-bisect approach seem to be fast as well:\n            //\n            // for (int k = 0; k < s_y_sum.size(); ++k) {\n            //     if (s_y_sum[k].first >= qy) {\n            //         res[asQ[i]] = s_y_sum[k].second;\n            //         break;\n            //     }\n            // }\n        }\n\n        return res;\n    }\n};\n```\n\nBonus:\n```cpp\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(\n            const vector<int>& Xs, const vector<int>& Ys, const vector<vector<int>>& queries) {\n        const int N = Xs.size();\n        vector<int> QXs(queries.size());\n        vector<int> QYs(queries.size());\n        for (int i = 0; i < queries.size(); ++i) {\n            QXs[i] = queries[i][0];\n            QYs[i] = queries[i][1];\n        }\n\n        auto rev_coo_cmpct = [](const vector<int>& dt, const vector<int>& q) {\n            vector<int> v;\n            v.reserve(dt.size() + q.size());\n            v.insert(v.end(), dt.begin(), dt.end());\n            v.insert(v.end(), q.begin(), q.end());\n            vector<int> as(v.size());\n            iota(as.begin(), as.end(), 0);\n            sort(as.begin(), as.end(), [&v](int a, int b) { return v[a] > v[b]; });\n            vector<int> cc(v.size());\n            int ccj = 0;\n            cc[as[0]] = ++ccj;\n            for (int i = 1; i < as.size(); ++i)\n                cc[as[i]] = v[as[i - 1]] > v[as[i]] ? ++ccj : ccj;\n            return cc;\n        };\n        vector<int> ccX = rev_coo_cmpct(Xs, QXs);\n        vector<int> ccY = rev_coo_cmpct(Ys, QYs);\n\n        const int fenwN = max(\n            *max_element(ccX.begin(), ccX.end()),\n            *max_element(ccY.begin(), ccY.end()));\n        unordered_map<long long, int> fenw(ccX.size() * 256);\n        auto upd = [fenwN, &fenw](int x, int y, int sum) {\n            const int M = fenwN;\n            for (long long i = x; i <= M; i += i & -i)\n                for (int j = y; j <= M; j += j & -j) {\n                    int& r = fenw[(i << 30) | j];\n                    if (r < sum)\n                        r = sum;\n                }\n        };\n        auto get = [&fenw](int x, int y) {\n            int res = 0;\n            for (long long i = x; i > 0; i -= i & -i)\n                for (int j = y; j > 0; j -= j & -j)\n                    res = max(res, fenw[(i << 30) | j]);\n            return res;\n        };\n\n        for (int i = 0; i < N; ++i)\n            upd(ccX[i], ccY[i], Xs[i] + Ys[i]);\n        vector<int> res(queries.size());\n        for (int i = 0; i < queries.size(); ++i) {\n            int r = get(ccX[N + i], ccY[N + i]);\n            res[i] = r > 0 ? r : -1;\n        }\n        return res;\n    }\n};\n```
['C++']