#U1920FG1. Timeline
Timeline
Bessie attended NN milking sessions (1≤N≤1051≤N≤105) over the past MM days (2≤M≤1092≤M≤109). However, she is having trouble remembering when she attended each session.For each session i=1…Ni=1…N, she knows that it occurred no earlier than day SiSi (1≤Si≤M1≤Si≤M). Additionally, Bessie has CC memories (1≤C≤1051≤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 1…M1…M such that all constraints from her memories are satisfied.
SCORING:
- Test cases 2-4 satisfy N,C≤103N,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 1…M1…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, a≠ba≠b, aa and bb are in the range 1…N1…N, and xx is in the range 1…M1…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.