시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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개 줄을 출력해야 한다. 각 줄은 나무수염이 보호하는 구역에 있는 나무의 좌표이다.

예제 입력 1

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

예제 출력 1

3 3
1 5
2 5
5 1
5 2

힌트

W3sicHJvYmxlbV9pZCI6IjQ0MzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjFcdWFjZTBcdWI5NzggXHVjMjMyIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1ZDRcdWQyYjhcdWIyOTQgXHVjMjMyXHVjNzU4IFx1YzIxOFx1ZDYzOFx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjOTExXHVhYzA0XHVhY2M0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWIwOThcdWM3NzRcdWFjMDAgXHViOWNlXHVjNzQwIFx1YzVkNFx1ZDJiOFx1Yzc3OCBcdWIwOThcdWJiMzRcdWMyMThcdWM1ZmNcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmNmNFx1ZDYzOFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViMDk4XHViYjM0XHVjNjQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM4MGFcdWM3NDAgXHVjNWQ0XHVkMmI4IFx1YjNkOVx1YjhjY1x1Yzc3OCBcdWJlMGNcdWI4MDhcdWFjMDhcdWI3N2NcdWI0ZGNcdWFjMDAgXHViY2Y0XHVkNjM4XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhZGY4XHViNGU0XHVjNzQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVkMzIxXHVhY2UwXHViOTc4IFx1YzIzMlx1Yzc0NCBcdWJjZjRcdWQ2MzhcdWQ1NThcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjMyXHVjNzU4IFx1YjA5OFx1YmIzNFx1YjI5NCBcdWM5ZGRcdWMyMThcdWFjMWNcdWM3NzRcdWIyZTQuIFx1YjA5OFx1YmIzNFx1YzIxOFx1YzVmY1x1Yzc0MCBcdWM5YzFcdWMxMjAgXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzQ0IFx1YWRmOFx1YzViNCBcdWQ1NWMgXHVjYWJkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCwgXHVkNTVjIFx1Y2FiZFx1Yzc0MCBcdWJlMGNcdWI4MDhcdWFjMDhcdWI3N2NcdWI0ZGNcdWM3NTggXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwYyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YzIxOFx1YzY0MCBcdWJhNzRcdWM4MDFcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0XHViYTc0IFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWM3N2MgXHViMTQ0XHVjNWQwIFx1ZDU1YyBcdWI5YzhcdWI1MTRcdWM1MjkgXHViYTg3IFx1YjljYyBcdWIxNDRcdWIzZDlcdWM1NDggXHVjMmY4XHVjNmI4IFx1YWM4MyBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWNjXHVjNTdkLCBcdWM1YjRcdWI1YTQgXHViMDk4XHViYjM0XHVhYzAwIFx1YWNiZFx1YWNjNFx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWI0NTggXHVjOTExIFx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHVjMThkXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWJhYThcdWI0NTAgXHVjMThkXHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YzIxOCBOLCBcdWMyMzJcdWM3NTggXHViMTA4XHViZTQ0IFcsIFx1YzIzMlx1Yzc1OCBcdWIxOTJcdWM3NzQgSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIzMlx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NDAgKDAsMCksIChXLDApLCAoMCxIKSwgKFcsSClcdWFjMDAgXHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDUwMDAwMCwgMiAmbGU7IFcsSCAmbGU7IDEwMDAwLCBOXHVjNzQwIFx1YzlkZFx1YzIxOCwgV1x1YzY0MCBIXHViMjk0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM5ZGRcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0KTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHViMDk4XHViYjM0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWMyMzIgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YWNlMCwgKDAgJmx0OyB4ICZsdDsgVywgMCAmbHQ7IHkgJmx0OyBIKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVhY2I5XHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBOID0gVyA9IEggPSAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBOXC8yXHVhYzFjIFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1YjA5OFx1YmIzNFx1YzIxOFx1YzVmY1x1Yzc3NCBcdWJjZjRcdWQ2MzhcdWQ1NThcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVjODhjXHVkNDVjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ0MzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQYXJ0aXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBFbnRzIGFyZSBrbm93biBhcyB0aGUgc2hlcGhlcmRzIG9mIHRoZSBmb3Jlc3QuIFRyZWViZWFyZCwgdGhlIG9sZGVzdCBsaXZpbmcgRW50IGluIE1pZGRsZSBFYXJ0aCwgbmVlZHMgdG8gZGV0ZXJtaW5lIHdoaWNoIHRyZWVzIGhlIGlzIHRvIHNoZXBoZXJkIGFuZCB3aGljaCB0cmVlcyBhcmUgdG8gYmUgc2hlcGhlcmRlZCBieSBoaXMgeW91bmcgZmVsbG93IEVudCwgQnJlZ2FsYWQuIFRoZXkgaGF2ZSBhIHJlY3Rhbmd1bGFyIHBvcnRpb24gb2YgRmFuZ29ybiBmb3Jlc3QgY29udGFpbmluZyBhbiBldmVuIG51bWJlciBvZiB0cmVlcyB0aGF0IHRoZXkgbmVlZCB0byBkaXZpZGUgaW50byB0d28gcGllY2VzIHVzaW5nIGEgc2luZ2xlIHN0cmFpZ2h0IGJvdW5kYXJ5IGxpbmUuIEluIG9yZGVyIHRvIGVxdWl0YWJseSBkaXN0cmlidXRlIHRoZSB3b3JrbG9hZCwgVHJlZWJlYXJkIGFuZCBCcmVnYWxhZCBoYXZlIGRlY2lkZWQgdGhhdCBlYWNoIG9mIHRoZWlyIGhhbHZlcyBvZiB0aGUgZm9yZXN0IG5lZWQgdG8gY29udGFpbiBlcXVhbCBhcmVhIGFuZCBjb250YWluIGFuIGVxdWFsIG51bWJlciBvZiB0cmVlcy4gSWYgYSB0cmVlIGxpZXMgZXhhY3RseSBvbiB0aGUgZGl2aWRpbmcgbGluZSwgdGhlbiB0aGF0IHRyZWUgaXMgY291bnRlZCBpbiBvbmUgb3IgdGhlIG90aGVyIG9mIHRoZSBoYWx2ZXMgb2YgdGhlIGZvcmVzdCBidXQgbm90IGJvdGguIEFueSB0cmVlIGV4YWN0bHkgb24gdGhlIGRpdmlkaW5nIGxpbmUgbWF5IGJlIGFzc2lnbmVkIHRvIGVpdGhlciBUcmVlYmVhcmQgb3IgQnJlZ2FsYWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2YgbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBsaW5lIHdpdGggMyBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgTiwgVywgYW5kIEgsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdHJlZXMsIHRoZSB3aWR0aCBvZiB0aGUgZm9yZXN0LCBhbmQgdGhlIGhlaWdodCBvZiB0aGUgZm9yZXN0LCByZXNwZWN0aXZlbHkuIFRoZSBmb3Jlc3QmIzM5O3MgZm91ciBjb3JuZXJzIGFyZSAoMCwgMCksIChXLCAwKSwgKDAsIEgpLCBhbmQgKFcsIEgpLiBGb2xsb3dpbmcgdGhpcyBsaW5lIGFyZSBOIGxpbmVzIGVhY2ggd2l0aCBhIHBhaXIgb2Ygc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHhpIGFuZCB5aSBkZW5vdGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIGl0aCB0cmVlLiBGdXJ0aGVybW9yZSw8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4yICZsZTsgTiAmbGU7IDUwMDAwLCAyICZsZTsgVyAmbGU7IDEwMDAwLCAyICZsZTsgSCAmbGU7IDEwMDAwLCBOIGlzIGV2ZW4sIFcgYW5kIEggYXJlIG5vdCBib3RoIGV2ZW4uPFwvbGk+XHJcblx0PGxpPjAgJmx0OyB4aSAmbHQ7IFcsIDAgJmx0OyB5aSAmbHQ7IEggZm9yIGFsbCBpLiBBbGwgbG9jYXRpb25zIG9mIHRyZWVzIGFyZSBkaXN0aW5jdC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbnB1dCB3aWxsIGJlIHRlcm1pbmF0ZWQgd2l0aCBhIGNhc2Ugd2hlcmUgTiA9IFcgPSBIID0gMCwgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvdXQgTlwvMiBsaW5lcy4gT24gZWFjaCBsaW5lLCBwcmludCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHhpIGFuZCB5aSwgZGVub3RpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBpdGggdHJlZSBpbiB0aGUgaGFsZiBvZiB0aGUgZm9yZXN0IHRoYXQgaXMgdG8gYmUgc2hlcGhlcmRlZCBieSBUcmVlYmVhcmQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d