※この問題は A Most Popular Matcha's Snow Land (Easy) の問題と全く同じ構成をしていますが、制約のみが異なります。この問題に正解できれば (Easy) の問題も正解できます。

問題

GreenTea 王国には、”Matcha’s Snow Land” といういつ行っても行列ができるほど人気な遊園地があります。その遊園地は、このご時世なので来る前に必ず予約をしなければ入れないシステムとなっています。そんな遊園地でクリスマスのイルミネーションが輝き始める夜頃、matcharate君はアルバイトをしていました。

今月のmatcharate君のタスクは、予約が最も殺到している日の区間を調べることです。今、ここに $N$ 日間の予約の管理表があります。上司のError君によると、$M$ 人の予約があり、$i\ (1\le i\le M)$ 人目は $A_i$ 日目から $B_i$ 日目までの予約を受け取っていることが分かっているようです。この情報から、Error君が出した次の質問に $Q$ 回だけ答えてください。

• 予約管理表において、 $L_j$ 日目から $R_j$ 日目までに予約された1日の予約数の最大値 $K$ として、1日に $K$ 個の予約が入っている日数はいくつありますか？

入力・制約

・$2\le N,M\le 10^5$
・$1\le A_i, B_i\le N$
・$1\le Q\le \bm{3\times 10^5}$
・$1\le L_j\lt R_j\le N\ (1\le j\le Q)$

出力

$Q$ 行出力せよ。$j$ 行目には $j$ 個目の質問の答えを出力せよ。

入出力例

10 5
1 4
3 6
9 10
2 7
8 10
3
1 5
2 8
1 7

2
2
2

• $1$ 人目では $1$ 日目から $4$ 日目までの予約を
• $2$ 人目では $3$ 日目から $6$ 日目までの予約を、
• $3$ 人目では $9$ 日目から $10$ 日目までの予約を、
• $4$ 人目では $2$ 日目から $7$ 日目までの予約を、
• $5$ 人目では $8$ 日目から $10$ 日目までの予約を入れました。

最終的に管理表には $1$ 日目から順に $(1,2,3,3,2,2,1,1,2,2)$ と書かれます。ここで各要素は $k\ (1\le k\le N)$ 日目に入っている予約数を表します。

よって例えば $1$ つ目の質問において、$1$ 日目から $5$ 日目までの区間で $1$ 日の最大予約人数は $3(=K)$ 人です。$3,4$ 日目の $2$ 日間が $3(=K)$ 人だけ予約をされているので、$2$ を出力します。