Timeline#10123
Bessie attended milking sessions over the past 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 s_i. Additionally, Bessie has memories, each described by a triple (a, b, x), where she recalls that session happened at least days after session .
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 such that all constraints from her memories are satisfied.
The first line of input contains n~(1 \le n \le 10^5), m~(2 \le m \le 10^9), and c~(1 \le c \le 10^5). The next line contains integers s_1, s_2,...,s_n~(1 \le s_i \le m). Each is in the range .
The next lines contain three integers and indicating that session happened at least days after . For each line, a \ne b, and are in the range , and is in the range .
Print 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.
Example 1