AT_abc216_g [ABC216G] 01Sequence

[problemUrl]: https://atcoder.jp/contests/abc216/tasks/abc216_g `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 $ は上記の条件を全て満たさなければならない。

### 制約 - $ 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` の数が最小化されていないので、不正解です。