Задача H. Чай ≡

Условие

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

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

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

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

Температура кипения воды составляет 100 градусов Цельсия. Мощность чайника составляет N, что означает, что если в чайнике x мл воды, то температура воды в чайнике изменяется по формуле T(t) = T₀ + Ntx, где T₀ — температура воды в момент включения чайника, а t — время в секундах, прошедшее с момента включения чайника. Когда температура воды достигает 100 градусов, чайник автоматически выключается.

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

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

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

Формат входного файла

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

Формат выходного файла

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

Примеры тестов

3 1000 200 1
1 500
501 300
551 300

401.0
701.0
1021.0