#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int n, q;
int ans[N];
vector<int> val;
ii a[2 * N];
struct Query {
int a, b, id;
};
Query qu[N];
struct Bit {
int bit[2 * N];
void up(int x, int val) {
for(; x <= 2 * n; x += x & -x) bit[x] = max(bit[x], val);
}
int get(int x) {
int ret = 0;
for(; x; x -= x & -x) ret = max(ret, bit[x]);
return ret;
}
};
Bit bit;
struct Smt {
int seg[8 * N], lz[8 * N];
void push(int id) {
int val = lz[id];
if(val != 0) {
seg[id << 1] = max(seg[id << 1], val);
seg[id << 1 | 1] = max(seg[id << 1 | 1], val);
lz[id << 1] = max(lz[id << 1], val);
lz[id << 1 | 1] = max(lz[id << 1 | 1], val);
lz[id] = 0;
}
}
void up(int id, int l, int r, int u, int v, int val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
seg[id] = max(seg[id], val);
lz[id] = max(lz[id], val);
return;
}
int mid = l + r >> 1;
push(id);
up(id << 1, l, mid, u, v, val);
up(id << 1 | 1, mid + 1, r, u, v, val);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int l, int r, int pos) {
if(pos < l || pos > r) return 0;
if(l == r) return seg[id];
int mid = l + r >> 1;
push(id);
return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
}
};
Smt it;
void Solve() {
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
FOR(i, 1, n) a[i].se = lower_bound(val.begin(), val.end(), a[i].se) - val.begin() + 1;
FOR(i, 1, n) qu[i].b = lower_bound(val.begin(), val.end(), qu[i].b) - val.begin() + 1;
sort(a + 1, a + 1 + n + q, [&] (ii &a, ii &b) {
return (a.fi == b.fi ? a.se < b.se : a.fi > b.fi);
});
sort(qu + 1, qu + 1 + q, [&] (Query &a, Query &b) {
return a.a > b.a;
});
// FOR(i, 1, n + q) {
// cout << a[i].fi << ' ' << a[i].se << '\n';
// }
// cout << '\n';
int p = 1;
FOR(i, 1, n + q) {
if(a[i].se != (int)2e9) {
// cout << a[i].se << ' ';
int mx = bit.get(a[i].se) + 1;
bit.up(a[i].se, mx);
it.up(1, 1, 2 * n, a[i].se, 2 * n, mx);
// cout << mx << '\n';
}
if(a[i].se == (int)2e9) {
while(p <= q && qu[p].a == a[i].fi) {
// cout << qu[p].a << ' ' << qu[p].b << ' ' << qu[p].id << ' ' << a[i].fi << '\n';
ans[qu[p].id] = it.get(1, 1, 2 * n, qu[p].b);
p++;
}
}
}
FOR(i, 1, q) {
cout << ans[i] << '\n';
}
}
signed main() {
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) {
cin >> n >> q;
FOR(i, 1, n) {
cin >> a[i].fi >> a[i].se;
val.pb(a[i].se);
}
FOR(i, 1, q) {
cin >> qu[i].a >> qu[i].b;
qu[i].id = i;
val.pb(qu[i].b);
a[i + n] = {qu[i].a, (int)2e9};
}
Solve();
}
}
