플러그 (Plugs)
시간 제한1초메모리 제한1024 MB
각 진술은 [C,D] 구간의 어떤 플러그도 [A,B] 구간 회사의 소켓에 맞지 않는다는 뜻이며, 이 조건을 모두 만족하는 유일한 플러그와 회사의 대응을 복원한다.
문제
JOI 나라에는 전기 플러그를 만드는 회사가 N개 있고, JOI 나라는 각 회사에 1부터 N까지의 정수를 ID로 부여한다. 각 전기 플러그 회사는 전기 플러그와 소켓을 한 쌍씩 만들지만, 모든 회사의 전기 플러그와 소켓은 다른 회사의 것과 모양이 다르다.
JOI 나라의 법률에 따라 소켓에는 전기 플러그 회사의 ID를 인쇄하게 되어 있지만, 전기 플러그에는 ID가 인쇄되어 있지 않다. 어느 전기 가게의 점장은 이런 JOI 나라의 사정 때문에 손님의 요구에 빠르게 대응할 수 있도록, JOI 나라에 존재하는 N종류의 전기 플러그를 하나씩 회사 ID 순서대로 넣은 공구함을 가지고 있었다. 그러나 어느 날, 점장은 우연히 공구함의 내용물을 흐트러뜨리고 말았다. 점장은 어떤 소켓에 어떤 전기 플러그가 들어가지 않는 것은 알아낼 수 있어도, 전기 플러그를 보고 어느 전기 플러그 회사의 전기 플러그인지 판단할 수는 없기 때문에, 공구함의 내용물을 원래대로 되돌릴 수 없게 되었다. 점장은 고민 끝에, 어떤 어려운 문제든 아주 쉽게 풀어내기로 유명한 L 교수에게 해결을 의뢰했다.
L 교수는 순서가 뒤섞인 전기 플러그에 정리를 위해 1부터 N까지 번호를 붙이고, 그것을 바탕으로 점장에게서 M개의 증언을 끌어냈다. 점장의 k번째 증언은 "전기 플러그 회사의 ID가 Ak부터 Bk인 소켓에는, Ck번째부터 Dk번째의 어느 전기 플러그도 들어가지 않는다"라는 것이다. 그 후, L 교수는 "수수께끼는 해결되었다. 이 M개의 증언을 만족하는 전기 플러그와 회사의 대응 관계는 하나로 정해졌다. 나머지는 자네에게 맡기겠네."라고 말하고 떠나 버렸다. 매우 부당한 이야기이지만, 제자인 당신은 문제를 해결해 전기 플러그와 회사의 대응 관계를 점장에게 알려야 한다.
점장의 증언으로부터 전기 플러그의 대응 관계를 특정하는 프로그램을 작성하라.
그림 1
입력
표준 입력에서 다음 입력을 읽는다.
- 1번째 줄에는 정수 N과 M이 공백으로 구분되어 쓰여 있다.
- 이어지는 M개의 줄은 한 줄에 하나의 증언을 기술한다. 이 줄들 중 k번째 줄은 k번째 증언을 기술하며, 정수 Ak, Bk, Ck, Dk가 공백으로 구분되어 쓰여 있다.
출력
표준 출력에 다음 데이터를 출력한다.
- 데이터는 N개의 줄로 이루어지며, i번째 줄은 ID가 i인 회사가 만드는 전기 플러그의 번호를 포함한다.
제한
- 1 ≤ N ≤ 3,000 JOI 나라에 존재하는 전기 플러그 회사의 수
- 1 ≤ M ≤ 100,000 점장의 증언 수
- 1 ≤ Ak ≤ Bk ≤ N, 1 ≤ Ck ≤ Dk ≤ N, 1 ≤ k ≤ M k번째 증언의 내용