Finally, someone meets some girl. So, the end of the world is coming. Some girl becomes a sacrificial offering of this year to avoid someone to be close to other one in one year. This is totally your fault, because someone’s friend discovers your sensor network in the campus. It’s too late to save the world. What you can do is to revenge. You are so evil and you want to edit someone’s grade. You randomly select the interval of the grades and give the highest grade a random value. Please output the grades after editing.
Each test case starts with a line containing two integers n(1<=n<=105) and q(1<=q<=2*105)indicating the number of the grades and the number of events. Then, one line contains n integers representing someone’s original grades. Following this are q lines, each containing three integers x, y, c(1<=x<=y<=n). For every event, adjusts the highest value between [x, y] to c. If there is more than one highest value, choose the number has the smaller index.
Please output one line containing someone’s final grades.