B Restore Testcase 2

問題

制限時間: 10 sec メモリ制限: 1024 MB

Restore Testcase 2

Statement

以下のような問題 \(Z\) を作りました。

【問題 \(Z\)】

長さ \(N\) の数列 \(A\) があります。はじめ、各要素はすべて \(0\) です。\(q=1,2,\dots,Q\) の順に以下のクエリを行います。

数列の \(l_q\) 番目から \(r_q\) 番目を \(c_q\) に変える。

すべてのクエリを行った後の \(A\) を出力してください。

問題 \(Z\) のテストケースは以下のような形式になっています。

	\(N~Q\)
	\(l_1~r_1~c_1\)
	\(l_2~r_2~c_2\)
	\(\vdots\)
	\(l_Q~r_Q~c_Q\)

問題 \(Z\) のテストケースを用意し、出力結果も保存していましたが、テストケースの \(2\) 行目から \(Q+1\) 行目までをシャッフルしてしまいました。シャッフルした後のテストケースと出力結果である数列 \(A\) が与えられるので、シャッフルする前のテストケースとしてあり得るものを \(1\) つ求めてください。ただし、そのようなテストケースが \(1\) つ以上存在することは保証されます。

Input

\(q=1,2,\dots,Q\) について、問題 \(Z\) のシャッフル後のテストケースの上から \(q+1\) 行目を

\(l'_q~r'_q~c'_q\)

としたとき、入力は以下の形式で与えられます。

	\(N~Q\)
	\(l'_1~r'_1~c'_1\)
	\(l'_2~r'_2~c'_2\)
	\(\vdots\)
	\(l'_Q~r'_Q~c'_Q\)
	\(A_1~A_2~\dots~A_N\)

入力は以下の制約をすべて満たします。

\(1 \leq N \leq 200000\)
\(1 \leq Q \leq 200000\)
\(1 \leq l'_q \leq r'_q \leq N\)
\(1 \leq c'_q \leq N\)
\(0 \leq A_i \leq N\)
入力はすべて整数
条件を満たす解が存在する

Output

入力の \(2\) 行目から \(Q+1\) 行目までを条件を満たすように並び替えて合計 \(Q\) 行で出力してください。 \(q\) 行目には、元のテストケースの \(q+1\) 行目を出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

(10点): \(0 \leq A_i \leq 1, \; c_q=1\)
(25点): \(N\leq 3000,\; Q\leq 3000\)
(65点): 追加制約はありません。

Example

Input 1

Output 1

1 2 3
2 2 1
4 4 4

サンプル