시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB695511.905%

문제

상근이는 세계 최고의 인기 게임 월드 오브 큐브를 만드는 게임 회사에 취직한다.

게임은 박스 형태의 물체 안에서 진행된다. (박스를 수학적으로 말하면 직육면체) 게임에서 이 박스 안을 홀이라고 부른다. 홀 안에 있는 플레이어에게는 초점 N개가 주어진다. 플레이어는 중심이 초점 중 하나이고, 축에 평행한 정육면체를 N개 만들어야 한다.

게임의 목표는 N개의 정육면체를 이용해서 홀을 가득 채우는 것이다. 정육면체는 겹쳐도 되고, 홀의 경계를 넘어가도 된다. 하지만, 정육면체는 모두 같은 크기를 가져야 한다.

초점이 주어졌을 때, 홀을 가득 채우는 방법 중, 정육면체의 변의 길이가 가장 작은 것을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 초점의 개수 N과 홀의 크기 X, Y, Z가 주어진다. (1 ≤ N ≤ 50, 1 ≤ X,Y,Z ≤ 109) 홀의 한 꼭짓점은 원점 (0,0,0)에 있고, 반대편 꼭짓점은 (X,Y,Z) 이다.

다음 N개 줄에는 초점의 좌표 x, y, z가 주어진다. (0 ≤ x ≤ X, 0 ≤ y ≤ Y, 0 ≤ z ≤ Z)

입력의 마지막 줄에는 0이 네 개 주어진다.

출력

각 테스트 케이스에 대해서, 다음을 출력한다.

k. D

k는 테스트 케이스의 번호이고, D는 게임의 목표를 달성하는 정육면체의 변의 길이이다. D는 정수이다. 

예제 입력 1

2 4 4 8
2 2 2
2 2 6
2 4 4 8
2 2 2
2 2 5
0 0 0 0

예제 출력 1

1. 4
2. 6
W3sicHJvYmxlbV9pZCI6IjQ4ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDRcdWI0ZGMgXHVjNjI0XHViZTBjIFx1ZDA1MFx1YmUwYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzEzOFx1YWNjNCBcdWNkNWNcdWFjZTBcdWM3NTggXHVjNzc4XHVhZTMwIFx1YWM4Y1x1Yzc4NCBcdWM2ZDRcdWI0ZGMgXHVjNjI0XHViZTBjIFx1ZDA1MFx1YmUwY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzhjXHVjNzg0IFx1ZDY4Y1x1YzBhY1x1YzVkMCBcdWNkZThcdWM5YzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWJjMTVcdWMyYTQgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YmIzY1x1Y2NiNCBcdWM1NDhcdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiAoXHViYzE1XHVjMmE0XHViOTdjIFx1YzIxOFx1ZDU1OVx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5ZDBcdWQ1NThcdWJhNzQgXHVjOWMxXHVjNzIxXHViYTc0XHVjY2I0KSBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjNzc0IFx1YmMxNVx1YzJhNCBcdWM1NDhcdWM3NDQgXHVkNjQwXHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNC4gXHVkNjQwIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNWQwXHVhYzhjXHViMjk0IFx1Y2QwOFx1YzgxMCBOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YzkxMVx1YzJlY1x1Yzc3NCBcdWNkMDhcdWM4MTAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YWNlMCwgXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWI5N2MgTlx1YWMxYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQ2NDBcdWM3NDQgXHVhYzAwXHViNGRkIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1YjI5NCBcdWFjYjlcdWNjZDBcdWIzYzQgXHViNDE4XHVhY2UwLCBcdWQ2NDBcdWM3NTggXHVhY2JkXHVhY2M0XHViOTdjIFx1YjExOFx1YzViNFx1YWMwMFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHVkMDZjXHVhZTMwXHViOTdjIFx1YWMwMFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QwOFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQ2NDBcdWM3NDQgXHVhYzAwXHViNGRkIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTUgXHVjOTExLCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NTggXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkMDhcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMgXHVkNjQwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBYLCBZLCBaXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAsIDEgJmxlOyBYLFksWiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHVkNjQwXHVjNzU4IFx1ZDU1YyBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHVjNmQwXHVjODEwICgwLDAsMClcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWJjMThcdWIzMDBcdWQzYjggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwIChYLFksWikgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDA4XHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4LCB5LCB6XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyB4ICZsZTsgWCwgMCAmbGU7IHkgJmxlOyBZLCAwICZsZTsgeiAmbGU7IFopPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViMTI0IFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5rLiBEPFwvcHJlPlxyXG5cclxuPHA+a1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCwgRFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViOTdjIFx1YjJlY1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NTggXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gRFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDg4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldvcmxkIG9mIGN1YmVzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UmcnNxdW87dmUgYmVlbiBhc3NpZ25lZCB0aGUgdGFzayBvZiBwcm9ncmFtbWluZyBhIG5ldyB2aWRlbyBnYW1lIGNhbGxlZCB0aGUgV29ybGQgb2YgQ3ViZXMuIFRoZSBnYW1lIGlzIHBsYXllZCBpbnNpZGUgYSBib3gtc2hhcGVkIG9iamVjdCAobWF0aGVtYXRpY2FsbHkgc3BlYWtpbmc6IGEgcmVjdGFuZ3VsYXIgY3Vib2lkKSB3aGljaCB3ZSZyc3F1bztsbCBjYWxsIHRoZSBoYWxsLiBXaXRoaW4gdGhlIGhhbGwsIHRoZSBwbGF5ZXIgaXMgYXNzaWduZWQgTiBwb3NpdGlvbnMsIGNhbGxlZCBmb2NhbCBwb2ludHMuIFRoZSBwbGF5ZXIgbXVzdCBidWlsZCBOIGN1YmVzLCBhbGwgcGFyYWxsZWwgdG8gdGhlIGF4ZXMsIGFuZCBlYWNoIGlzIGNlbnRlcmVkIGFyb3VuZCBvbmUgb2YgdGhlIGZvY2FsIHBvaW50cy4gVGhlIG1pc3Npb24gaXMgZm9yIHRoZSBOIGN1YmVzIHRvIGNvbXBsZXRlbHkgXHVmYjAxbGwgdGhlIGhhbGwuIEl0IGlzIGFjY2VwdGFibGUgZm9yIHRoZSBjdWJlcyB0byBvdmVybGFwIGFuZCBldmVuIHRvIGV4dGVuZCBiZXlvbmQgdGhlIGhhbGwuIFRoZSBvbmx5IHJlc3RyaWN0aW9uIGlzIHRoYXQgYWxsIHRoZSBjdWJlcyBtdXN0IGJlIG9mIGVxdWFsIHNpZGUtbGVuZ3RoLiBBbmQgd2Ugd291bGQgbGlrZSB5b3UgdG8gY29tcHV0ZSB0aGUgbWluaW11bSBzdWNoIGxlbmd0aC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIHVzaW5nIE4rMSBsaW5lcy48XC9wPlxyXG5cclxuPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIHNwZWNpXHVmYjAxZXMgZm91ciBpbnRlZ2VyczogKDEgJmxlOyBOICZsZTsgNTApIGlzIHRoZSBudW1iZXIgb2YgY3ViZXMgYW5kICgxICZsZTsgWCwgWSwgWiAmbGU7IDEwPHN1cD45PFwvc3VwPikgYXJlIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBoYWxsLiBPbmUgY29ybmVyIG9mIHRoZSBoYWxsIGlzIGF0IHRoZSBvcmlnaW4gKDAsMCwwKSwgd2l0aCB0aGUgb3Bwb3NpbmcgY29ybmVyIGF0IChYLCBZLCBaKS48XC9wPlxyXG5cclxuPHA+TiBsaW5lcyBmb2xsb3csIGVhY2ggc3BlY2lmeWluZyB0aGUgY29vcmRpbmF0ZSBvZiBhIGZvY2FsIHBvaW50IHVzaW5nIHRocmVlIGludGVnZXJzOiAoMCAmbGU7IHggJmxlOyBYKSwgKDAgJmxlOyB5ICZsZTsgWSApLCBhbmQgKDAgJmxlOyB6ICZsZTsgWikuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBmb3VyIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPmsuIFx1MDAwMkQ8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCBvbmUsKSBhbmQgRCBpcyBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBzbWFsbGVzdCBsZW5ndGggb2YgdGhlIGN1YmUgZWRnZXMgc28gdGhhdCB0aGUgTiBjdWJlcyB3b3VsZCBjb21wbGV0ZWx5IFx1ZmIwMWxsIHRoZSBoYWxsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=