Problem Statement

Consider the following problem.

問題文：
長さ $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 solved this problem and obtained $B_i$ as the answer to the $i$-th query.

However, after solving the problem, yuki lost the sequence $\{ A_i \}$ and can no longer tell whether the answers are actually correct.

If there exists a sequence $\{ A_i \}$ that satisfies the constraints and for which the answers to all queries match, construct one such sequence; otherwise, output -1.

Input

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

• All inputs are integers.
• $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$

Output

If there exists a sequence $\{ A_i \}$ of length $N$ consisting of integers between $1$ and $10^9$, inclusive, such that the minimum of $A_{l_i}, A_{l_i + 1}, \cdots, A_{r_i}$ is $B_i$ for every $i \ (1 \leq i \leq Q)$, output one such sequence; otherwise, output -1.

Sample

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