Restore the Sequence

Time limit1sMemory limit128 MB

Summary

Reconstruct a permutation of 1..N that satisfies M range max/min constraints, or report impossibility.

Level: Medium7 of 10
Topics: Greedy, Backtracking, Simulation
Solved: No attempts yet

Problem

There is a sequence A of length N. A is a permutation of the integers from 1 to N, so every integer in that range appears exactly once.

You are given M descriptions of A. Each description has one of the following forms.

1 x y v: the maximum value among the x-th through y-th elements of A is v.
2 x y v: the minimum value among the x-th through y-th elements of A is v.

Find and print one original sequence A that satisfies every description. If more than one sequence satisfies the descriptions, any one of them may be printed.

Input

The first line contains the sequence size N and the number of descriptions M.

1 <= N <= 200, 0 <= M <= 40000

Each of the next M lines contains one description in the form 1 x y v or 2 x y v.

Output

Print N integers on the first line: a sequence A that satisfies all descriptions.

If no such sequence exists, print -1.

Examples3

Example 1
Input
```
3 2
1 1 1 1
2 2 2 2
```
Expected output
```
1 2 3
```
Example 2
Input
```
4 2
1 1 1 1
2 3 4 1
```
Expected output
```
-1
```
Example 3
Input
```
5 2
1 2 3 3
2 4 5 4
```
Expected output
```
1 2 3 4 5
```