Earliest Milking Times

Bessie participated in N milkings over the last M days, but she has forgotten the day on which each milking occurred. For the i-th milking, she remembers that it could not have happened before day \(S_i\). Moreover, she has C memories. Each memory is given as a triple \((a, b, x)\) which means that the b-th milking occurred at least \(x\) days after the a-th milking was completed (i.e. \(\text{day}(b) \geq \text{day}(a) + x\)).

Your task is to compute the earliest possible day for each milking such that all conditions are satisfied. It is guaranteed that there exists a valid schedule where:

• For each \(1 \leq i \leq N\), the i-th milking is scheduled on a day between \(S_i\) and \(M\) (inclusive).
• All memory constraints \((a, b, x)\) are fulfilled.

Note: The constraints should be applied iteratively. In other words, if one memory constraint forces a change in the scheduled day of one milking, it might further force changes in the schedule of subsequent milkings.

inputFormat

The first line contains three integers \(M\), \(N\) and \(C\) \( (1 \leq N \leq M, C \geq 0)\) representing the total number of days, the number of milkings, and the number of memory constraints.

The second line contains \(N\) integers \(S_1, S_2, \ldots, S_N\) where \(S_i\) is the earliest possible day for the i-th milking.

The following \(C\) lines each contain three integers \(a\), \(b\), \(x\) indicating that the b-th milking must happen at least \(x\) days after the a-th milking, i.e. \(\text{day}(b) \geq \text{day}(a) + x\).

outputFormat

Output a single line with \(N\) integers, where the i-th integer represents the earliest day on which the i-th milking can be scheduled, satisfying all the constraints.

sample

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

1 4 8