题目描述

禁止超越所有车辆，但低速车辆、畜力车、轻便摩托车和无边车的两轮摩托车除外。

今晚超级英雄“瓦特曼”计划去看望他亲爱的祖母。由于他没有及时续办飞行执照，只能驾驶瓦特车穿越哥谭的堵车路段。他必须尽快办完事到达祖母家，毕竟馅饼已经快凉了！

瓦特曼的一段路要在一条双向单车道道路上行驶。本道路可以看成一条无限长直线。两条车道上一共有 $N$ 辆车。已知第 $i$ 辆车的初始位置 $p_i$ 和恒定速度 $v_i$。因此，在时刻 $t$，第 $i$ 辆车的坐标为

但该公式只在这辆车尚未追上同向更慢车辆时成立。由于该路段禁止超车，一辆更快的车追上同向更慢的车后，必须降低速度，并在余下时间一直跟在它后面行驶。

瓦特曼自认为已经足够经常考虑普通人的命运，所以今天可以稍微无视一些交通规则。他计划借用对向车道超车，但作为正常超级英雄，他仍想避免危险。因此，只有当对向最近车辆与他之间至少有安全距离 $d$ 时，他才会超车。

瓦特曼的计划经常变化：他还不知道什么时候出发、选择什么路线、驾驶哪辆瓦特车，也不知道会把多远的距离视为安全。因此，他请你对 $Q$ 组不同参数计算这段道路上的最短通行时间。

车长忽略不计，所有车辆都视为直线上的点。更快车辆一旦追上更慢车辆，就在距离 $0$ 处跟随。若在瓦特车行驶方向上，对向车道不存在距离小于 $d$ 的迎面车辆，则瓦特曼可以超车。对向车道上与瓦特车坐标相同的车辆不阻碍超车。超车一旦开始，立即完成，并立刻回到原车道。

由于浮点计算存在误差，评测保证瓦特曼不会需要基于非常接近的数值比较来决定是否超车。也就是说，若将 $d$ 任意增减 $0 \le eps \le 0.001$，正确答案不会改变。

输入格式

第一行包含两个整数 $N,Q$，表示道路上的车辆数量和瓦特曼的查询数。

接下来 $N$ 行，每行包含两个整数 $p_i,v_i$，表示第 $i$ 辆车的初始位置和初始速度。速度 $v_i>0$ 的车辆在一条车道上行驶，$v_i<0$ 的车辆在另一条车道上行驶。保证所有 $p_i$ 互不相同。

接下来 $Q$ 行，每行包含五个整数 $t_i,a_i,b_i,v_i,d_i$，分别表示瓦特曼计划驶入道路的时间、起点、终点、瓦特车最大速度，以及他认为安全的最小对向距离。

保证 $a_i\ne b_i$，且在时刻 $t_i$，除瓦特车外没有任何车辆位于坐标 $a_i$。同时保证 $v_i>0$ 当且仅当 $b_i>a_i$。

输出格式

对于每个查询，输出一行实数，表示瓦特曼从起点到终点的最短时间。

若你的答案为 $A$，标准答案为 $B$，当

时，答案会被判为正确。

数据范围

$0 \le N \le 10000$，$1 \le Q \le 5000$。
$|p_i| \le 100000$，$|v_i| \le 100000$，$v_i\ne 0$。
$|a_i|,|b_i| \le 100000$，$0<|v_i|<100000$，$0 \le t_i,d_i \le 100000$。

样例

样例 1

1 1
10 10
0 0 100 20 10

5.0000000000

样例 2

2 1
20 5
200 -10
4 10 100 10 40

10.0000000000

样例 3

6 3
20 1
10 10
5 100
80 -1
90 -10
95 -100
0 0 100 10 1
0 0 100 10 100
0 100 0 -10 100

10.0000000000
35.0000000000
35.0000000000

样例解释

第一个样例中，没有车辆会阻碍瓦特曼超车，他能以最大速度行驶并用最短可能时间到达。

第二个样例中，瓦特曼会在坐标 $70$ 处追上第一辆车，此时第二辆车位于坐标 $100$，已经太近，无法超车。瓦特曼必须以较慢速度行驶 $2$ 秒，直到第二辆车经过。

评分说明