시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1103 243 185 20.857%

문제

보이저 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

힌트

초기 상태 위(U) 방향 오른쪽(R) 방향 아래(D) 방향 왼쪽(L) 방향
../.\
.....
.CS..
...C.
\.../
*.***
*.*.*
*C*.*
*..C*
*****
../.\
.....
.C***
...C.
\.../
../.\
.....
.C*..
..*C.
\.*./
../.\
.....
.C*..
...C.
\.../
  17초 3초 3초 1초
W3sicHJvYmxlbV9pZCI6IjM5ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWM3NzRcdWM4MDAgMVx1ZDYzOCIsImRlc2NyaXB0aW9uIjoiPHA+XHViY2Y0XHVjNzc0XHVjODAwIDFcdWQ2MzhcdWIyOTQgMTk3N1x1YjE0NFx1YzVkMCBcdWJjMWNcdWMwYWNcdWI0MWMgTkFTQVx1Yzc1OCBcdWQwZGNcdWM1OTFcdWFjYzQgXHViYjM0XHVjNzc4IFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc3NFx1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YmNmNFx1Yzc3NFx1YzgwMCAxXHVkNjM4XHViMjk0IFx1ZDBkY1x1YzU5MVx1YWQ4Y1x1YjM2ZVx1YWMxYyAoXHVkNWVjXHViOWFjXHVjNjI0XHVjMmRjXHVjMmE0KVx1YzVkMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1Yzc3NFx1YzgwMCAxXHVkNjM4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM2MjRcdWI3OWMgXHVhZTMwXHVhYzA0XHViM2Q5XHVjNTQ4IFx1ZDY1Y1x1YjNkOVx1ZDU1OFx1YjI5NCBcdWQwZDBcdWMwYWNcdWMxMjBcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1ZDU2ZFx1YzEzMVx1YWNjNFx1Yjk3YyBcdWI5Y2NcdWIwYTAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWI3N2NcdWI1MTRcdWM2MjQgXHVjMmRjXHVhZGY4XHViMTEwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVhZTMwXHViODVkXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMTMxXHVhY2M0XHViOTdjIE4gKiBNXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IE5cdWQ1ODkgTVx1YzVmNFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWQ1ODlcdWMxMzEsIFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTI0IFx1Y2U3OChcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2N2NcdWNhYmQpXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2NcdWMxMWMgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzQ0IFx1YmNmNFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhZGY4XHViMTEwXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODA0XHVkMzBjXHViNDE4XHViYTcwLCBcdWQ1ODlcdWMxMzFcdWM3NDQgXHViOWNjXHViMGFjXHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM4MDRcdWQzMGNcdWI0MThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IDkwXHViM2M0XHViODVjIFx1YmMxNFx1YjAwY1x1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDU4OVx1YzEzMVx1Yzc0MCAmIzM5O1wvJiMzOTtcdWM2NDAgJiMzOTtcXCYjMzk7XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NCBcdWI0NTAgXHVjODg1XHViOTU4XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViYzE4XHVjMGFjXHViNDE4XHViMjk0IFx1YmM5NVx1Y2U1OVx1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2lnbmFsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzOXB4OyB3aWR0aDo2NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHViZTE0XHViNzk5XHVkNjQwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDQgXHViOWNjXHViMDk4XHVhYzcwXHViMDk4IFx1ZDU2ZFx1YzEzMVx1YWNjNFx1Yjk3YyBcdWJjOTdcdWM1YjRcdWIwYTAgXHViNTRjIFx1YWU0Y1x1YzljMCBcdWFjYzRcdWMxOGQgXHVjODA0XHVkMzBjXHViNDFjXHViMmU0LiBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxXHVjZDA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDBcdWMwYWNcdWMxMjBcdWM3NzQgXHVjNWI0XHViMjkwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NDQgXHViY2Y0XHViMGI0XHViYTc0LCBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHVkNTZkXHVjMTMxXHVhY2M0IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgJiMzOTtcLyYjMzk7XHVjNjQwICYjMzk7XFwmIzM5O1x1YjI5NCBcdWQ1ODlcdWMxMzFcdWM3NDQsIENcdWIyOTQgXHViZTE0XHViNzk5XHVkNjQwXHVjNzQ0LCAmIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwZDBcdWMwYWNcdWMxMjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OCBQUlx1YWNmYyBQQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUFIgJmxlOyBOLCAxICZsZTsgUEMgJmxlOyBNKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzQ0IFx1YmNmNFx1YjBiNFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoVTogXHVjNzA0LCBSOiBcdWM2MjRcdWI5NzhcdWNhYmQsIEQ6IFx1YzU0NFx1Yjc5OCwgTDogXHVjNjdjXHVjYWJkKTxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgVSwgUiwgRCwgTFx1Yzc1OCBcdWMyMWNcdWMxMWMgXHVjOTExIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHVkNTZkXHVjMTMxXHVhY2M0IFx1YjBiNFx1YzVkMFx1YzExYyBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVjODA0XHVkMzBjXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgJnF1b3Q7Vm95YWdlciZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoxMDAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjAlXCI+XHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkYzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjAlXCI+XHVjNzA0KFUpIFx1YmMyOVx1ZDVhNTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjAlXCI+XHVjNjI0XHViOTc4XHVjYWJkKFIpIFx1YmMyOVx1ZDVhNTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjAlXCI+XHVjNTQ0XHViNzk4KEQpIFx1YmMyOVx1ZDVhNTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjAlXCI+XHVjNjdjXHVjYWJkKEwpIFx1YmMyOVx1ZDVhNTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG4uLlwvLlxcXHJcbi4uLi4uXHJcbi5DUy4uXHJcbi4uLkMuXHJcblxcLi4uXC88XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG4qLioqKlxyXG4qLiouKlxyXG4qQyouKlxyXG4qLi5DKlxyXG4qKioqKjxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZSBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHJcbi4uXC8uXFxcclxuLi4uLi5cclxuLkMqKipcclxuLi4uQy5cclxuXFwuLi5cLzxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZSBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHJcbi4uXC8uXFxcclxuLi4uLi5cclxuLkMqLi5cclxuLi4qQy5cclxuXFwuKi5cLzxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZSBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHJcbi4uXC8uXFxcclxuLi4uLi5cclxuLkMqLi5cclxuLi4uQy5cclxuXFwuLi5cLzxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4xN1x1Y2QwODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjNcdWNkMDg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4zXHVjZDA4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+MVx1Y2QwODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5ODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWT1lBR0VSIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgVm95YWdlciAxIHNwYWNlIHByb2JlIChub3QgdG8gYmUgY29uZnVzZWQgd2l0aCB0aGUgSW50cmVwaWQtY2xhc3Mgc3RhcnNoaXApIHdhcyBsYXVuY2hlZCBhIGxvbmcgdGltZSBhZ28sIGluIDE5NzcsIGFuZCBpcyBjdXJyZW50bHkgb24gdGhlIHZlcmdlIG9mIGxlYXZpbmcgb3VyIFNvbGFyIFN5c3RlbS4gQXMgaXQgdHJhdmVscyBmdXJ0aGVyIHRocm91Z2ggc3BhY2UsIGl0IGhhcyBiZWVuIHByb2dyYW1tZWQgdG8gbGVhdmUgYSByYWRpbyBzaWduYWwgbWVzc2FnZSBpbiBhbnkgc3RhciBzeXN0ZW0gaXQgc3R1bWJsZXMgdXBvbiwgdG8gbWFyayB0aGUgcHJvYmUmIzM5O3MgcGF0aCBmb3IgYXMgbG9uZyBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGV0IHVzIGFzc3VtZSB0aGF0IGEgc3RhciBzeXN0ZW0gY2FuIGJlIHJlcHJlc2VudGVkIGJ5IGEgcmVjdGFuZ3VsYXIgZ3JpZCB3aXRoIE4gcm93cyBhbmQgTSBjb2x1bW5zLCBkaXZpZGluZyB0aGUgc3BhY2UgaW50byBOIGJ5IE0gZXF1YWwgY2VsbHMuIEVhY2ggY2VsbCBjYW4gY29udGFpbiBhIHNpbmdsZSBwbGFuZXQsIGJsYWNrIGhvbGUsIG9yIGJlIGVtcHR5LiBUaGUgcHJvYmUgYnJvYWRjYXN0cyB0aGUgc2lnbmFsIGZyb20gYSBwcmUtZGV0ZXJtaW5lZCBlbXB0eSBjZWxsLCBpbiBvbmUgb2YgdGhlIGZvdXIgYXhpcy1hbGlnbmVkIGRpcmVjdGlvbnMgKCZsZHF1bztVJnJkcXVvOy11cCwgJmxkcXVvO1ImcmRxdW87LXJpZ2h0LCAmbGRxdW87RCZyZHF1bzstZG93biwgJmxkcXVvO0wmcmRxdW87LWxlZnQpLiBVcG9uIGJlaW5nIGJyb2FkY2FzdCwgdGhlIHNpZ25hbCBwcm9wYWdhdGVzIGluIGEgc3RyYWlnaHQgbGluZSBhbG9uZyB0aGUgc2FtZSByb3dcL2NvbHVtbiB1bnRpbCBpdCByZWFjaGVzIGEgcGxhbmV0LCB3aGVyZSBpdCBpcyBkZWZsZWN0ZWQgYnkgOTAgZGVncmVlcyBpbiBhbm90aGVyIGRpcmVjdGlvbi4gVGhlcmUgYXJlIHR3byBraW5kcyBvZiBwbGFuZXRzLCB3aGljaCB3ZSB3aWxsIGRlbm90ZSBieSAmYmRxdW87XC8mbGRxdW87IGFuZCAmYmRxdW87XFwmbGRxdW87LiBUaGUgZGVmbGVjdGlvbiBydWxlcyBhcmUgc2hvd24gaW4gdGhlIGltYWdlIGJlbG93OiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NpZ25hbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzlweDsgd2lkdGg6NjU3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHNpZ25hbCBwZXJtYW5lbnRseSBsZWF2ZXMgdGhlIHN5c3RlbSB1cG9uIGVpdGhlciBlbnRyaW5nIGEgY2VsbCBjb250YWluaW5nIGEgYmxhY2sgaG9sZSwgb3IgcHJvcGFnYXRpbmcgb3V0c2lkZSB0aGUgZWRnZXMgb2YgdGhlIHJlY3Rhbmd1bGFyIGdyaWQuIEl0IGlzIGFsc28ga25vd24gdGhhdCB0aGUgc2lnbmFsIG5lZWRzIG9uZSBzZWNvbmQgdG8gcHJvcGFnYXRlIGZyb20gdGhlIGN1cnJlbnQgY2VsbCB0byBhIG5laWdoYm91cmluZyBvbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlIGRpcmVjdGlvbiBpbiB3aGljaCB0aGUgcHJvYmUgbmVlZHMgdG8gYnJvYWRjYXN0IHRoZSBzaWduYWwgc28gdGhhdCBpdCByZW1haW5zIHdpdGhpbiB0aGUgc3lzdGVtIGZvciBhcyBsb25nIGFzIHBvc3NpYmxlLCBvdXRwdXR0aW5nIHRoZSBvcHRpbWFsIGRpcmVjdGlvbiBhcyB3ZWxsIGFzIHRoZSByZXN1bHRpbmcgbG9uZ2VzdCB0aW1lLiBJZiBpdCBpcyBwb3NzaWJsZSBmb3IgdGhlIHNpZ25hbCB0byByZW1haW4gaW4gdGhlIHN5c3RlbSBpbmRlZmluaXRlbHksIG91dHB1dCB0aGUgbWVzc2FnZSAmYmRxdW87Vm95YWdlciZsZHF1bzsgaW5zdGVhZCBvZiB0aGUgcmVxdWlyZWQgdGltZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyA1MDApIGFuZCBNICgxICZsZTsgTSAmbGU7IDUwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIE0gY2hhcmFjdGVycyBmcm9tIHRoZSBzZXQgeyZsZHF1bztcLyZyZHF1bzssICZsZHF1bztcXCZyZHF1bzssICZsZHF1bztDJnJkcXVvOywgJmxkcXVvOy4mcmRxdW87fSwgd2hlcmUgJmxkcXVvO1wvJnJkcXVvOyBhbmQgJmxkcXVvO1xcJnJkcXVvOyByZXByZXNlbnQgdGhlIHR3byBraW5kcyBvZiBwbGFuZXRzLCAmbGRxdW87QyZyZHF1bzsgcmVwcmVzZW50cyBhIGJsYWNrIGhvbGUsIGFuZCAmbGRxdW87LiZyZHF1bzsgcmVwcmVzZW50cyBhbiBlbXB0eSBjZWxsLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgUFIgKDEgJmxlOyBQUiAmbGU7IE4pIGFuZCBQQyAoMSAmbGU7IFBDICZsZTsgTSksIHRoZSByb3cgYW5kIGNvbHVtbiBudW1iZXIsIHJlc3BlY3RpdmVseSwgb2YgdGhlIGNlbGwgd2hlcmUgdGhlIHByb2JlIGlzIHNpdHVhdGVkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG9wdGltYWwgYnJvYWRjYXN0IGRpcmVjdGlvbiAoJmxkcXVvO1UmcmRxdW87LCAmbGRxdW87UiZyZHF1bzssICZsZHF1bztEJnJkcXVvOywgb3IgJmxkcXVvO0wmcmRxdW87KS4gSWYgdGhlIHNvbHV0aW9uIGlzIG5vdCB1bmlxdWUsIHNlbGVjdCB0aGUgZmlyc3Qgb3B0aW1hbCBvbmUgaW4gdGhlIGZvbGxvd2luZyBwcmlvcml0eSBvcmRlcjogZmlyc3QgJmxkcXVvO1UmcmRxdW87LCB0aGVuICZsZHF1bztSJnJkcXVvOywgdGhlbiAmbGRxdW87RCZyZHF1bzssIGFuZCBmaW5hbGx5ICZsZHF1bztMJnJkcXVvOy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIGxvbmdlc3QgdGltZSAob3IgbWVzc2FnZSkuPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoxMDAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMCVcIj5zdGFydDxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMCVcIj4mIzM5O1UmIzM5OyBkaXJlY3Rpb248XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+JiMzOTtSJiMzOTsgZGlyZWN0aW9uPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjIwJVwiPiYjMzk7RCYjMzk7IGRpcmVjdGlvbjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMCVcIj4mIzM5O0wmIzM5OyBkaXJlY3Rpb248XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8ZGl2IHN0eWxlPVwiZm9udC1mYW1pbHk6bW9ub3NwYWNlO1wiPi4uXC8uXFw8YnIgXC8+XHJcblx0XHRcdC4uLi4uPGJyIFwvPlxyXG5cdFx0XHQuQ1MuLjxiciBcLz5cclxuXHRcdFx0Li4uQy48YnIgXC8+XHJcblx0XHRcdFxcLi4uXC88XC9kaXY+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxkaXYgc3R5bGU9XCJmb250LWZhbWlseTptb25vc3BhY2U7XCI+Ki4qKio8YnIgXC8+XHJcblx0XHRcdCouKi4qPGJyIFwvPlxyXG5cdFx0XHQqQyouKjxiciBcLz5cclxuXHRcdFx0Ki4uQyo8YnIgXC8+XHJcblx0XHRcdCoqKioqPFwvZGl2PlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8ZGl2IHN0eWxlPVwiZm9udC1mYW1pbHk6bW9ub3NwYWNlO1wiPi4uXC8uXFw8YnIgXC8+XHJcblx0XHRcdC4uLi4uPGJyIFwvPlxyXG5cdFx0XHQuQyoqKjxiciBcLz5cclxuXHRcdFx0Li4uQy48YnIgXC8+XHJcblx0XHRcdFxcLi4uXC88XC9kaXY+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxkaXYgc3R5bGU9XCJmb250LWZhbWlseTptb25vc3BhY2U7XCI+Li5cLy5cXDxiciBcLz5cclxuXHRcdFx0Li4uLi48YnIgXC8+XHJcblx0XHRcdC5DKi4uPGJyIFwvPlxyXG5cdFx0XHQuLipDLjxiciBcLz5cclxuXHRcdFx0XFwuKi5cLzxcL2Rpdj5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PGRpdiBzdHlsZT1cImZvbnQtZmFtaWx5Om1vbm9zcGFjZTtcIj4uLlwvLlxcPGJyIFwvPlxyXG5cdFx0XHQuLi4uLjxiciBcLz5cclxuXHRcdFx0LkMqLi48YnIgXC8+XHJcblx0XHRcdC4uLkMuPGJyIFwvPlxyXG5cdFx0XHRcXC4uLlwvPFwvZGl2PlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZD4xNyBzZWNvbmRzPFwvdGQ+XHJcblx0XHRcdDx0ZD4zIHNlY29uZHM8XC90ZD5cclxuXHRcdFx0PHRkPjMgc2Vjb25kczxcL3RkPlxyXG5cdFx0XHQ8dGQ+MSBzZWNvbmRzPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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