Trading#7482
Along the Almaty - Taraz highway, there are villages, numbered from to . With the arrival of winter, unknown traders brought knitted hats from a certain aul and began selling them in these villages. The traders follow two principles:
They do not sell in the same place for more than one day.
Each day, they increase the price of a hat.
More formally, each -th trader:
Starts selling in village l_i with an initial price of x_i per hat.
Moves to a neighboring village each day: if they sold in village yesterday, they sell in village j + 1 today.
Increases the price by each day: if the price was yesterday, today it is x + 1.
Finishes selling in village r_i (including selling in r_i on the last day).
For each village, determine the maximum price of a single hat throughout the entire trading history.
The first line contains two integers n~(1 \le n \le 3 \cdot 10^5) and m~(1 \le m \le 3 \cdot 10^5) — the number of villages and the number of traders, respectively.
The next lines each contain three integers: l_i, r_i~(1 \le l_i \le r_i \le n) and x_i~(1 \le x_i \le 10^9) — the starting and ending villages, as well as the initial price of a hat for the -th trader.
Print integers, where the -th number represents the maximum price of a hat throughout the entire trading history in the -th village. If no trade took place in a particular village, print .
Example 1
Example 2