#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds; using ordered_set = tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>; ostream &operator <<(ostream &out, vector <int> val) { for (auto v : val) { out << v << ' '; } return out; } struct mst { int n; vector <int> val; vector <ordered_set> tree; void upt(int num, int l, int r, int ind) { tree[num].insert(val[ind]); if (l == r - 1) { return; } int med = (l + r) / 2; if (med > ind) { upt(2 * num + 1, l, med, ind); } else { upt(2 * num + 2, med, r, ind); } } int get(int num, int l, int r, int low, int high, int k) { if (l >= low && r <= high) { if (tree[num].empty()) { return 0; } return tree[num].size() - tree[num].order_of_key(k); } int med = (l + r) / 2; int ans = 0; if (med > low) { ans += get(2 * num + 1, l, med, low, high, k); } if (med < high) { ans += get(2 * num + 2, med, r, low, high, k); } return ans; } public: void init(int nn, vector <int> &nval) { val = nval; n = nn; tree.resize(4 * n); } int get(int l, int r, int k) { if (l >= r) { return 0; } return get(0, 0, n, l, r, k); } void upt(int ind) { upt(0, 0, n, ind); } }; struct query { int a, b, c, ind; void init(int num) { cin >> a >> b >> c; ind = num; } }; struct value { int s, t, ind; void init(int num) { cin >> s >> t; ind = num; } }; void solve() { int n; cin >> n; int m; cin >> m; vector <value> val(n); for (int i = 0; i < n; ++i) { val[i].init(i); } vector <query> q(m); for (int i = 0; i < m; ++i) { q[i].init(i); } sort(q.begin(), q.end(), [](query &v1, query &v2) { return v1.c > v2.c; }); sort(val.begin(), val.end(), [](value &v1, value &v2) { return v1.s < v2.s; }); for (int i = 0; i < n; ++i) { val[i].ind = i; } auto nval = val; sort(nval.begin(), nval.end(), [](value &v1, value &v2) { return v1.s + v1.t > v2.s + v2.t; }); vector <int> cv(n); for (int i = 0; i < n; ++i) { cv[i] = val[i].t; } mst now; now.init(n, cv); int ind1 = 0; vector <pair <int, int>> ans; for (int i = 0; i < m; ++i) { while (ind1 < n && nval[ind1].s + nval[ind1].t >= q[i].c) { now.upt(nval[ind1].ind); ++ind1; } int l = - 1, r = n; while (r - l > 1) { int med = (l + r) / 2; if (val[med].s < q[i].a) { l = med; } else { r = med; } } ans.emplace_back(q[i].ind, now.get(r, n, q[i].b)); } sort(ans.begin(), ans.end()); for (auto v : ans) { cout << v.second << '\n'; } } signed main() { cin.tie(0); ios::sync_with_stdio(false); int t = 1; // cin >> t; for (int i = 0; i < t; ++i) { solve(); } }