시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

あなたは,マトリョーシカ人形を販売する店を開こうとしている.そこで,あなたは N 個のマトリョーシ カ人形を工場に注文した.これらには 1 から N までの番号が付けられている.このうち i 番目 (1 ≦ i ≦ N) のマトリョーシカ人形は,底面の直径 Ri cm で高さ Hi cm の,中が空洞の直円柱とみなすことができる.

マトリョーシカ人形は入れ子にして保管することができる.それぞれのマトリョーシカ人形は,底面の 直径と高さがともにより小さい他のマトリョーシカ人形を 1 つだけ収納することが出来る.収納されるマ トリョーシカ人形は,他のマトリョーシカ人形を収納していてもよい.

ある日,マトリョーシカ人形を注文した工場から連絡が届いた.注文した N 個のマトリョーシカ人形は すべてを一度に用意することはできないので,N 個のマトリョーシカ人形のうち底面の直径が A cm 以上で あり,高さが B cm 以下であるものすべてが事前に届くそうだ.

A, B の値は急に変更されるかもしれない.そこで,あなたは,Q 個の組 (Aj, Bj) (1 ≦ j ≦ Q) のそれぞれ に対して,事前に届くマトリョーシカ人形を入れ子にして保管したときの,どのマトリョーシカ人形にも 収納されていないマトリョーシカ人形の個数の最小値をあらかじめ求めておくことにした.

それぞれのマトリョーシカ人形の底面の直径と高さの情報と,Q 個の組 (Aj, Bj) (1 ≦ j ≦ Q) が与えら れる.それぞれの組について,事前に届くマトリョーシカ人形を入れ子にして保管したときの,どのマト リョーシカ人形にも収納されていないマトリョーシカ人形の個数の最小値を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N, Q が空白を区切りとして書かれている.これは,注文したマトリョーシカ人形 の個数が N 個であり,A, B の値の組が Q 個与えられることを表す.
  • 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,整数 Ri, Hi が空白を区切りとして書かれている.これは, i 番目のマトリョーシカ人形は,底面の直径が Ri cm で高さが Hi cm であることを表す.
  • 続く Q 行のうちの j 行目 (1 ≦ j ≦ Q) には,整数 Aj , Bj が空白を区切りとして書かれている.

출력

出力は Q 行からなる.j 行目 (1 ≦ j ≦ Q) には,組 (Aj, Bj) について,事前に届くマトリョーシカ人形を 入れ子にして保管したときの,どのマトリョーシカ人形にも収納されていないマトリョーシカ人形の個数 の最小値を出力せよ.

제한

  • 1 ≦ N ≦ 200 000.
  • 1 ≦ Q ≦ 200 000.
    1 ≦ Ri ≦ 1 000 000 000 (1 ≦ i ≦ N).
    1 ≦ Hi ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • 1 ≦ Aj ≦ 1 000 000 000 (1 ≦ j ≦ Q).
  • 1 ≦ Bj ≦ 1 000 000 000 (1 ≦ j ≦ Q).

예제 입력 1

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

예제 출력 1

0
1
2
  • (A, B) = (10, 5) のとき,底面の直径が 10 cm 以上で高さが 5 cm 以下であるマトリョーシカ人形は 1 つも存在しないので,0 を出力する.
  • (A, B) = (3, 5) のとき,底面の直径が 3 cm 以上で高さが 5 cm 以下であるマトリョーシカ人形,すなわ ち 1 番目, 7 番目のマトリョーシカ人形が届く. 7 番目のマトリョーシカ人形は 1 番目のマトリョー シカ人形の中に収納することができる.どのマトリョーシカ人形にも収納されていないマトリョーシ カ人形の個数の最小値は 1 である.
  • (A, B) = (3, 9) のとき,底面の直径が 3 cm 以上で高さが 9 cm 以下であるマトリョーシカ人形,すな わち 1 番目,2 番目,3 番目,7 番目のマトリョーシカ人形が届く.この場合, 7 番目のマトリョー シカ人形を 1 番目のマトリョーシカ人形の中に収納して,1 番目のマトリョーシカ人形を 3 番目のマ トリョーシカ人形の中に収納することができる.どのマトリョーシカ人形にも収納されていないマト リョーシカ人形の個数の最小値は 2 である.

예제 입력 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

예제 출력 2

3
1
3
5
0
2
1
3