eolymp
bolt
Try our new interface for solving problems
Məsələlər

Хронология событий

Хронология событий

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Беси посетила 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.

Giriş verilənləri #1
4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
Çıxış verilənləri #1
1
6
3
8
Mənbə 2020 USACO Февраль Золото