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

サンプル