你正身处机场的走廊中，走廊里按顺序排列着 $G$ ($1 \le G \le 10^9$) 个登机口，编号为 $1$ 到 $G$。登机口 $i$ 的入口距离走廊起点的距离为 $100 \cdot i$ 米。

这里还有 $N$ ($0 \le N \le 10^5$) 条自动步道。第 $i$ 条自动步道单向运行，从登机口 $A_i$ ($1 \le A_i \le G$) 的入口到另一个不同的登机口 $B_i$ ($1 \le B_i \le G$) 的入口，运行速度为 $S_i$ ($1 \le S_i \le 10^9$) 米/分钟。在走廊的任意一点，每个方向（朝向走廊起点或远离走廊起点）上最多只有一条自动步道在运行。然而，一条自动步道的起点可能会与另一条朝相同方向运行的自动步道的终点位于同一个登机口。

你可以以 $W$ ($1 \le W \le 10^9$) 米/分钟的速度在走廊上沿任一方向步行。此外，当处于某条自动步道的起点时，你可以选择走上该步道，此时它将直接把你送到它的终点——你不能在其中途上行或下行。在第 $i$ 条自动步道上时，你的移动速度将为 $W + S_i$ 米/分钟。

为了在等待（理所当然延误了的）航班时消磨时间，你给自己提出了 $Q$ ($1 \le Q \le 10^5$) 个询问。第 $i$ 个询问需要求出从登机口 $X_i$ ($1 \le X_i \le G$) 到登机口 $Y_i$ ($1 \le Y_i \le G$) 所需的最短时间。为了让事情更有趣，你决定除非能正确回答所有这些询问，否则就不登机——所以你最好不要搞砸了！

输入格式

第一行包含四个整数：登机口数量 $G$ ($1 \le G \le 10^9$)；步行速度 $W$ ($1 \le W \le 10^9$)；自动步道数量 $N$ ($0 \le N \le 10^5$)；以及询问数量 $Q$ ($1 \le Q \le 10^5$)。

接下来的 $N$ 行，每行包含三个整数，描述第 $i$ 条自动步道（$i = 1..N$）：起点登机口 $A_i$ ($1 \le A_i \le G$)；终点登机口 $B_i$ ($1 \le B_i \le G$)；速度 $S_i$ ($1 \le S_i \le 10^9$)。注意，对于任意 $i$，都有 $A_i \neq B_i$。

接下来的 $Q$ 行，每行包含两个整数，描述第 $i$ 个询问（$i = 1..Q$）：起点登机口 $X_i$ ($1 \le X_i \le G$)；以及终点登机口 $Y_i$ ($1 \le Y_i \le G$)。

你可以认为，对于某些测试用例，至少有一些 $G$、$N$ 和 $Q$ 的值较小。这一信息可能会有所帮助，也可能没有。

输出格式

输出共 $Q$ 行，每行包含一个实数，表示从登机口 $X_i$ 旅行到登机口 $Y_i$ 所需的最短时间（以分钟为单位），其中 $i = 1..Q$。如果输出的答案与正确答案的相对误差在 $10^{-4}$ 以内，则判定为正确：也就是说，如果正确答案为 $D$，则处于区间 $[D \cdot (1 - 10^{-4}), D \cdot (1 + 10^{-4})]$ 内的值都将被判定为正确。

样例

样例输入 1

6 10 3 4
2 3 15
4 2 150
3 6 290
3 2
2 3
1 4
4 6

样例输出 1

10.0
4.0
24.0
6.25

说明

对于第一个询问，你只需从登机口 3 步行到登机口 2，以 10 米/分钟的速度移动 100 米。

对于第二个询问，你应该立即登上从登机口 2 到登机口 3 的自动步道，以 $10 + 15 = 25$ 米/分钟的速度移动 100 米。

对于第三个询问，你应该步行到登机口 2（耗时 10 分钟），然后像之前一样乘坐自动步道（耗时 4 分钟），接着步行到登机口 4（耗时 10 分钟）。

最后，对于第四个询问，你应该乘坐从登机口 4 到登机口 2 的自动步道（耗时 1.25 分钟），然后乘坐从登机口 2 到登机口 3 的自动步道（耗时 4 分钟），最后乘坐从登机口 3 到登机口 6 的自动步道（耗时 1 分钟）。