프로그램 명: coci_informacije(special judge)
제한시간: 1 초
[요약]
미코는 심심해서 1 에서 N 까지의 숫자 를 한 번만 사용하여 크기 N 의 수열 A 를 적었다.
이 후 다른 종이에 다음 형식으로 M 개를 적었다.
-
1 x y v - x 와 y (x ,y 포함)사이에 최대 수 v
-
2 x y v - x 와 y (x ,y 포함)사이에 최소 수 v
그런데 슬라브코가 와서 처음에 쓴 A 수열의 종이를 가져가 버렸다. 미코를 도와 두 번째 쓴 M 개의 보고 원래 수열을 찾아내는 것이다. 여러개의 답이 존재할 수 있고 답이 존재하지 않으면 -1 을 출력한다.
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.
입력
-
The first line of input contains two positive integers, N (1 ≤ N ≤ 200), the length of the sequence, and M (0 ≤ M ≤ 40 000), the number of descriptions.
-
Each of the following M lines contains a description as described above.
출력
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.
입출력 예
input
3 2
1 1 1 1
2 2 2 2
output
1 2 3
input
4 2
1 1 1 1
2 3 4 1
output
-1
input
5 2
1 2 3 3
2 4 5 4
output
1 2 3 4 5
출처:coci/2012-2013/contest2 5/6
[질/답]
[제출 현황]
[푼 후(0)]