CF167A.Wizards and Trolleybuses

In some country live wizards. They love to ride trolleybuses.

A city in this country has a trolleybus depot with n trolleybuses. Every day the trolleybuses leave the depot, one by one and go to the final station. The final station is at a distance of d meters from the depot. We know for the i-th trolleybus that it leaves at the moment of time t__i seconds, can go at a speed of no greater than v__i meters per second, and accelerate with an acceleration no greater than a meters per second squared. A trolleybus can decelerate as quickly as you want (magic!). It can change its acceleration as fast as you want, as well. Note that the maximum acceleration is the same for all trolleys.

Despite the magic the trolleys are still powered by an electric circuit and cannot overtake each other (the wires are to blame, of course). If a trolleybus catches up with another one, they go together one right after the other until they arrive at the final station. Also, the drivers are driving so as to arrive at the final station as quickly as possible.

You, as head of the trolleybuses' fans' club, are to determine for each trolley the minimum time by which it can reach the final station. At the time of arrival at the destination station the trolleybus does not necessarily have zero speed. When a trolley is leaving the depot, its speed is considered equal to zero. From the point of view of physics, the trolleybuses can be considered as material points, and also we should ignore the impact on the speed of a trolley bus by everything, except for the acceleration and deceleration provided by the engine.

在某个国家生活着一些巫师，他们酷爱乘坐无轨电车。

该国某城市有一座无轨电车停车场，内有 $n$ 辆无轨电车。每天，这些无轨电车依次从停车场出发，驶向终点站。终点站距停车场 $d$ 米。已知第 $i$ 辆无轨电车于时刻 $t_i$（单位：秒）出发，其最大行驶速度为 $v_i$ 米/秒，最大加速度为 $a$ 米/秒²。无轨电车可以以任意快的速度减速（毕竟这是魔法！），也可以以任意快的速度改变加速度。注意：所有无轨电车的最大加速度均为相同的常数 $a$。

尽管拥有魔法，这些无轨电车仍依靠电路供电，因此彼此之间不能超车（当然，这要归咎于架空电线）。若一辆无轨电车追上前方另一辆，则它们将紧随其后、以相同运动状态一同行驶，直至抵达终点站。此外，所有司机均以尽可能早地抵达终点站为目标进行驾驶。

作为无轨电车爱好者俱乐部主席，你需要为每辆无轨电车计算其抵达终点站所需的最短时间。到达终点站时，无轨电车的速度未必为零。无轨电车刚离开停车场时，其初速度视为零。从物理学角度，可将无轨电车视为质点；除发动机提供的加速度与减速度外，其余一切因素对无轨电车速度的影响均忽略不计。

The first input line contains three space-separated integers n, a, d (1 ≤ n ≤ 105, 1 ≤ a, d ≤ 106) — the number of trolleybuses, their maximum acceleration and the distance from the depot to the final station, correspondingly.

Next n lines contain pairs of integers t__i v__i (0 ≤ _t_1 < _t_2... < t__n - 1 < t__n ≤ 106, 1 ≤ v__i ≤ 106) — the time when the i-th trolleybus leaves the depot and its maximum speed, correspondingly. The numbers in the lines are separated by spaces.

第一行输入包含三个以空格分隔的整数 $n$、$a$、$d$（$1 \leq n \leq 10^5$，$1 \leq a, d \leq 10^6$），分别表示无轨电车的数量、其最大加速度以及从车辆段到终点站的距离。

接下来的 $n$ 行每行包含一对整数 $t_i$、$v_i$（$0 \leq t_1 < t_2 < \cdots < t_{n-1} < t_n \leq 10^6$，$1 \leq v_i \leq 10^6$），分别表示第 $i$ 辆无轨电车离开车辆段的时刻及其最大速度。每行中的数字以空格分隔。

For each trolleybus print a single line the time it arrives to the final station. Print the times for the trolleybuses in the order in which the trolleybuses are given in the input. The answer will be accepted if the absolute or relative error doesn't exceed 10 - 4.

对于每辆无轨电车，输出一行，表示其到达终点站的时间。按输入中给出无轨电车的顺序输出各辆无轨电车的到达时间。若绝对误差或相对误差不超过 $10^{-4}$，则答案视为正确。

In the first sample the second trolleybus will catch up with the first one, that will happen at distance 510.5 meters from the depot. The trolleybuses will go the remaining 9489.5 meters together at speed 10 meters per second. As a result, both trolleybuses will arrive to the final station by the moment of time 1000.5 seconds. The third trolleybus will not catch up with them. It will arrive to the final station by the moment of time 11000.05 seconds.

在第一个样例中，第二辆无轨电车将追上第一辆无轨电车，追及点距车辆段 $510.5$ 米。此后，两辆无轨电车将以 $10$ 米/秒的速度共同行驶剩余的 $9489.5$ 米。因此，两辆无轨电车均将在时刻 $1000.5$ 秒到达终点站。第三辆无轨电车不会追上它们，它将在时刻 $11000.05$ 秒到达终点站。