시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 13 3 3 37.500%

문제

엔트는 숲의 수호자이다. 중간계에서 가장 나이가 많은 엔트인 나무수염은 자신이 보호해야 하는 나무와 자신이 젊은 엔트 동료인 브레갈라드가 보호해야 하는 나무를 결정하려고 한다.

그들은 직사각형 모양의 팡고른 숲을 보호하고 있고, 이 숲의 나무는 짝수개이다. 나무수염은 직선 경계선을 그어 한 쪽은 자신이, 한 쪽은 브레갈라드의 구역으로 나눌 것이다. 만약, 각 구역에 있는 나무의 수와 면적이 다르다면 이들은 일 년에 한 마디씩 몇 만 년동안 싸울 것 이기 때문에, 공평하게 나누어야 한다.

만약, 어떤 나무가 경계선 위에 있다면, 둘 중 한 구역에 속해야 한다. 두 구역에 모두 속하는 나무는 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 나무의 수 N, 숲의 너비 W, 숲의 높이 H가 주어진다. 숲의 꼭지점은 (0,0), (W,0), (0,H), (W,H)가 된다. 다음 N개의 줄에는 나무의 좌표가 주어진다. (2 ≤ N ≤ 500000, 2 ≤ W,H ≤ 10000, N은 짝수, W와 H는 동시에 짝수가 아니다)

모든 나무의 좌표는 숲 안에 있고, (0 < x < W, 0 < y < H)를 만족한다. 나무의 위치가 겹치는 경우는 없다.

입력은 N = W = H = 0인 경우에 끝난다.

출력

각 테스트 케이스에 대해서, N/2개 줄을 출력해야 한다. 각 줄은 나무수염이 보호하는 구역에 있는 나무의 좌표이다.

예제 입력

2 5 6
2 3
3 3
4 5 6
1 5
2 5
3 5
4 5
4 10 11
5 1
5 2
5 3
5 4
0 0 0

예제 출력

3 3
1 5
2 5
5 1
5 2

힌트