Contest Duration: - (local time) (100 minutes) Back to Home
G - 01Sequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

01 のみからなる長さ N の数列 A=(A_1,A_2,\dots,A_N) であって、以下の条件を満たすものを考えます。

すべての i=1,2,\dots,M について、A_{L_i}, A_{L_i+1},\dots ,A_{R_i}1X_i 個以上含まれる

なお、制約のもとで条件を満たす数列 A は必ず存在します。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2} )
• 1 \leq L_i \leq R_i \leq N
• 1 \leq X_i \leq R_i-L_i+1
• i \neq j ならば (L_i,R_i) \neq (L_j,R_j)
• 入力は全て整数

入力

N M
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_M R_M X_M


出力

01 のみからなる数列 A を空白区切りで出力せよ。

A_1 A_2 \dots A_N


入力例 1

6 3
1 4 3
2 2 1
4 6 2


出力例 1

0 1 1 1 0 1


1 1 0 1 1 0 などの答えも正解です。
0 1 1 1 1 1 などの答えは含まれる 1 の数が最小化されていないので、不正解です。

入力例 2

8 2
2 6 1
3 5 3


出力例 2

0 0 1 1 1 0 0 0


Score : 600 points

Problem Statement

Consider a sequence of length N consisting of 0s and 1s, A=(A_1,A_2,\dots,A_N), that satisfies the following condition.

For every i=1,2,\dots,M, there are at least X_i occurrences of 1 among A_{L_i}, A_{L_i+1}, \dots, A_{R_i}.

Print one such sequence with the fewest number of occurrences of 1s.

There always exists a sequence that satisfies the condition under the Constraints.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2} )
• 1 \leq L_i \leq R_i \leq N
• 1 \leq X_i \leq R_i-L_i+1
• (L_i,R_i) \neq (L_j,R_j) if i \neq j.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_M R_M X_M


Output

Print a sequence A consisting of 0s and 1s, with spaces in between.

A_1 A_2 \dots A_N


It must satisfy all the requirements above.

Sample Input 1

6 3
1 4 3
2 2 1
4 6 2


Sample Output 1

0 1 1 1 0 1


Another acceptable output is 1 1 0 1 1 0.
On the other hand, 0 1 1 1 1 1, which has more than the fewest number of 1s, is unacceptable.

Sample Input 2

8 2
2 6 1
3 5 3


Sample Output 2

0 0 1 1 1 0 0 0