Задача U. Честная очередь

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В одном из травмпунктов города Владивостока прием пациентов осуществляется по следующим правилам:

Обычно во все кабинеты имеется очередь. Некоторые люди, если им надо попасть сразу в два кабинета, занимают две очереди, а остальные — сначала проходят рентген, а потом занимают очередь в кабинет вторичного приема.

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

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

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

Входной файл содержит числа N P Q, за которыми следуют N наборов чисел.

В каждом наборе первое число означает время прихода пациента ti, измеренное в минутах с начала приема. Далее идет число, обозначающее, в какие кабинеты требуется попасть i-му пациенту — 1, если сперва в кабинет рентгенографии и 2, если сразу в кабинет вторичного приема.

Для пациентов, которым требуется сделать снимок, далее идет число 1 или 2, обозначающее, займет ли пациент он место в одной очереди или в двух.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ P, Q ≤ 15, 0 ≤ ti ≤ 1000, ti < ti + 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5 10
0 1 1
5 1 1
15 20
2
2 5 5
0 1 1
5 2  
15 5
3
3 5 10 0 1 2 2 2 3 2
32 10 19

0.079s 0.011s 13