题目描述

0 と 1 のみからなる長さ $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}$ に 1 が $X_i$ 個以上含まれる

条件を満たす数列 $A$ のうち、含まれる 1 の数が最も少ない例を $1$ つ出力してください。

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

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

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

$A_1$ $A_2$ $\dots$ $A_N$

数列 $A$ は上記の条件を全て満たさなければならない。

题目大意

你需要构造出一个长度为 $n$ 的 $01$ 序列，满足 $m$ 个限制 $(l_i,r_i,x_i)$：在 $[l_i,r_i]$ 这段区间内，序列上 $1$ 的个数不小于 $x_i$。你需要保证你的方案中包含 $1$ 的个数最小。

数据保证有解。

$1 \le n,m \le 2 \times 10^5$

6 3
1 4 3
2 2 1
4 6 2

0 1 1 1 0 1

8 2
2 6 1
3 5 3

0 0 1 1 1 0 0 0

提示

制約

• $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)$
• 入力は全て整数

Sample Explanation 1

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