D - Repainting the Fence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君の家の前に、N 枚の板からなるフェンスがあります。板には左から順に 1 から N までの番号が付いています。

最初、すべての板の色番号は 0（未塗装）です。

高橋君はこれから M 回の塗り替えを順に行います。i 回目 (1 \leq i \leq M) の塗り替えでは、板 L_i から板 R_i まで（両端を含む）のすべての板を色番号 C_i で上書きします。すでに色が付いている板も、新しい色番号 C_i に変わります。

すべての塗り替えが終わった後の、各板の最終的な色番号を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • 入力はすべて整数である。

入力

N M
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_M R_M C_M

1 行目には、板の枚数 N と塗り替えの回数 M がスペース区切りで与えられる。続く M 行のうち i 行目には、i 回目の塗り替えで塗る区間の左端 L_i、右端 R_i、色番号 C_i がスペース区切りで与えられる。

出力

最終的な各板の色番号を、板 1 から板 N までの順にスペース区切りで 1 行に出力してください。

入力例 1

5 3
1 3 2
2 5 4
4 4 7

出力例 1

2 4 4 7 4

入力例 2

6 4
3 6 1
1 2 9
2 5 3
6 6 8

出力例 2

9 3 3 3 3 8

入力例 3

12 7
1 12 5
3 8 2
6 10 9
2 2 4
11 12 7
5 7 1
9 9 6

出力例 3

5 4 2 2 1 1 1 9 6 9 7 7

入力例 4

20 11
1 5 3
6 10 4
11 15 5
16 20 6
4 17 8
2 2 1
19 20 9
7 13 2
1 20 10
5 5 11
10 18 12

出力例 4

10 10 10 10 11 10 10 10 10 12 12 12 12 12 12 12 12 12 10 10

入力例 5

1 0

出力例 5

0

Score : 400 pts

Problem Statement

There is a fence consisting of N boards in front of Takahashi's house. The boards are numbered from 1 to N from left to right.

Initially, the color number of every board is 0 (unpainted).

Takahashi will perform M repainting operations in order. In the i-th (1 \leq i \leq M) repainting operation, he overwrites all boards from board L_i to board R_i (inclusive) with color number C_i. Even boards that are already painted will be changed to the new color number C_i.

Determine the final color number of each board after all repainting operations are completed.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • All inputs are integers.

Input

N M
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_M R_M C_M

The first line contains the number of boards N and the number of repainting operations M, separated by a space. Each of the following M lines contains, for the i-th repainting operation, the left endpoint L_i, the right endpoint R_i, and the color number C_i, separated by spaces.

Output

Print the final color numbers of each board, from board 1 to board N, separated by spaces, on a single line.

Sample Input 1

5 3
1 3 2
2 5 4
4 4 7

Sample Output 1

2 4 4 7 4

Sample Input 2

6 4
3 6 1
1 2 9
2 5 3
6 6 8

Sample Output 2

9 3 3 3 3 8

Sample Input 3

12 7
1 12 5
3 8 2
6 10 9
2 2 4
11 12 7
5 7 1
9 9 6

Sample Output 3

5 4 2 2 1 1 1 9 6 9 7 7

Sample Input 4

20 11
1 5 3
6 10 4
11 15 5
16 20 6
4 17 8
2 2 1
19 20 9
7 13 2
1 20 10
5 5 11
10 18 12

Sample Output 4

10 10 10 10 11 10 10 10 10 12 12 12 12 12 12 12 12 12 10 10

Sample Input 5

1 0

Sample Output 5

0