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

문제

보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다.

보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다.

항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오른쪽, 왼쪽)중에서 하나를 골라서 시그널을 보낸다.

시그널은 항상 일직선으로 전파되며, 행성을 만났을 경우에는 전파되는 방향이 90도로 바뀌게 된다. 행성은 '/'와 '\'로 표현되는 두 종류가 있으며, 반사되는 법칙은 아래 그림과 같다.

시그널이 블랙홀이 있는 칸을 만나거나 항성계를 벗어날 때 까지 계속 전파된다. 시그널이 인접한 칸으로 이동하는데 걸리는 시간은 1초이다.

탐사선이 어느 방향으로 시그널을 보내면, 시그널이 항성계 내부에 있는 시간이 최대가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 500)

다음 N개 줄에는 M개의 문자가 주어지며, '/'와 '\'는 행성을, C는 블랙홀을, '.'는 빈 칸을 나타낸다.

마지막 줄에는 탐사선이 있는 위치 PR과 PC가 주어진다. (1 ≤ PR ≤ N, 1 ≤ PC ≤ M)

출력

첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽)

만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다.

둘째 줄에는 가장 긴 시간을 출력한다. 만약, 시그널이 항성계 내에서 무한히 전파될 수 있다면 "Voyager"를 출력한다.

예제 입력 1

5 5
../.\
.....
.C...
...C.
\.../
3 3

예제 출력 1

U
17

예제 입력 2

5 5
....\
\..\.
./\..
\../C
.\../
1 1

예제 출력 2

D
12

예제 입력 3

5 7
/.....\
../..\.
\...../
/.....\
\.\.../
3 3

예제 출력 3

R
Voyager

힌트

초기 상태 위(U) 방향 오른쪽(R) 방향 아래(D) 방향 왼쪽(L) 방향
../.\
.....
.CS..
...C.
\.../
*.***
*.*.*
*C*.*
*..C*
*****
../.\
.....
.C***
...C.
\.../
../.\
.....
.C*..
..*C.
\.*./
../.\
.....
.C*..
...C.
\.../
  17초 3초 3초 1초
W3sicHJvYmxlbV9pZCI6IjM5ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWM3NzRcdWM4MDAgMVx1ZDYzOCIsImRlc2NyaXB0aW9uIjoiPHA+XHViY2Y0XHVjNzc0XHVjODAwIDFcdWQ2MzhcdWIyOTQgMTk3N1x1YjE0NFx1YzVkMCBcdWJjMWNcdWMwYWNcdWI0MWMgTkFTQVx1Yzc1OCBcdWQwZGNcdWM1OTFcdWFjYzQgXHViYjM0XHVjNzc4IFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc3NFx1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YmNmNFx1Yzc3NFx1YzgwMCAxXHVkNjM4XHViMjk0IFx1ZDBkY1x1YzU5MVx1YWQ4Y1x1YjM2ZVx1YWMxYyAoXHVkNWVjXHViOWFjXHVjNjI0XHVjMmRjXHVjMmE0KVx1YzVkMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1Yzc3NFx1YzgwMCAxXHVkNjM4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM2MjRcdWI3OWMgXHVhZTMwXHVhYzA0XHViM2Q5XHVjNTQ4IFx1ZDY1Y1x1YjNkOVx1ZDU1OFx1YjI5NCBcdWQwZDBcdWMwYWNcdWMxMjBcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1ZDU2ZFx1YzEzMVx1YWNjNFx1Yjk3YyBcdWI5Y2NcdWIwYTAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWI3N2NcdWI1MTRcdWM2MjQgXHVjMmRjXHVhZGY4XHViMTEwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVhZTMwXHViODVkXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMTMxXHVhY2M0XHViOTdjIE4gKiBNXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IE5cdWQ1ODkgTVx1YzVmNFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWQ1ODlcdWMxMzEsIFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTI0IFx1Y2U3OChcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2N2NcdWNhYmQpXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2NcdWMxMWMgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzQ0IFx1YmNmNFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhZGY4XHViMTEwXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODA0XHVkMzBjXHViNDE4XHViYTcwLCBcdWQ1ODlcdWMxMzFcdWM3NDQgXHViOWNjXHViMGFjXHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM4MDRcdWQzMGNcdWI0MThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IDkwXHViM2M0XHViODVjIFx1YmMxNFx1YjAwY1x1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDU4OVx1YzEzMVx1Yzc0MCAmIzM5O1wvJiMzOTtcdWM2NDAgJiMzOTtcXCYjMzk7XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NCBcdWI0NTAgXHVjODg1XHViOTU4XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViYzE4XHVjMGFjXHViNDE4XHViMjk0IFx1YmM5NVx1Y2U1OVx1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDY0ZGU4MmItNWZjZS00NmFjLWE1NGEtMzE1YjBhMTU3MTM2XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2NDFweDsgaGVpZ2h0OiAxMzRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhZGY4XHViMTEwXHVjNzc0IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjljY1x1YjA5OFx1YWM3MFx1YjA5OCBcdWQ1NmRcdWMxMzFcdWFjYzRcdWI5N2MgXHViYzk3XHVjNWI0XHViMGEwIFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkIFx1YzgwNFx1ZDMwY1x1YjQxY1x1YjJlNC4gXHVjMmRjXHVhZGY4XHViMTEwXHVjNzc0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMVx1Y2QwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGQwXHVjMGFjXHVjMTIwXHVjNzc0IFx1YzViNFx1YjI5MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzQ0IFx1YmNmNFx1YjBiNFx1YmE3NCwgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzc0IFx1ZDU2ZFx1YzEzMVx1YWNjNCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyA1MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsICYjMzk7XC8mIzM5O1x1YzY0MCAmIzM5O1xcJiMzOTtcdWIyOTQgXHVkNTg5XHVjMTMxXHVjNzQ0LCBDXHViMjk0IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc0NCwgJiMzOTsuJiMzOTtcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMGQwXHVjMGFjXHVjMTIwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNTggUFJcdWFjZmMgUENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFBSICZsZTsgTiwgMSAmbGU7IFBDICZsZTsgTSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1YWRmOFx1YjExMFx1Yzc0NCBcdWJjZjRcdWIwYjRcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFU6IFx1YzcwNCwgUjogXHVjNjI0XHViOTc4XHVjYWJkLCBEOiBcdWM1NDRcdWI3OTgsIEw6IFx1YzY3Y1x1Y2FiZCk8XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFUsIFIsIEQsIExcdWM3NTggXHVjMjFjXHVjMTFjIFx1YzkxMSBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzc0IFx1ZDU2ZFx1YzEzMVx1YWNjNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHViYjM0XHVkNTVjXHVkNzg4IFx1YzgwNFx1ZDMwY1x1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0ICZxdW90O1ZveWFnZXImcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjIwJVwiPlx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGM8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjIwJVwiPlx1YzcwNChVKSBcdWJjMjlcdWQ1YTU8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjIwJVwiPlx1YzYyNFx1Yjk3OFx1Y2FiZChSKSBcdWJjMjlcdWQ1YTU8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjIwJVwiPlx1YzU0NFx1Yjc5OChEKSBcdWJjMjlcdWQ1YTU8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjIwJVwiPlx1YzY3Y1x1Y2FiZChMKSBcdWJjMjlcdWQ1YTU8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cclxuLi5cLy5cXFxyXG4uLi4uLlxyXG4uQ1MuLlxyXG4uLi5DLlxyXG5cXC4uLlwvPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cclxuKi4qKipcclxuKi4qLipcclxuKkMqLipcclxuKi4uQypcclxuKioqKio8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG4uLlwvLlxcXHJcbi4uLi4uXHJcbi5DKioqXHJcbi4uLkMuXHJcblxcLi4uXC88XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG4uLlwvLlxcXHJcbi4uLi4uXHJcbi5DKi4uXHJcbi4uKkMuXHJcblxcLiouXC88XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG4uLlwvLlxcXHJcbi4uLi4uXHJcbi5DKi4uXHJcbi4uLkMuXHJcblxcLi4uXC88XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+MTdcdWNkMDg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4zXHVjZDA4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+M1x1Y2QwODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjFcdWNkMDg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzOTg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVk9ZQUdFUiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIFZveWFnZXIgMSBzcGFjZSBwcm9iZSAobm90IHRvIGJlIGNvbmZ1c2VkIHdpdGggdGhlIEludHJlcGlkLWNsYXNzIHN0YXJzaGlwKSB3YXMgbGF1bmNoZWQgYSBsb25nIHRpbWUgYWdvLCBpbiAxOTc3LCBhbmQgaXMgY3VycmVudGx5IG9uIHRoZSB2ZXJnZSBvZiBsZWF2aW5nIG91ciBTb2xhciBTeXN0ZW0uIEFzIGl0IHRyYXZlbHMgZnVydGhlciB0aHJvdWdoIHNwYWNlLCBpdCBoYXMgYmVlbiBwcm9ncmFtbWVkIHRvIGxlYXZlIGEgcmFkaW8gc2lnbmFsIG1lc3NhZ2UgaW4gYW55IHN0YXIgc3lzdGVtIGl0IHN0dW1ibGVzIHVwb24sIHRvIG1hcmsgdGhlIHByb2JlJiMzOTtzIHBhdGggZm9yIGFzIGxvbmcgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxldCB1cyBhc3N1bWUgdGhhdCBhIHN0YXIgc3lzdGVtIGNhbiBiZSByZXByZXNlbnRlZCBieSBhIHJlY3Rhbmd1bGFyIGdyaWQgd2l0aCBOIHJvd3MgYW5kIE0gY29sdW1ucywgZGl2aWRpbmcgdGhlIHNwYWNlIGludG8gTiBieSBNIGVxdWFsIGNlbGxzLiBFYWNoIGNlbGwgY2FuIGNvbnRhaW4gYSBzaW5nbGUgcGxhbmV0LCBibGFjayBob2xlLCBvciBiZSBlbXB0eS4gVGhlIHByb2JlIGJyb2FkY2FzdHMgdGhlIHNpZ25hbCBmcm9tIGEgcHJlLWRldGVybWluZWQgZW1wdHkgY2VsbCwgaW4gb25lIG9mIHRoZSBmb3VyIGF4aXMtYWxpZ25lZCBkaXJlY3Rpb25zICgmbGRxdW87VSZyZHF1bzstdXAsICZsZHF1bztSJnJkcXVvOy1yaWdodCwgJmxkcXVvO0QmcmRxdW87LWRvd24sICZsZHF1bztMJnJkcXVvOy1sZWZ0KS4gVXBvbiBiZWluZyBicm9hZGNhc3QsIHRoZSBzaWduYWwgcHJvcGFnYXRlcyBpbiBhIHN0cmFpZ2h0IGxpbmUgYWxvbmcgdGhlIHNhbWUgcm93XC9jb2x1bW4gdW50aWwgaXQgcmVhY2hlcyBhIHBsYW5ldCwgd2hlcmUgaXQgaXMgZGVmbGVjdGVkIGJ5IDkwIGRlZ3JlZXMgaW4gYW5vdGhlciBkaXJlY3Rpb24uIFRoZXJlIGFyZSB0d28ga2luZHMgb2YgcGxhbmV0cywgd2hpY2ggd2Ugd2lsbCBkZW5vdGUgYnkgJmJkcXVvO1wvJmxkcXVvOyBhbmQgJmJkcXVvO1xcJmxkcXVvOy4gVGhlIGRlZmxlY3Rpb24gcnVsZXMgYXJlIHNob3duIGluIHRoZSBpbWFnZSBiZWxvdzombmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNjRkZTgyYi01ZmNlLTQ2YWMtYTU0YS0zMTViMGExNTcxMzZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDY0MXB4OyBoZWlnaHQ6IDEzNHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgc2lnbmFsIHBlcm1hbmVudGx5IGxlYXZlcyB0aGUgc3lzdGVtIHVwb24gZWl0aGVyIGVudHJpbmcgYSBjZWxsIGNvbnRhaW5pbmcgYSBibGFjayBob2xlLCBvciBwcm9wYWdhdGluZyBvdXRzaWRlIHRoZSBlZGdlcyBvZiB0aGUgcmVjdGFuZ3VsYXIgZ3JpZC4gSXQgaXMgYWxzbyBrbm93biB0aGF0IHRoZSBzaWduYWwgbmVlZHMgb25lIHNlY29uZCB0byBwcm9wYWdhdGUgZnJvbSB0aGUgY3VycmVudCBjZWxsIHRvIGEgbmVpZ2hib3VyaW5nIG9uZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgZGlyZWN0aW9uIGluIHdoaWNoIHRoZSBwcm9iZSBuZWVkcyB0byBicm9hZGNhc3QgdGhlIHNpZ25hbCBzbyB0aGF0IGl0IHJlbWFpbnMgd2l0aGluIHRoZSBzeXN0ZW0gZm9yIGFzIGxvbmcgYXMgcG9zc2libGUsIG91dHB1dHRpbmcgdGhlIG9wdGltYWwgZGlyZWN0aW9uIGFzIHdlbGwgYXMgdGhlIHJlc3VsdGluZyBsb25nZXN0IHRpbWUuIElmIGl0IGlzIHBvc3NpYmxlIGZvciB0aGUgc2lnbmFsIHRvIHJlbWFpbiBpbiB0aGUgc3lzdGVtIGluZGVmaW5pdGVseSwgb3V0cHV0IHRoZSBtZXNzYWdlICZiZHF1bztWb3lhZ2VyJmxkcXVvOyBpbnN0ZWFkIG9mIHRoZSByZXF1aXJlZCB0aW1lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgxICZsZTsgTiAmbGU7IDUwMCkgYW5kIE0gKDEgJmxlOyBNICZsZTsgNTAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgTSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNldCB7JmxkcXVvO1wvJnJkcXVvOywgJmxkcXVvO1xcJnJkcXVvOywgJmxkcXVvO0MmcmRxdW87LCAmbGRxdW87LiZyZHF1bzt9LCB3aGVyZSAmbGRxdW87XC8mcmRxdW87IGFuZCAmbGRxdW87XFwmcmRxdW87IHJlcHJlc2VudCB0aGUgdHdvIGtpbmRzIG9mIHBsYW5ldHMsICZsZHF1bztDJnJkcXVvOyByZXByZXNlbnRzIGEgYmxhY2sgaG9sZSwgYW5kICZsZHF1bzsuJnJkcXVvOyByZXByZXNlbnRzIGFuIGVtcHR5IGNlbGwuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBQUiAoMSAmbGU7IFBSICZsZTsgTikgYW5kIFBDICgxICZsZTsgUEMgJmxlOyBNKSwgdGhlIHJvdyBhbmQgY29sdW1uIG51bWJlciwgcmVzcGVjdGl2ZWx5LCBvZiB0aGUgY2VsbCB3aGVyZSB0aGUgcHJvYmUgaXMgc2l0dWF0ZWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgb3B0aW1hbCBicm9hZGNhc3QgZGlyZWN0aW9uICgmbGRxdW87VSZyZHF1bzssICZsZHF1bztSJnJkcXVvOywgJmxkcXVvO0QmcmRxdW87LCBvciAmbGRxdW87TCZyZHF1bzspLiBJZiB0aGUgc29sdXRpb24gaXMgbm90IHVuaXF1ZSwgc2VsZWN0IHRoZSBmaXJzdCBvcHRpbWFsIG9uZSBpbiB0aGUgZm9sbG93aW5nIHByaW9yaXR5IG9yZGVyOiBmaXJzdCAmbGRxdW87VSZyZHF1bzssIHRoZW4gJmxkcXVvO1ImcmRxdW87LCB0aGVuICZsZHF1bztEJnJkcXVvOywgYW5kIGZpbmFsbHkgJmxkcXVvO0wmcmRxdW87LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbG9uZ2VzdCB0aW1lIChvciBtZXNzYWdlKS48XC9wPlxyXG4iLCJoaW50IjoiPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyIHRoLWNlbnRlclwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+c3RhcnQ8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+JiMzOTtVJiMzOTsgZGlyZWN0aW9uPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjIwJVwiPiYjMzk7UiYjMzk7IGRpcmVjdGlvbjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMCVcIj4mIzM5O0QmIzM5OyBkaXJlY3Rpb248XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+JiMzOTtMJiMzOTsgZGlyZWN0aW9uPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PGRpdiBzdHlsZT1cImZvbnQtZmFtaWx5Om1vbm9zcGFjZTtcIj4uLlwvLlxcPGJyIFwvPlxyXG5cdFx0XHQuLi4uLjxiciBcLz5cclxuXHRcdFx0LkNTLi48YnIgXC8+XHJcblx0XHRcdC4uLkMuPGJyIFwvPlxyXG5cdFx0XHRcXC4uLlwvPFwvZGl2PlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8ZGl2IHN0eWxlPVwiZm9udC1mYW1pbHk6bW9ub3NwYWNlO1wiPiouKioqPGJyIFwvPlxyXG5cdFx0XHQqLiouKjxiciBcLz5cclxuXHRcdFx0KkMqLio8YnIgXC8+XHJcblx0XHRcdCouLkMqPGJyIFwvPlxyXG5cdFx0XHQqKioqKjxcL2Rpdj5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PGRpdiBzdHlsZT1cImZvbnQtZmFtaWx5Om1vbm9zcGFjZTtcIj4uLlwvLlxcPGJyIFwvPlxyXG5cdFx0XHQuLi4uLjxiciBcLz5cclxuXHRcdFx0LkMqKio8YnIgXC8+XHJcblx0XHRcdC4uLkMuPGJyIFwvPlxyXG5cdFx0XHRcXC4uLlwvPFwvZGl2PlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8ZGl2IHN0eWxlPVwiZm9udC1mYW1pbHk6bW9ub3NwYWNlO1wiPi4uXC8uXFw8YnIgXC8+XHJcblx0XHRcdC4uLi4uPGJyIFwvPlxyXG5cdFx0XHQuQyouLjxiciBcLz5cclxuXHRcdFx0Li4qQy48YnIgXC8+XHJcblx0XHRcdFxcLiouXC88XC9kaXY+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxkaXYgc3R5bGU9XCJmb250LWZhbWlseTptb25vc3BhY2U7XCI+Li5cLy5cXDxiciBcLz5cclxuXHRcdFx0Li4uLi48YnIgXC8+XHJcblx0XHRcdC5DKi4uPGJyIFwvPlxyXG5cdFx0XHQuLi5DLjxiciBcLz5cclxuXHRcdFx0XFwuLi5cLzxcL2Rpdj5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPiZuYnNwOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTcgc2Vjb25kczxcL3RkPlxyXG5cdFx0XHQ8dGQ+MyBzZWNvbmRzPFwvdGQ+XHJcblx0XHRcdDx0ZD4zIHNlY29uZHM8XC90ZD5cclxuXHRcdFx0PHRkPjEgc2Vjb25kczxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 3번