Cpp 6 lines || Using 2D Sparse Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nusing str = string;\nusing ll = long long;\nusing ld = long double;\n\n#define ar array\n#define vt vector\n#define pb push_back\n#define fi first\n#define se second\n#define all(c) (c).begin(), (c).end()\n#define len(x) (int)(x).size()\n#define elif else if\n#define def function\n\n#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))\n#define F_OR1(e) F_OR(i, 0, e, 1)\n#define F_OR2(i, e) F_OR(i, 0, e, 1)\n#define F_OR3(i, b, e) F_OR(i, b, e, 1)\n#define F_OR4(i, b, e, s) F_OR(i, b, e, s)\n#define GET5(a, b, c, d, e, ...) e\n#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)\n#define rep(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)\n#define each(x, a) for (auto& x: a)\n\ntemplate <class T>\nconstexpr T inf = 0;\ntemplate <>\nconstexpr int inf<int> = 1\'000\'000\'005;\ntemplate <>\nconstexpr long long inf<long long> = (long long)(inf<int>) * inf<int> * 2;\n\nclass Solution {\ntemplate<class B, class T, class F>\nstruct segment_tree_2d_sparse{\n    vector<B> X;\n    vector<vector<array<B, 2>>> Y;\n    vector<vector<T>> data;\n    F TT; // Commutative monoid operation (always adjacent)\n    T T_id; // Commutative monoid identity\n    // Every point holds T_id except for base points\n    // O(n log^2 n)\n    segment_tree_2d_sparse(vector<pair<array<B, 2>, T>> init, F TT, T T_id): X(init.size()), TT(TT), T_id(T_id){\n        int n = (int)init.size();\n        sort(init.begin(), init.end());\n        for(auto i = 0; i < n; ++ i) X[i] = init[i].first[0];\n        X.erase(unique(X.begin(), X.end()), X.end());\n        Y.resize(X.size() << 1);\n        data.resize(X.size() << 1);\n        vector<vector<pair<array<B, 2>, T>>> hold(X.size() << 1);\n        for(auto i = 0, x = 0; i < n; ++ i){\n            auto [pos, val] = init[i];\n            while(X[x] < pos[0]) ++ x;\n            hold[x + (int)X.size()].push_back({{pos[1], pos[0]}, val});\n        }\n        for(auto x = 2 * (int)X.size() - 1; x; -- x){\n            if(x < (int)X.size()) merge(hold[x << 1].begin(), hold[x << 1].end(), hold[x << 1 | 1].begin(), hold[x << 1 | 1].end(), back_inserter(hold[x]));\n            auto &Y0 = Y[x];\n            auto &hold0 = hold[x];\n            sort(hold0.begin(), hold0.end());\n            Y0.resize(hold0.size());\n            for(auto j = 0; j < (int)hold0.size(); ++ j) Y0[j] = hold0[j].first;\n            Y0.erase(unique(Y0.begin(), Y0.end()), Y0.end());\n            data[x].resize(Y0.size() << 1, T_id);\n            for(auto j = 0, y = 0; j < (int)hold0.size(); ++ j){\n                while(Y0[y] < hold0[j].first) ++ y;\n                data[x][y + (int)Y0.size()] = TT(data[x][y + (int)Y0.size()], hold0[j].second);\n            }\n            for(auto y = (int)Y0.size() - 1; y; -- y) data[x][y] = TT(data[x][y << 1], data[x][y << 1 | 1]);\n        }\n    }\n    // O(n log^2 n)\n    segment_tree_2d_sparse(vector<array<B, 2>> base, F TT, T T_id){\n        vector<pair<array<B, 2>, T>> init(base.size());\n        for(auto i = 0; i < (int)base.size(); ++ i) init[i] = {base[i], T_id};\n        *this = segment_tree_2d_sparse(init, TT, T_id);\n    }\n    segment_tree_2d_sparse &operator=(const segment_tree_2d_sparse &otr){\n        X = otr.X;\n        Y = otr.Y;\n        data = otr.data;\n        return *this;\n    }\n    // O(log^2 n)\n    void set(B _p, B _q, T x){\n        int p = lower_bound(X.begin(), X.end(), _p) - X.begin();\n        assert(p < (int)X.size() && X[p] == _p);\n        for(p += (int)X.size(); p; p >>= 1){\n            auto &Y0 = Y[p];\n            auto &data0 = data[p];\n            int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin();\n            assert(q < (int)Y0.size() && Y0[q][0] == _q && Y0[q][1] == _p);\n            for(data0[q += (int)Y0.size()] = x; q >>= 1; ) data0[q] = TT(data0[q << 1], data0[q << 1 | 1]);\n        }\n    }\n    // O(log n)\n    T query(B _p, B _q){\n        int p = lower_bound(X.begin(), X.end(), _p) - X.begin();\n        if(p == (int)X.size() || X[p] != _p) return T_id;\n        auto &Y0 = Y[p + (int)X.size()];\n        int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin();\n        if(q == (int)Y0.size() || Y0[q] != array{_q, _p}) return T_id;\n        return data[p + (int)X.size()][q + (int)Y0.size()];\n    }\n    // O(log^2 n)\n    T query(B _xl, B _xr, B _yl, B _yr){\n        int xl = lower_bound(X.begin(), X.end(), _xl) - X.begin();\n        int xr = lower_bound(X.begin(), X.end(), _xr) - X.begin();\n        T res = T_id;\n        for(xl += (int)X.size(), xr += (int)X.size(); xl < xr; xl >>= 1, xr >>= 1){\n            if(xl & 1){\n                auto &Y0 = Y[xl];\n                auto &data0 = data[xl];\n                int yl = lower_bound(Y0.begin(), Y0.end(), array{_yl, numeric_limits<B>::min()}) - Y0.begin();\n                int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin();\n                for(yl += (int)Y0.size(), yr += (int)Y0.size(); yl < yr; yl >>= 1, yr >>= 1){\n                    if(yl & 1) res = TT(res, data0[yl ++]);\n                    if(yr & 1) res = TT(res, data0[-- yr]);\n                }\n                ++ xl;\n            }\n            if(xr & 1){\n                -- xr;\n                auto &Y0 = Y[xr];\n                auto &data0 = data[xr];\n                int yl = lower_bound(Y0.begin(), Y0.end(), array{_yl, numeric_limits<B>::min()}) - Y0.begin();\n                int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin();\n                for(yl += (int)Y0.size(), yr += (int)Y0.size(); yl < yr; yl >>= 1, yr >>= 1){\n                    if(yl & 1) res = TT(res, data0[yl ++]);\n                    if(yr & 1) res = TT(res, data0[-- yr]);\n                }\n            }\n        }\n        return res;\n    }\n};\n\npublic:\n    vector<int> maximumSumQueries(vector<int>& x, vector<int>& y, vector<vector<int>>& queries) {\n        \n        vt<pair<ar<int, 2>, ll>> init;\n        rep(i, len(x)) init.pb({{x[i], y[i]}, x[i] + y[i]});\n        segment_tree_2d_sparse seg(init, [&](ll l, ll r){ return max(l, r); }, -inf<ll>);\n\n        vt<int> res;\n        each(qq, queries) {\n            ll ret = seg.query(qq[0], inf<int>, qq[1], inf<int>);\n            ret != -inf<ll> ? res.pb(ret): res.pb(-1);\n        }\n        return res;\n    }\n};\n```
['C++']