시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 186 65 45 31.690%

문제

수업시간이 너무나 지루했던 태석이는 종이에 길이가 N인 수열 A를 적었다. 이 수열은 1보다 크거나 같고, N보다 작거나 같은 양의 정수로 이루어져 있고, 각 숫자는 정확히 한 번씩 등장한다.

그런 다음 태석이는 다른 종이에 수열 A에 대한 설명을 M개 적었다.

각 설명은 다음과 같은 형태로 되어있다.

  • 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v
  • 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v

태석이는 설명만 적은 종이를 보성이에게 주었다. 보성이는 M개의 설명만 가지고 태석이가 원래 적은 수열을 맞추어보려고 한다.

M개의 설명이 주어졌을 때, 태석이가 원래 적은 수열을 구해 출력하는 프로그램을 작성하시오. 수열은 여러개 존재할 수 있다.

입력

첫째 줄에 수열의 크기 N과 설명의 개수 M이 주어진다. (1<=N<=200, 0<=M<=40,000) 둘째 줄부터 M개의 줄에는 태석이의 설명이 문제 설명과 같은 형식으로 주어진다.

출력

첫째 줄에 태석이가 원래 적은 수 N개를 공백으로 구분하여 출력한다. 만약 태석이의 설명과 일치하는 수열이 없다면 -1을 출력한다.

예제 입력

3 2
1 1 1 1
2 2 2 2

예제 출력

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

힌트