题目描述

考虑一个由 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}$ 中至少有 $X_i$ 个 1。

输出一个满足条件的序列，其中 1 的数量最少。

在约束条件下，总是存在满足条件的序列。

约束条件

• $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$

输出格式

输出一个由 0 和 1 组成的序列 $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