문제
Farmer John은 포크리프트 자격증을 따기 위한 훈련을 받고 있습니다. 훈련의 일환으로, 그는 오래된 창고에서 1번부터 N번까지 번호가 매겨진 N개의 상자를 모두 치워야 합니다. 상자들은 2차원 평면 위의 축에 평행한 직사각형으로 모델링할 수 있는데, +x 방향은 동쪽, +y 방향은 북쪽입니다. 상자 i는 남서쪽 모서리가 (x_i1, y_i1)이고 북동쪽 모서리가 (x_i2, y_i2)에 위치합니다. 모든 좌표는 1부터 2N 사이의 정수이며, 서로 다른 두 상자의 모서리끼리는 x좌표나 y좌표가 공유되지 않습니다. 모든 상자는 넓이가 0보다 크며, 어떤 두 상자도 서로 겹치지 않습니다.
Farmer John은 창고의 남서쪽 입구를 통해 상자들을 한 번에 하나씩 제거할 계획입니다. 단, 포크리프트의 물리적 한계로 인해 어떤 상자의 북동쪽 모서리 기준으로 그보다 남쪽과 서쪽에 위치한 다른 상자의 일부라도 있으면, 그 상자는 제거할 수 없습니다.
예를 들어, N=4인 경우 아래와 같은 그림에서 상자 4를 제거하려면 음영 처리된 영역에 다른 상자가 없어야 합니다. 그림에서는 상자 2와 3이 상자 4의 제거를 막고 있지만, 상자 1은 제거에 방해가 되지 않습니다.
Farmer John은 모든 상자를 제거할 방법을 결정하고자 합니다. 여러분의 프로그램은 정수 M에 따라 두 가지 모드로 동작해야 합니다.
모드 1 (
M = 1 ): 1부터 N까지의 순열을 하나 생성하여 상자를 제거하는 올바른 순서를 출력합니다. 올바른 순서가 여러 가지 있다면 아무 것이나 출력해도 됩니다. 이러한 순서가 항상 존재함은 증명할 수 있습니다.모드 2 (
M = 2 ):k = 1, 2, …, N 에 대해, 만약 상자 1부터 k-1까지 이미 제거된 상태에서 상자 k를 제거할 수 있다면 1, 그렇지 않으면 0으로 이루어진 N글자의 이진 문자열을 출력합니다.
입력
첫 번째 줄에 테스트 케이스의 수
각 테스트 케이스는 다음과 같이 구성됩니다:
첫 번째 줄에 정수
이후
N 개의 줄 각각에 네 개의 정수x_{i1}, y_{i1}, x_{i2}, y_{i2} 가 공백으로 구분되어 주어지며, 이는 상자 i의 남서쪽 모서리와 북동쪽 모서리의 좌표를 나타냅니다.모든 테스트 케이스의
N 의 합은5·10^5 를 넘지 않습니다.
출력
각 테스트 케이스에 대하여:
(M = 1) 인 경우: 한 줄에N 개의 정수를 공백으로 구분하여 출력합니다.j 번째 정수는j 번째로 제거할 상자의 번호를 나타냅니다.(M = 2) 인 경우: 한 줄에N 자리 이진 문자열을 출력합니다.k 번째 문자는 상자1 부터k-1 까지 제거된 상태에서 상자k 를 제거할 수 있으면 1, 아니면 0입니다.
예제 #1
2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4
1 3 2 4
2 3 1
상자 1은 제거에 방해받지 않습니다.
상자 3은 상자 1에 의해 막힙니다.
상자 2는 상자 3에 의해 막힙니다.
상자 4는 상자 2와 3에 의해 막힙니다.
예제 #2
2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4
1011
011
첫 번째 테스트 케이스에서, 상자 2는 상자 3에 의해 막히므로 Farmer John은 상자 2를 상자 3이 제거되기 전에 제거할 수 없습니다.
로그인해야 코드를 작성할 수 있어요.