20477번 - Чай 스페셜 저지다국어

Члены жюри Всероссийской командной олимпиады школьников по программированию очень любят пить чай. Но, к сожалению, в их распоряжении всего один чайник, имеющий объем $v$~мл. Работа жюри хорошо отлажена, поэтому точно известно, кто и когда отправиться пить чай, и сколько воды ему для этого нужно.

Рассмотрим действия, предпринимаемые членами жюри для получения желанного напитка.

Когда человек из жюри подходит к чайнику, то если никого больше у чайника нет, он смотрит, достаточно ли в чайнике воды. Если в чайнике не хватает воды для этого человека, то он доливает в чайник воды до полного объема в $v$ мл. Если же воды достаточно, то вода в чайник не доливается. После этого чайник включается и доводит воду до температуры 100 градусов. После этого член жюри наливает себе необходимый объем кипятка для заварки чая и отходит от чайника.

Если в момент прихода к чайнику член жюри обнаруживает других людей, ожидающих кипятка, то он становится в очередь и дожидается, пока все предыдущие люди выполнят свои действия с чайником.

Температура кипения воды составляет 100 градусов Цельсия. Мощность чайника составляет $N$, что означает, что если в чайнике $x$ мл воды, то температура воды в чайнике изменяется по формуле $T(t) = T_0 + \frac{Nt}{x}$, где $T_0$ --- температура воды в момент включения чайника, а $t$ --- время в секундах, прошедшее с момента включения чайника. Когда температура воды достигает 100 градусов, чайник автоматически выключается.

Когда чайник выключен, вода в нем начинает остывать. Вне зависимости от количества жидкости в чайнике, температура воды падает со скоростью $k$ градусов в секунду. Когда вода достигает комнатной температуры в 20 градусов, остывание прекращается.

Заливаемая в чайник вода имеет комнатную температуру 20 градусов. При доливании воды в чайник температура воды усредняется, а именно, если в чайнике было $w$ мл воды температуры $T$, то температура воды в чайнике после его заполнения станет $\frac{wT + 20(v-w)}{v}$.

Известны времена, когда члены жюри идут пить чай, а также количество кипятка им необходимое. Требуется для каждого члена жюри вывести в какой момент он начнет пить чай. Считается, что разливают воду по чашкам и заваривают чай члены жюри моментально, при этом всегда наливая себе ровно необходимый им объем. Изначально чайник пуст.

Первая строка входного файла содержит четыре целых числа $m$, $v$, $N$ и $k$ ($1 \le m \le 100\,000$, $1 \le v, N, k \le 1000$) --- количество членов жюри, пьющих чай, объем чайника в мл, мощность чайника и скорость остывания воды в чайнике. Далее следуют $m$ строк --- описания людей, пьющих чай. В каждой строке два целых числа $t_i$ и $a_i$ ($1 \le t_i \le 10^6$; $1 \le a_i \le v$) --- время в секундах от начала олимпиады, когда член жюри отправиться пить чай, и необходимый ему объем воды в мл. Никакие два члена жюри не отправляются пить чай одновременно.

В выходной файл выведите $m$ строк по одному числу в каждой --- время в секундах от начала олимпиады, когда соответствующий член жюри начнет пить чай. Ответ должен иметь абсолютную или относительную погрешность не более $10^{-7}$.