E - 歩くNPCたち（Walking NPCs） Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

joisinoお姉ちゃんの次の仕事は、ゲーム中のNPCの動きの確認である。
左右に無限に伸びる直線上に、N人のNPCが立っている。
また彼らは、ある一定の速度で決まった方向へ歩いている。
直線上の一点を基準に、そこから右にx進んだ場所は、座標xで表される。
ゲーム開始時、i番目のNPCは、座標X_iに立っており、また、１秒ごとに、V_iだけ移動する。
より正確に言えば、ゲーム開始からt秒後に、i番目のNPCは、座標X_i+V_i×tの位置にいる。
2人以上のNPCが、同時に同じ位置にいるかもしれない。
これらのNPCの動きがゲームの仕様を満たしているかを確認するために、Q個の質問に答えなくてはならない。
i番目の質問は、ゲーム開始からT_i秒後に、座標L_iと座標R_iの間にNPCは何人いるか、というものである。
なお、座標L_iや座標R_iにいるNPCも、座標L_iと座標R_iの間にいるとみなす。
joisinoお姉ちゃんの仕事は、これらの質問すべてに答えるプログラムを作ることである。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 V_1
X_2 V_2
:
X_N V_N
Q
T_1 L_1 R_1
T_2 L_2 R_2
:
T_Q L_Q R_Q
  • 1行目には、NPCの数を表す整数N(1 ≦ N ≦ 10^5)が与えられる。
  • 続くN行のうちi行目には、i番目のNPCの、初期位置X_i(0≦X_i≦10^5)と、符号付きの移動速度V_i(-10^5≦V_i≦10^5)が与えられる。
  • 次の１行には、質問の個数を表す整数Q(1≦Q≦10^5)が与えられる。
  • 続くQ行のうちi行目には、質問の内容を示す整数T_i(0≦T_i≦10^5),L_i(0≦L_i≦10^5),R_i(L_i≦R_i≦10^5)が与えられる。

出力

出力はQ行からなる。
i行目には、i番目の質問に対する答えを出力せよ。

入力例1

3
4 1
8 -3
1 2
4
1 3 4
3 0 10
2 2 6
0 1 5

出力例1

1
2
3
2

0～3秒後の、NPCの位置は、以下の図の通りである。

入力例2

4
0 50000
100000 -50000
0 2
100000 -3
6
0 50000 50000
1 50000 50000
2 50000 50000
20000 40000 40000
20001 39998 40001
20001 39997 40002

出力例2

0
2
0
2
0
2

入力例3

10
67812 -965
1766 93025
25587 -3294
14569 22
8830 203
50857 7
23407 -836
82660 80780
89781 1
86061 -1
10
97289 65405 94453
49386 73492 97497
75412 82840 94438
93076 43725 95471
18439 76630 93787
373 51319 92018
65554 30886 93533
66039 14298 95837
68359 90674 98196
31448 31879 98393

出力例3

0
0
0
0
0
4
0
1
0
1