A. Волшебники и троллейбусы
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В некоторой стране живут волшебники. Они любят ездить на троллейбусах.

В одном городе этой страны есть троллейбусное депо с n троллейбусами. Каждый день троллейбусы выезжают из депо один за другим и едут до конечной станции. Конечная станция находится на расстоянии d метров от депо. Про i-ый троллейбус известно, что он выезжает в момент времени ti секунд, может ехать со скоростью не более vi метров в секунду и ускоряться с ускорением, не превосходящем a метров в секунду за секунду. Замедляться троллейбус может сколь угодно быстро (магия!). Менять свое ускорение троллейбус может также сколь угодно быстро. Обратите внимание, что максимальное ускорение у всех троллейбусов одинаковое.

Несмотря на волшебство, троллейбусы все еще питаются от электрической цепи и не могут обгонять друг друга (во всем виноваты, конечно же, провода). Если один троллейбус догоняет другой, то они едут вплотную друг за другом, пока не приедут на конечную станцию. При этом водители едут так, чтобы приехать на конечную станцию как можно быстрее.

Вам, как главе клуба любителей троллейбусов, предстоит определить для каждого троллейбуса минимальное время, к которому он может доехать до конечной станции. Во время приезда на конечную станцию не обязательно иметь нулевую скорость. При выезде из депо скорость троллейбуса считается равной нулю. С точки зрения физики, троллейбусы можно считать материальными точками, а также следует пренебречь воздействием на скорость троллейбуса всего, кроме ускорения и замедления, обеспечиваемого двигателем.

Входные данные

В первой строке входных данных записаны три целых числа через пробел n, a, d (1 ≤ n ≤ 105, 1 ≤ a, d ≤ 106) — количество троллейбусов, максимальное ускорение троллейбусов и расстояние от депо до конечной станции, соответственно.

В следующих n строках записаны пары целых чисел ti vi (0 ≤ t1 < t2... < tn - 1 < tn ≤ 106, 1 ≤ vi ≤ 106) — время отправления из депо i-го троллейбуса и его максимальная скорость, соответственно. Числа в строках разделяются пробелами.

Выходные данные

Для каждого троллейбуса выведите время приезда на конечную станцию в отдельной строке. Времена для троллейбусов выводите в порядке задания троллейбусов во входном файле. Ответ будет засчитан, если абсолютная или относительная погрешность не превосходит 10 - 4.

Примеры
Входные данные
3 10 10000
0 10
5 11
1000 1
Выходные данные
1000.5000000000
1000.5000000000
11000.0500000000
Входные данные
1 2 26
28 29
Выходные данные
33.0990195136
Примечание

В первом примере второй троллейбус догонит первый, это произойдет на расстоянии 510.5 метров от депо. Оставшиеся 9489.5 метров они проедут вместе со скоростью 10 метров в секунду. В итоге оба троллейбуса прибудут на конечную станцию к моменту времени 1000.5 секунд. Третий троллейбус их не догонит. Он приедет на конечную станцию к моменту времени 11000.05 секунд.