Bessie attended n milking sessions over the past m days. However, she is having trouble remembering when she attended each session.
For each session i=1...n, she knows that it occurred no earlier than day si. Additionally, Bessie has c memories, each described by a triple (a,b,x), where she recalls that session b happened at least x days after a.
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...m such that all constraints from her memories are satisfied.
The first line of input contains n (1≤n≤105), m (2≤m≤109), and c (1≤c≤105). The next line contains n integers s1,s2,...,sn (1≤si≤m). Each is in the range 1...m.
The next c lines contain three integers a,b and x indicating that session b happened at least x days after a. For each line a=b,a and b are in the range 1...n, and x is in the range 1...m.
Print n lines giving the earliest possible date of occurrence for each session.
Session two occurred at least five days after session one, so it cannot have occurred before day 1+5=6. Session four occurred at least two days after session two, so it cannot have occurred before day 6+2=8.