회의실 배정

문제 정보

문제

회사가 빠르게 성장하면서 사람들이 늘어나면 가장 먼저 부족해지는 것이 화장실과 회의실입니다. 빠르게 확장하고 있는 치선이네 회사에서는 최근 회의실이 문제가 되고 있습니다.

치선이네 회사에는 N개의 팀이 있는데 이 팀들은 모두 금요일 오후에 주간 회의를 하고, 한 달의 마지막 날에 월간 회의를 합니다. 이번 달에는 금요일과 한 달의 마지막 날이 겹치는데, 공교롭게도 에어콘 공사 때문에 그 날 한 개의 회의실밖에 사용할 수 없습니다. 때문에 각 팀은 주간 회의와 월간 회의 중 하나만을 하기로 했는데, 하나밖에 없는 회의실을 어떻게 나누어 사용할지 정하는 일이 막내인 치선이에게 떨어졌습니다.

각 팀마다 주간 회의를 하는 시간과 월간 회의를 하는 시간은 정해져 있습니다. 회의실은 한 번에 한 개의 팀만 사용할 수 있으며, 한 번 시작한 회의를 중간에 끊을 수 없습니다. 단 앞 팀이 회의를 끝내자마자 다음 팀이 곧장 회의를 시작하는 것은 가능하다고 합시다. 각 팀마다 두 회의의 시작 시간과 끝 시간이 주어질 때, 각 팀에 두 시간 중 하나를 배정해서 회의 시간이 서로 겹치지 않도록 할 수 있는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 팀의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에 각 4개의 정수로, 각 팀의 주간 회의 시간 ai, bi (0 <= ai < bi < 43200) 과 월간 회의 시간 ci, di (0 <= ci < di < 43200) 이 주어집니다. 이 때 [ai,bi) 와 [ci,di) 구간이 각 팀의 회의 시간을 나타냅니다.

출력

만약 테스트 케이스에 주어진 팀들이 모두 회의실을 사용할 수 있는 방법이 없다면, 한 줄 IMPOSSIBLE 을 출력합니다. 만약 회의실을 사용할 수 있는 방법이 있다면, 한 줄에 POSSIBLE 을 출력한 뒤 그 후 N 줄에 각 2개의 정수로 각 팀이 회의실을 사용할 시작 시간과 끝 시간을 출력합니다. 만약 답이 여러 개 있을 수 있다면 아무 것이나 출력해도 좋습니다.

예제 입력

3
2
1 10 10 20
1 10 10 20
3
1 10 10 20
1 10 10 20
1 10 10 20
3
2 5 6 9
1 3 8 10
4 7 11 12

예제 출력

POSSIBLE
10 20
1 10
IMPOSSIBLE
POSSIBLE
2 5
8 10
11 12

노트

18개의 댓글이 있습니다.