問題文

次のような問題があります。

問題文：
長さ $N$ の数列 $A_1, A_2, \cdots, A_N$ があります。次の $Q$ 個のクエリに答えてください。
・ $i$ 個目のクエリでは整数 $l_i, r_i$ が与えられる。 $A_{l_i}, A_{l_i + 1}, \cdots, A_{r_i}$ の最小値を求めよ。

制約：
$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
$1 \leq l_i \leq r_i \leq N \ (1 \leq i \leq Q)$

yukiさんはこの問題を解いたところ、 $i$ 番目のクエリに対する解が $B_i$ となりました。

しかし問題を解いた後で数列 $\{ A_i \}$ を紛失してしまったため、本当に答えが合っているのかどうかわからなくなってしまいました。

制約を満たし、かつクエリに対する解が全て一致する数列 $\{ A_i \}$ が存在するならそれを1つ構築し、存在しないなら-1を出力してください。

入力

$N \ Q$
$l_1 \ r_1 \ B_1$
$\vdots$
$l_Q \ r_Q \ B_Q$

• 入力は全て整数
• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq B_i \leq 10^9$
• $1 \leq l_i \leq r_i \leq N$

出力

$1$ 以上 $10^9$ 以下の整数から成り、任意の $i \ (1 \leq i \leq Q)$ に対し $A_{l_i}, A_{l_i + 1}, \cdots, A_{r_i}$ の最小値が $B_i$ となる長さ $N$ の数列 $\{ A_i \}$ が存在するならその一例を、存在しないなら-1を出力してください。

サンプル

5 3
1 3 1
3 5 3
4 5 4

2 1 3 5 4

3 2
1 2 2
1 1 1

-1

4 3
1 3 1
2 4 1
1 4 1

1 1 1 1