問題文
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)。 表示
- 下一步1行表示问题的数量(整数)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