INFORMACIJE

Xem dạng PDF

Gửi bài giải


Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
COCI 2012-2013
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mirko was bored, so he took ~a~ piece of paper and wrote down a sequence ~A~ of length ~N~, which contains each positive integer between ~1~ and ~N~, inclusive, exactly once. After that, he took another piece of paper and wrote down ~M~ descriptions of the sequence ~A~.

Each description has one of the following formats:

  • ~1~ ~x~ ~y~ ~v~ -- the largest number in positions between ~x~ and ~y~ (inclusive) equals ~v~
  • ~2~ ~x~ ~y~ ~v~ -- the smallest number in positions between ~x~ and ~y~ (inclusive) equals ~v~

Then Slavko came, saw, and stole the first paper. Mirko is desperate and has asked you to find some sequence matching the descriptions, not necessarily equal to the original sequence.

Input

The first line of input contains two positive integers, ~N~ ~(1 \leq N \leq 200)~, the length of the sequence, and ~M~ ~(0 \leq M \leq 40 000)~, the number of descriptions.

Each of the following ~M~ lines contains ~a~ description as described above.

Output

The first and only line of output must contain a sequence of ~N~ space-separated positive integers (matching the descriptions and containing all positive integers from ~1~ to ~N)~, or ~- 1~ if no such sequence exists.

Sample Input 1

3 2
1 1 1 1
2 2 2 2

Sample Output 1

1 2 3

Sample Input 2

4 2
1 1 1 1
2 3 4 1

Sample Output 2

-1

Sample Input 3

5 2
1 2 3 3
2 4 5 4

Sample Output 3

1 3 2 5 4

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.