#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int MAXQ = 200000;
const int MAXV = 400000; // N + Q
struct Doll {
int R, H;
};
struct Query {
int A, B, id;
};
struct Node {
int val;
Node *left, *right;
Node() : val(0), left(nullptr), right(nullptr) {}
Node(int v, Node* l, Node* r) : val(v), left(l), right(r) {}
};
int N, Q;
Doll dolls[MAXN];
Query queries[MAXQ];
vector<int> values;
int compH[MAXN];
int compB[MAXQ];
int ans[MAXQ];
Node* roots[MAXN + 1];
Node* nullNode;
Node* build(int l, int r) {
if (l == r) return new Node(0, nullNode, nullNode);
int mid = (l + r) >> 1;
return new Node(0, build(l, mid), build(mid + 1, r));
}
Node* update(Node* node, int l, int r, int pos, int val) {
if (l == r) return new Node(val, nullNode, nullNode);
int mid = (l + r) >> 1;
if (pos <= mid) {
Node* newLeft = update(node->left, l, mid, pos, val);
return new Node(max(newLeft->val, node->right->val), newLeft, node->right);
} else {
Node* newRight = update(node->right, mid + 1, r, pos, val);
return new Node(max(node->left->val, newRight->val), node->left, newRight);
}
}
int query(Node* node, int l, int r, int L, int R) {
if (node == nullNode || r < L || R < l) return 0;
if (L <= l && r <= R) return node->val;
int mid = (l + r) >> 1;
return max(query(node->left, l, mid, L, R),
query(node->right, mid + 1, r, L, R));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
nullNode = new Node(0, nullptr, nullptr);
nullNode->left = nullNode->right = nullNode;
cin >> N >> Q;
for (int i = 0; i < N; ++i) {
cin >> dolls[i].R >> dolls[i].H;
values.push_back(dolls[i].H);
}
for (int i = 0; i < Q; ++i) {
cin >> queries[i].A >> queries[i].B;
queries[i].id = i;
values.push_back(queries[i].B);
}
// Сжатие координат высот
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int M = values.size();
for (int i = 0; i < N; ++i) {
compH[i] = lower_bound(values.begin(), values.end(), dolls[i].H) - values.begin() + 1;
}
for (int i = 0; i < Q; ++i) {
compB[i] = lower_bound(values.begin(), values.end(), queries[i].B) - values.begin() + 1;
}
// Сортировка матрёшек по убыванию R
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (dolls[i].R != dolls[j].R) return dolls[i].R > dolls[j].R;
return dolls[i].H > dolls[j].H;
});
// Построение персистентного дерева отрезков
roots[0] = build(1, M);
for (int i = 0; i < N; ++i) {
int idx = order[i];
int h = compH[idx];
int cur = query(roots[i], 1, M, 1, h) + 1;
roots[i + 1] = update(roots[i], 1, M, h, cur);
}
// Обработка запросов
for (int i = 0; i < Q; ++i) {
int A = queries[i].A;
int B = compB[i];
// Бинарный поиск последней матрёшки с R >= A
int lo = 0, hi = N - 1, idx = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (dolls[order[mid]].R >= A) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if (idx == -1) {
ans[queries[i].id] = 0;
} else {
Node* root = roots[idx + 1];
ans[queries[i].id] = query(root, 1, M, 1, B);
}
}
for (int i = 0; i < Q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
