Хронология событий
Хронология событий
Беси посетила n доек за последние m дней. Однако ей трудно запомнить, когда она посещала каждую дойку.
Для каждой дойки i = 1,..., n она знает, что та случилась не ранее дня s_i. К тому же Беси имеет c заметок, каждая из которых описывается тройкой (a, b, x), указывающих что дойка b случилась как минимум через x дней после дойки a.
Помогите Беси вычислить наиболее ранние возможные даты доек. Гарантируется, что все заметки Беси корректны, то есть существует решение (все числа в интервале [1, m]), удовлетворяющее всем заметкам.
Giriş verilənləri
Первая строка содержит числа n~(1 \le n \le 10^5), m~(2 \le m \le 10^9), c~(1 \le c \le 10^5). Следующая строка содержит n целых чисел s_1, s_2,...,s_n~(1 \le s_i \le m), каждое из которых находится в интервале [1, m].
Следующие c строк содержат по три целых числа a, b, x указывающих, что дойка b случилась не менее чем через x дней после дойки a. Для каждой строки, a \ne b, a и b принадлежат интервалу [1, n], а x принадлежат интервалу [1, m].
Çıxış verilənləri
Выведите n строк, определяющих наиболее ранние возможные даты доек.
Nümunə
Второй сеанс произошел по крайней мере через пять дней после первого сеанса, поэтому он не мог произойти раньше дня номер 1 + 5 = 6. Четвертый сеанс произошел по крайней мере через два дня после второго сеанса, поэтому он не мог произойти раньше дня номер 6 + 2 = 8.
4 10 3 1 2 3 4 1 2 5 2 4 2 3 4 4
1 6 3 8