시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 575 136 80 20.408%

문제

곰돌이가 숲에서 꿀벌이 숨겨놓은 비밀 꿀단지를 발견했다. 단지에 가득 들어 있는 꿀을 먹으려는 순간 근처에 있는 벌 한 마리가 곰돌이를 발견하고 동료 벌들에게 신호를 보냈다. 곰돌이는 곧 수많은 벌들이 벌집을 출발해 자신을 공격할 것을 직감하고, 벌들의 공격을 피해 자신의 집으로 돌아가야 한다고 생각했다. 곰돌이는 꿀단지가 있는 위치에 가능한 한 오래 남아 꿀을 먹은 후 꿀단지를 떠나 안전하게 집에 도착하고 싶다. 곰돌이가 가장 늦게 떠나도 되는 시간을 계산하라.

곰돌이와 벌들이 있는 숲은 단위 정사각형들의 칸으로 구성된 N 행과 N 개의 열의 격자 판이다. 격자 판의 각 정사각형 칸에는 나무 한 그루가 있거나, 풀밭이거나, 벌집이거나, 곰돌이 집이다. 곰돌이는 한 번에 한 칸씩만 동, 서, 남, 북으로 인접한 칸들 중 하나로 이동할 수 있다. (대각선 방향으로 인접한 칸으로는 이동할 수 없다.) 그리고 곰돌이는 나무나 벌집이 있는 칸으로는 이동할 수 없고 오직 풀밭이 있는 인접한 칸으로만 이동할 수 있다. 곰돌이는 1분에 최대 S칸을 움직일 수 있다.

벌이 곰돌이를 최초로 발견하고 다른 벌들에게 신호를 보내는 순간에 곰돌이는 꿀단지가 있는 풀밭 간에 있다. 벌집이 있는 칸에는 무수히 많은 벌들이 있다고 가정한다. (벌집이 있는 칸은 하나 이상일 수 있음에 유의하자.) 이 숲의 시계는 분 단위로 움직인다. 매 분마다 다음과 같은 이벤트가 발생한다:

  • 만약 곰돌이가 현재 꿀을 먹고 있다면, 곰돌이는 자신이 계속 꿀을 먹을지 아니면 꿀단지를 떠나 집으로 갈지를 결정해야 한다. 만약 꿀을 계속 먹겠다고 결정하면 1 분 동안은 움직일 수 없다. 반대로 가겠다고 결정하면, 즉각 떠나야 하며 1 분에 최대 S 칸을 이동할 수 있다. 떠나게 되면 꿀단지는 가지고 갈 수 없기 때문에, 떠난 후에는 꿀을 다시 먹을 순 없다. 곰돌이가 이동할 수 있는 칸은 위에서 설명한 것처럼 동, 서, 남, 북으로 인접한 풀밭이 있는 칸이다.
  • 곰돌이가 1분 동안 꿀을 먹거나 움직인 후, 1 분이 완료되는 순간 벌들은 자신들이 있는 칸에서 인접한 모든 칸으로 퍼져 나간다. 이 때, 벌들이 이동할 수 있는 칸은 동, 서, 남, 북 중 한 방향으로 인접한 칸이어야 하며 그 중 풀밭이 있는 칸이어야 한다. (대각선 방향으로 이웃한 칸으로는 이동이 불가능하다.) 결국, 벌들이 있는 각 칸에서 그 칸에 인접한 모든 풀밭 칸으로 벌들이 동시에 한 칸씩 퍼져 나가게 된다. 주의할 점은 어떤 칸에 벌들이 있게 되면 그 칸에는 영원히 벌들이 존재하게 된다는 것이다. 즉, 시간이 흐를수록 벌들이 숲의 여러 칸으로 확산되어 벌들이 있는 칸이 계속 늘어나게 된다.

다시 한번 벌들의 움직임을 설명하면 다음과 같다 : 벌 한마리가 신호를 보내는 순간에는 벌집이 있는 칸들에만 벌들이 있게 된다. 1 분이 완료되는 순간에는 벌들은 벌집이 있는 칸들과 그 칸들에 인접한 모든 풀밭 칸을 차지하게 된다. 2 분이 완료되는 순간에는 벌집이 있는 칸 모두와 벌집에 인접한 모든 풀밭 칸들과 그 풀밭 칸들에 인접한 모든 풀밭 칸들을 차지하게 된다. 충분히 긴 시간이 지나게 되면, 벌집에서 출발하여 도달 가능한 모든 풀밭 칸을 벌들이 차지하게 될 것이다.

곰돌이와 벌들은 숲 밖으로 나갈 수 없으며, 곰돌이가 꿀을 먹는 시간은 정수 값이다.

벌들이 차지한 칸에 곰돌이가 함께 있게 되는 순간 곰돌이는 벌들에 의해 잡히게 된다.

숲의 지도가 주어졌을 때, 곰돌이가 집에 도착하기 전에 벌들에게 잡히지 않으면서 꿀단지가 있는 위치에서 계속해서 꿀을 먹을 수 있는 가장 긴 시간을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다 :

  • 첫째 줄은 두 정수 N과 S가 공백을 사이에 두고 주어진다.
  • 다음 N개의 줄에는 지도 정보가 주어진다. 각 줄에는 N개의 문자가 공백 없이 주어지는 데, 각 문자는 한 칸의 상태를 다음과 같이 나타낸다 :
    • T는 나무가 있는 칸을 나타낸다.
    • G는 풀밭이 있는 칸을 나타낸다.
    • M은 곰돌이의 최초 위치(꿀단지가 있는 칸)이고 동시에 풀밭 칸이기도 하다.
    • D는 곰돌이의 집을 나타내는데, 곰돌이는 들어갈 수 있지만 벌들은 들어갈 수 없다.
    • H는 벌집이 있는 칸을 나타낸다.

주의사항 : 지도는 항상 정확히 하나의 M, 정확히 하나의 D 그리고 하나 이상의 H를 포함하고 있다. 또한 곰돌이의 최초 위치부터 곰돌이의 집을 연결하는 G 칸들의 경로가 하나 이상 반드시 존재하며, 적어도 하나 이상의 벌집과 꿀단지(곰돌이의 최초 위치)를 연결하는 풀밭 칸의 경로도 하나 이상 존재한다. 곰돌이의 최초 위치에 인접한 칸에 곰돌이의 집이나 벌집이 위치할 수도 있다. 마지막으로 벌들은 곰돌이의 집을 통과할 수 없다.

  • 1 <= N <= 800 지도의 크기 (한 변을 이루는 칸의 수)
  • 1 <= S <= 1,000 곰돌이가 1 분 동안 움직일 수 있는 칸의 최대 수

출력

출력은 반드시 표준 출력으로 해야 하며, 한 줄에 하나의 정수를 출력한다. 그 정수는 곰돌이가 최초 위치에서 안전하게 집에 도달하기 위해, 꿀을 계속해서 먹을 수 있는 가장 긴 시간(분)이다.

만약 곰돌이가 벌들에게 잡히지 않고 집에 도달하는 것이 불가능하다면 표준 출력으로 -1을 출력해야 한다.

예제 입력 1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

예제 출력 1

1

예제 입력 2

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

예제 출력 2

2

힌트

곰돌이가 1 분 동안 꿀을 먹은 후, 오른쪽 방향으로 일직선 최단 경로를 통해 다음 2분에 걸쳐 안전하게 집에 도착할 수 있다. 따라서 곰돌이가 꿀을 먹을 수 있는 최장 시간은 1분이 되어 출력 값은 1이다.

W3sicHJvYmxlbV9pZCI6IjU0NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjBcdWIzY2NcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCBcdWMyMzJcdWM1ZDBcdWMxMWMgXHVhZmMwXHViYzhjXHVjNzc0IFx1YzIyOFx1YWNhOFx1YjE5M1x1Yzc0MCBcdWJlNDRcdWJjMDAgXHVhZmMwXHViMmU4XHVjOWMwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHViMmU4XHVjOWMwXHVjNWQwIFx1YWMwMFx1YjRkZCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWZjMFx1Yzc0NCBcdWJhMzlcdWM3M2NcdWI4MjRcdWIyOTQgXHVjMjFjXHVhYzA0IFx1YWRmY1x1Y2M5OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzhjIFx1ZDU1YyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVhY2YwXHViM2NjXHVjNzc0XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YWNlMCBcdWIzZDlcdWI4Y2MgXHViYzhjXHViNGU0XHVjNWQwXHVhYzhjIFx1YzJlMFx1ZDYzOFx1Yjk3YyBcdWJjZjRcdWIwYzhcdWIyZTQuIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YjI5NCBcdWFjZTcgXHVjMjE4XHViOWNlXHVjNzQwIFx1YmM4Y1x1YjRlNFx1Yzc3NCBcdWJjOGNcdWM5ZDFcdWM3NDQgXHVjZDljXHViYzFjXHVkNTc0IFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVhYzgzXHVjNzQ0IFx1YzljMVx1YWMxMFx1ZDU1OFx1YWNlMCwgXHViYzhjXHViNGU0XHVjNzU4IFx1YWNmNVx1YWNhOVx1Yzc0NCBcdWQ1M2NcdWQ1NzQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC4gXHVhY2YwXHViM2NjXHVjNzc0XHViMjk0IFx1YWZjMFx1YjJlOFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjNjI0XHViNzk4IFx1YjBhOFx1YzU0NCBcdWFmYzBcdWM3NDQgXHViYTM5XHVjNzQwIFx1ZDZjNCBcdWFmYzBcdWIyZThcdWM5YzBcdWI5N2MgXHViNWEwXHViMDk4IFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWM5ZDFcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVhY2YwXHViM2NjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWIyYTZcdWFjOGMgXHViNWEwXHViMDk4XHViM2M0IFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWFjZjBcdWIzY2NcdWM3NzRcdWM2NDAgXHViYzhjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWMyMzJcdWM3NDAgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YjRlNFx1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIE4gXHVkNTg5XHVhY2ZjIE4gXHVhYzFjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWFjYTlcdWM3OTAgXHVkMzEwXHVjNzc0XHViMmU0LiBcdWFjYTlcdWM3OTAgXHVkMzEwXHVjNzU4IFx1YWMwMSBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjZTc4XHVjNWQwXHViMjk0IFx1YjA5OFx1YmIzNCBcdWQ1NWMgXHVhZGY4XHViOGU4XHVhYzAwIFx1Yzc4OFx1YWM3MFx1YjA5OCwgXHVkNDgwXHViYzJkXHVjNzc0XHVhYzcwXHViMDk4LCBcdWJjOGNcdWM5ZDFcdWM3NzRcdWFjNzBcdWIwOTgsIFx1YWNmMFx1YjNjY1x1Yzc3NCBcdWM5ZDFcdWM3NzRcdWIyZTQuIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1ZDU1YyBcdWNlNzhcdWM1MjlcdWI5Y2MgXHViM2Q5LCBcdWMxMWMsIFx1YjBhOCwgXHViZDgxXHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWI0ZTQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YjMwMFx1YWMwMVx1YzEyMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4pIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjZjBcdWIzY2NcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0XHViMDk4IFx1YmM4Y1x1YzlkMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzNjXHViODVjXHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhY2UwIFx1YzYyNFx1YzljMSBcdWQ0ODBcdWJjMmRcdWM3NzQgXHVjNzg4XHViMjk0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YjI5NCAxXHViZDg0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBTXHVjZTc4XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjOGNcdWM3NzQgXHVhY2YwXHViM2NjXHVjNzc0XHViOTdjIFx1Y2Q1Y1x1Y2QwOFx1Yjg1YyBcdWJjMWNcdWFjYWNcdWQ1NThcdWFjZTAgXHViMmU0XHViOTc4IFx1YmM4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWMyZTBcdWQ2MzhcdWI5N2MgXHViY2Y0XHViMGI0XHViMjk0IFx1YzIxY1x1YWMwNFx1YzVkMCBcdWFjZjBcdWIzY2NcdWM3NzRcdWIyOTQgXHVhZmMwXHViMmU4XHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWQ0ODBcdWJjMmQgXHVhYzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHViYzhjXHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM1ZDBcdWIyOTQgXHViYjM0XHVjMjE4XHVkNzg4IFx1YjljZVx1Yzc0MCBcdWJjOGNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gKFx1YmM4Y1x1YzlkMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1Yzc0Y1x1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWM3OTAuKSBcdWM3NzQgXHVjMjMyXHVjNzU4IFx1YzJkY1x1YWNjNFx1YjI5NCBcdWJkODQgXHViMmU4XHVjNzA0XHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC4gXHViOWU0IFx1YmQ4NFx1YjljOFx1YjJlNCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc3NFx1YmNhNFx1ZDJiOFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NWNcdWIyZTQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCBcdWQ2MDRcdWM3YWMgXHVhZmMwXHVjNzQ0IFx1YmEzOVx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhY2M0XHVjMThkIFx1YWZjMFx1Yzc0NCBcdWJhMzlcdWM3NDRcdWM5YzAgXHVjNTQ0XHViMmM4XHViYTc0IFx1YWZjMFx1YjJlOFx1YzljMFx1Yjk3YyBcdWI1YTBcdWIwOTggXHVjOWQxXHVjNzNjXHViODVjIFx1YWMwOFx1YzljMFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZmMwXHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWJhMzlcdWFjYTBcdWIyZTRcdWFjZTAgXHVhY2IwXHVjODE1XHVkNTU4XHViYTc0IDEgXHViZDg0IFx1YjNkOVx1YzU0OFx1Yzc0MCBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViYzE4XHViMzAwXHViODVjIFx1YWMwMFx1YWNhMFx1YjJlNFx1YWNlMCBcdWFjYjBcdWM4MTVcdWQ1NThcdWJhNzQsIFx1Yzk4OVx1YWMwMSBcdWI1YTBcdWIwOThcdWM1N2MgXHVkNTU4XHViYTcwIDEgXHViZDg0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBTIFx1Y2U3OFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNWEwXHViMDk4XHVhYzhjIFx1YjQxOFx1YmE3NCBcdWFmYzBcdWIyZThcdWM5YzBcdWIyOTQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWMwOCBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNWEwXHViMDljIFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWFmYzBcdWM3NDQgXHViMmU0XHVjMmRjIFx1YmEzOVx1Yzc0NCBcdWMyMWMgXHVjNWM2XHViMmU0LiBcdWFjZjBcdWIzY2NcdWM3NzRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVhYzgzXHVjYzk4XHViN2ZjIFx1YjNkOSwgXHVjMTFjLCBcdWIwYTgsIFx1YmQ4MVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkNDgwXHViYzJkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCAxXHViZDg0IFx1YjNkOVx1YzU0OCBcdWFmYzBcdWM3NDQgXHViYTM5XHVhYzcwXHViMDk4IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWQ2YzQsIDEgXHViZDg0XHVjNzc0IFx1YzY0NFx1YjhjY1x1YjQxOFx1YjI5NCBcdWMyMWNcdWFjMDQgXHViYzhjXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNzNjXHViODVjIFx1ZDM3Y1x1YzgzOCBcdWIwOThcdWFjMDRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmM4Y1x1YjRlNFx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDAgXHViM2Q5LCBcdWMxMWMsIFx1YjBhOCwgXHViZDgxIFx1YzkxMSBcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwIFx1YWRmOCBcdWM5MTEgXHVkNDgwXHViYzJkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHViMzAwXHVhYzAxXHVjMTIwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWM2YzNcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjXHViMjk0IFx1Yzc3NFx1YjNkOVx1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuKSBcdWFjYjBcdWFkNmQsIFx1YmM4Y1x1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFkZjggXHVjZTc4XHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVkNDgwXHViYzJkIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWJjOGNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1ZDU1YyBcdWNlNzhcdWM1MjkgXHVkMzdjXHVjODM4IFx1YjA5OFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzhmY1x1Yzc1OFx1ZDU2MCBcdWM4MTBcdWM3NDAgXHVjNWI0XHViNWE0IFx1Y2U3OFx1YzVkMCBcdWJjOGNcdWI0ZTRcdWM3NzQgXHVjNzg4XHVhYzhjIFx1YjQxOFx1YmE3NCBcdWFkZjggXHVjZTc4XHVjNWQwXHViMjk0IFx1YzYwMVx1YzZkMFx1ZDc4OCBcdWJjOGNcdWI0ZTRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjMmRjXHVhYzA0XHVjNzc0IFx1ZDc1MFx1Yjk3Y1x1YzIxOFx1Yjg1ZCBcdWJjOGNcdWI0ZTRcdWM3NzQgXHVjMjMyXHVjNzU4IFx1YzVlY1x1YjdlYyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVkNjU1XHVjMGIwXHViNDE4XHVjNWI0IFx1YmM4Y1x1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0IFx1YWNjNFx1YzE4ZCBcdWIyOThcdWM1YjRcdWIwOThcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjJlNFx1YzJkYyBcdWQ1NWNcdWJjODggXHViYzhjXHViNGU0XHVjNzU4IFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWMxMjRcdWJhODVcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNCA6IFx1YmM4YyBcdWQ1NWNcdWI5YzhcdWI5YWNcdWFjMDAgXHVjMmUwXHVkNjM4XHViOTdjIFx1YmNmNFx1YjBiNFx1YjI5NCBcdWMyMWNcdWFjMDRcdWM1ZDBcdWIyOTQgXHViYzhjXHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWI0ZTRcdWM1ZDBcdWI5Y2MgXHViYzhjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YWM4YyBcdWI0MWNcdWIyZTQuIDEgXHViZDg0XHVjNzc0IFx1YzY0NFx1YjhjY1x1YjQxOFx1YjI5NCBcdWMyMWNcdWFjMDRcdWM1ZDBcdWIyOTQgXHViYzhjXHViNGU0XHVjNzQwIFx1YmM4Y1x1YzlkMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHViNGU0XHVhY2ZjIFx1YWRmOCBcdWNlNzhcdWI0ZTRcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YmFhOFx1YjRlMCBcdWQ0ODBcdWJjMmQgXHVjZTc4XHVjNzQ0IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIDIgXHViZDg0XHVjNzc0IFx1YzY0NFx1YjhjY1x1YjQxOFx1YjI5NCBcdWMyMWNcdWFjMDRcdWM1ZDBcdWIyOTQgXHViYzhjXHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzggXHViYWE4XHViNDUwXHVjNjQwIFx1YmM4Y1x1YzlkMVx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYWE4XHViNGUwIFx1ZDQ4MFx1YmMyZCBcdWNlNzhcdWI0ZTRcdWFjZmMgXHVhZGY4IFx1ZDQ4MFx1YmMyZCBcdWNlNzhcdWI0ZTRcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YmFhOFx1YjRlMCBcdWQ0ODBcdWJjMmQgXHVjZTc4XHViNGU0XHVjNzQ0IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWFlMzQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzljMFx1YjA5OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YmM4Y1x1YzlkMVx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgXHViM2M0XHViMmVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVkNDgwXHViYzJkIFx1Y2U3OFx1Yzc0NCBcdWJjOGNcdWI0ZTRcdWM3NzQgXHVjYzI4XHVjOWMwXHVkNTU4XHVhYzhjIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmMFx1YjNjY1x1Yzc3NFx1YzY0MCBcdWJjOGNcdWI0ZTRcdWM3NDAgXHVjMjMyIFx1YmMxNlx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVhY2YwXHViM2NjXHVjNzc0XHVhYzAwIFx1YWZjMFx1Yzc0NCBcdWJhMzlcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4Y1x1YjRlNFx1Yzc3NCBcdWNjMjhcdWM5YzBcdWQ1NWMgXHVjZTc4XHVjNWQwIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCBcdWQ1NjhcdWFlZDggXHVjNzg4XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWFjMDQgXHVhY2YwXHViM2NjXHVjNzc0XHViMjk0IFx1YmM4Y1x1YjRlNFx1YzVkMCBcdWM3NThcdWQ1NzQgXHVjN2ExXHVkNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjMyXHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjZjBcdWIzY2NcdWM3NzRcdWFjMDAgXHVjOWQxXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViYzhjXHViNGU0XHVjNWQwXHVhYzhjIFx1YzdhMVx1ZDc4OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVhZmMwXHViMmU4XHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YWZjMFx1Yzc0NCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ0NWNcdWM5MDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI5N2MgXHVjNzdkXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNCA6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWI0NTAgXHVjODE1XHVjMjE4IE5cdWFjZmMgU1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWIzYzQgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIzNzAsIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWIyOTQgXHVkNTVjIFx1Y2U3OFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQgOlxyXG5cdDx1bD5cclxuXHRcdDxsaT5UXHViMjk0IFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5HXHViMjk0IFx1ZDQ4MFx1YmMyZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5NXHVjNzQwIFx1YWNmMFx1YjNjY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWNkMDggXHVjNzA0XHVjZTU4KFx1YWZjMFx1YjJlOFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4KVx1Yzc3NFx1YWNlMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVkNDgwXHViYzJkIFx1Y2U3OFx1Yzc3NFx1YWUzMFx1YjNjNCBcdWQ1NThcdWIyZTQuPFwvbGk+XHJcblx0XHQ8bGk+RFx1YjI5NCBcdWFjZjBcdWIzY2NcdWM3NzRcdWM3NTggXHVjOWQxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NFx1YjM3MCwgXHVhY2YwXHViM2NjXHVjNzc0XHViMjk0IFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjIFx1YmM4Y1x1YjRlNFx1Yzc0MCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5IXHViMjk0IFx1YmM4Y1x1YzlkMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4ZmNcdWM3NThcdWMwYWNcdWQ1NmQgOiBcdWM5YzBcdWIzYzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NThcdWIwOThcdWM3NTggTSwgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBEIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IEhcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YWNmMFx1YjNjY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWNkMDggXHVjNzA0XHVjZTU4XHViZDgwXHVkMTMwIFx1YWNmMFx1YjNjY1x1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IEcgXHVjZTc4XHViNGU0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmM4Y1x1YzlkMVx1YWNmYyBcdWFmYzBcdWIyZThcdWM5YzAoXHVhY2YwXHViM2NjXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1Y2QwOCBcdWM3MDRcdWNlNTgpXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQ0ODBcdWJjMmQgXHVjZTc4XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YjNjNCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVhY2YwXHViM2NjXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1Y2QwOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWFjZjBcdWIzY2NcdWM3NzRcdWM3NTggXHVjOWQxXHVjNzc0XHViMDk4IFx1YmM4Y1x1YzlkMVx1Yzc3NCBcdWM3MDRcdWNlNThcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YmM4Y1x1YjRlNFx1Yzc0MCBcdWFjZjBcdWIzY2NcdWM3NzRcdWM3NTggXHVjOWQxXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmx0Oz0gTiAmbHQ7PSA4MDAgXHVjOWMwXHViM2M0XHVjNzU4IFx1ZDA2Y1x1YWUzMCAoXHVkNTVjIFx1YmNjMFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzIxOCk8XC9saT5cclxuXHQ8bGk+MSAmbHQ7PSBTICZsdDs9IDEsMDAwIFx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCAxIFx1YmQ4NCBcdWIzZDlcdWM1NDggXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWMyMTg8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNDVjXHVjOTAwIFx1Y2Q5Y1x1YjgyNVx1YzczY1x1Yjg1YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHVjODE1XHVjMjE4XHViMjk0IFx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCBcdWNkNWNcdWNkMDggXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWM5ZDFcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhZmMwXHVjNzQ0IFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzJkY1x1YWMwNChcdWJkODQpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVhY2YwXHViM2NjXHVjNzc0XHVhYzAwIFx1YmM4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3YTFcdWQ3ODhcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzlkMVx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBcdWQ0NWNcdWM5MDAgXHVjZDljXHViODI1XHVjNzNjXHViODVjIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWNmMFx1YjNjY1x1Yzc3NFx1YWMwMCAxIFx1YmQ4NCBcdWIzZDlcdWM1NDggXHVhZmMwXHVjNzQ0IFx1YmEzOVx1Yzc0MCBcdWQ2YzQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzdjXHVjOWMxXHVjMTIwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1YjJlNFx1Yzc0YyAyXHViZDg0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjOWQxXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVhY2YwXHViM2NjXHVjNzc0XHVhYzAwIFx1YWZjMFx1Yzc0NCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWM3YTUgXHVjMmRjXHVhYzA0XHVjNzQwIDFcdWJkODRcdWM3NzQgXHViNDE4XHVjNWI0IFx1Y2Q5Y1x1YjgyNSBcdWFjMTJcdWM3NDAgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0NjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNZWNobyIsImRlc2NyaXB0aW9uIjoiPHA+TWVjaG8gdGhlIGJlYXIgaGFzIGZvdW5kIGEgbGl0dGxlIHRyZWFzdXJlICZuZGFzaDsgdGhlIGJlZXMmcnNxdW87IHNlY3JldCBob25leXBvdCwgd2hpY2ggaXMgZnVsbCBvZiBob25leSEgSGUgd2FzIGhhcHBpbHkgZWF0aW5nIGhpcyBuZXdmb3VuZCB0cmVhc3VyZSB1bnRpbCBzdWRkZW5seSBvbmUgYmVlIHNhdyBoaW0gYW5kIHNvdW5kZWQgdGhlIGJlZSBhbGFybS4gSGUga25vd3MgdGhhdCBhdCB0aGlzIHZlcnkgbW9tZW50IGhvcmRlcyBvZiBiZWVzIHdpbGwgZW1lcmdlIGZyb20gdGhlaXIgaGl2ZXMgYW5kIHN0YXJ0IHNwcmVhZGluZyBhcm91bmQgdHJ5aW5nIHRvIGNhdGNoIGhpbS4gSGUga25vd3MgaGUgaGFzIHRvIGxlYXZlIHRoZSBob25leXBvdCBhbmQgZ28gaG9tZSBxdWlja2x5LCBidXQgdGhlIGhvbmV5IGlzIHNvIHN3ZWV0IHRoYXQgTWVjaG8gZG9lc24mcnNxdW87dCB3YW50IHRvIGxlYXZlIHRvbyBzb29uLiBIZWxwIE1lY2hvIGRldGVybWluZSB0aGUgbGF0ZXN0IHBvc3NpYmxlIG1vbWVudCB3aGVuIGhlIGNhbiBsZWF2ZS48XC9wPlxyXG5cclxuPHA+TWVjaG8mcnNxdW87cyBmb3Jlc3QgaXMgcmVwcmVzZW50ZWQgYnkgYSBzcXVhcmUgZ3JpZCBvZiBOIGJ5IE4gdW5pdCBjZWxscywgd2hvc2Ugc2lkZXMgYXJlIHBhcmFsbGVsIHRvIHRoZSBub3J0aC1zb3V0aCBhbmQgZWFzdC13ZXN0IGRpcmVjdGlvbnMuIEVhY2ggY2VsbCBpcyBvY2N1cGllZCBieSBhIHRyZWUsIGJ5IGEgcGF0Y2ggb2YgZ3Jhc3MsIGJ5IGEgaGl2ZSBvciBieSBNZWNobyZyc3F1bztzIGhvbWUuIFR3byBjZWxscyBhcmUgY29uc2lkZXJlZCBhZGphY2VudCBpZiBvbmUgb2YgdGhlbSBpcyBpbW1lZGlhdGVseSB0byB0aGUgbm9ydGgsIHNvdXRoLCBlYXN0IG9yIHdlc3Qgb2YgdGhlIG90aGVyIChidXQgbm90IG9uIGEgZGlhZ29uYWwpLiBNZWNobyBpcyBhIGNsdW1zeSBiZWFyLCBzbyBldmVyeSB0aW1lIGhlIG1ha2VzIGEgc3RlcCwgaXQgaGFzIHRvIGJlIHRvIGFuIGFkamFjZW50IGNlbGwuIE1lY2hvIGNhbiBvbmx5IHdhbGsgb24gZ3Jhc3MgYW5kIGNhbm5vdCBnbyB0aHJvdWdoIHRyZWVzIG9yIGhpdmVzLCBhbmQgaGUgY2FuIG1ha2UgYXQgbW9zdCBTIHN0ZXBzIHBlciBtaW51dGUuPFwvcD5cclxuXHJcbjxwPkF0IHRoZSBtb21lbnQgd2hlbiB0aGUgYmVlIGFsYXJtIGlzIHNvdW5kZWQsIE1lY2hvIGlzIGluIHRoZSBncmFzc3kgY2VsbCBjb250YWluaW5nIHRoZSBob25leXBvdCwgYW5kIHRoZSBiZWVzIGFyZSBpbiBldmVyeSBjZWxsIGNvbnRhaW5pbmcgYSBoaXZlICh0aGVyZSBtYXkgYmUgbW9yZSB0aGFuIG9uZSBoaXZlIGluIHRoZSBmb3Jlc3QpLiBEdXJpbmcgZWFjaCBtaW51dGUgZnJvbSB0aGlzIHRpbWUgb253YXJkcywgdGhlIGZvbGxvd2luZyBldmVudHMgaGFwcGVuIGluIHRoZSBmb2xsb3dpbmcgb3JkZXI6PFwvcD5cclxuXHJcbjxwPklmIE1lY2hvIGlzIHN0aWxsIGVhdGluZyBob25leSwgaGUgZGVjaWRlcyB3aGV0aGVyIHRvIGtlZXAgZWF0aW5nIG9yIHRvIGxlYXZlLiBJZiBoZSBjb250aW51ZXMgZWF0aW5nLCBoZSBkb2VzIG5vdCBtb3ZlIGZvciB0aGUgd2hvbGUgbWludXRlLiBPdGhlcndpc2UsIGhlIGxlYXZlcyBpbW1lZGlhdGVseSBhbmQgdGFrZXMgdXAgdG8gUyBzdGVwcyB0aHJvdWdoIHRoZSBmb3Jlc3QgYXMgZGVzY3JpYmVkIGFib3ZlLiBNZWNobyBjYW5ub3QgdGFrZSBhbnkgb2YgdGhlIGhvbmV5IHdpdGggaGltLCBzbyBvbmNlIGhlIGhhcyBtb3ZlZCBoZSBjYW5ub3QgZWF0IGhvbmV5IGFnYWluLjxiciBcLz5cclxuQWZ0ZXIgTWVjaG8gaXMgZG9uZSBlYXRpbmcgb3IgbW92aW5nIGZvciB0aGUgd2hvbGUgbWludXRlLCB0aGUgYmVlcyBzcHJlYWQgb25lIHVuaXQgZnVydGhlciBhY3Jvc3MgdGhlIGdyaWQsIG1vdmluZyBvbmx5IGludG8gdGhlIGdyYXNzeSBjZWxscy4gU3BlY2lmaWNhbGx5LCB0aGUgc3dhcm0gb2YgYmVlcyBzcHJlYWRzIGludG8gZXZlcnkgZ3Jhc3N5IGNlbGwgdGhhdCBpcyBhZGphY2VudCB0byBhbnkgY2VsbCBhbHJlYWR5IGNvbnRhaW5pbmcgYmVlcy4gRnVydGhlcm1vcmUsIG9uY2UgYSBjZWxsIGNvbnRhaW5zIGJlZXMgaXQgd2lsbCBhbHdheXMgY29udGFpbiBiZWVzICh0aGF0IGlzLCB0aGUgc3dhcm0gZG9lcyBub3QgbW92ZSwgYnV0IGl0IGdyb3dzKS48XC9wPlxyXG5cclxuPHA+SW4gb3RoZXIgd29yZHMsIHRoZSBiZWVzIHNwcmVhZCBhcyBmb2xsb3dzOiBXaGVuIHRoZSBiZWUgYWxhcm0gaXMgc291bmRlZCwgdGhlIGJlZXMgb25seSBvY2N1cHkgdGhlIGNlbGxzIHdoZXJlIHRoZSBoaXZlcyBhcmUgbG9jYXRlZC4gQXQgdGhlIGVuZCBvZiB0aGUgZmlyc3QgbWludXRlLCB0aGV5IG9jY3VweSBhbGwgZ3Jhc3N5IGNlbGxzIGFkamFjZW50IHRvIGhpdmVzIChhbmQgc3RpbGwgdGhlIGhpdmVzIHRoZW1zZWx2ZXMpLiBBdCB0aGUgZW5kIG9mIHRoZSBzZWNvbmQgbWludXRlLCB0aGV5IGFkZGl0aW9uYWxseSBvY2N1cHkgYWxsIGdyYXNzeSBjZWxscyBhZGphY2VudCB0byBncmFzc3kgY2VsbHMgYWRqYWNlbnQgdG8gaGl2ZXMsIGFuZCBzbyBvbi4gR2l2ZW4gZW5vdWdoIHRpbWUsIHRoZSBiZWVzIHdpbGwgZW5kIHVwIHNpbXVsdGFuZW91c2x5IG9jY3VweWluZyBhbGwgZ3Jhc3N5IGNlbGxzIGluIHRoZSBmb3Jlc3QgdGhhdCBhcmUgd2l0aGluIHRoZWlyIHJlYWNoLjxcL3A+XHJcblxyXG48cD5OZWl0aGVyIE1lY2hvIG5vciB0aGUgYmVlcyBjYW4gZ28gb3V0c2lkZSB0aGUgZm9yZXN0LiBBbHNvLCBub3RlIHRoYXQgYWNjb3JkaW5nIHRvIHRoZSBydWxlcyBhYm92ZSwgTWVjaG8gd2lsbCBhbHdheXMgZWF0IGhvbmV5IGZvciBhbiBpbnRlZ2VyIG51bWJlciBvZiBtaW51dGVzLjxcL3A+XHJcblxyXG48cD5UaGUgYmVlcyBjYXRjaCBNZWNobyBpZiBhdCBhbnkgcG9pbnQgaW4gdGltZSBNZWNobyBmaW5kcyBoaW1zZWxmIGluIGEgY2VsbCBvY2N1cGllZCBieSBiZWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYSBtYXAgb2YgdGhlIGZvcmVzdCwgZGV0ZXJtaW5lcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgbWludXRlcyB0aGF0IE1lY2hvIGNhbiBjb250aW51ZSBlYXRpbmcgaG9uZXkgYXQgaGlzIGluaXRpYWwgbG9jYXRpb24sIHdoaWxlIHN0aWxsIGJlaW5nIGFibGUgdG8gZ2V0IHRvIGhpcyBob21lIGJlZm9yZSBhbnkgb2YgdGhlIGJlZXMgY2F0Y2ggaGltLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3QgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0IHRoZSBmb2xsb3dpbmcgZGF0YTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgUywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IE4gbGluZXMgcmVwcmVzZW50IHRoZSBtYXAgb2YgdGhlIGZvcmVzdC4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyBOIGNoYXJhY3RlcnMgd2l0aCBlYWNoIGNoYXJhY3RlciByZXByZXNlbnRpbmcgb25lIHVuaXQgY2VsbCBvZiB0aGUgZ3JpZC4gVGhlIHBvc3NpYmxlIGNoYXJhY3RlcnMgYW5kIHRoZWlyIGFzc29jaWF0ZWQgbWVhbmluZ3MgYXJlIGFzIGZvbGxvd3M6XHJcblx0PHVsPlxyXG5cdFx0PGxpPlQgZGVub3RlcyBhIHRyZWU8XC9saT5cclxuXHRcdDxsaT5HIGRlbm90ZXMgYSBncmFzc3kgY2VsbDxcL2xpPlxyXG5cdFx0PGxpPk0gZGVub3RlcyB0aGUgaW5pdGlhbCBsb2NhdGlvbiBvZiBNZWNobyBhbmQgdGhlIGhvbmV5cG90LCB3aGljaCBpcyBhbHNvIGEgZ3Jhc3N5IGNlbGw8XC9saT5cclxuXHRcdDxsaT5EIGRlbm90ZXMgdGhlIGxvY2F0aW9uIG9mIE1lY2hvJnJzcXVvO3MgaG9tZSwgd2hpY2ggTWVjaG8gY2FuIGVudGVyLCBidXQgdGhlIGJlZXMgY2Fubm90LjxcL2xpPlxyXG5cdFx0PGxpPkggZGVub3RlcyB0aGUgbG9jYXRpb24gb2YgYSBoaXZlPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tk9URTogSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBtYXAgd2lsbCBjb250YWluIGV4YWN0bHkgb25lIGxldHRlciBNLCBleGFjdGx5IG9uZSBsZXR0ZXIgRCBhbmQgYXQgbGVhc3Qgb25lIGxldHRlciBILiBJdCBpcyBhbHNvIGd1YXJhbnRlZWQgdGhhdCB0aGVyZSBpcyBhIHNlcXVlbmNlIG9mIGFkamFjZW50IGxldHRlcnMgRyB0aGF0IGNvbm5lY3RzIE1lY2hvIHRvIGhpcyBob21lLCBhcyB3ZWxsIGFzIGEgc2VxdWVuY2Ugb2YgYWRqYWNlbnQgbGV0dGVycyBHIHRoYXQgY29ubmVjdHMgYXQgbGVhc3Qgb25lIGhpdmUgdG8gdGhlIGhvbmV5cG90IChpLmUuLCB0byBNZWNobyZyc3F1bztzIGluaXRpYWwgbG9jYXRpb24pLiBUaGVzZSBzZXF1ZW5jZXMgbWlnaHQgYmUgYXMgc2hvcnQgYXMgbGVuZ3RoIHplcm8sIGluIGNhc2UgTWVjaG8mcnNxdW87cyBob21lIG9yIGEgaGl2ZSBpcyBhZGphY2VudCB0byBNZWNobyZyc3F1bztzIGluaXRpYWwgbG9jYXRpb24uIEFsc28sIG5vdGUgdGhhdCB0aGUgYmVlcyBjYW5ub3QgcGFzcyB0aHJvdWdoIG9yIGZseSBvdmVyIE1lY2hvJnJzcXVvO3MgaG9tZS4gVG8gdGhlbSwgaXQgaXMganVzdCBsaWtlIGEgdHJlZS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDgwMCBUaGUgc2l6ZSAoc2lkZSBsZW5ndGgpIG9mIHRoZSBtYXA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFMgJmxlOyAxLDAwMCBUaGUgbWF4aW11bSBudW1iZXIgb2Ygc3RlcHMgTWVjaG8gY2FuIHRha2UgaW4gZWFjaCBtaW51dGUmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBtdXN0IHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIG1pbnV0ZXMgdGhhdCBNZWNobyBjYW4gY29udGludWUgZWF0aW5nIGhvbmV5IGF0IGhpcyBpbml0aWFsIGxvY2F0aW9uLCB3aGlsZSBzdGlsbCBiZWluZyBhYmxlIHRvIGdldCBob21lIHNhZmVseS48XC9wPlxyXG5cclxuPHA+SWYgTWVjaG8gY2Fubm90IHBvc3NpYmx5IHJlYWNoIGhpcyBob21lIGJlZm9yZSB0aGUgYmVlcyBjYXRjaCBoaW0sIHRoZSBudW1iZXIgeW91ciBwcm9ncmFtIHdyaXRlcyB0byBzdGFuZGFyZCBvdXRwdXQgbXVzdCBiZSAtMSBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5TYW1wbGUgMTxcL3A+XHJcblxyXG48cD5BZnRlciBlYXRpbmcgaG9uZXkgZm9yIG9uZSBtaW51dGUsIE1lY2hvIGNhbiB0YWtlIHRoZSBzaG9ydGVzdCBwYXRoIGRpcmVjdGx5IHRvIHRoZSByaWdodCBhbmQgaGUgd2lsbCBiZSBob21lIGluIGFub3RoZXIgdHdvIG1pbnV0ZXMsIHNhZmUgZnJvbSB0aGUgYmVlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2FtcGxlIDI8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZWF0aW5nIGhvbmV5IGZvciB0d28gbWludXRlcywgTWVjaG8gY2FuIHRha2Ugc3RlcHMgJnJhcnI7JnVhcnI7JnJhcnI7IGR1cmluZyB0aGUgdGhpcmQgbWludXRlLCB0aGVuIHN0ZXBzICZyYXJyOyZyYXJyOyZyYXJyOyBkdXJpbmcgdGhlIGZvdXJ0aCBtaW51dGUgYW5kIHN0ZXBzICZkYXJyOyZyYXJyOyBkdXJpbmcgdGhlIGZpZnRoIG1pbnV0ZS4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2009 6번