坐标平面中有 $$$N$$$ 个气泡。气泡非常小,可以假设每个气泡都是一个点 $$$(X_i, Y_i)$$$。
$$$Q$$$ 泡泡杯决赛入围者计划与泡泡一起玩。每位决赛选手都会链接使用无限长的泡泡杯棒来弹出一些泡泡。第 $$$i$$$ 决赛入围者希望将棍子放在矢量 $$$(dxi, dyi)$$$ 的方向上,并玩以下游戏,直到 $$$K_i$$$ 气泡被弹出。游戏开始时,决赛选手将棍子放在矢量 $$$(dx_i, dy_i)$$$ 的方向上,并将其从无穷远向左扫过,直到碰到某个气泡,气泡立即弹出。保证这一步只会击中一个气泡。之后,决赛选手开始以逆时针方向旋转棒,旋转中心位于上一个气泡被弹出的位置。当下一个气泡被击中时,它立即破裂并成为新的旋转中心。该过程持续进行,直到 $$$K_i$$$ 气泡被弹出。保证这个过程中木棍不会同时击中两个气泡。
对于每个决赛入围者,找出最后会弹出的气泡。请注意,每个游戏都以所有 $$$N$$$ 气泡的配置开始,因此游戏不依赖于之前的游戏。
输入
第一行包含一个整数 $$$N$$$ — 气泡的数量。 ($$$1 \leq N \leq 10^5$$$)
接下来的 $$$N$$$ 行包含两个整数。第 $$$i$$$ 行包含整数 $$$X_i$$$ 和 $$$Y_i$$$ — 第 $$$i$$$ 气泡的坐标。 ($$$-10^9 \leq X_i, Y_i \leq 10^9$$$, $$$(X_i, Y_i) \neq (X_j, Y_j)$$$ 对于 $$$i \neq j$$$)
下一行包含一个整数 $$$Q$$$ — 愿意玩泡泡的决赛入围者的数量。 ($$$1 \leq Q \leq 10^5$$$)
接下来的 Q 行每行包含 3 个整数。第 $$$i$$$ 行包含整数 $$$dx_i$$$、$$$dy_i$$$ 和 $$$K_i$$$。 ($$$-10^9 \leq dx_i, dy_i \leq 10^9$$$, $$$1 \leq K_i \leq N$$$)
输出
对于每个 $$$Q$$$ 决赛入围者,在单独的行中打印最后弹出的气泡的索引。
示例
输入 #1
4 0 0 1 0 0 1 1 1 2 1 -1 3 -1 1 4
输出 #1
4 2
输入 #2
4 1 1 2 2 7 1 1 7 3 2 2 1 1 -5 4 -6 5 3
输出 #2
3 2 3
注意
有两名决赛入围者愿意玩泡泡。如果第一名决赛入围者玩气泡,则坐标 (0, 0)、(1, 0) 和 (1, 1) 处的气泡将按顺序弹出。他们的索引分别是 1、2 和 4,所以答案是 4。如果第二个决赛入围者玩气泡,那么坐标 (1, 1)、(0, 1)、(0, 0) 和 (1, 0) 处的气泡将按顺序弹出,所以答案是 2。
可视化:链接。