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

문제

상근이가 지배하는 나라에는 도시가 N개 있고, 도시는 M개의 양방향 도로로 연결되어 있다. 이 중 K개 도시에는 쇼핑몰이 있고, 국민은 도로를 통해서 쇼핑몰이 있는 마을로 가고, 쇼핑을 한다.

쇼핑몰이 멀리 떨어져 있는 사람은 쇼핑몰로 가기 위해 긴 시간 운전을 해야 한다. 상근이는 실정을 파악하기 위해서 쇼핑몰과 집의 최단 거리가 집의 위치에 따라서 어떻게 달라지는지 구하기로 한다. 집은 도시에 있을 수도 있고, 도로 위에 있을 수도 있다.

도로의 정보와 쇼핑몰이 있는 도시가 주어졌을 때, 쇼핑몰이 있는 도시와 가장 먼 거리에 있는 집까지의 거리를 구하는 프로그램을 작성하시오. 도시 속을 이동하는데 걸리는 시간은 0이다. 또, 사람들은 항상 최단 경로를 이용한다.

입력

첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N)

다음 M개 줄에는 도로의 정보 a, b, l이 주어진다. a와 b를 잇는 도로의 길이가 l(1 ≤ l ≤ 1000)임을 의미하며, a와 b가 같은 경우는 없다. 두 도시 p와 q에 대해서, 두 도시를 잇는 도로는 2개 이상 존재하지 않는다. 항상 도로를 이용해서 모든 도시로 이동할 수 있다.

다음 K개 줄에는 쇼핑몰이 있는 도시의 번호가 주어진다. 한 도시에 쇼핑몰이 여러 개 있을 수는 없다.

출력

쇼핑몰이 있는 곳에서 가장 멀리 떨어져 있는 집과의 거리(쇼핑몰과 집의 최단 거리의 최솟값)를 소수점 첫째자리에서 반올림해서 출력한다.

예제 입력 1

3 3 1
1 2 1
2 3 1
3 1 1
1

예제 출력 1

2

예제 입력 2

4 5 2
1 2 4
1 3 1
2 3 2
2 4 2
3 4 1
2
4

예제 출력 2

3

힌트

예제 1의 경우에 도로의 길이는 모두 1이고, 쇼핑몰은 1번 도시에만 있다. 쇼핑몰과 가장 먼 거리에 있는 집의 위치는 2번 도시와 3번 도시를 연결하는 도로에서 2번 도시와 거리가 0.5만큼 떨어져 있는 위치 위에 있는 곳이다. 이 집과 쇼핑몰의 거리는 1.5이다. 따라서, 반올림하면 2가 된다.

W3sicHJvYmxlbV9pZCI6IjU1NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxZmNcdWQ1NTFcdWJhYjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM5YzBcdWJjMzBcdWQ1NThcdWIyOTQgXHViMDk4XHViNzdjXHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1YWMwMCBOXHVhYzFjIFx1Yzc4OFx1YWNlMCwgXHViM2M0XHVjMmRjXHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjOTExIEtcdWFjMWMgXHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWQ2ZFx1YmJmY1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViOWM4XHVjNzQ0XHViODVjIFx1YWMwMFx1YWNlMCwgXHVjMWZjXHVkNTUxXHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMWZjXHVkNTUxXHViYWIwXHVjNzc0IFx1YmE0MFx1YjlhYyBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWMxZmNcdWQ1NTFcdWJhYjBcdWI4NWMgXHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFlMzQgXHVjMmRjXHVhYzA0IFx1YzZiNFx1YzgwNFx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmU0XHVjODE1XHVjNzQ0IFx1ZDMwY1x1YzU0NVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMWZjXHVkNTUxXHViYWIwXHVhY2ZjIFx1YzlkMVx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjXHVhYzAwIFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YzViNFx1YjViYlx1YWM4YyBcdWIyZWNcdWI3N2NcdWM5YzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1Y1x1YjJlNC4gXHVjOWQxXHVjNzQwIFx1YjNjNFx1YzJkY1x1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHViM2M0XHViODVjIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YzY0MCBcdWMxZmNcdWQ1NTFcdWJhYjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxZmNcdWQ1NTFcdWJhYjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1YzY0MCBcdWFjMDBcdWM3YTUgXHViYTNjIFx1YWM3MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjOWQxXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViM2M0XHVjMmRjIFx1YzE4ZFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAwXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTiwgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNLCBcdWMxZmNcdWQ1NTFcdWJhYjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjNjNFx1YzJkY1x1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuICgyICZsZTsgTiAmbGU7IDMwMDAsIDEgJmxlOyBNICZsZTsgMTA8c3VwPjU8XC9zdXA+LCAxICZsZTsgSyAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0IGEsIGIsIGxcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhXHVjNjQwIGJcdWI5N2MgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgbCgxICZsZTsgbCZuYnNwOyZsZTsgMTAwMClcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCBhXHVjNjQwIGJcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjQ1MCBcdWIzYzRcdWMyZGMgcFx1YzY0MCBxXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViNDUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHViMjk0IDJcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxZmNcdWQ1NTFcdWJhYjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNWQwIFx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWJhNDBcdWI5YWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWFjZmNcdWM3NTggXHVhYzcwXHViOWFjKFx1YzFmY1x1ZDU1MVx1YmFiMFx1YWNmYyBcdWM5ZDFcdWM3NTggXHVjZDVjXHViMmU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTIpXHViOTdjIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWNjYWJcdWM5ZjhcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHViYzE4XHVjNjJjXHViOWJjXHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIDFcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIDFcdWM3NzRcdWFjZTAsIFx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc0MCAxXHViYzg4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YjljYyBcdWM3ODhcdWIyZTQuIFx1YzFmY1x1ZDU1MVx1YmFiMFx1YWNmYyBcdWFjMDBcdWM3YTUgXHViYTNjIFx1YWM3MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCAyXHViYzg4IFx1YjNjNFx1YzJkY1x1YzY0MCAzXHViYzg4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVjNWQwXHVjMTFjIDJcdWJjODggXHViM2M0XHVjMmRjXHVjNjQwIFx1YWM3MFx1YjlhY1x1YWMwMCAwLjVcdWI5Y2NcdWQwN2MgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWM5ZDFcdWFjZmMgXHVjMWZjXHVkNTUxXHViYWIwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAxLjVcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViYzE4XHVjNjJjXHViOWJjXHVkNTU4XHViYTc0IDJcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzcxYzZkMTg0LTAwYzgtNDA0Ni05ODVmLTU1MDRjYWE4ODgyM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjIxcHg7IGhlaWdodDogMTgxcHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NTUxIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JIFx1NTZmZFx1MzA2ZVx1OGNiN1x1MzA0NFx1NzI2OVx1NGU4Ylx1NjBjNSAoU2hvcHBpbmcgaW4gSk9JIEtpbmdkb20pIiwiZGVzY3JpcHRpb24iOiI8cD5KT0kgXHU1NmZkXHUzMDZiXHUzMDZmIE4gXHU1MDBiXHUzMDZlXHU3NTNhXHUzMDRjXHUzMDQyXHUzMDhhXHVmZjBjXHUzMDVkXHUzMDhjXHUzMDg5XHUzMDZlXHU5NTkzXHUzMDZmIE0gXHU2NzJjXHUzMDZlXHU1M2NjXHU2NWI5XHU1NDExXHUzMDZiXHU5MDFhXHU4ODRjXHU1M2VmXHU4MGZkXHUzMDZhXHU5MDUzXHU4ZGVmXHUzMDY3XHU3ZDUwXHUzMDcwXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlSyBcdTUwMGJcdTMwNmVcdTc1M2FcdTMwNmJcdTMwNmZcdTMwYjdcdTMwZTdcdTMwYzNcdTMwZDRcdTMwZjNcdTMwYjBcdTMwZTJcdTMwZmNcdTMwZWJcdTMwNGNcdTMwNDJcdTMwOGFcdWZmMGNcdTU2ZmRcdTZjMTFcdTMwNmZcdTkwNTNcdThkZWZcdTMwOTJcdTkwMWFcdTMwNjNcdTMwNjZcdTMwNWRcdTMwOGNcdTMwODlcdTMwNmVcdTc1M2FcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNmJcdTg4NGNcdTMwNGRcdThjYjdcdTMwNDRcdTcyNjlcdTMwOTJcdTMwNTlcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1YmI2XHUzMDZlXHU1ODM0XHU2MjQwXHUzMDZiXHUzMDg4XHUzMDYzXHUzMDY2XHUzMDZmXHVmZjBjXHU4Y2I3XHUzMDQ0XHU3MjY5XHUzMDZiXHU4ODRjXHUzMDRmXHUzMDVmXHUzMDgxXHUzMDZiXHU5NTc3XHUzMDQ0XHU4ZGRkXHU5NmUyXHUzMDkyXHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHU1ZmM1XHU4OTgxXHUzMDRjXHUzMDQyXHUzMDhhXHVmZjBjXHUzMDVkXHUzMDhjXHUzMDZmXHU5NzVlXHU1ZTM4XHUzMDZiXHU0ZTBkXHU0ZmJmXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHU1NmZkXHU3MzhiXHUzMDZmXHUzMDUzXHUzMDZlXHU1YjlmXHU2MGM1XHUzMDkyXHU2MjhhXHU2M2UxXHUzMDU5XHUzMDhiXHUzMDVmXHUzMDgxXHVmZjBjXHUzMGI3XHUzMGU3XHUzMGMzXHUzMGQ0XHUzMGYzXHUzMGIwXHUzMGUyXHUzMGZjXHUzMGViXHUzMDZlXHUzMDQyXHUzMDhiXHU3NTNhXHUzMDdlXHUzMDY3XHUzMDZlXHU2NzAwXHU3N2VkXHU4ZGRkXHU5NmUyXHUzMDRjXHU1YmI2XHUzMDZlXHU1ODM0XHU2MjQwXHUzMDZiXHUzMDg4XHUzMDYzXHUzMDY2XHUzMDY5XHUzMDhjXHUzMDYwXHUzMDUxXHU5NTc3XHUzMDRmXHUzMDZhXHUzMDhhXHUzMDQ2XHUzMDhiXHUzMDZlXHUzMDRiXHUzMDkyXHU4YWJmXHUzMDc5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDVmXHVmZjBlXHU1YmI2XHUzMDZmXHU5MDUzXHU4ZGVmXHUzMDZlXHU5MDE0XHU0ZTJkXHUzMDZiXHU1ZWZhXHUzMDY2XHUzMDg5XHUzMDhjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDgyXHUzMDQyXHUzMDhiXHUzMDZlXHUzMDY3IChcdTUxNjVcdTUyOWJcdTRmOGIgMSBcdTMwNmVcdThhYWNcdTY2MGVcdTMwOTJcdTUzYzJcdTcxNjcpXHVmZjBjXHUzMDUzXHUzMDZlXHU4YWJmXHU2N2ZiXHUzMDZmXHU5NzVlXHU1ZTM4XHUzMDZiXHU1OTI3XHU1OTA5XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHUzMDVkXHUzMDUzXHUzMDY3XHU1NmZkXHU3MzhiXHUzMDZmXHVmZjBjXHU1MTJhXHU3OWMwXHUzMDZhXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGRlXHUzMGZjXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZiXHVmZjBjXHU4YWJmXHU2N2ZiXHUzMDkyXHU4ODRjXHUzMDQ2XHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDZlXHU0ZjVjXHU2MjEwXHUzMDkyXHU0ZjlkXHU5ODNjXHUzMDU3XHUzMDVmXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1OTA1M1x1OGRlZlx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA2OFx1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA2ZVx1MzA0Mlx1MzA4Ylx1NzUzYVx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1MzA2OFx1MzA0ZFx1ZmYwY1x1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA2ZVx1MzA0Mlx1MzA4Ylx1NzUzYVx1MzA0Ylx1MzA4OVx1MzA4Mlx1MzA2M1x1MzA2OFx1MzA4Mlx1OTA2MFx1MzA0NFx1OTA1M1x1OGRlZlx1NGUwYVx1MzA2ZVx1NzBiOSAoXHU3YWVmXHU3MGI5XHUzMDgyXHU1NDJiXHUzMDgwKSBcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGVcdTc1M2FcdTMwNmVcdTRlMmRcdTMwOTJcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdTMwNmVcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdThkZGRcdTk2ZTJcdTMwNmZcdTcxMjFcdTg5OTZcdTMwNTdcdTMwNjZcdTMwODhcdTMwNDRcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1NTE2NVx1NTI5Ylx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4sIE0sIEsgXHUzMDRjXHU3YTdhXHU3NjdkXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY3XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlTiBcdTMwNmYgSk9JIFx1NTZmZFx1MzA2ZVx1NzUzYVx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1ZmYwY00gXHUzMDZmIEpPSSBcdTU2ZmRcdTMwNmVcdTkwNTNcdThkZWZcdTMwNmVcdTY3MmNcdTY1NzBcdTMwOTJcdWZmMGNLIFx1MzA2Zlx1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA0Y1x1MzA0Mlx1MzA4Ylx1NzUzYVx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1ODg2OFx1MzA1OVx1ZmYwZVx1NzUzYVx1MzA2Ylx1MzA2ZiAxLCAyLCAuLi4gLCBOIFx1MzA2ZVx1NzU2YVx1NTNmN1x1MzA0Y1x1MzA2NFx1MzA1MVx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgTSBcdTg4NGNcdTMwNmZcdTkwNTNcdThkZWZcdTMwNmVcdTYwYzVcdTU4MzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVpICsgMSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgTSkgXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiwgbDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyBiPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyBsPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2N1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY2kgXHU2NzJjXHU3NmVlXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDRjXHU3NTNhIGE8c3ViPmk8XC9zdWI+IFx1MzA2OFx1NzUzYSBiPHN1Yj5pPFwvc3ViPiBcdTMwOTJcdTdkNTBcdTMwOTNcdTMwNjdcdTMwNGFcdTMwOGFcdWZmMGNcdTk1NzdcdTMwNTVcdTMwNGNsaSBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVcdTkwNTNcdThkZWZcdTMwNmVcdTRlMjFcdTdhZWZcdTMwNGNcdTU0MGNcdTMwNThcdTc1M2FcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNcdTRlZmJcdTYxMGZcdTMwNmUgMiBcdTMwNjRcdTMwNmVcdTc1M2EgcCwgcSBcdTMwNmJcdTViZmVcdTMwNTdcdWZmMGNwXHUzMDY4IHEgXHUzMDkyXHU3ZDUwXHUzMDc2XHU5MDUzXHU4ZGVmXHUzMDZmIDIgXHU2NzJjXHU0ZWU1XHU0ZTBhXHU1YjU4XHU1NzI4XHUzMDU3XHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDY5XHUzMDZlXHU3NTNhXHUzMDRiXHUzMDg5XHUzMDY5XHUzMDZlXHU3NTNhXHUzMDc4XHUzMDgyXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDkyXHUzMDVmXHUzMDY5XHUzMDYzXHUzMDY2XHU4ODRjXHUzMDRmXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPlx1N2Q5YVx1MzA0ZiBLIFx1ODg0Y1x1MzA2Zlx1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZWkrTSsxIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBLKSBcdTMwNmJcdTMwNmYgMSBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgczxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbGU7IE4pXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHU3NTNhIHM8c3ViPmk8XC9zdWI+IFx1MzA2Ylx1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA0Y1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZXM8c3ViPjE8XC9zdWI+LCAuLi4sIHM8c3ViPks8XC9zdWI+IFx1MzA2ZVx1NGUyZFx1MzA2Ylx1NTQwY1x1MzA1OFx1NTAyNFx1MzA0YyAyXHU1NmRlXHU0ZWU1XHU0ZTBhXHU3M2ZlXHUzMDhjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTMwYjdcdTMwZTdcdTMwYzNcdTMwZDRcdTMwZjNcdTMwYjBcdTMwZTJcdTMwZmNcdTMwZWJcdTMwNmVcdTMwNDJcdTMwOGJcdTc1M2FcdTMwN2VcdTMwNjdcdTMwNmVcdTY3MDBcdTc3ZWRcdThkZGRcdTk2ZTJcdTMwNmVcdTY3MDBcdTU5MjdcdTUwMjRcdTMwNmVcdTVjMGZcdTY1NzBcdTcwYjlcdTRlZTVcdTRlMGJcdTMwOTJcdTU2ZGJcdTYzNjhcdTRlOTRcdTUxNjVcdTMwNTdcdTMwNWZcdTY1NzRcdTY1NzAgMVx1MzA2NFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdTUxNjVcdTUyOWJcdTRmOGIgMSBcdTMwNmZcdTZiMjFcdTMwNmVcdTMwODhcdTMwNDZcdTMwNmFcdTc1M2FcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVcdTkwNTNcdThkZWZcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmZcdTMwNTlcdTMwNzlcdTMwNjYgMSBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTMwYjdcdTMwZTdcdTMwYzNcdTMwZDRcdTMwZjNcdTMwYjBcdTMwZTJcdTMwZmNcdTMwZWJcdTMwNmZcdTc1M2EgMSBcdTMwNmJcdTMwNTdcdTMwNGJcdTMwNmFcdTMwNDRcdWZmMGVcdTMwYjdcdTMwZTdcdTMwYzNcdTMwZDRcdTMwZjNcdTMwYjBcdTMwZTJcdTMwZmNcdTMwZWJcdTMwNmVcdTMwNDJcdTMwOGJcdTc1M2FcdTMwN2VcdTMwNjdcdTMwODJcdTMwNjNcdTMwNjhcdTMwODJcdTkwNjBcdTMwNDRcdTcwYjlcdTMwNmZcdWZmMGNcdTc1M2EgMiBcdTMwNjhcdTc1M2EgMyBcdTMwOTJcdTdkNTBcdTMwNzZcdTkwNTNcdThkZWZcdTRlMGFcdTMwNmVcdWZmMGNcdTc1M2EgMiBcdTMwNGJcdTMwODlcdThkZGRcdTk2ZTIgMC41IFx1MzA2ZVx1NGY0ZFx1N2Y2ZVx1MzA2Ylx1MzA0Mlx1MzA4Ylx1NzBiOVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1MzBiN1x1MzBlN1x1MzBjM1x1MzBkNFx1MzBmM1x1MzBiMFx1MzBlMlx1MzBmY1x1MzBlYlx1MzA2ZVx1MzA0Mlx1MzA4Ylx1NzUzYVx1MzA3ZVx1MzA2N1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA2ZiAxLjUgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHUzMDg4XHUzMDYzXHUzMDY2XHVmZjBjXHUzMDVkXHUzMDhjXHUzMDkyXHU1NmRiXHU2MzY4XHU0ZTk0XHU1MTY1XHUzMDU3XHUzMDVmXHU1MDI0XHUzMDY3XHUzMDQyXHUzMDhiIDIgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNzFjNmQxODQtMDBjOC00MDQ2LTk4NWYtNTUwNGNhYTg4ODIzXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMjFweDsgaGVpZ2h0OiAxODFweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHU1MTY1XHU1MjliXHU0ZjhiIDEgXHUzMDZiXHU1YmZlXHU1ZmRjXHUzMDU5XHUzMDhiXHU1NmYzPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4yICZsZTsgTiAmbGU7IDMwMDAgSk9JIFx1NTZmZFx1MzA2ZVx1NzUzYVx1MzA2ZVx1NTAwYlx1NjU3MDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDEwMDAwMCA9IDEwPHN1cD41PFwvc3VwPiBKT0kgXHU1NmZkXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDZlXHU2NzJjXHU2NTcwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBLICZsZTsgTiBcdTMwYjdcdTMwZTdcdTMwYzNcdTMwZDRcdTMwZjNcdTMwYjBcdTMwZTJcdTMwZmNcdTMwZWJcdTMwNGNcdTMwNDJcdTMwOGJcdTc1M2FcdTMwNmVcdTUwMGJcdTY1NzA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMCBpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1OTU3N1x1MzA1NTxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2011 3번