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

문제

어떤 신문엔 이러한 퍼즐이 있다. 3x3의 표에 영문자가 하나씩 있으며, 이 영문자들을 사용해서 최대한 많은 영단어를 만드는 것이 목표이다. 예를 들면, 아래의 퍼즐판에서는 'LINT', 'TILL', 'BRILLIANT' 등을 만들 수 있다.


단어는 최소 4글자 이상이어야 하며, 한 글자당 최대 1번만 사용할 수 있다. 따라서 10글자 이상의 단어는 만들 수 없다. 또한, 표의 정중앙에 있는 글자는 반드시 사용해야 한다. 위 퍼즐판의 경우 'I'는 반드시 사용해야 한다.

따라서 어떤 글자가 가운데에 있느냐에 따라 퍼즐의 난이도는 천차만별일 것이다. 퍼즐 제작자 남규는 퍼즐판에 어떤 글자를 배치할지는 결정했으나 멍청해서 어떤 글자를 가운데에 놓을지까지는 정하지 못했다.

보다 못한 조수 재혁이가 어떤 글자를 놓아야 퍼즐이 가장 쉬워지는지(즉, 만들 수 있는 단어의 개수가 가장 많음), 또 어떤 글자를 놓아야 퍼즐이 가장 어려워지는지(즉, 만들 수 있는 단어의 개수가 가장 적음)를 알려주려고 한다. 그러나 재혁이가 망각한 사실이 있으니 자신도 멍청하다는 것이었다. 따라서 당신이 이 문제를 대신 풀어주어야 한다.

또한 문제 속 세상의 사람들은 우리보다도 멍청해서, 우리보다 훨씬 적은 수의 영단어를 사용한다. 이 단어들을 모두 담고 있는 사전과 퍼즐판에 배치할 9개의 문자가 주어졌을 때, 문제를 푸는 프로그램을 작성하시오.

입력

입력의 처음에는 사전을 이루는 최대 20만 개의 단어가 주어진다. 각 단어는 4~9글자의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 또한 사전순으로 정렬되어 있다. 사전 입력의 끝에는 한 줄에 걸쳐 '-' 한 글자가 주어진다.

그 다음부터 여러 개의 퍼즐판이 주어진다. 각 퍼즐판은 9개의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 맨 끝에는 한 줄에 걸쳐 '#' 한 글자가 주어진다.

출력

각 퍼즐판마다 정답을 예제 형식에 맞게 한 줄에 하나씩 출력한다.

각 문제마다 정답의 개수를 가장 적게 하기 위해 정중앙에 놓아야 할 문자들과 그때의 정답 개수, 정답의 개수를 가장 많게 하기 위해 정중앙에 놓아야 할 문자들과 그 때의 정답 개수를 공백으로 구분하여 출력한다.

한 개 이상의 문자가 답을 만족할 경우 문자들을 알파벳순으로 정렬하여 출력하며, 중복된 문자는 출력하지 않는다. 첫 번째 예제 출력에서 보듯이 I나 L은 여러 번 등장하지만 한 번씩만 출력하였다.

예제 입력 1

APPLE
BANANA
BANE
BRILLIANT
LINT
PALE
PROBLEM
TILL
TRILL
-
LARBITNLI
LEPAPBNNA
LEPAPBNAM
#

예제 출력 1

AB 1 ILT 4
BN 1 AE 3
M 0 AE 3
W3sicHJvYmxlbV9pZCI6IjExNDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjQgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMmUwXHViYjM4XHVjNWQ0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjNzg4XHViMmU0LiAzeDNcdWM3NTggXHVkNDVjXHVjNWQwIFx1YzYwMVx1YmIzOFx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHVjNjAxXHViYjM4XHVjNzkwXHViNGU0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YzYwMVx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmFhOVx1ZDQ1Y1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgXHVjNTQ0XHViNzk4XHVjNzU4IFx1ZDM3Y1x1Yzk5MFx1ZDMxMFx1YzVkMFx1YzExY1x1YjI5NCAmIzM5O0xJTlQmIzM5OywgJiMzOTtUSUxMJiMzOTssICYjMzk7QlJJTExJQU5UJiMzOTsgXHViNGYxXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE0OFwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTFweDsgd2lkdGg6MTExcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+PGJyIFwvPlxyXG5cdWIyZThcdWM1YjRcdWIyOTQgXHVjZDVjXHVjMThjIDRcdWFlMDBcdWM3OTAgXHVjNzc0XHVjMGMxXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVkNTVjIFx1YWUwMFx1Yzc5MFx1YjJmOSBcdWNkNWNcdWIzMDAgMVx1YmM4OFx1YjljYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIDEwXHVhZTAwXHVjNzkwIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIyZThcdWM1YjRcdWIyOTQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVkNDVjXHVjNzU4IFx1YzgxNVx1YzkxMVx1YzU1OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3MDQgXHVkMzdjXHVjOTkwXHVkMzEwXHVjNzU4IFx1YWNiZFx1YzZiMCAmIzM5O0kmIzM5O1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNTMwXHViNzdjXHVjMTFjIFx1YzViNFx1YjVhNCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVhYzAwXHVjNmI0XHViMzcwXHVjNWQwIFx1Yzc4OFx1YjI5MFx1YjBkMFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkMzdjXHVjOTkwXHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YjI5NCBcdWNjOWNcdWNjMjhcdWI5Y2NcdWJjYzRcdWM3N2MgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQzN2NcdWM5OTAgXHVjODFjXHVjNzkxXHVjNzkwIFx1YjBhOFx1YWRkY1x1YjI5NCBcdWQzN2NcdWM5OTBcdWQzMTBcdWM1ZDAgXHVjNWI0XHViNWE0IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NjBcdWM5YzBcdWIyOTQgXHVhY2IwXHVjODE1XHVkNTg4XHVjNzNjXHViMDk4IFx1YmE0ZFx1Y2NhZFx1ZDU3NFx1YzExYyBcdWM1YjRcdWI1YTQgXHVhZTAwXHVjNzkwXHViOTdjIFx1YWMwMFx1YzZiNFx1YjM3MFx1YzVkMCBcdWIxOTNcdWM3NDRcdWM5YzBcdWFlNGNcdWM5YzBcdWIyOTQgXHVjODE1XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2Y0XHViMmU0IFx1YmFiYlx1ZDU1YyBcdWM4NzBcdWMyMTggXHVjN2FjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YzViNFx1YjVhNCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDM3Y1x1Yzk5MFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjMjZjXHVjNmNjXHVjOWMwXHViMjk0XHVjOWMwKFx1Yzk4OSwgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzRjKSwgXHViNjEwIFx1YzViNFx1YjVhNCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDM3Y1x1Yzk5MFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNWI0XHViODI0XHVjNmNjXHVjOWMwXHViMjk0XHVjOWMwKFx1Yzk4OSwgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzRjKVx1Yjk3YyBcdWM1NGNcdWI4MjRcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjN2FjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YjlkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWMyZTRcdWM3NzQgXHVjNzg4XHVjNzNjXHViMmM4IFx1Yzc5MFx1YzJlMFx1YjNjNCBcdWJhNGRcdWNjYWRcdWQ1NThcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHVjNWM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHViMmY5XHVjMmUwXHVjNzc0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViMzAwXHVjMmUwIFx1ZDQ4MFx1YzViNFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWJiMzhcdWM4MWMgXHVjMThkIFx1YzEzOFx1YzBjMVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHVjNmIwXHViOWFjXHViY2Y0XHViMmU0XHViM2M0IFx1YmE0ZFx1Y2NhZFx1ZDU3NFx1YzExYywgXHVjNmIwXHViOWFjXHViY2Y0XHViMmU0IFx1ZDZlOFx1YzUyYyBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzYwMVx1YjJlOFx1YzViNFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjJmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVjODA0XHVhY2ZjIFx1ZDM3Y1x1Yzk5MFx1ZDMxMFx1YzVkMCBcdWJjMzBcdWNlNThcdWQ1NjAgOVx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAyMFx1YjljYyBcdWFjMWNcdWM3NTggXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YjJlOFx1YzViNFx1YjI5NCA0fjlcdWFlMDBcdWM3OTBcdWM3NTggXHVjNjAxXHVjNWI0IFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjMGFjXHVjODA0IFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgJiMzOTstJiMzOTsgXHVkNTVjIFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGNcdWJkODBcdWQxMzAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQzN2NcdWM5OTBcdWQzMTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMzdjXHVjOTkwXHVkMzEwXHVjNzQwIDlcdWFjMWNcdWM3NTggXHVjNjAxXHVjNWI0IFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5ZTggXHViMDVkXHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwICYjMzk7IyYjMzk7IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQzN2NcdWM5OTBcdWQzMTBcdWI5YzhcdWIyZTQgXHVjODE1XHViMmY1XHVjNzQ0IFx1YzYwOFx1YzgxYyBcdWQ2MTVcdWMyZGRcdWM1ZDAgXHViOWRlXHVhYzhjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YmIzOFx1YzgxY1x1YjljOFx1YjJlNCBcdWM4MTVcdWIyZjVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTVcdWM5MTFcdWM1NTlcdWM1ZDAgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU2MCBcdWJiMzhcdWM3OTBcdWI0ZTRcdWFjZmMgXHVhZGY4XHViNTRjXHVjNzU4IFx1YzgxNVx1YjJmNSBcdWFjMWNcdWMyMTgsIFx1YzgxNVx1YjJmNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhYzAwXHVjN2E1IFx1YjljZVx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzgxNVx1YzkxMVx1YzU1OVx1YzVkMCBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTYwIFx1YmIzOFx1Yzc5MFx1YjRlNFx1YWNmYyBcdWFkZjggXHViNTRjXHVjNzU4IFx1YzgxNVx1YjJmNSBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWIyZjVcdWM3NDQgXHViOWNjXHVjODcxXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWJiMzhcdWM3OTBcdWI0ZTRcdWM3NDQgXHVjNTRjXHVkMzBjXHViY2IzXHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzAsIFx1YzkxMVx1YmNmNVx1YjQxYyBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjZDljXHViODI1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1XHVjNWQwXHVjMTFjIFx1YmNmNFx1YjRlZlx1Yzc3NCBJXHViMDk4IExcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkNTVjIFx1YmM4OFx1YzUyOVx1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTE0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNlbnRyYWwgVGFyZ2V0IiwiZGVzY3JpcHRpb24iOiI8cD5UYXJnZXQgaXMgYSBjb21tb24gbmV3c3BhcGVyIHdvcmQgcHV6emxlIGluIHdoaWNoIHlvdSBhcmUgZ2l2ZW4gYSBncmlkIGNvbnRhaW5pbmcgbmluZSBsZXR0ZXJzIGFuZCBtdXN0IGZpbmQgYXMgbWFueSB3b3JkcyBhcyBwb3NzaWJsZSB1c2luZyB0aG9zZSBsZXR0ZXJzLiBGb3IgZXhhbXBsZSwgdGhlIGxldHRlcnMgaW4gdGhlIGZvbGxvd2luZyBncmlkIGNhbiBiZSB1c2VkIHRvIGZvcm0gdGhlIHdvcmRzICZsc3F1bztMSU5UJnJzcXVvOywgJmxzcXVvO1RJTEwmcnNxdW87LCBhbmQgJmxzcXVvO0JSSUxMSUFOVCZyc3F1bzssIGFtb25nIG90aGVyczo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE0OFwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTFweDsgd2lkdGg6MTExcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V29yZHMgbXVzdCBiZSBhdCBsZWFzdCBmb3VyIGxldHRlcnMgaW4gbGVuZ3RoLCBhbmQgbWF5IHVzZSBlYWNoIGxldHRlciBpbiB0aGUgZ3JpZCBhdCBtb3N0IG9uY2UuIChUaHVzIHRoZXkgY2FuIGJlIG5vIGxvbmdlciB0aGFuIG5pbmUgbGV0dGVycy4pIEZ1cnRoZXJtb3JlLCB0aGV5IG11c3QgY29udGFpbiB0aGUgZ3JpZCZyc3F1bztzIGNlbnRyYWwgbGV0dGVyLCBpbiB0aGlzIGNhc2UgJmxzcXVvO0kmcnNxdW87LjxcL3A+XHJcblxyXG48cD5PbmNlIHRoZSBwdXp6bGUtbWFrZXIgaGFzIGNob3NlbiB0aGUgbGV0dGVycyB0byBwdXQgaW4gdGhlIGdyaWQsIHRoZSBjaG9pY2Ugb2Ygd2hpY2ggaXMgdG8gYmUgdGhlIGNlbnRyYWwgbGV0dGVyIG1ha2VzIGEgZ3JlYXQgZGlmZmVyZW5jZSB0byB0aGUgbnVtYmVyIG9mIHdvcmRzIHRoYXQgY2FuIGJlIG1hZGUsIGFuZCBoZW5jZSB0aGUgZGlmZmljdWx0eSBvZiB0aGUgcHV6emxlLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRoZSBwdXp6bGUtbWFrZXImcnNxdW87cyBhc3Npc3RhbnQuIFlvdSBoYXZlIGJlZW4gZ2l2ZW4gdGhlIHB1enpsZS1tYWtlciZyc3F1bztzIGRpY3Rpb25hcnkgb2YgdmFsaWQgd29yZHMsIGFuZCBtdXN0IGFuYWx5c2UgcG90ZW50aWFsIGdyaWRzIHRvIHNlZSBob3cgbWFueSB3b3JkcyBmcm9tIHRoZSBkaWN0aW9uYXJ5IGNhbiBiZSBmb3JtZWQgZnJvbSB0aGVtLiBPbiBlYWNoIGdyaWQsIHRoZSBwdXp6bGUtbWFrZXIgaGFzIG5vdCB5ZXQgZGVjaWRlZCB3aGljaCBsZXR0ZXIgdG8gcHV0IGluIHRoZSBjZW50cmFsIHBvc2l0aW9uLCBhbmQgd291bGQgbGlrZSB0byBrbm93IHdoaWNoIGNob2ljZXMgd291bGQgcGVybWl0IHRoZSBzbWFsbGVzdCBhbmQgbGFyZ2VzdCBudW1iZXJzIG9mIHdvcmRzIHRvIGJlIGZvcm1lZC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3RlbnRpYWwgZ3JpZCwgeW91IG11c3QgZmluZCBvdXQgd2hpY2ggbGV0dGVyIG9yIGxldHRlcnMsIHdoZW4gcGxhY2VkIGluIHRoZSBjZW50cmFsIHBvc2l0aW9uLCBwZXJtaXQgdGhlIGZld2VzdCB3b3JkcyBmcm9tIHRoZSBkaWN0aW9uYXJ5IHRvIGJlIGZvcm1lZCBhY2NvcmRpbmcgdG8gdGhlIHJ1bGVzLiBBbmQgeW91IG11c3QgZmluZCBvdXQganVzdCBob3cgbWFueSB3b3JkcyB0aGF0IGlzLiBBbmQgc2ltaWxhcmx5IHlvdSBtdXN0IGZpbmQgb3V0IHdoaWNoIGxldHRlciBvciBsZXR0ZXJzIHBsYWNlZCBjZW50cmFsbHkgcGVybWl0IHRoZSBtb3N0IGRpY3Rpb25hcnkgd29yZHMgdG8gYmUgZm9ybWVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgYSBkaWN0aW9uYXJ5IG9mIHVwIHRvIDIwMCwwMDAgd29yZHMgZm9sbG93ZWQgYnkgYW55IG51bWJlciBvZiBncmlkcyB0byBiZSBhbmFseXNlZCBhZ2FpbnN0IHRoYXQgZGljdGlvbmFyeS48XC9wPlxyXG5cclxuPHA+VGhlIGRpY3Rpb25hcnkgY29uc2lzdHMgb2Ygd29yZHMgd2l0aCBiZXR3ZWVuIGZvdXIgYW5kIG5pbmUgdXBwZXJjYXNlIGxldHRlcnMsIG9uZSBwZXIgbGluZSwgZ2l2ZW4gaW4gYWxwaGFiZXRpY2FsIG9yZGVyLiBBIHNpbmdsZSAmbHNxdW87LSZyc3F1bzsgb24gYSBsaW5lIGJ5IGl0c2VsZiBpbmRpY2F0ZXMgdGhlIGVuZCBvZiB0aGUgZGljdGlvbmFyeS48XC9wPlxyXG5cclxuPHA+U3Vic2VxdWVudCBsaW5lcyBlYWNoIGNvbnRhaW4gb25lIGdyaWQgdG8gYmUgYW5hbHlzZWQuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29uc2lzdHMgb2YgZXhhY3RseSBuaW5lIHVwcGVyY2FzZSBsZXR0ZXJzLiBBIHNpbmdsZSAmbHNxdW87IyZyc3F1bzsgb24gYSBsaW5lIGJ5IGl0c2VsZiBpbmRpY2F0ZXMgdGhlIGVuZCBvZiBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCBncmlkLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgY2VudHJhbCBsZXR0ZXIocykgdGhhdCBwcm9kdWNlIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygd29yZHMgYW5kIHRoYXQgbnVtYmVyIGl0c2VsZiwgYW5kIHRoZSBjZW50cmFsIGxldHRlcihzKSB0aGF0IHByb2R1Y2UgdGhlIGdyZWF0ZXN0IG51bWJlciBvZiB3b3JkcyBhbmQgdGhhdCBudW1iZXIgaXRzZWxmLiBXaGVyZSB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIGxldHRlciB0aGF0IHByb2R1Y2VzIHRoZSBtaW5pbXVtIG9yIG1heGltdW0sIG91dHB1dCBhbGwgdGhlIGFwcHJvcHJpYXRlIGxldHRlcnMgaW4gYWxwaGFiZXRpY2FsIG9yZGVyICh3aXRob3V0IGR1cGxpY2F0ZXMsIGV2ZW4gaWYgYSBsZXR0ZXIgYXBwZWFycyBpbiB0aGUgZ3JpZCBtb3JlIHRoYW4gb25jZSZtZGFzaDtzdWNoIGFzIEkgb3IgTCBpbiB0aGUgZ3JpZCBwaWN0dXJlZCkuIFNlcGFyYXRlIGVhY2ggbnVtYmVyIGFuZCBncm91cCBvZiBsZXR0ZXJzIHdpdGggYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2006 I번

  • 문제를 번역한 사람: kks227