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

문제

알라딘은 궁전에서 지루한 삶에 싫증을 느꼈다. 항상 변함없이 똑같은 일과 부인 자스민과 아이들은 알라딘에게 더 이상 큰 흥미를 가져다주지 못했다. 그는, 더 이상 궁전에서 지루한 삶을 살 수 없다고 생각했고 모험을 떠나기로 했다.

알라딘이 살고있는 나라에는 요정이 나타나는 램프가 묻혀있다는 전설이 있다. 이 램프는 지금까지 그 누구도 찾지 못했던 램프이다. 알라딘은 이 램프를 찾기로 했다.

예로부터 내려오는 전설에 의하면 램프는 사막에 묻혀있다. 사막은 N*N 칸이 그리드형태로 배열되어 있는 모습으로 나타낼 수 있다. 행과 열은 위에서 부터 아래로, 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 어떤 칸에는 마법사가 살고 있고, 마법사는 알라딘에게 가야할 방향을 알려준다.

알라딘은 사막의 가장 왼쪽 위 칸에서 모험을 시작한다. 이 날은 월요일이며, 알라딘은 오른쪽을 보고 있다. 알라딘은 아래 세 단계를 거쳐서 다음 칸으로 이동하게 된다.

  1. 알라딘이 있는 칸에 마법사가 깨어있다면, 알라딘은 마법사가 말해주는 방향으로 방향을 바꾼다. 이때, 마법사가 말하는 방향은 90도 왼쪽 방향과 오른족 방향 둘 중 하나이다.
  2. 알라딘이 한 칸 전진했을 때, 사막읙 경계를 벗어난다면, 그는 180도 방향을 바꾼다.
  3. 알라딘은 한 칸 전진하고, 이것은 정확하게 하루가 걸린다. (1, 2단계에 걸리는 시간은 없다)

모든 마법사가 말해주는 방향은 요일에 따라서 다르고, 길이가 7인 문자열로 나타낼 수 있다. 문자열은 'L', 'R', 'S'로 이루어져 있으며, 각 문자는 어떤 요일에 무슨 방향을 말해주는지를 나타낸다. 첫 번째 문자는 월요일, 두 번째 문자는 화요일, ... 이며, 'L'은 왼쪽으로, 'R'은 오른쪽으로 방향을 바꾸라는 의미이다. 'S'는 그 날은 마법사가 잠을 잔다는 뜻이다.

알라딘은 모험을 떠나기전에 유명한 예언가는 알라딘이 방향을 K번 바꾼다면 (1단계와 2단계) 램프를 발견한다고 말했다. 이 예언대로라면 알라딘은 며칠 만에 램프를 발견하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사막의 크기 N과 예언가의 예언 K가 주어진다. (2 ≤ N ≤ 200, 1 ≤ K ≤ 1,000,000,000)

둘째 줄에는 마법사의 수 M이 주어진다. (0 ≤ M ≤ 10000)

다음 M개 줄에는 마법사의 위치 R, C와 스케쥴을 나타내는 문자열이 주어진다. R은 마법사가 있는 행의 번호, C는 열의 번호이다.

한 칸에 두 명 이상의 마법사가 있는 경우는 없으며, 항상 (1, 1)에는 마법사가 없다.

출력

첫째 줄에 램프를 발견하는데 총 며칠이 걸리는지 출력한다.

예제 입력 1

3 1
0

예제 출력 1

2

예제 입력 2

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

예제 출력 2

4

예제 입력 3

5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS

예제 출력 3

10
W3sicHJvYmxlbV9pZCI6IjI5NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWI3N2NcdWI1MThcdWFjZmMgXHViN2E4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWI3N2NcdWI1MThcdWM3NDAgXHVhZDgxXHVjODA0XHVjNWQwXHVjMTFjIFx1YzljMFx1YjhlOFx1ZDU1YyBcdWMwYjZcdWM1ZDAgXHVjMmViXHVjOTlkXHVjNzQ0IFx1YjI5MFx1YWYwOFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YmNjMFx1ZDU2OFx1YzVjNlx1Yzc3NCBcdWI2MTFcdWFjMTlcdWM3NDAgXHVjNzdjXHVhY2ZjIFx1YmQ4MFx1Yzc3OCBcdWM3OTBcdWMyYTRcdWJiZmNcdWFjZmMgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1YzU0Y1x1Yjc3Y1x1YjUxOFx1YzVkMFx1YWM4YyBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1ZDA3MCBcdWQ3NjVcdWJiZjhcdWI5N2MgXHVhYzAwXHVjODM4XHViMmU0XHVjOGZjXHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViMjk0LCBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YWQ4MVx1YzgwNFx1YzVkMFx1YzExYyBcdWM5YzBcdWI4ZThcdWQ1NWMgXHVjMGI2XHVjNzQ0IFx1YzBiNCBcdWMyMTggXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YWNlMCBcdWJhYThcdWQ1ZDhcdWM3NDQgXHViNWEwXHViMDk4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHViNzdjXHViNTE4XHVjNzc0IFx1YzBiNFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgXHVjNjk0XHVjODE1XHVjNzc0IFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWI3YThcdWQ1MDRcdWFjMDAgXHViYjNiXHVkNjAwXHVjNzg4XHViMmU0XHViMjk0IFx1YzgwNFx1YzEyNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI3YThcdWQ1MDRcdWIyOTQgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YWRmOCBcdWIyMDRcdWFkNmNcdWIzYzQgXHVjYzNlXHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjM1OCBcdWI3YThcdWQ1MDRcdWM3NzRcdWIyZTQuIFx1YzU0Y1x1Yjc3Y1x1YjUxOFx1Yzc0MCBcdWM3NzQgXHViN2E4XHVkNTA0XHViOTdjIFx1Y2MzZVx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWIwYjRcdWI4MjRcdWM2MjRcdWIyOTQgXHVjODA0XHVjMTI0XHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YmE3NCBcdWI3YThcdWQ1MDRcdWIyOTQgXHVjMGFjXHViOWM5XHVjNWQwIFx1YmIzYlx1ZDYwMFx1Yzc4OFx1YjJlNC4gXHVjMGFjXHViOWM5XHVjNzQwIE4qTiBcdWNlNzhcdWM3NzQgXHVhZGY4XHViOWFjXHViNGRjXHVkNjE1XHVkMGRjXHViODVjIFx1YmMzMFx1YzVmNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViYWE4XHVjMmI1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzQwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWJkODBcdWQxMzAgXHVjNTQ0XHViNzk4XHViODVjLCBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWI5YzhcdWJjOTVcdWMwYWNcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHViOWM4XHViYzk1XHVjMGFjXHViMjk0IFx1YzU0Y1x1Yjc3Y1x1YjUxOFx1YzVkMFx1YWM4YyBcdWFjMDBcdWM1N2NcdWQ1NjAgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YzU0Y1x1YjgyNFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHViNzdjXHViNTE4XHVjNzQwIFx1YzBhY1x1YjljOVx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM1ZDBcdWMxMWMgXHViYWE4XHVkNWQ4XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjBhMFx1Yzc0MCBcdWM2ZDRcdWM2OTRcdWM3N2NcdWM3NzRcdWJhNzAsIFx1YzU0Y1x1Yjc3Y1x1YjUxOFx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNTRjXHViNzdjXHViNTE4XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWMxMzggXHViMmU4XHVhY2M0XHViOTdjIFx1YWM3MFx1Y2NkMFx1YzExYyBcdWIyZTRcdWM3NGMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjNTRjXHViNzdjXHViNTE4XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM1ZDAgXHViOWM4XHViYzk1XHVjMGFjXHVhYzAwIFx1YWU2OFx1YzViNFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjNTRjXHViNzdjXHViNTE4XHVjNzQwIFx1YjljOFx1YmM5NVx1YzBhY1x1YWMwMCBcdWI5ZDBcdWQ1NzRcdWM4ZmNcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYmNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViOWM4XHViYzk1XHVjMGFjXHVhYzAwIFx1YjlkMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDAgOTBcdWIzYzQgXHVjNjdjXHVjYWJkIFx1YmMyOVx1ZDVhNVx1YWNmYyBcdWM2MjRcdWI5NzhcdWM4NzEgXHViYzI5XHVkNWE1IFx1YjQ1OCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NGNcdWI3N2NcdWI1MThcdWM3NzQgXHVkNTVjIFx1Y2U3OCBcdWM4MDRcdWM5YzRcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWI5YzlcdWM3NTkgXHVhY2JkXHVhY2M0XHViOTdjIFx1YmM5N1x1YzViNFx1YjA5Y1x1YjJlNFx1YmE3NCwgXHVhZGY4XHViMjk0IDE4MFx1YjNjNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmJjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NGNcdWI3N2NcdWI1MThcdWM3NDAgXHVkNTVjIFx1Y2U3OCBcdWM4MDRcdWM5YzRcdWQ1NThcdWFjZTAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgXHVkNTU4XHViOGU4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gKDEsIDJcdWIyZThcdWFjYzRcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM1YzZcdWIyZTQpPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjljOFx1YmM5NVx1YzBhY1x1YWMwMCBcdWI5ZDBcdWQ1NzRcdWM4ZmNcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YzY5NFx1Yzc3Y1x1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHViMmU0XHViOTc0XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWFjMDAgN1x1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmIzM5O0wmIzM5OywgJiMzOTtSJiMzOTssICYjMzk7UyYjMzk7XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzY5NFx1Yzc3Y1x1YzVkMCBcdWJiMzRcdWMyYTggXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjlkMFx1ZDU3NFx1YzhmY1x1YjI5NFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHViMjk0IFx1YzZkNFx1YzY5NFx1Yzc3YywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgXHVkNjU0XHVjNjk0XHVjNzdjLCAuLi4gXHVjNzc0XHViYTcwLCAmIzM5O0wmIzM5O1x1Yzc0MCBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMsICYjMzk7UiYjMzk7XHVjNzQwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gJiMzOTtTJiMzOTtcdWIyOTQgXHVhZGY4IFx1YjBhMFx1Yzc0MCBcdWI5YzhcdWJjOTVcdWMwYWNcdWFjMDAgXHVjN2EwXHVjNzQ0IFx1Yzc5NFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Yjc3Y1x1YjUxOFx1Yzc0MCBcdWJhYThcdWQ1ZDhcdWM3NDQgXHViNWEwXHViMDk4XHVhZTMwXHVjODA0XHVjNWQwIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM2MDhcdWM1YjhcdWFjMDBcdWIyOTQgXHVjNTRjXHViNzdjXHViNTE4XHVjNzc0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBLXHViYzg4IFx1YmMxNFx1YWZiY1x1YjJlNFx1YmE3NCAoMVx1YjJlOFx1YWNjNFx1YzY0MCAyXHViMmU4XHVhY2M0KSBcdWI3YThcdWQ1MDRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTVjXHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YzYwOFx1YzViOFx1YjMwMFx1Yjg1Y1x1Yjc3Y1x1YmE3NCBcdWM1NGNcdWI3N2NcdWI1MThcdWM3NDAgXHViYTcwXHVjZTYwIFx1YjljY1x1YzVkMCBcdWI3YThcdWQ1MDRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWI5YzlcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWFjZmMgXHVjNjA4XHVjNWI4XHVhYzAwXHVjNzU4IFx1YzYwOFx1YzViOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMjAwLCAxICZsZTsgSyAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHViYzk1XHVjMGFjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBNICZsZTsgMTAwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWJjOTVcdWMwYWNcdWM3NTggXHVjNzA0XHVjZTU4IFIsIENcdWM2NDAgXHVjMmE0XHVjZjAwXHVjOTc0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBSXHVjNzQwIFx1YjljOFx1YmM5NVx1YzBhY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVkNTg5XHVjNzU4IFx1YmM4OFx1ZDYzOCwgQ1x1YjI5NCBcdWM1ZjRcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVjZTc4XHVjNWQwIFx1YjQ1MCBcdWJhODUgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjljOFx1YmM5NVx1YzBhY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVkNTZkXHVjMGMxICgxLCAxKVx1YzVkMFx1YjI5NCBcdWI5YzhcdWJjOTVcdWMwYWNcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViN2E4XHVkNTA0XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWNkMWQgXHViYTcwXHVjZTYwXHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktSVVNLQSIsImRlc2NyaXB0aW9uIjoiPHA+QWxhZGRpbiBoYXMgYmVjb21lIGJvcmVkIG9mIGxpZmUgYXQgdGhlIHBhbGFjZS4gSGUgaGFzIGEgc3RlYWR5IGpvYiwgaGlzIHdpZmUgSmFzbWluZSwga2lkcyBhcmUgb24gdGhld2F5IGFuZCBsaWZlIGlzIGJlY29taW5nIG1vbm90b25vdXMuIFByb21wdGVkIGJ5IGFsbCB0aGlzLCBoZSBoYXMgZGVjaWRlZCB0byBoYXZlIG9uZSBtb3JlIGFkdmVudHVyZSBiZWZvcmUgc2V0dGxpbmcgZG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGUgaGFzIGRlY2lkZWQgdG8gZmluZCB0aGUgR29sZGVuIFBlYXIsIGFuIGV4dHJlbWVseSB2YWx1YWJsZSBsZWdlbmRhcnkgYXJ0aWZhY3QgdGhhdCBubyBvbmUgaGFzIGJlZW4gYWJsZSB0byBmaW5kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZGVzZXJ0IEFsYWRkaW4gaXMgc2VhcmNoaW5nIGlzIGNhbiBiZSBtb2RlbGVkIGFzIGFuIE4mdGltZXM7TiBncmlkIG9mIGNlbGxzLiBSb3dzIGFuZCBjb2x1bW5zIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggTiB0b3AgdG8gYm90dG9tIGFuZCBsZWZ0IHRvIHJpZ2h0LiBTb21lIG9mIHRoZSBjZWxscyBpbiB0aGUgZGVzZXJ0IGNvbnRhaW4gd2l6YXJkcyB0aGF0IGhlbHAgQWxhZGRpbiYjMzk7cyBxdWVzdCBpbiBhbiB1bnVzdWFsIHdheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxhZGRpbiBzdGFydHMgaGlzIHF1ZXN0IGluIHRoZSB0b3AgbGVmdCBjb3JuZXIgb2YgdGhlIGRlc2VydCBvbiBhIE1vbmRheSBmYWNpbmcgcmlnaHQuIEhpcyBtb3ZlbWVudCBpbnZvbHZlcyByZXBlYXRpbmcgdGhlc2Ugc3RlcHM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+SWYgdGhlIGN1cnJlbnQgY2VsbCBjb250YWlucyBhIHdpemFyZCB0aGF0IGlzIGF3YWtlLCB0aGVuIEFsYWRkaW4gdHVybnMgOTAgZGVncmVlcyBsZWZ0IG9yIHJpZ2h0LCBkZXBlbmRpbmcgb24gd2hhdCB0aGUgd2l6YXJkIHNheXMuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIG1vdmluZyBmb3J3YXJkIHdvdWxkIHRha2UgQWxhZGRpbiBvdXQgb2YgZGVzZXJ0LCBoZSB0dXJucyAxODAgZGVncmVlcy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+QWxhZGRpbiBtb3ZlcyBmb3J3YXJkIG9uZSBjZWxsIGFuZCBpdCB0YWtlcyBoaW0gZXhhY3RseSBvbmUgZGF5LiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZvciBlYWNoIHdpemFyZCB3ZSBrbm93IGhpcyBsb2NhdGlvbiBhbmQgaGlzIGFjdGl2aXR5IHNjaGVkdWxlIGZvciBlYWNoIGRheSBvZiB0aGUgd2Vlay4gVGhlIHNjaGVkdWxlIGlzIGEgc3RyaW5nIG9mIGV4YWN0bHkgc2V2ZW4gbGV0dGVycyAmIzM5O0wmIzM5OywgJiMzOTtSJiMzOTsgb3IgJiMzOTtTJiMzOTssIGVhY2ggY2hhcmFjdGVyIHRlbGxpbmcgdXMgd2hhdCB0aGUgd2l6YXJkIGRvZXMgb24gb25lIGRheSBvZiB0aGUgd2VlayAoc3RhcnRpbmcgd2l0aCBNb25kYXkpLiBUaGUgbGV0dGVyICYjMzk7TCYjMzk7IG1lYW5zIHRoYXQgQWxhZGRpbiB3aWxsIGJlIHRvbGQgdG8gdHVybiBsZWZ0LCAmIzM5O1ImIzM5OyB0aGF0IEFsYWRkaW4gd2lsbCBiZSB0b2xkIHRvIHR1cm4gcmlnaHQsIHdoaWxlICYjMzk7UyYjMzk7IG1lYW5zIHRoZSB3aXphcmQgc2xlZXBzIHRoYXQgZGF5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbiBvbGQgcHJvcGhlY3kgc2F5cyB0aGF0IGFmdGVyIEsgY2hhbmdlcyBpbiBkaXJlY3Rpb24gKGluIHN0ZXBzIDEgYW5kXC9vciAyKSBBbGFkZGluIHdpbGwgZmluZCB0aGUgUGVhci4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyBob3cgbWFueSBkYXlzIHRoZSBzZWFyY2ggd2lsbCBsYXN0LCBhY2NvcmRpbmcgdG8gdGhlIGFuY2llbnQgcHJvcGhlY3kuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSyAoMiAmbGU7IE4gJmxlOyAyMDAsIDEgJmxlOyBLICZsZTsgMSAwMDAgMDAwIDAwMCksIHRoZSBzaXplIG9mIHRoZSBkZXNlcnQgYW5kIHRoZSBudW1iZXIgb2YgZGlyZWN0aW9uIGNoYW5nZXMgaW4gdGhlIHByb3BoZWN5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBNICgwICZsZTsgTSAmbGU7IDEwMDAwKSwgdGhlIG51bWJlciBvZiB3aXphcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMSAmbGU7IFIsIEMgJmxlOyBOKSwgYW5kIGEgc3RyaW5nIG9mIHNldmVuIGxldHRlcnMgJiMzOTtMJiMzOTssICYjMzk7UiYjMzk7IG9yICYjMzk7UyYjMzk7LiBUaGUgbnVtYmVycyByZXByZXNlbnQgdGhlIHJvdyBhbmQgY29sdW1uIHdoZXJlIHRoZSB3aXphcmQgaXMgbG9jYXRlZCwgd2hpbGUgdGhlIHN0cmluZyBpcyBoaXMgc2NoZWR1bGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byB3aXphcmRzIHdpbGwgc2hhcmUgdGhlIHNhbWUgY2VsbCwgbm9yIHdpbGwgdGhlcmUgYmUgYSB3aXphcmQgaW4gY2VsbCAoMSwgMSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZW5ndGggb2YgdGhlIHNlYXJjaCBpbiBkYXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUsIEFsYWRkaW4gbW92ZXMgdHdpY2UsIHJlYWNoaW5nIHRoZSBlZGdlIG9mIHRoZSBkZXNlcnQuIEhlIHRoZW4gdHVybnMgMTgwIGRlZ3JlZXMgYW5kIGZpbmRzIHRoZSBQZWFyLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIGV4YW1wbGUsIEFsYWRkaW4gcmVhY2hlcyB0aGUgZmlyc3Qgd2l6YXJkIG9uIHRoZSB0aGlyZCBkYXksIGJ1dCB0aGUgd2l6YXJkIGlzIHNsZWVwaW5nIHNvIEFsYWRkaW4gY29udGludWVzIGluIHRoZSBzYW1lIGRpcmVjdGlvbi4gQWZ0ZXIgdHdvIG1vcmUgZGF5cyBoZSByZWFjaGVzIHRoZSBvdGhlciB3aXphcmQgd2hvIHRlbGxzIGhpbSB0byB0dXJuIGxlZnQuIEFsYWRkaW4gZG9lcyBzbywgcmVhY2hlcyB0aGUgZWRnZSBvZiB0aGUgZGVzZXJ0LCB0dXJucyBiYWNrIGFuZCBmaW5kcyB0aGUgcGFpci48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #5 6번