在一个光滑的水平直轨道上有 $n$ 个小球。轨道可以看作是一条数轴。小球可以看作是质量相同的质点。

在开始时，小球 $i$ 位于位置 $X_i$。它的初始速度为 $V_i$，并且正朝着方向 $D_i = \pm 1$ 运动。

此外，给定一个常数 $C$。在任何时刻，小球 $i$ 的加速度 $A_i$ 和速度 $V_i$ 方向相同，并且神奇地满足方程 $A_i \cdot V_i = C$。

由于有多个小球，它们在运动过程中可能会相互碰撞。我们假设所有碰撞均为完全弹性碰撞。

有多次询问。每次询问包含两个整数 $t$ 和 $k$。你的任务是求出在开始后恰好 $t$ 秒时，所有小球中第 $k$ 小的速度。

注意，完全弹性碰撞定义为碰撞过程中没有动能损失的碰撞。

输入格式

输入的第一行包含两个整数 $n$ 和 $C$（$1 \le n \le 10^5$，$1 \le C \le 10^9$）。

接下来 $n$ 行。其中第 $i$ 行包含三个整数 $V_i$，$X_i$，$D_i$。$V_i$ 表示小球 $i$ 的初始速度（$1 \le V_i \le 10^5$），$X_i$ 表示小球 $i$ 的初始位置（$1 \le X_i \le 10^9$），$D_i$ 表示小球 $i$ 的运动方向（$D_i \in \{-1, 1\}$）。

下一行包含一个整数 $1 \le q \le 10^5$，表示询问的数量。此后 $q$ 行，每行包含两个整数 $1 \le t \le 10^9$ 和 $1 \le k \le n$。

输出格式

对于每个询问，输出单行，包含一个实数，表示绝对误差不超过 $10^{-3}$ 的答案。

样例

输入样例 1

3 7
3 3 1
3 10 -1
2 7 1
3
2 3
1 2
3 3

输出样例 1

6.083
4.796
7.141