Mirko's Lost Sequence

Mirko wrote down a sequence \(A\) of \(N\) elements which is a permutation of \(\{1,2,\dots,N\}\). Then he noted down \(M\) descriptions about \(A\) on another paper. Unfortunately, the original sequence is lost. Your task is to construct any permutation \(A\) that satisfies all the \(M\) descriptions.

Each description is given in one of the following two forms:

• 1 x y v: Indicates that the maximum value on the interval \([x,y]\) is \(v\), i.e., \(\max\{A_x, A_{x+1}, \dots, A_y\} = v\). This means that for every index \(i\) with \(x \le i \le y\), \(A_i \le v\), and at least one \(A_i = v\).
• 2 x y v: Indicates that the minimum value on the interval \([x,y]\) is \(v\), i.e., \(\min\{A_x, A_{x+1}, \dots, A_y\} = v\). This means that for every index \(i\) with \(x \le i \le y\), \(A_i \ge v\), and at least one \(A_i = v\).

Your constructed sequence does not have to match Mirko's original sequence, but it must satisfy every provided description.

The constraints imposed by the descriptions affect the possible values at each position. For every index \(i\), we can derive an allowable range \([L_i, R_i]\) for \(A_i\) (initially \([1,N]\)). Each maximum constraint \(1\; x\; y\; v\) forces \(R_i \le v\) for \(x \le i \le y\) and requires that at least one index in \([x,y]\) gets the value \(v\). Similarly, each minimum constraint \(2\; x\; y\; v\) forces \(L_i \ge v\) for \(x \le i \le y\) and requires that at least one index in \([x,y]\) gets the value \(v\).

After obtaining the allowed ranges for each position, you need to assign a unique number from \(1\) to \(N\) to each position such that the assignment falls within the allowed range and all the interval conditions are satisfied.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

The next \(M\) lines each contain a description in one of the following formats:

• 1 x y v — indicating that the maximum of \(A_x, A_{x+1}, \dots, A_y\) is \(v\).
• 2 x y v — indicating that the minimum of \(A_x, A_{x+1}, \dots, A_y\) is \(v\).

outputFormat

If a valid permutation exists, output the \(N\) numbers of the permutation (space‐separated) on a single line. If there is no valid permutation, output -1.

sample

5 3
1 1 3 3
2 2 5 2
1 4 5 5

1 2 3 4 5