Хронологія подій#10123

Хронологія подій

1 секунда

128 мегабайтів

Середня

Бесі відвідала $n$ сеансів доїння за останні $m$ днів. Однак їй важко запам'ятати, коли відбувся кожен сеанс.

Для кожного сеансу $i = 1, ..., n$ i = 1,..., n вона знає, що він відбувся не раніше дня $s_{i}$ s_i. Крім того, Бесі має $c$ нотаток, кожна з яких описується трійкою $(a, b, x)$ (a, b, x), що вказує на те, що сеанс $b$ відбувся щонайменше через $x$ днів після сеансу $a$ .

Допоможіть Бесі обчислити найраніші можливі дати сеансів доїння. Гарантовано, що всі нотатки Бесі коректні, тобто існує розв'язок (усі числа в інтервалі $[1, m]$ ), що задовольняє всім нотаткам.

Вхідні дані

Перший рядок містить числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), $m (2 \leq m \leq 1 0^{9})$ m~(2 \le m \le 10^9), $c (1 \leq c \leq 1 0^{5})$ c~(1 \le c \le 10^5). Наступний рядок містить $n$ цілих чисел $s_{1}, s_{2}, ..., s_{n} (1 \leq s_{i} \leq m)$ s_1, s_2,...,s_n~(1 \le s_i \le m), кожне з яких знаходиться в інтервалі $[1, m]$ .

Наступні $c$ рядків містять по три цілих числа $a, b, x$ a, b, x, що вказують, що сеанс $b$ відбувся не менше ніж через $x$ днів після сеансу $a$ . Для кожного рядка, $a \neq = b$ a \ne b, $a$ і $b$ належать інтервалу $[1, n]$ , а $x$ належить інтервалу $[1, m]$ .

Вихідні дані

Виведіть $n$ рядків, що визначають найраніші можливі дати сеансів доїння.

Приклади

Другий сеанс відбувся щонайменше через п'ять днів після першого сеансу, тому він не міг відбутися раніше дня номер $1 + 5 = 6$ 1 + 5 = 6. Четвертий сеанс відбувся щонайменше через два дні після другого сеансу, тому він не міг відбутися раніше дня номер $6 + 2 = 8$ 6 + 2 = 8.

Приклад 1