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

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

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

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

Вхідні дані

Перший рядок містить числа $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]$.

Вихідні дані

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

Приклади

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