시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB4210933.333%

문제

원섭이와 상현이는 보드 게임을 구매했다. 게임판은 무한 이진 트리와 비슷한 형태이다. 게임판은 노드와 노드를 연결하는 양방향 도로로 이루어져 있다.

루트 노드는 게임판의 가장 위에 있고, 이 노드의 레벨은 0이다. 모든 노드는 항상 두 자식을 가지며, 왼쪽 자식과 오른쪽 자식이다. 왼쪽 자식의 위치는 부모 노드의 왼쪽 아래이고, 오른쪽 자식의 위치는 오른쪽 아래이다. 자식 노드의 레벨은 부모 노드의 레벨보다 1 크다.

도로는 부모 노드와 자식 노드를 연결하는 도로가 있고, 같은 레벨에 있는 노드를 모두 연결하는 도로가 있다. 같은 레벨에 있는 노드를 모두 연결하는 도로는 각 레벨의 가장 왼쪽 노드에서 시작하며, 각각의 노드와 그 오른쪽에 있는 노드를 연결한다.

한 노드에서 도로를 한 번 이용해서 다른 노드로 이동할 수 있다. 이동은 다음과 같이 총 5가지가 있으며, 한 글자로 나타낼 수 있다.

  • 왼쪽 자식으로 이동: 1
  • 오른쪽 자식으로 이동: 2
  • 부모 노드로 이동: U
  • 같은 레벨의 바로 왼쪽에 있는 노드로 이동: L
  • 같은 레벨의 바로 오른쪽에 있는 노드로 이동: R

위와 같은 이동의 연속을 경로라고 한다.

예를 들어, 루트 노드에서 '221LU'로 이동한다면, A가 적힌 노드로 이동할 수 있다.

게임판 위의 두 노드가 주어진다. 이때, 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작상하시오. 두 노드는 루트에서 이동한 경로로 주어지며, 두 경로가 같은 노드인 경우에 답은 0이다.

입력

첫째 줄에 루트에서 첫 번째 노드로 이동하는 경로가 주어진다.

둘째 줄에 루트에서 두 번째 노드로 이동하는 경로가 주어진다.

두 경로의 길이는 100,000을 넘지 않으며, 항상 올바른 경로이다. (즉, 이동할 수 없는 상황은 나타나지 않는다)

출력

첫째 줄에 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최솟값을 출력한다.

예제 입력 1

221LU
12L2

예제 출력 1

3

힌트

문제의 그림은 예제를 나타낸다.

W3sicHJvYmxlbV9pZCI6IjkyODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWI0ZGMgXHVhYzhjXHVjNzg0IFwiXHVkMmI4XHViOWFjXCIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMFx1YzEyZFx1Yzc3NFx1YzY0MCBcdWMwYzFcdWQ2MDRcdWM3NzRcdWIyOTQgXHViY2Y0XHViNGRjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1ODhcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0MCBcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1YzY0MCBcdWJlNDRcdWMyYjdcdWQ1NWMgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDAgXHViMTc4XHViNGRjXHVjNjQwIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4ZThcdWQyYjggXHViMTc4XHViNGRjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWI4MDhcdWJjYThcdWM3NDAgMFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHViNDUwIFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWJhNzAsIFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGRcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc3NFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHViZDgwXHViYWE4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHVjNzc0XHViMmU0LiBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc0MCBcdWJkODBcdWJhYTggXHViMTc4XHViNGRjXHVjNzU4IFx1YjgwOFx1YmNhOFx1YmNmNFx1YjJlNCAxIFx1ZDA2Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViODVjXHViMjk0IFx1YmQ4MFx1YmFhOCBcdWIxNzhcdWI0ZGNcdWM2NDAgXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzE5XHVjNzQwIFx1YjgwOFx1YmNhOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMTc4XHViNGRjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YjgwOFx1YmNhOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMTc4XHViNGRjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHViMjk0IFx1YWMwMSBcdWI4MDhcdWJjYThcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTc4XHViNGRjXHVjNjQwIFx1YWRmOCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZWdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjYycHg7IHdpZHRoOjQ2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViM2M0XHViODVjXHViOTdjIFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjNkOVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2QxZCA1XHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOTogMTxcL2xpPlxyXG5cdDxsaT5cdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOTogMjxcL2xpPlxyXG5cdDxsaT5cdWJkODBcdWJhYTggXHViMTc4XHViNGRjXHViODVjIFx1Yzc3NFx1YjNkOTogVTxcL2xpPlxyXG5cdDxsaT5cdWFjMTlcdWM3NDAgXHViODA4XHViY2E4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWIzZDk6IEw8XC9saT5cclxuXHQ8bGk+XHVhYzE5XHVjNzQwIFx1YjgwOFx1YmNhOFx1Yzc1OCBcdWJjMTRcdWI4NWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5OiBSPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM3NzRcdWIzZDlcdWM3NTggXHVjNWYwXHVjMThkXHVjNzQ0IFx1YWNiZFx1Yjg1Y1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjhlOFx1ZDJiOCBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWMxMWMgJiMzOTsyMjFMVSYjMzk7XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNFx1YmE3NCwgQVx1YWMwMCBcdWM4MDFcdWQ3OGMgXHViMTc4XHViNGRjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWQzMTAgXHVjNzA0XHVjNzU4IFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDU1YyBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMGMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI0NTAgXHViMTc4XHViNGRjXHViMjk0IFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVhY2JkXHViODVjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViNDUwIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHViMTc4XHViNGRjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWIyZjVcdWM3NDAgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViMTc4XHViNGRjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWQ1NmRcdWMwYzEgXHVjNjJjXHViYzE0XHViOTc4IFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gKFx1Yzk4OSwgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzQwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHViMTc4XHViNGRjXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3NzRcdWIzZDkgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNjA4XHVjODFjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkyODMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCb2FyZCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFNsYXZrbyBoYXZlIGEgbmV3IGJvYXJkIGdhbWUuIFRoZSBnYW1lIGJvYXJkIHJlc2VtYmxlcyBhIGNvbXBsZXRlIGluZmluaXRlIGJpbmFyeSB0cmVlLiBNb3JlIHByZWNpc2VseSwgdGhlIGJvYXJkIGNvbnNpc3RzIG9mIG5vZGVzIGFuZCB0d28td2F5IHJvYWRzIGNvbm5lY3RpbmcgdGhlbS4gVGhlIHJvb3Qgbm9kZSBpcyBsb2NhdGVkIGF0IHRoZSB0b3Agb2YgdGhlIGJvYXJkIGFuZCB3ZSBzYXkgaXQgaXMgYXQgbGV2ZWwgemVyby4gRWFjaCBub2RlIGhhcyBleGFjdGx5IHR3byBjaGlsZHJlbiwgdGhlIGxlZnQgY2hpbGQgYW5kIHRoZSByaWdodCBjaGlsZCwgbG9jYXRlZCBpbiB0aGUgbG93ZXItbGVmdCBhbmQgdGhlIGxvd2VyLXJpZ2h0IGRpcmVjdGlvbnMgb2YgdGhlIHBhcmVudCBub2RlLiBUaGUgbGV2ZWwgb2YgYSBjaGlsZCBub2RlIGlzIG9uZSBncmVhdGVyIHRoYW4gdGhlIGxldmVsIG9mIHRoZSBwYXJlbnQgbm9kZS4gSW4gYWRkaXRpb24gdG8gcm9hZHMgY29ubmVjdGluZyBhIHBhcmVudCBub2RlIHdpdGggaXRzIGNoaWxkcmVuLCB0aGVyZSBhcmUgcm9hZHMgY29ubmVjdGluZyBhbGwgb2YgdGhlIG5vZGVzIGF0IGEgcGFydGljdWxhciBsZXZlbCAmbmRhc2g7IGZvciBlYWNoIGxldmVsLCBzdGFydGluZyBmcm9tIHRoZSBsZWZ0bW9zdCBub2RlLCB0aGVyZSBpcyBhIHJvYWQgY29ubmVjdGluZyBlYWNoIG5vZGUgdG8gdGhlIG5leHQgbm9kZSB0byB0aGUgcmlnaHQgb24gdGhlIHNhbWUgbGV2ZWwuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZWdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjYycHg7IHdpZHRoOjQ2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkVhY2ggcGF0aCB0aHJvdWdoIHRoZSBnYW1lIGJvYXJkIGlzIGEgc2VxdWVuY2Ugb2Ygc3RlcHMsIGVhY2ggbW92aW5nIGZyb20gYSBub2RlIHRvIGEgZGlmZmVyZW50IG5vZGUgdmlhIGEgc2luZ2xlIHJvYWQuIEVhY2ggc3RlcCBjYW4gYmUgZGVzY3JpYmVkIGJ5IGEgc2luZ2xlIGNoYXJhY3RlciBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmNoYXJhY3RlciAmcXVvdDsxJnF1b3Q7IGRlc2NyaWJlcyBtb3ZpbmcgZnJvbSBhIG5vZGUgdG8gaXRzIGxlZnQgY2hpbGQsPFwvbGk+XHJcblx0PGxpPmNoYXJhY3RlciAmcXVvdDsyJnF1b3Q7IGRlc2NyaWJlcyBtb3ZpbmcgZnJvbSBhIG5vZGUgdG8gaXRzIHJpZ2h0IGNoaWxkLDxcL2xpPlxyXG5cdDxsaT5jaGFyYWN0ZXIgJnF1b3Q7VSZxdW90OyBkZXNjcmliZXMgbW92aW5nIGZyb20gYSBub2RlIHRvIGl0cyBwYXJlbnQsPFwvbGk+XHJcblx0PGxpPmNoYXJhY3RlciAmcXVvdDtMJnF1b3Q7IGRlc2NyaWJlcyBtb3ZpbmcgZnJvbSBhIG5vZGUgdG8gdGhlIG5leHQgbm9kZSB0byB0aGUgbGVmdCBvbiB0aGUgc2FtZSBsZXZlbCw8XC9saT5cclxuXHQ8bGk+Y2hhcmFjdGVyICZxdW90O1ImcXVvdDsgZGVzY3JpYmVzIG1vdmluZyBmcm9tIGEgbm9kZSB0byB0aGUgbmV4dCBub2RlIHRvIHRoZSByaWdodCBvbiB0aGUgc2FtZSBsZXZlbC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgd2Ugd2VyZSB0byBzdGFydCBhdCB0aGUgcm9vdCBub2RlIGFuZCB0YWtlIHRoZSBzZXF1ZW5jZSBvZiBzdGVwcyAmcXVvdDsyMjFMVSZxdW90OyB3ZSB3b3VsZCBlbmQgdXAgaW4gdGhlIG5vZGUgZGVub3RlZCB3aXRoIHRoZSBsZXR0ZXIgJmJkcXVvO0FcdTIwMWYgaW4gdGhlIGZpZ3VyZSBhYm92ZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCwgZ2l2ZW4gdHdvIG5vZGVzIG9uIHRoZSBib2FyZCwgZmluZCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHN0ZXBzIG5lZWRlZCB0byBnbyBmcm9tIG9uZSBub2RlIHRvIHRoZSBvdGhlci4gVGhlIHR3byBub2RlcyBhcmUgZ2l2ZW4gYnkgc3BlY2lmeWluZyBwYXRocyBmcm9tIHRoZSByb290IG5vZGUgdG8gdGhlbS4gSWYgdGhlIHR3byBwYXRocyBsZWFkIHRvIHRoZSBzYW1lIG5vZGUsIHRoZSBhbnN3ZXIgaXMgemVyby48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgYXQgbW9zdCAxMDAgMDAwIGNoYXJhY3RlcnMgJm5kYXNoOyB0aGUgcGF0aCBmcm9tIHRoZSByb290IHRvIHRoZSBmaXJzdCBub2RlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBhdCBtb3N0IDEwMCAwMDAgY2hhcmFjdGVycyAmbmRhc2g7IHRoZSBwYXRoIGZyb20gdGhlIHJvb3QgdG8gdGhlIHNlY29uZCBub2RlLjxcL3A+XHJcblxyXG48cD5UaGUgdHdvIHBhdGhzIHdpbGwgYmUgdmFsaWQgKGl0IHdpbGwgYmUgcG9zc2libGUgdG8gbWFrZSBldmVyeSBtb3ZlIGluIGJvdGggc2VxdWVuY2VzKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAtIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygc3RlcHMgbmVlZGVkIHRvIGdvIGZyb20gb25lIG5vZGUgdG8gdGhlIG90aGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2013 > Day 2 4번