수열 복원하기
시간 제한1초메모리 제한128 MB
구간별 최대값 또는 최소값 조건 M개를 만족하는 1부터 N까지의 순열을 복원하거나 불가능함을 출력합니다.
문제
길이가 N인 수열 A가 있다. A는 1 이상 N 이하의 정수로 이루어진 순열이며, 각 정수는 정확히 한 번씩 등장한다.
수열 A에 대한 설명 M개가 주어진다. 각 설명은 다음 두 가지 중 하나이다.
1 x y v: A의 x번째 수부터 y번째 수까지 중 최댓값이 v이다.2 x y v: A의 x번째 수부터 y번째 수까지 중 최솟값이 v이다.
모든 설명을 만족하는 원래 수열 A를 하나 구해 출력하시오. 조건을 만족하는 수열이 여러 개라면 아무거나 출력해도 된다.
입력
첫째 줄에 수열의 크기 N과 설명의 개수 M이 주어진다.
1 <= N <= 200, 0 <= M <= 40000
둘째 줄부터 M개의 줄에 설명이 주어진다. 각 줄은 1 x y v 또는 2 x y v 형식이다.
출력
첫째 줄에 조건을 모두 만족하는 수열 A의 원소 N개를 공백으로 구분하여 출력한다.
조건을 만족하는 수열이 없다면 -1을 출력한다.