#U1920FG1. Timeline

Timeline

Bessie attended NN milking sessions (1N1051≤N≤105) over the past MM days (2M1092≤M≤109). However, she is having trouble remembering when she attended each session.For each session i=1Ni=1…N, she knows that it occurred no earlier than day SiSi (1SiM1≤Si≤M). Additionally, Bessie has CC memories (1C1051≤C≤105), each described by a triple (a,b,x)(a,b,x), where she recalls that session bb happened at least xx days after aa.

Help Bessie by computing the earliest possible date of occurrence for each milking session. It is guaranteed that Bessie did not remember incorrectly; in other words, there exists an assignment of sessions to days in the range 1M1…M such that all constraints from her memories are satisfied.

SCORING:

  • Test cases 2-4 satisfy N,C103N,C≤103.
  • Test cases 5-10 satisfy no additional constraints.

INPUT FORMAT (file timeline.in):

The first line of input contains NN, MM, and CC.The next line contains NN space-separated integers S1**,S2**,,SNS1,S2,…,SN. Each is in the range 1M1…M.

The next CC lines contain three integers, aa, bb, and xx indicating that session bb happened at least xx days after aa. For each line, aba≠b, aa and bb are in the range 1N1…N, and xx is in the range 1M1…M.

OUTPUT FORMAT (file timeline.out):

Output NN lines giving the earliest possible date of occurrence for each session.

SAMPLE INPUT:

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

SAMPLE OUTPUT:

1
6
3
8

Session two occurred at least five days after session one, so it cannot have occurred before day 1+5=**6.**1+5=6. Session four occurred at least two days after session two, so it cannot have occurred before day 6+2=86+2=8.