問題
長さ N の数列がある.
最初、この数列のすべての要素は 0 である.
この数列に対し、あわせて Q 回次の操作を行う.
- 数列の Li 番目から Ri 番目(両端を含む) を Ti に書き換える. ただし、数列の最初の要素が 1 番目である.
最終的に数列の各値が何になったか求めよ.
入力
N Q L1 R1 T1 : LQ RQ TQ
- 1 行目に数列の長さ N (1 ≤ N ≤ 105), 操作の回数 Q (1 ≤ Q ≤ 105) が与えられる.
- その後 Q 行にかけて, 操作が順に与えられる. このうち i(1 ≤ i ≤ N) 行目は i 回目の操作を表し, 数列の Li 番目から Ri (1 ≤ Li ≤ Ri ≤ N) 番目を Ti (1 ≤ T ≤ 109) に書き換えることを意味する.
N ≤ 3000 を追加で満たすテストケースにすべて正解すると, 5 点が与えられる.
出力
出力は N 行からなる. 上から i 行目に操作後の数列の i 番目の要素の値を出力せよ.
入出力例
入力例 1
5 2 1 3 10 2 4 20
出力例 1
10 20 20 20 0
- 最初数列は, {0, 0, 0, 0, 0} である.
- 1 回目の操作のあと, 数列は {10, 10, 10, 0, 0} となる.
- 2 回目の操作のあと, 数列は {10, 20, 20, 20, 0} となる.
入力例 2
10 4 2 7 22 3 5 4 6 10 1 4 4 12
出力例 2
0 22 4 12 4 1 1 1 1 1