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

문제

숭이는 자신이 가신 열쇠더미의 절반을 혜빈이에게 주려고 한다. 열쇠는 나선형을 따라 밀어서 열쇠 고리에 걸거나 분리할 수 있다. 같은 방식으로 열쇠 고리도 서로 연결하거나 분리 할 수 있다. 열쇠 고리에 열쇠를 연결하는 작업은 성가신 작업이기 때문에(숭이는 혜빈이가 손톱에 네일아트를 해주기 때문에 손톱을 다쳐선 안된다) 이 과정을 최소로 하여 연결하려고 한다.

열쇠를 연결하거나 분리하거나, 열쇠 고리를 연결하거나 분리하는 것은 하나의 작업으로 간주된다. 열쇠를 밀어서 연결하거나 분리하는것은 고리를 연결하거나 분리하는 것에 비해 비해 매우 힘들기 때문에 숭이는 열쇠를 연결하거나 분리하는 과정을 최소로 하려고 한다. 만약 열쇠를 연결하거나 분리하는 횟수가 서로 같다면 열쇠 고리를 연결하거나 분리하는 과정을 최소로 해야 한다.

모든 작업이 완료되면, 숭이는 혜빈이에게 열쇠 더미를 건네준다(정확히 숭이꺼, 혜빈이꺼 두덩이로 분리되어야 한다). 예외가 되는 경우는 숭이가 갖는 열쇠 더미가 없거나 혜빈이에게 줄 수 있는 열쇠 더미가 없는 경우이다. 각각의 열쇠는 반드시 하나의 고리에 연결되어 있어야 한다. 열쇠 고리는 남은것이 생길 수 있다. 이때에는 두 그룹에서 분리시킨다

아래의 왼쪽 그림은 네개의 열쇠와 세개의 고리로 연결되어 있는 초기 상태를 나타낸다. 숭이는 혜빈이에게 2개의 열쇠인 N,R을 주려고 한다. 이때에 두 번의 열쇠 동작과 한번의 고리 동작으로 줄 수 있다. 이러한 결과가 아래의 오른쪽 그림이다.

입력

각각의 테스트 케이스는 하나 또는 여러개의 줄로 이루어져 있다. 각각의 테스트 케이스는 2개 문자로 이루어져 있다. 영어 소문자는 열쇠 고리를 나타내며 대문자는 열쇠를 나타낸다. 입력된 2개의 문자는 열쇠와 고리가 연결된 상태를 나타내거나, 고리와 고리가 연결된 상태를 나타낸다. 테스트 케이스 마지막 줄에는 0이 주어진다.

A부터 M까지의 열쇠는 숭이가 갖고, N부터 Z까지의 열쇠는 혜빈이에게 준다.

두 개의 문자가 모두 대문자인 경우는 없다. 테스트 케이스 내에서 같은 쌍으로 이루어진 문자열은 주어지지 않는다. 각각의 열쇠는 반드시 하나의 고리에 연결되어야 한다. 초기에 주어지는 열쇠 상태에서 고리에는 반드시 열쇠가 연결되어 있다(분리하면서 고리만 존재하는 경우는 발생할 수 있다). 존재하는 모든 열쇠와 고리는 반드시 한번 이상 주어진다.

출력

각각의 테스트 케이스에 대해서 열쇠를 연결하거나 분리하는 최소 횟수와 고리를 연결하거나 분리하는 최소 횟수를 출력한다.

만일 그러한 경우가 없다면 "impossible"을 출력한다.

예제 입력 1

ab
bc
aA
aN
Rb
cB
0
aA
bB
Cc
0
aA
aZ
0
aA
bB
cC
xX
yY
ax
xb
by
yc
0

예제 출력 1

Case 1: 2 1
Case 2: 0 2
Case 3: impossible
Case 4: 0 7
W3sicHJvYmxlbV9pZCI6IjQyMDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWMxZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIyZFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzAwXHVjMmUwIFx1YzVmNFx1YzFlMFx1YjM1NFx1YmJmOFx1Yzc1OCBcdWM4MDhcdWJjMThcdWM3NDQgXHVkNjFjXHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzVmNFx1YzFlMFx1YjI5NCBcdWIwOThcdWMxMjBcdWQ2MTVcdWM3NDQgXHViNTMwXHViNzdjIFx1YmMwMFx1YzViNFx1YzExYyBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHVjNWQwIFx1YWM3OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHViM2M0IFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHVjNWQwIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQwIFx1YzEzMVx1YWMwMFx1YzJlMCBcdWM3OTFcdWM1YzVcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwKFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWQ2MWNcdWJlNDhcdWM3NzRcdWFjMDAgXHVjMTkwXHVkMWIxXHVjNWQwIFx1YjEyNFx1Yzc3Y1x1YzU0NFx1ZDJiOFx1Yjk3YyBcdWQ1NzRcdWM4ZmNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzE5MFx1ZDFiMVx1Yzc0NCBcdWIyZTRcdWNjZDBcdWMxMjAgXHVjNTQ4XHViNDFjXHViMmU0KSBcdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWM1ZWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWY0XHVjMWUwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YzVmNFx1YzFlMCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhYzcwXHViMDk4IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1Yzc5MVx1YzVjNVx1YzczY1x1Yjg1YyBcdWFjMDRcdWM4ZmNcdWI0MWNcdWIyZTQuIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWJjMDBcdWM1YjRcdWMxMWMgXHVjNWYwXHVhY2IwXHVkNTU4XHVhYzcwXHViMDk4IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjI5NFx1YWM4M1x1Yzc0MCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhYzcwXHViMDk4IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM1ZDAgXHViZTQ0XHVkNTc0IFx1YmU0NFx1ZDU3NCBcdWI5ZTRcdWM2YjAgXHVkNzk4XHViNGU0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMyMmRcdWM3NzRcdWIyOTQgXHVjNWY0XHVjMWUwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNWY0XHVjMWUwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWIyZTRcdWJhNzQgXHVjNWY0XHVjMWUwIFx1YWNlMFx1YjlhY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjXHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc5MVx1YzVjNVx1Yzc3NCBcdWM2NDRcdWI4Y2NcdWI0MThcdWJhNzQsIFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWQ2MWNcdWJlNDhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjNWY0XHVjMWUwIFx1YjM1NFx1YmJmOFx1Yjk3YyBcdWFjNzRcdWIxMjRcdWM5MDBcdWIyZTQoXHVjODE1XHVkNjU1XHVkNzg4IFx1YzIyZFx1Yzc3NFx1YWViYywgXHVkNjFjXHViZTQ4XHVjNzc0XHVhZWJjIFx1YjQ1MFx1YjM2OVx1Yzc3NFx1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0KS4gXHVjNjA4XHVjNjc4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjMjJkXHVjNzc0XHVhYzAwIFx1YWMxNlx1YjI5NCBcdWM1ZjRcdWMxZTAgXHViMzU0XHViYmY4XHVhYzAwIFx1YzVjNlx1YWM3MFx1YjA5OCBcdWQ2MWNcdWJlNDhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjMWUwIFx1YjM1NFx1YmJmOFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNWY0XHVjMWUwXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2UwXHViOWFjXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHViMjk0IFx1YjBhOFx1Yzc0MFx1YWM4M1x1Yzc3NCBcdWMwZGRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFkZjhcdWI4ZjlcdWM1ZDBcdWMxMWMgXHViZDg0XHViOWFjXHVjMmRjXHVkMGE4XHViMmU0PFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YjEyNFx1YWMxY1x1Yzc1OCBcdWM1ZjRcdWMxZTBcdWM2NDAgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YWNlMFx1YjlhY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMyMmRcdWM3NzRcdWIyOTQgXHVkNjFjXHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjIDJcdWFjMWNcdWM3NTggXHVjNWY0XHVjMWUwXHVjNzc4IE4sUlx1Yzc0NCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGNcdWM1ZDAgXHViNDUwIFx1YmM4OFx1Yzc1OCBcdWM1ZjRcdWMxZTAgXHViM2Q5XHVjNzkxXHVhY2ZjIFx1ZDU1Y1x1YmM4OFx1Yzc1OCBcdWFjZTBcdWI5YWMgXHViM2Q5XHVjNzkxXHVjNzNjXHViODVjIFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleXMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTkwcHg7IHdpZHRoOjUyOXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NThcdWIwOTggXHViNjEwXHViMjk0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMlx1YWMxYyBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNjAxXHVjNWI0IFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjI5NCBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNWY0XHVjMWUwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzg1XHViODI1XHViNDFjIDJcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViMjk0IFx1YzVmNFx1YzFlMFx1YzY0MCBcdWFjZTBcdWI5YWNcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjNzBcdWIwOTgsIFx1YWNlMFx1YjlhY1x1YzY0MCBcdWFjZTBcdWI5YWNcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1YmQ4MFx1ZDEzMCBNXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzVmNFx1YzFlMFx1YjI5NCBcdWMyMmRcdWM3NzRcdWFjMDAgXHVhYzE2XHVhY2UwLCBOXHViZDgwXHVkMTMwIFpcdWFlNGNcdWM5YzBcdWM3NTggXHVjNWY0XHVjMWUwXHViMjk0IFx1ZDYxY1x1YmU0OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YzMwZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjZTBcdWI5YWNcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjZDA4XHVhZTMwXHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM1ZjRcdWMxZTAgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1YWNlMFx1YjlhY1x1YzVkMFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjNWY0XHVjMWUwXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQoXHViZDg0XHViOWFjXHVkNTU4XHViYTc0XHVjMTFjIFx1YWNlMFx1YjlhY1x1YjljYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0KS4gXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM1ZjRcdWMxZTBcdWM2NDAgXHVhY2UwXHViOWFjXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NWNcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNWY0XHVjMWUwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1YzY0MCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhYzcwXHViMDk4IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNzdjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90O2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyMDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLZXlzIiwiZGVzY3JpcHRpb24iOiI8cD5BZGFtIGNhcnJpZXMgYSBidW5jaCBvZiBrZXlzIGF0dGFjaGVkIHRvIGtleSByaW5ncywgc29tZSBvZiB3aGljaCBtYXkgYmUgY29ubmVjdGVkIHRvIGVhY2ggb3RoZXIuIFRoZSByaW5ncyBhcmUgY29tbW9uIGtleSByaW5ncywgc28gYSBrZXkgY2FuIGJlIGF0dGFjaGVkIHRvIG9yIGRldGFjaGVkIGZyb20gYSByaW5nIGJ5IHNsaWRpbmcgYWxvbmcgdGhlIHNwaXJhbC4gSW4gdGhlIHNhbWUgd2F5LCB0d28gcmluZ3MgY2FuIGJlIGNvbm5lY3RlZCBvciBkaXNjb25uZWN0ZWQuIEFkYW0gd2FudHMgdG8gZ2l2ZSBzb21lIG9mIHRoZSBrZXlzIHRvIEJyZW5kYS4gU2luY2UgbWFuaXB1bGF0aW5nIHRoZSBrZXlzIGFuZCByaW5ncyBpcyBvZnRlbiBhbiBhbm5veWluZyB0YXNrIChhbmQgYWxzbyBkYW5nZXJvdXMgdG8gb25lJnJzcXVvO3MgXHVmYjAxbmdlcm5haWxzKSwgQWRhbSBpcyBsb29raW5nIGZvciBhIHdheSB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGtleSBhbmQgcmluZyBvcGVyYXRpb25zLjxcL3A+XHJcblxyXG48cD5FdmVyeSBrZXkgYXR0YWNobWVudCwga2V5IGRldGFjaG1lbnQsIHJpbmcgY29ubmVjdGlvbiwgb3IgcmluZyBkaXNjb25uZWN0aW9uIGlzIGNvbnNpZGVyZWQgb25lIG9wZXJhdGlvbi4gU2luY2UgbWFuaXB1bGF0aW5nIHR3byByaW5ncyBpcyBzaWduaVx1ZmIwMWNhbnRseSBlYXNpZXIgdGhhbiBzbGlkaW5nIGEga2V5LCB3ZSBcdWZiMDFyc3Qgd2FudCB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGtleXMgYmVpbmcgZGV0YWNoZWQgYW5kIGF0dGFjaGVkLiBBbW9uZyBzb2x1dGlvbnMgd2l0aCB0aGUgc2FtZSBtaW5pbWFsIG51bWJlciBvZiBrZXkgb3BlcmF0aW9ucywgeW91IG5lZWQgdG8gXHVmYjAxbmQgdGhlIG9uZSB3aXRoIHRoZSBtaW5pbWFsIG51bWJlciBvZiByaW5nIGNvbm5lY3Rpb25zIGFuZCBkaXNjb25uZWN0aW9ucy48XC9wPlxyXG5cclxuPHA+V2hlbiBhbGwgdGhlIG9wZXJhdGlvbnMgYXJlIGNvbXBsZXRlLCBBZGFtIGFuZCBCcmVuZGEgbXVzdCBlYWNoIGNhcnJ5IG9uZSBjb25uZWN0ZWQgZ3JvdXAgb2YgcmluZ3MgYW5kIGtleXMuIFRoZSBvbmx5IGV4Y2VwdGlvbiBpcyB3aGVuIGVpdGhlciBvZiB0aGVtIHdvdWxkIGhhdmUgbm8ga2V5cyBhdCBhbGwmbWRhc2g7aW4gc3VjaCBhIGNhc2UsIG5vIHJpbmcgaXMgbmVlZGVkLiBFYWNoIGtleSBtdXN0IGJlIGF0dGFjaGVkIHRvIGV4YWN0bHkgb25lIHJpbmcuIFNvbWUgcmluZ3MgKGJ1dCBub3Qga2V5cykgbWF5IGJlIGNvbnNpZGVyZWQgbGVmdG92ZXJzIGFuZCBtYXkgcmVtYWluIGRpc2Nvbm5lY3RlZCBmcm9tIHRoZSB0d28gZ3JvdXBzLjxcL3A+XHJcblxyXG48cD5UaGUgbGVmdCBzaWRlIG9mIHRoZSBmb2xsb3dpbmcgXHVmYjAxZ3VyZSBzaG93cyBhbiBpbml0aWFsIGNvblx1ZmIwMWd1cmF0aW9uIGNvbnNpc3Rpbmcgb2YgZm91ciBrZXlzIG9uIHRocmVlIHJpbmdzLiBBZGFtIHdpc2hlcyB0byBnaXZlIEJyZW5kYSB0aGUgdHdvIGtleXMgbGFiZWxlZCBOIGFuZCBSLiBUaGlzIGNhbiBiZSBhY2NvbXBsaXNoZWQgYnkgdHdvIGtleSBvcGVyYXRpb25zIGFuZCBvbmUgcmluZyBvcGVyYXRpb24sIHJlc3VsdGluZyBpbiB0aGUgY29uXHVmYjAxZ3VyYXRpb24gc2hvd24gb24gdGhlIHJpZ2h0IHNpZGUgb2YgdGhlIFx1ZmIwMWd1cmUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva2V5cy5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTBweDsgd2lkdGg6NTI5cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIG9uZSBvciBtb3JlIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSB0d28gbGV0dGVyIHN0cmluZy4gTG93ZXJjYXNlIGxldHRlcnMgKGEgLSB6KSByZXByZXNlbnQga2V5IHJpbmdzIGFuZCB1cHBlcmNhc2UgbGV0dGVycyAoQSAtIFopIHJlcHJlc2VudCBrZXlzLiBUaGUgdHdvIGxldHRlcnMgb24gYSBsaW5lIHNwZWNpZnkgZWl0aGVyIGEga2V5IGF0dGFjaGVkIHRvIGEgcmluZyBvciB0d28gcmluZ3MgY29ubmVjdGVkIHRvZ2V0aGVyLiBUaGUgZW5kIG9mIGVhY2ggdGVzdCBjYXNlIGlzIGRlbm90ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIGRpZ2l0IHplcm8uPFwvcD5cclxuXHJcbjxwPktleXMgZGVub3RlZCBieSBsZXR0ZXJzIEEgdGhyb3VnaCBNIHJlbWFpbiB3aXRoIEFkYW0sIGFuZCBrZXlzIGRlbm90ZWQgYnkgbGV0dGVycyBOIHRocm91Z2ggWiBhcmUgZ2l2ZW4gdG8gQnJlbmRhLjxcL3A+XHJcblxyXG48cD5ObyBsaW5lIGNvbnRhaW5zIHR3byB1cHBlcmNhc2UgbGV0dGVycy4gTm8gcGFpciBvZiBsZXR0ZXJzIGFyZSBzcGVjaVx1ZmIwMWVkIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBzYW1lIHRlc3QgY2FzZS4gRWFjaCBrZXkgaXMgY29ubmVjdGVkIHRvIGV4YWN0bHkgb25lIHJpbmcuIFRoZXJlIGFyZSBubyAmbGRxdW87Y2lyY2xlcyZyZHF1bzsgaW4gdGhlIHJpbmcgY29uXHVmYjAxZ3VyYXRpb25zIChkaXNjb25uZWN0aW5nIGFueSB0d28gcmluZ3Mgd2lsbCBpbmNyZWFzZSB0aGUgbnVtYmVyIG9mIGNvbm5lY3RlZCBncm91cHMpLiBBbGwgZXhpc3Rpbmcga2V5cyBhbmQgcmluZ3MgYXJlIG1lbnRpb25lZCBhdCBsZWFzdCBvbmNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSB0aGUgY2FzZSBudW1iZXIgZm9sbG93ZWQgYnkgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGtleSBhdHRhY2hcL2RldGFjaCBvcGVyYXRpb25zIGFuZCB0aGUgbWluaW1hbCBudW1iZXIgb2YgcmluZyBjb25uZWN0XC9kaXNjb25uZWN0IG9wZXJhdGlvbnMuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIG5vIHdheSB0byBzcGxpdCB0aGUga2V5cyBhcyByZXF1ZXN0ZWQsIGRpc3BsYXkgdGhlIGNhc2UgbnVtYmVyIGFuZCB0aGUgd29yZCBpbXBvc3NpYmxlIGluc3RlYWQgb2YgdGhlIHR3byBpbnRlZ2Vycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > World Finals > 2012 World Finals F번

  • 문제를 번역한 사람: lll4592