题目描述

本题译自 CCC 2014 Stage2 Day2 T3「Gates」

你现在正在一个有 $G$ 个登机口的机场里，登机口由 $1$ 到 $G$ 编号。第 $i$ 个登机口离机场入口有 $100i$ 米远。

同时机场里还有 $N$ 个水平自动扶梯，第 $i$ 个水平自动扶梯单向地以每分钟 $S_i$ 米从登机口 $A_i$ 到另外一个登机口 $B_i$。在走道的任意一个点，相同方向（朝着机场入口或者远离机场入口）的水平自动扶梯至多只有一条在移动。然而，可能有两条水平自动扶梯从同一登机口出发且同向同终点。

你可以以 $W$ 米每分钟的速度沿着走道走，当你在一个水平自动扶梯的起点时，你可以选择走上去，如果你选择了，它就会把你送到它的终点。即使该自动扶梯经过某个非起点或终点的位置，你不能在该位置离开或开始乘坐该水平自动扶梯。当你在水平自动扶梯 $i$ 上时，你的速度为 $W+S_i$ 米每分钟。

当你在等你晚点的飞机时，为了找乐子，你问了自己 $Q$ 个问题，第 $i$ 个问题为寻找从登机口 $X_i$ 到登机口 $Y_i$ 的最短时间。为了使问题更加有趣，你决定不正确回答问题不登机，因此你最好不要把事情搞砸了！

输入格式

第一行四个整数 $G,W,N,Q$，分别表示登机口数量、走路速度、水平自动扶梯数量、询问数量。

接下来 $N$ 行每行三个整数 $A_i,B_i,S_i$，表示水平自动扶梯 $i$ 的起点和终点以及水平自动扶梯的速度。其中 $A_i\neq B_i,$ $1\le i \le N$。

接下来 $Q$ 行每行两个整数 $X_i,Y_i(1\le i \le Q)$，表示起始登机口和目标登机口。

输出格式

输出 $Q$ 行，每行一个实数，表示从登机口 $X_i$ 到登机口 $Y_i$ 最少要多少分钟，其中 $1\le i\le Q$。

你的结果的正确性将以如下方式进行判断：如果 $D$ 是标准答案，那么在范围 $[D\cdot (1-10^{-4}),D\cdot (1+10^{-4})]$ 内的结果都被认为是正确的。

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

10.0
4.0
24.0
6.25

数据范围与提示

对于某些数据，$G,N,Q$ 中至少一个值是较小的。这个信息也许有用，也许没用。

对于 $100\%$ 的数据，$1\le G\le 10^9,$ $1\le N\le 10^5,$ $1\le Q\le 10^5,$ $1\le A_i,B_i,X_i,Y_i\le G,$ $1\le W,S_i\le 10^9$。其中，对于 $X_i,Y_i$，$1\le i \le Q$；对于 $A_i,B_i,S_i$，$1\le i\le G$。