Беси посетила $n$ доек за последние $m$ дней. Однако ей трудно запомнить, когда она посещала каждую дойку. Для каждой дойки $i = 1,..., n$ она знает, что та случилась не ранее дня $s_i$. К тому же Беси имеет $c$ заметок, каждая из которых описывается тройкой $(a, b, x)$, указывающих что дойка $b$ случилась как минимум через $x$ дней после дойки $a$. Помогите Беси вычислить наиболее ранние возможные даты доек. Гарантируется, что все заметки Беси корректны, то есть существует решение (все числа в интервале $[1, m]$), удовлетворяющее всем заметкам. \InputFile Первая строка содержит числа $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]$. \OutputFile Выведите $n$ строк, определяющих наиболее ранние возможные даты доек. \Examples Второй сеанс произошел по крайней мере через пять дней после первого сеанса, поэтому он не мог произойти раньше дня номер $1 + 5 = 6$. Четвертый сеанс произошел по крайней мере через два дня после второго сеанса, поэтому он не мог произойти раньше дня номер $6 + 2 = 8$.