Беси посетила доек за последние дней. Однако ей трудно запомнить, когда она посещала каждую дойку.
Для каждой дойки она знает, что та случилась не ранее дня . К тому же Беси имеет заметок, каждая из которых описывается тройкой , указывающих что дойка случилась как минимум через дней после дойки .
Помогите Беси вычислить наиболее ранние возможные даты доек. Гарантируется, что все заметки Беси корректны, то есть существует решение (все числа в интервале ), удовлетворяющее всем заметкам.
Первая строка содержит числа , , . Следующая строка содержит целых чисел , каждое из которых находится в интервале .
Следующие строк содержат по три целых числа указывающих, что дойка случилась не менее чем через дней после дойки . Для каждой строки, и принадлежат интервалу , а принадлежат интервалу .
Выведите строк, определяющих наиболее ранние возможные даты доек.
Второй сеанс произошел по крайней мере через пять дней после первого сеанса, поэтому он не мог произойти раньше дня номер . Четвертый сеанс произошел по крайней мере через два дня после второго сеанса, поэтому он не мог произойти раньше дня номер .