/**
* __ __ __ __
* \ \ / / \ \ / (_) _____
* \ \ / /_ _\ \ / / _ ___|_ _|
* \ \/ /| | | |\ \/ / | |/ _ \ | |
* \ / | |_| | \ / | | __/ | |
* \/ \__,_| \/ |_|\____||_|
*
* Author: ~Noah's Ark~
* Born on: 2024-24-03 11:15
**/
#include <iostream>
#include <vector>
#include <algorithm>
#define ____vuviet__ signed main
#define taskname "matryoshka"
using namespace std;
using lli = long long;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define GetBit(x, k) ((x >> k) & 1)
#define OnBit(x, k) (x | (1LL << k))
#define OffBit(x, k) (x & ~(1LL << k))
#define FlipBit(x, k) (x ^ (1LL << k))
constexpr int maxn = 1e6 + 36;
vector<int> grp[maxn], question[maxn];
int n, q, r[maxn], h[maxn];
pair<int, int> qr[maxn];
struct TFenwickTree
{
vector<lli> data;
int sz;
void init(int sz)
{
this->sz = sz;
data.resize(sz + 1);
}
void update(int i, lli v)
{
for (; i <= sz; i += (i & -i))
data[i] = max(data[i], v);
}
lli get(int i)
{
lli res = 0;
for (; i > 0; i -= (i & -i))
res = max(res, data[i]);
return res;
}
};
void Initial()
{
vector<int> vals;
for (int i = 1; i <= n; ++i)
vals.pb(r[i]), vals.pb(h[i]);
for (int i = 1; i <= q; ++i)
vals.pb(qr[i].fi), vals.pb(qr[i].se);
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 1; i <= n; ++i)
{
r[i] = lb(all(vals), r[i]) - vals.begin() + 1;
h[i] = lb(all(vals), h[i]) - vals.begin() + 1;
}
for (int i = 1; i <= q; ++i)
{
qr[i].fi = lb(all(vals), qr[i].fi) - vals.begin() + 1;
qr[i].se = lb(all(vals), qr[i].se) - vals.begin() + 1;
}
}
void SolvebyNoahzArk()
{
cin >> n >> q;
for (int i = 1; i <= n; ++i)
cin >> r[i] >> h[i];
for (int i = 1; i <= q; ++i)
cin >> qr[i].fi >> qr[i].se;
Initial();
for (int i = 1; i <= n; ++i)
grp[r[i]].pb(h[i]);
for (int x = 1; x < maxn; ++x)
sort(all(grp[x]));
for (int i = 1; i <= q; ++i)
question[qr[i].fi].pb(i);
TFenwickTree ft;
ft.init(maxn);
vector<int> res(q + 1);
for (int i = maxn - 1; i >= 0; --i)
{
for (int x : grp[i])
ft.update(x, ft.get(x) + 1);
for (int x : question[i])
res[x] = ft.get(qr[x].se);
}
for (int i = 1; i <= q; ++i)
cout << res[i] << "\n";
}
____vuviet__()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t-- > 0)
SolvebyNoahzArk();
return 0;
}
