시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 64 MB | 35 | 22 | 21 | 61.765% |
There are N small villages close to the highway between Almaty and Taraz numbered from 1 to N. At the beginning of the winter M unknown traders began trading knitted hats in these villages. They have only two rules: never trade in one place more than once (one day) and increase the price on hats each day.
More formally, each i-th trader:
The problem is for each village to determine the maximal price that was there during the whole trading history.
Each line contains two integer number N (1 ≤ N ≤ 300000) and M (1 ≤ M ≤ 300000) - number of villages and traders accordingly.
Next M lines contains 3 numbers each: Li, Ri (1 ≤ Li ≤ Ri ≤ N) and Xi (1 ≤ Xi ≤ 109) - numbers of first and last village and starting price for i-th trader.
Output N integer numbers separating them with spaces - i-th number being the maximal price for the trading history of i-th village. If there was no trading in some village, output 0 for it.
5 2 1 3 2 2 4 6
2 6 7 8 0
6 4 4 4 3 1 2 5 5 6 1 6 6 1
5 6 0 3 1 2