#include <bits/stdc++.h> using namespace std; struct BIT2D { int n; vector<vector<int>> ys; vector<vector<int>> bit; BIT2D(int n): n(n), ys(n+1), bit(n+1) {} void fake_update(int x, int y) { for (; x <= n; x += x & -x) ys[x].push_back(y); } void build() { 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); } } void add(int x, int y, int v) { for (; x <= n; x += x & -x) { int yy = lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin() + 1; for (; yy < (int)bit[x].size(); yy += yy & -yy) bit[x][yy] += v; } } int sum(int x, int y) { int res = 0; for (; x > 0; x -= x & -x) { int yy = upper_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin(); for (; yy > 0; yy -= yy & -yy) res += bit[x][yy]; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<int> S(N), T(N); for (int i = 0; i < N; i++) cin >> S[i] >> T[i]; struct Query { int A, B, C, id; }; vector<Query> queries(Q); for (int i = 0; i < Q; i++) { cin >> queries[i].A >> queries[i].B >> queries[i].C; queries[i].id = i; } // Prepare points vector<array<int,3>> students(N); vector<int> allU, allV; for (int i = 0; i < N; i++) { int u = T[i]; int v = S[i] + T[i]; students[i] = {S[i], u, v}; allU.push_back(u); allV.push_back(v); } // Compress U and V sort(allU.begin(), allU.end()); allU.erase(unique(allU.begin(), allU.end()), allU.end()); sort(allV.begin(), allV.end()); allV.erase(unique(allV.begin(), allV.end()), allV.end()); auto getU = [&](int x) { return int(lower_bound(allU.begin(), allU.end(), x) - allU.begin()) + 1; }; auto getV = [&](int x) { return int(lower_bound(allV.begin(), allV.end(), x) - allV.begin()) + 1; }; for (auto &s : students) { s[1] = getU(s[1]); s[2] = getV(s[2]); } // Sort students by S descending sort(students.begin(), students.end(), [](auto &a, auto &b) { return a[0] > b[0]; }); // Prepare BIT BIT2D bit(allU.size()); // Fake updates to build structure for (auto &s : students) bit.fake_update(s[1], s[2]); bit.build(); // Sort queries by A descending sort(queries.begin(), queries.end(), [](auto &a, auto &b) { return a.A > b.A; }); vector<int> answer(Q); int ptr = 0; for (auto &q : queries) { while (ptr < N && students[ptr][0] >= q.A) { bit.add(students[ptr][1], students[ptr][2], 1); ptr++; } int uB = lower_bound(allU.begin(), allU.end(), q.B) - allU.begin(); int vC = lower_bound(allV.begin(), allV.end(), q.C) - allV.begin(); int total = bit.sum(allU.size(), allV.size()); int lessU = bit.sum(uB, allV.size()); int lessV = bit.sum(allU.size(), vC); int lessUV = bit.sum(uB, vC); answer[q.id] = total - lessU - lessV + lessUV; } for (int i = 0; i < Q; i++) cout << answer[i] << '\n'; }