타임라인

Bessie는 지난 $M$일($2 \le M \le 10^9$) 동안 $N$번의 착유 세션($1\le N\le 10^5$)에 참여했다. 그런데 각 세션이 언제였는지 기억하지 못하고 있다.

각 세션 $i = 1 \ldots N$에 대해, 그 세션이 $S\_i$일($1\le S\_i\le M$)보다 이르지 않게 일어났다는 것은 알고 있다. 또한 Bessie에게는 $C$개의 기억($1\le C\le 10^5$)이 있는데, 각 기억은 세 쌍 $(a,b,x)$로 주어지며 세션 $b$가 $a$보다 적어도 $x$일 뒤에 일어났다는 것이다.

각 착유 세션이 일어날 수 있는 가장 이른 날짜를 구해 Bessie를 도와주자. Bessie가 잘못 기억한 경우는 없음이 보장된다. 즉, $1\ldots M$ 범위의 날짜에 세션을 배정하여 기억에 따른 모든 제약을 만족하는 방법이 존재한다.

첫째 줄에 $N$, $M$, $C$가 주어진다.

다음 줄에 $N$개의 정수 $S\_1,S\_2,\ldots, S\_N$이 공백으로 구분되어 주어진다. 각 값은 $1 \ldots M$ 범위이다.

다음 $C$개의 줄에 세 정수 $a$, $b$, $x$가 주어지며, 이는 세션 $b$가 $a$보다 적어도 $x$일 뒤에 일어났다는 뜻이다. 각 줄에서 $a \neq b$이고, $a$와 $b$는 $1 \ldots N$ 범위이며, $x$는 $1 \ldots M$ 범위이다.

각 세션이 일어날 수 있는 가장 이른 날짜를 $N$개의 줄에 출력한다.

세션 2는 세션 1보다 적어도 5일 뒤에 일어났으므로 $1+5=6$일보다 이르게 일어날 수 없다. 세션 4는 세션 2보다 적어도 2일 뒤에 일어났으므로 $6+2=8$일보다 이르게 일어날 수 없다.