在广袤的泡泡王国（Bubble Kingdom）中，最先进的交通方式是泡泡传送带（Bubble Belt）系统：这是一个由 $N$ 条神奇的传送带组成的网络，它们可以瞬间将物体在空中传送。王国的工程师们早已完善了利用这些传送带在悬浮于地面高处的各种平台之间运输货物和人员的技术。

然而，一个新的挑战出现了：古老的泡泡杯（Bubble Cup）比赛！共有 $Q$ 位参赛者，他们的任务是寻找将魔法球从悬浮在地面上方的平台落到地面本身的最快方法。每位参赛者必须仔细规划如何优化现有泡泡传送带的使用，并用陈旧、较慢的传送带来扩充系统，以最大程度地减少魔法球落地所需的时间。

以下是泡泡传送带系统的工作原理：

• 泡泡传送带是水平的线段，位于地面上方的不同高度，平行于 $x$ 轴。每条传送带在 $x$ 轴上的两个点之间延伸（但不包括这两个端点本身），如果魔法球落到传送带上，它将被传送到其最左端或最右端。
• 现有的泡泡传送带互不重叠，但它们可以共享相同的端点。如果两条泡泡传送带共享同一个端点，魔法球将在该共享端点处从两条泡泡传送带之间穿过并下落。
• 有些传送带较快，有些较慢。每条传送带都有一个配速（速度的倒数），单位为秒/米。
• 地面层位于 $y = 0$，而泡泡传送带漂浮在正的 $y$ 坐标处。
• 一旦魔法球离开传送带，它就会进入自由落体状态，并以每米 $1$ 秒的配速下落。魔法球在传送带上移动时可能具有的任何水平动量都会瞬间消失，魔法球将直接垂直下落。
• 作为参赛者，你可以使用无限条任意尺寸的陈旧泡泡传送带，它们以每 $K$ 秒 $1$ 米的固定配速移动（即配速为 $K$ 秒/米）。这些传送带可以放置在任何实数 $x$ 和 $y$ 坐标处，可以具有任意长度，可以向任意方向移动，你可以策略性地使用它们来加速魔法球的下落。
• 保证任何已有的泡泡传送带都比你可以放置的陈旧泡泡传送带更快。
• 你放置的新泡泡传送带不能与任何已有或其他新放置的泡泡传送带重叠，但可以共享端点。由于泡泡传送带没有厚度，它们在垂直方向上可以无限接近。

目标是什么？每位参赛者都会得到一个魔法球的初始位置 $(X, Y)$，他们的任务是计算出魔法球从空中给定点落到地面所需的最快时间，这需要明智地同时使用现有传送带和新传送带。每位参赛者可以独立于对手放置新传送带。换句话说，新放置的传送带在下一位参赛者开始其回合之前会消失。

输入格式

第一行包含三个整数 $N$、$Q$ 和 $K$：分别表示初始放置的泡泡传送带数量、参赛者数量以及陈旧泡泡传送带的配速（单位为秒/米）($1 \le N, Q \le 2 \cdot 10^5$, $5 \le K \le 10^6$)。

接下来的 $N$ 行，每行包含四个整数 $Y$、$X_1$、$X_2$ 和 $T$：分别表示传送带距离地面的高度、传送带在 $x$ 轴上的左右端点，以及传送带移动魔法球一米所需的时间（$1 \le Y \le 10^6$, $1 \le X_1 < X_2 \le 2 \cdot 10^5$, $-K < T < K, T \ne 0$）。负的 $T$ 表示传送带向左移动，正的 $T$ 表示向右移动。这 $N$ 条已有的泡泡传送带不会重叠，但它们可以拥有相同的端点。

接下来的 $Q$ 行，每行包含两个值 $X$ 和 $Y$：表示魔法球的初始 $x$ 坐标（为一个整数）和初始 $y$ 坐标（为一个整数加上 $0.5$，换句话说，魔法球从两层传送带之间开始下落）。限制条件为：$1 \le X \le 2 \cdot 10^5$, $0.5 \le Y \le 1\,000\,000.5$。

输出格式

对于每位参赛者，输出一个实数：魔法球从起点 $(X, Y)$ 落到地面 $y = 0$ 所需的最短时间。如果你的答案的绝对或相对误差不超过 $10^{-12}$，则将被视为正确。

样例

输入样例 1

5 3 100
1 1 100 99
10 1 50 -1
3 1000 1005 -1
3 1005 1008 -1
2 1000 1100 99
40 1.5
55 10.5
1007 3.5

输出样例 1

3901.5
559.5
208.5

说明

在样例中，三位参赛者可以使用以下构造方式（注意，这些并不是唯一的最佳方案）：

• 第一位参赛者可以在从点 $(1, 1.1)$ 到 $(41, 1.1)$ 之间放置一条向左移动（配速为 $K$）的额外泡泡传送带。这将使魔法球落到这条新传送带上，沿着它从 $X = 40$ 移动到 $X = 1$，然后直接落到地面，总耗时为 $0.4 + (40 - 1) \cdot K + 1.1 = 3901.5$ 秒。
• 第二位参赛者可以在从点 $(49.999\dots, 10.1)$ 到 $(56, 10.1)$ 之间放置一条向左移动（配速为 $K$）的新泡泡传送带。这将使魔法球落到这条新传送带上，沿着它从 $X = 55$ 移动到 $X = 49.999\dots$，然后落到 $Y = 10$ 处的传送带上。这条传送带将以配速 $1$ 将魔法球从 $X = 49.999\dots$ 移动到 $X = 1$，之后它将落到地面。总时间为 $0.4 + (55 - 49.999\dots) \cdot K + 0.1 + (49.999\dots - 1) \cdot 1 + 10 = 559.5$ 秒。
• 第三位参赛者希望避免魔法球落到 $Y = 2$ 处的泡泡传送带上，因为那是一条非常长且慢的传送带，所以他应该使用 $Y = 3$ 处的泡泡传送带和新放置的泡泡传送带将魔法球移动到 $X = 1000$。问题在于他不能同时使用 $Y = 3$ 处的两条泡泡传送带，因为泡泡传送带不能重叠，且魔法球会从 $X = 1005$ 处的缝隙中掉下去。他最好的策略是在 $Y = 3.1$ 处，从 $X = 1004.999\dots$ 到 $X = 1008$ 放置一条向左移动的新泡泡传送带，让魔法球从 $X = 1005$ 落到 $Y = 3$ 处的泡泡传送带上，移动到 $X = 1000$，沿着它移动，然后从 $X = 1000$ 处落到地面。这将总共花费 $0.4 + (1007 - 1004.999\dots) \cdot K + 0.1 + (1004.999\dots - 1000) \cdot 1 + 3 = 208.5$ 秒。