Bessie attended milking sessions over the past days. However, she is having trouble remembering when she attended each session.
For each session , she knows that it occurred no earlier than day . Additionally, Bessie has memories, each described by a triple , where she recalls that session happened at least days after .
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 , , and . The next line contains integers . Each is in the range .
The next lines contain three integers and indicating that session happened at least days after . For each line 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 . Session four occurred at least two days after session two, so it cannot have occurred before day .