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

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