Задача Лифт

Описание

В N-этажном здании имеется лифт со следующей схемой работы:

1. при нажатии кнопки вызова лифта на каком-нибудь этаже, номер этого этажа добавляется в очередь вызовов.
2. если в момент вызова лифт стоит, и движение еще не происходило, или с момента остановки прошло не менее A секунд, то лифт начинает двигаться по направлению к этажу, с которого он вызван. Этот вызов будет считаться текущим;
3. расстояние между двумя последовательными этажами лифт проходит за B секунд;
4. если лифт проезжает этаж, номер которого есть в очереди вызовов, он мгновенно останавливается (этот момент будем считать моментом обработки соответствующего вызова);
5. после остановки один экземпляр номера этажа удаляется из очереди вызовов, лифт стоит на месте в течение A секунд (время на высадку и посадку пассажиров), а затем продолжает движение к этажу текущего вызова;
6. если лифт остановился на этаже текущего вызова, то текущим вызовом становится наиболее ранний необработанный вызов из очереди вызовов;
7. если в момент начала движения приходит вызов с текущего этажа, то лифт опять останавливается.

Требуется определить моменты времени, в которые будут обработаны вызовы. Изначально лифт стоит на первом этаже.

Формат входных данных

На первой строке входного файла даны 4 целых числа: N - количество этажей, M - количество вызовов, A - количество секунд на высадку и посадку пассажиров, B - время проезда лифта между двумя этажами (1 <= N, M <= 10 ⁵ , 1 <= A, B <= 100). Следующие M строк содержат по два целых числа:
T _i - количество секунд, прошедших с момента времени 0 до i-го вызова, F _i - этаж, с которого был сделан i-й вызов (1 <= T _i <= 10 ⁵ , 1 <= F _i <= N, T _i <= T _i+1 для всех i от 1 до M - 1). В случае, когда T _i = T _i+1 i-й вызов считается сделанным раньше i+1-го. Числа на каждой строке разделены пробелами.

Формат выходных данных

Выведите моменты обработки вызовов (количество секунд, прошедших от момента времени 0 до обработки) в порядке, соответствующем порядку появления вызовов во входном файле, по одному на строке.