Restore the Permutation from MEX Constraints

You are given an integer n and m pieces of information about a permutation of the numbers from 0 to n (the permutation has length n+1 and is 0-indexed). Each piece of information is a triple (l, r, val) which indicates that the mex (minimum excluded value) of the subarray from index l to r is val.

The mex of an interval [l, r] is defined as the smallest nonnegative integer that does not appear in that interval. In other words, if we denote by \(p_0, p_1, ..., p_n\) the permutation, then for a given interval \([l, r]\), the condition \[ \mathrm{mex}(\{p_l, p_{l+1}, \dots, p_r\}) = val \] implies that:

• For every integer \(x\) with \(0 \le x < val\), there exists an index \(i\) with \(l \le i \le r\) such that \(p_i=x\).
• If \(val \le n\), then \(p_i \neq val\) for all indices \(i\) with \(l \le i \le r\).

If val = n+1, then it means that all numbers from 0 to n appear in the interval. Note that if val = n+1 then necessarily \(l=0\) and \(r=n\), otherwise the condition cannot hold.

Your task is to restore any permutation that satisfies all the given constraints, or determine that there is no solution. If there is a solution, output the permutation as a sequence of n+1 integers separated by spaces; otherwise, output -1.

inputFormat

The first line contains two integers n and m (0 ≤ n, m), where n is the maximum number in the permutation (so the permutation has n+1 numbers) and m is the number of constraints.

Each of the next m lines contains three integers l, r and val representing that the mex of the subarray from index l to r is val (0-indexed). It is guaranteed that 0 ≤ l ≤ r ≤ n. Note that if val equals n+1, then it must be that l = 0 and r = n as the whole permutation is required.

outputFormat

If a valid permutation exists, output the permutation on a single line as n+1 integers separated by spaces. If no valid permutation exists, output -1.

sample

2 1
0 1 2

0 1 2