Беси посетила \(N\) доек (\(1\le N\le 10^5\)) за последние \(M\) дней (\(2 \le M \le 10^9\)).
Для каждой дойки \(i = 1 \ldots N\), она знает, что та случилась не ранее дня \(S_i\) (\(1\le S_i\le M\)).
Дополнительно, Беси имеет \(C\) заметок (\(1\le C\le 10^5\)), каждая описывается тройкой \((a,b,x)\),
указывающей, что дойка \(b\) случилась как минимум через \(x\) дней после дойки \(a\).
Помогите Беси вычислить наиболее ранние возможные даты доек.
Гарантируется, что все заметки Беси корректны, то есть существует решение (все числа
в интервале \(1\ldots M\)), удовлетворяющее всем заметкам.
ОЦЕНИВАНИЕ:
- В тестах 2-4 \(N,C \le 10^3\).
- В тестах 5-10 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл timeline.in):
Первая строка ввода содержит
\(N\),
\(M\),
\(C\).
Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел
\(S_1,S_2,\ldots, S_N\). Каждое в интервале \(1 \ldots M\).
Следующие \(C\) строк содержат по три целых числа \(a\), \(b\), \(x\) указывающих,
что дойка \(b\) случилась не менее чем через \(x\) дней после дойки \(a\).
Для каждой строки, \(a \neq b\), \(a\) и \(b\) в интервале \(1 \ldots N\), а \(x\) в интервале 1 \ldots M$.
ФОРМАТ ВЫВОДА (файл timeline.out):
Выведите \(N\) строк, определяющих наиболее ранние возможные даты доек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
|
1
6
3
8
|