시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 1 1 (100%) 1
문제
밀코는 지루했다. 그래서 그는 종이조각을 가져와 길이 N짜리 수열 A를 썼는데, 이 수열은 1과 N사이의 정수를 정확히 한번씩만 포함한다. 그러고나서, 그는 다른 종이조각들을 가져와 수열 A를 설명하는 M개의 설명문을 썼다. 각 설명문은 다음과 같은 형식으로 이루어져있다: - 1 x y v - x번째와 y번째 사이에 있는 수들 중 가장 큰 수는 v이다. - 2 x y v - x번째와 y번째 사이에 있는 수들 중 가장 작은 수는 v이다. 그리고 슬라브코가와서, 보고는, 첫번째 종이를 훔쳐갔다. 밀코는 절망했고 위의 설명을 만족하는 적당한 수열을 찾아달라고 부탁했는데, 꼭 처음 수열과 같을 필요는 없다.
입력
첫번째 줄에는 두개의 양의 정수, 수열의 길이를 나타내는 N(1<=N<=200)과, 설명문의 갯수를 나타내는 M (0<=M<=40 000)이 주어진다. 각 M개의 줄에 걸쳐 위에서 설명한 대로의 설명문들이 주어진다.
출력
첫번째 줄에 단하나의 줄로 N개의 공백으로 구분된 양의 정수를 출력한다. (설명문에 부합해야 하고 1과 N사이의 모든 양의 정수를 포함하고 있어야 한다.) 또는 만약 그러한 수열이 없다면 -1을 출력한다.
힌트
입력예제1 ``` 3 2 1 1 1 1 2 2 2 2 ``` 출력예제1 ``` 1 2 3 ``` 입력예제2 ``` 4 2 1 1 1 1 2 3 4 1 ``` 출력예제2 ``` -1 ``` 입력예제3 ``` 5 2 1 2 3 3 2 4 5 4 ``` 출력예제3 ``` 1 2 3 4 5 ```