17704번 - Matryoshka 서브태스크다국어

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

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

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

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

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

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

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

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

• 1 ≦ N ≦ 200 000．
• 1 ≦ Q ≦ 200 000． 1 ≦ R_i ≦ 1 000 000 000 (1 ≦ i ≦ N)． 1 ≦ H_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ A_j ≦ 1 000 000 000 (1 ≦ j ≦ Q)．
• 1 ≦ B_j ≦ 1 000 000 000 (1 ≦ j ≦ Q)．