시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 1024 MB 166 41 29 46.774%

문제

사진: 유클리드 좌표계에서 20개의 점으로 만든 Voronoi Diagram. 출처: Wikipedia

평면 위에 있는 크기 n의 점 집합을 생각하자. 이 점 집합의 Voronoi Diagram은, 평면 상의 점을 "어떤 점과 가장 가까운가?" 에 대한 기준으로 분할한 그림을 뜻한다. 예를 들어, 위 사진에서 평면 상의 모든 위치는, 그 위치와 가장 가까운 검은 점에 따라서 색이 칠해져 있다. Voronoi Diagram은 O(n log(n))에 계산하는 알고리즘이 알려져 있지만, 매우 어렵고 복잡한 알고리즘으로 악명이 높다. 

모 대회에서 Voronoi Diagram에 대한 문제를 풀지 못한 민규는, 그 충격으로 인해서 매일 매일을 술과 함께 보내고 있었다. 어느 날 오후, 민규는 여느 때와 같이 낮술을 하고 있다가, 매우 천재적인 Voronoi Diagram 알고리즘을 발견하였다! 민규는 이에 관한 논문을 쓰기 전에 2018 KAIST RUN Spring Contest 에 관련된 문제를 출제하여서 만점자의 출현을 막으려 한다. 

민규의 Voronoi Diagram 알고리즘은 왜 천재적일까? 보통 Voronoi Diagram은 평면에서만 적용되는데, 민규의 Voronoi Diagram은 더 일반화된 구조인 그래프에서 적용되기 때문이다. 정점이 N개이고, 양의 가중치가 있는 간선이 M개 있는 연결 그래프를 생각하자. 이 그래프에서 크기 K의 정점 집합이 주어졌을 때, 이 점 집합의 "Voronoi Diagram" 은 이 그래프의 모든 간선 상의 위치에 대해서, "정점 집합에 있는 어떤 점과 가장 가까운가" 에 대한 기준으로 분할한 그림을 뜻한다. 만약 같은 거리의 점이 여러 개 있으면, 이들 중 가장 정점의 번호가 작은 정점을 기준으로 한다. 

가중치 있는 그래프가 주어졌을 때, 당신은 각각의 점에 대해서, "Voronoi Diagram"에서 해당 점과 가장 가깝게 표현된 간선의 길이를 모두 더한 값을 출력해야 한다. 이 문제를 풀고, 민규보다 먼저 논문을 써서 민규의 코를 납작하게 해주자!

입력

첫 번째 줄에 정점의 개수 N, 간선의 개수 M이 공백으로 구분되어 주어진다. 

이후 M개의 줄의 i번째 줄엔 간선이 잇는 두 정점의 번호 si, ei와, 간선의 가중치 wi가 세 개의 정수로 공백으로 구분되어 주어진다. 

다음 줄에 정점 집합의 크기 K가 주어진다.

다음 줄에 K개의 서로 다른 정수 ai가 오름차순으로 공백으로 구분되어 주어진다. 정점 집합을 이루고 있는 정점들의 번호를 뜻한다. 

입력으로 주어진 그래프는 연결그래프 임이 보장된다. 즉, 임의의 정점에서 임의의 정점으로 가는 경로가 존재한다. 

출력

K개의 줄에 걸쳐서 하나의 실수를 출력한다. i번째 줄에는, ai 번 정점을 가장 가까운 정점으로 가지는 길이의 합을 출력하라. 

모든 출력은 소수점 둘째 자리에서 반올림하여서 출력하여야 한다. 실수 오차 관리에 초점을 맞춘 최근 ACM-ICPC World Finals의 경향에 맞춰서, 출력 시 일체의 오차도 허용되지 않는다.

제한

  • 1 ≤ NM ≤ 250,000
  • 1 ≤ si, ei ≤ N
  • 1 ≤ wi ≤ 109
  • 1 ≤ KN
  • 1 ≤ aiN
  • 주어진 그래프는 연결그래프 이다.

서브태스크 1 (27점)

이 서브태스크는 다음의 조건을 만족한다.:

  • N ≤ 500

서브태스크 2 (73점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

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

예제 출력 1

7.5
7.5

예제 입력 2

5 4
1 2 10
2 4 20
3 4 30
4 5 50
2
1 3

예제 출력 2

80.0
30.0

예제 입력 3

11 10
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000
1 7 1000000000
1 8 1000000000
1 9 1000000000
1 10 1000000000
1 11 1000000000
1
1

예제 출력 3

10000000000.0

힌트

예제에 대한 그림은 다음과 같다.:

W3sicHJvYmxlbV9pZCI6IjE1Nzc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVm9yb25vaSBEaWFncmFtIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xNTc3NVwvdm9yb25vaS5wbmdcIiBzdHlsZT1cIndpZHRoOiA1MDBweDsgaGVpZ2h0OiA1MDBweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHVjMGFjXHVjOWM0OiBcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVjODhjXHVkNDVjXHVhY2M0XHVjNWQwXHVjMTFjIDIwXHVhYzFjXHVjNzU4IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTAgVm9yb25vaSBEaWFncmFtLiBcdWNkOWNcdWNjOTg6IFdpa2lwZWRpYTxcL3A+XHJcblxyXG48cD5cdWQzYzlcdWJhNzQgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQwNmNcdWFlMzAgPGVtPm48XC9lbT5cdWM3NTggXHVjODEwIFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWM4MTAgXHVjOWQxXHVkNTY5XHVjNzU4IDxzdHJvbmc+Vm9yb25vaSBEaWFncmFtPFwvc3Ryb25nPlx1Yzc0MCwgXHVkM2M5XHViYTc0IFx1YzBjMVx1Yzc1OCBcdWM4MTBcdWM3NDQgJnF1b3Q7XHVjNWI0XHViNWE0IFx1YzgxMFx1YWNmYyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0XHVhYzAwPyZxdW90OyBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWQ1NWMgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0IFx1YzBhY1x1YzljNFx1YzVkMFx1YzExYyBcdWQzYzlcdWJhNzQgXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM3MDRcdWNlNThcdWIyOTQsIFx1YWRmOCBcdWM3MDRcdWNlNThcdWM2NDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjODBcdWM3NDAgXHVjODEwXHVjNWQwIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMwYzlcdWM3NzQgXHVjZTYwXHVkNTc0XHVjODM4IFx1Yzc4OFx1YjJlNC4gVm9yb25vaSBEaWFncmFtXHVjNzQwIE8oPGVtPm48XC9lbT4mbmJzcDtsb2coPGVtPm48XC9lbT4pKVx1YzVkMCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0IFx1YzU0Y1x1YjgyNFx1YzgzOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWFjZTAgXHViY2Y1XHVjN2ExXHVkNTVjIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YzczY1x1Yjg1YyBcdWM1NDVcdWJhODVcdWM3NzQgXHViMTkyXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWJhYTggXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFZvcm9ub2kgRGlhZ3JhbVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YzljMCBcdWJhYmJcdWQ1NWMgXHViYmZjXHVhZGRjXHViMjk0LCBcdWFkZjggXHVjZGE5XHVhY2E5XHVjNzNjXHViODVjIFx1Yzc3OFx1ZDU3NFx1YzExYyBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjXHVjNzQ0IFx1YzIyMFx1YWNmYyBcdWQ1NjhcdWFlZDggXHViY2Y0XHViMGI0XHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWM2MjRcdWQ2YzQsIFx1YmJmY1x1YWRkY1x1YjI5NCBcdWM1ZWNcdWIyOTAgXHViNTRjXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIwYWVcdWMyMjBcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YWMwMCwgXHViOWU0XHVjNmIwIFx1Y2M5Y1x1YzdhY1x1YzgwMVx1Yzc3OCBWb3Jvbm9pIERpYWdyYW0gXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU1OFx1YzYwMFx1YjJlNCEgXHViYmZjXHVhZGRjXHViMjk0IFx1Yzc3NFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViMTdjXHViYjM4XHVjNzQ0IFx1YzRmMFx1YWUzMCBcdWM4MDRcdWM1ZDAgMjAxOCBLQUlTVCBSVU4gU3ByaW5nIENvbnRlc3QgXHVjNWQwIFx1YWQwMFx1YjgyOFx1YjQxYyBcdWJiMzhcdWM4MWNcdWI5N2MgXHVjZDljXHVjODFjXHVkNTU4XHVjNWVjXHVjMTFjIFx1YjljY1x1YzgxMFx1Yzc5MFx1Yzc1OCBcdWNkOWNcdWQ2MDRcdWM3NDQgXHViOWM5XHVjNzNjXHViODI0IFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViYmZjXHVhZGRjXHVjNzU4IFZvcm9ub2kgRGlhZ3JhbSBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDAgXHVjNjVjIFx1Y2M5Y1x1YzdhY1x1YzgwMVx1Yzc3Y1x1YWU0Yz8gXHViY2Y0XHVkMWI1IFZvcm9ub2kgRGlhZ3JhbVx1Yzc0MCBcdWQzYzlcdWJhNzRcdWM1ZDBcdWMxMWNcdWI5Y2MgXHVjODAxXHVjNmE5XHViNDE4XHViMjk0XHViMzcwLCBcdWJiZmNcdWFkZGNcdWM3NTggVm9yb25vaSBEaWFncmFtXHVjNzQwIFx1YjM1NCBcdWM3N2NcdWJjMThcdWQ2NTRcdWI0MWMgXHVhZDZjXHVjODcwXHVjNzc4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWM4MDFcdWM2YTlcdWI0MThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NzQgPGVtPk48XC9lbT5cdWFjMWNcdWM3NzRcdWFjZTAsIFx1YzU5MVx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCA8ZW0+TTxcL2VtPlx1YWMxYyBcdWM3ODhcdWIyOTQgXHVjNWYwXHVhY2IwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgXHVkMDZjXHVhZTMwIDxlbT5LPFwvZW0+XHVjNzU4IFx1YzgxNVx1YzgxMCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzgxMCBcdWM5ZDFcdWQ1NjlcdWM3NTggJnF1b3Q7Vm9yb25vaSBEaWFncmFtJnF1b3Q7IFx1Yzc0MCBcdWM3NzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFjMDRcdWMxMjAgXHVjMGMxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsICZxdW90O1x1YzgxNVx1YzgxMCBcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzViNFx1YjVhNCBcdWM4MTBcdWFjZmMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNFx1YWMwMCZxdW90OyBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWQ1NWMgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMxOVx1Yzc0MCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjODEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWM3NzRcdWI0ZTQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjOTExXHVjZTU4IFx1Yzc4OFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCAmcXVvdDtWb3Jvbm9pIERpYWdyYW0mcXVvdDtcdWM1ZDBcdWMxMWMgXHVkNTc0XHViMmY5IFx1YzgxMFx1YWNmYyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTVkXHVhYzhjIFx1ZDQ1Y1x1ZDYwNFx1YjQxYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIzNTRcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVhY2UwLCBcdWJiZmNcdWFkZGNcdWJjZjRcdWIyZTQgXHViYTNjXHVjODAwIFx1YjE3Y1x1YmIzOFx1Yzc0NCBcdWMzNjhcdWMxMWMgXHViYmZjXHVhZGRjXHVjNzU4IFx1Y2Y1NFx1Yjk3YyBcdWIwYTlcdWM3OTFcdWQ1NThcdWFjOGMgXHVkNTc0XHVjOGZjXHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCA8ZW0+TjxcL2VtPiwgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOCA8ZW0+TTxcL2VtPlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IDxlbT5NPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc1OCA8ZW0+aTxcL2VtPlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4N1x1YjI5NCBcdWI0NTAgXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOCA8ZW0+czxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5lPHN1Yj5pPFwvc3ViPjxcL2VtPlx1YzY0MCwgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OCA8ZW0+dzxzdWI+aTxcL3N1Yj48XC9lbT5cdWFjMDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjODEwIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWQwNmNcdWFlMzAgPGVtPks8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIDxlbT5LPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODE1XHVjMjE4IDxlbT5hPHN1Yj5pPFwvc3ViPjxcL2VtPlx1YWMwMCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxNVx1YzgxMCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVjNWYwXHVhY2IwXHVhZGY4XHViNzk4XHVkNTA0IFx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPjxlbT5LPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCwgPGVtPmE8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7XHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHViYzE4XHVjNjJjXHViOWJjXHVkNTU4XHVjNWVjXHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzJlNFx1YzIxOCBcdWM2MjRcdWNjMjggXHVhZDAwXHViOWFjXHVjNWQwIFx1Y2QwOFx1YzgxMFx1Yzc0NCBcdWI5ZGVcdWNkOTggXHVjZDVjXHVhZGZjIEFDTS1JQ1BDIFdvcmxkIEZpbmFsc1x1Yzc1OCBcdWFjYmRcdWQ1YTVcdWM1ZDAgXHViOWRlXHVjZGIwXHVjMTFjLCBcdWNkOWNcdWI4MjUgXHVjMmRjIDxzdHJvbmc+XHVjNzdjXHVjY2I0XHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjNjNCBcdWQ1YzhcdWM2YTlcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0PFwvc3Ryb25nPi48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC46PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE1Nzc1XC9pbWcxLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM5MXB4OyBoZWlnaHQ6IDM1MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xNTc3NVwvaW1nMi5wbmdcIiBzdHlsZT1cIndpZHRoOiA2MDBweDsgaGVpZ2h0OiAzNzlweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTU3NzVcL2ltZzMucG5nXCIgc3R5bGU9XCJ3aWR0aDogNDI5cHg7IGhlaWdodDogNDU5cHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IDxlbT5OPFwvZW0+LCZuYnNwOzxlbT5NPFwvZW0+ICZsZTsgMjUwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgPGVtPnM8c3ViPmk8XC9zdWI+PFwvZW0+LCA8ZW0+ZTxzdWI+aTxcL3N1Yj48XC9lbT4gJmxlOyBOPFwvbGk+XHJcblx0PGxpPjEgJmxlOyA8ZW0+dzxzdWI+aTxcL3N1Yj48XC9lbT4gJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT5LPFwvZW0+ICZsZTsgPGVtPk48XC9lbT48XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT5hPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDxlbT5OPFwvZW0+PFwvbGk+XHJcblx0PGxpPlx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVjNWYwXHVhY2IwXHVhZGY4XHViNzk4XHVkNTA0IFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+XHVjNzc0IFx1YzExY1x1YmUwY1x1ZDBkY1x1YzJhNFx1ZDA2Y1x1YjI5NCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC46PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gJmxlOyA1MDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjNzc0IFx1YzExY1x1YmUwY1x1ZDBkY1x1YzJhNFx1ZDA2Y1x1YjI5NCBcdWNkOTRcdWFjMDAgXHVjODFjXHVkNTVjIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTU3NzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWb3Jvbm9pIERpYWdyYW0iLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE1Nzc1XC92b3Jvbm9pLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDUwMHB4OyBoZWlnaHQ6IDUwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmU6IFZvcm9ub2kgRGlhZ3JhbSBtYWRlIHdpdGggMjAgcG9pbnRzLCB3aXRoIHJlc3BlY3QgdG8gRXVjbGlkZWFuIG1ldHJpYy4gU291cmNlOiA8ZW0+V2lraXBlZGlhPFwvZW0+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBDYXJ0ZXNpYW4gY29vcmRpbmF0ZSwgd2UgZGVmaW5lIHRoZSA8c3Ryb25nPlZvcm9ub2kgRGlhZ3JhbTxcL3N0cm9uZz4mbmJzcDtvZiBub25lbXB0eSBwb2ludCBzZXQgb2Ygc2l6ZSA8ZW0+bjxcL2VtPiZuYnNwO2FzIGEgZGlhZ3JhbSB0aGF0IGRpdmlkZXMgdGhlIHBsYW5lIGJ5IHRoZSBjcml0ZXJpYSAmcXVvdDt3aGljaCBwb2ludCBpbiBhIHNldCBpcyBjbG9zZXN0IGluIHRoaXMgbG9jYXRpb24/JnF1b3Q7LiBGb3IgZXhhbXBsZSwgaW4gdGhlIHBpY3R1cmUgYWJvdmUsIGV2ZXJ5IGxvY2F0aW9uIG92ZXIgdGhlIHBsYW5lIGlzIGNvbG9yZWQgYnkgdGhlIGNsb3Nlc3QgYmxhY2sgcG9pbnQgd2l0aCBzdWNoIGxvY2F0aW9uLiBUaGVyZSBpcyBhbiBhbGdvcml0aG0gdGhhdCBjb21wdXRlcyBWb3Jvbm9pIERpYWdyYW0gaW4gTyg8ZW0+bjxcL2VtPiBsb2coPGVtPm48XC9lbT4pKSwgYnV0IHRoaXMgaXMgaW5mYW1vdXMgdG8gYmUgdmVyeSBjb21wbGljYXRlZCBhbmQgaGFyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZmFpbGluZyB0byBzb2x2ZSBhIHByb2JsZW0gYWJvdXQgVm9yb25vaSBEaWFncmFtIGluIGFuIGltcG9ydGFudCBjb21wZXRpdGlvbiwgTWlua3l1IHdhcyBzaG9ja2VkLCBhbmQgaGUgc3RhcnRlZCBsaXZpbmcgd2l0aCBhbGNvaG9scyBldmVyeWRheSEgT25lIHN1bm55IGFmdGVybm9vbiwgTWlua3l1IHdhcyBkcmlua2luZyBiZWVycyBqdXN0IGxpa2UgdGhlIG90aGVyIGRheSwgYW5kIGZvdW5kIGFuIGluZ2VuaW91cyBhbGdvcml0aG0gZm9yIHNvbHZpbmcgVm9yb25vaSBEaWFncmFtcyEgQmVmb3JlIHdyaXRpbmcgYSBwYXBlciBhYm91dCBpdCwgTWlua3l1IHdhbnRzIHRvIHNldCBhIHByb2JsZW0gd2hpY2ggcmVxdWlyZXMgdGhpcyBhbGdvcml0aG0sIHRvIHByZXZlbnQgYW55IGZ1bGwgc2NvcmVycyBpbiAyMDE4IEtBSVNUIFJVTiBTcHJpbmcgQ29udGVzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2h5IGlzIE1pbmt5dSYjMzk7cyBhbGdvcml0aG0gZm9yIFZvcm9ub2kgRGlhZ3JhbSBncmVhdD8gVHJhZGl0aW9uYWwgYWxnb3JpdGhtIGZvciBWb3Jvbm9pIERpYWdyYW1zIHdvcmtzIG9ubHkgaW4gY2FydGVzaWFuIGNvb3JkaW5hdGUsIGJ1dCBNaW5reXUmIzM5O3MgYWxnb3JpdGhtIHdvcmtzIG9uIG1vcmUgZ2VuZXJhbGl6ZWQgc3RydWN0dXJlIC0tIHRoZSAmcXVvdDtncmFwaCZxdW90Oy4gQ29uc2lkZXIgYSBjb25uZWN0ZWQgZ3JhcGggd2l0aCA8ZW0+TjxcL2VtPiZuYnNwO3ZlcnRpY2VzIGFuZCA8ZW0+TTxcL2VtPiZuYnNwO2VkZ2VzIHdpdGggcG9zaXRpdmUgd2VpZ2h0LiBXaGVuIHlvdSBhcmUgZ2l2ZW4gYSBub25lbXB0eSB2ZXJ0ZXggc3Vic2V0IG9mIHNpemUgPGVtPks8XC9lbT4sIHRoZSAmcXVvdDtWb3Jvbm9pIERpYWdyYW0mcXVvdDsgb2YgdGhpcyBwb2ludCBzZXQgZGl2aWRlcyBhbGwgbG9jYXRpb24gaW4gdGhlIGVkZ2VzIGJ5IHRoZSBjcml0ZXJpYSAmcXVvdDt3aGljaCB2ZXJ0ZXggaW4gYSBzZXQgaXMgY2xvc2VzdCBpbiB0aGlzIGxvY2F0aW9uPyZxdW90OyBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHBvaW50cyB3aXRoIGVxdWFsIGRpc3RhbmNlLCB0aGUgb25lIHdpdGggc21hbGxlc3QgdmVydGV4IG51bWJlciBpcyBjb25zaWRlcmVkIGNsb3Nlci48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIHdlaWdodGVkIGNvbm5uZWN0ZWQgZ3JhcGggYW5kIGEgbm9uZW1wdHkgdmVydGV4IHN1YnNldCBvZiBzaXplIDxlbT5LPFwvZW0+LiBGb3IgZWFjaCB2ZXJ0ZXgsIHlvdSBzaG91bGQgY2FsY3VsYXRlIHRoZSB0b3RhbCBsZW5ndGggb2YgZWRnZXMgdGhhdCBpcyAmcXVvdDtjbG9zZXN0JnF1b3Q7IHRvIHRoZSBnaXZlbiB2ZXJ0ZXguIFNvbHZlIHRoaXMgcHJvYmxlbSwgYW5kIHdyaXRlIHRoZSBwYXBlciBmYXN0ZXIgdGhhbiBNaW5reXUsIHRvIHNjYXR0ZXIgaGlzIGhpZ2ggaG9wZXMhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyA8ZW0+TjxcL2VtPiwgYW5kIHRoZSBudW1iZXIgb2YgZWRnZXMgPGVtPk08XC9lbT4mbmJzcDthcmUgZ2l2ZW4gYXMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vycy48XC9wPlxyXG5cclxuPHA+SW4gdGhlIG5leHQgPGVtPk08XC9lbT4mbmJzcDtsaW5lcywgdHdvIGVuZHBvaW50IG9mIHRoZSA8ZW0+aTxcL2VtPi10aCBlZGdlIDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPiwgPGVtPmU8c3ViPmk8XC9zdWI+PFwvZW0+LCBhbmQgdGhlIHdlaWdodCBvZiA8ZW0+aTxcL2VtPi10aCBlZGdlIDxlbT53PHN1Yj5pPFwvc3ViPjxcL2VtPiZuYnNwO2lzIGdpdmVuIGFzIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vycy48XC9wPlxyXG5cclxuPHA+SW4gdGhlIG5leHQgbGluZSwgdGhlIHNpemUgb2YgdmVydGV4IHN1YnNldCA8ZW0+SzxcL2VtPiZuYnNwO2lzIGdpdmVuLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgbmV4dCBsaW5lLCA8ZW0+SzxcL2VtPiZuYnNwO2Rpc3RpbmN0IGludGVnZXIgPGVtPmE8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7aXMgZ2l2ZW4gaW4gaW5jcmVhc2luZyBvcmRlci4gRWFjaCBpbnRlZ2VyIGRlbm90ZXMgdGhlIG51bWJlciBvZiB2ZXJ0ZXggaW4gdGhlIHN1YnNldC48XC9wPlxyXG5cclxuPHA+WW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgZ2l2ZW4gZ3JhcGggaXMgY29ubmVjdGVkLiBJbiBvdGhlciB3b3JkcywgdGhlcmUgZXhpc3RzIGEgcGF0aCBmcm9tIGFueSB2ZXJ0ZXggdG8gdGhlIGFueSBvdGhlciB2ZXJ0ZXguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gPGVtPks8XC9lbT4mbmJzcDtsaW5lcywgcHJpbnQgb25lIGRlY2ltYWwgbnVtYmVyIGZvciBlYWNoIGxpbmUuIEluIDxlbT5pPFwvZW0+LXRoIGxpbmUsIHByaW50IHRoZSBzdW0gb2YgbGVuZ3RoIHdoaWNoIGNvbnNpZGVycyB2ZXJ0ZXggPGVtPmE8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7YXMgdGhlIGNsb3Nlc3QuPFwvcD5cclxuXHJcbjxwPkV2ZXJ5IG91dHB1dHRlZCBudW1iZXJzIHNob3VsZCBiZSBleGFjdGx5IHJvdW5kZWQgdG8gdGhlIGZpcnN0IGRpZ2l0IGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50IChzZWUgdGhlIHNhbXBsZSBpbnB1dFwvb3V0cHV0IGZvciBjbGFyaWZpY2F0aW9uKS4gSW4gYWNjb3JkYW5jZSB0byB0aGUgcmVjZW50IEFDTS1JQ1BDIFdvcmxkIEZpbmFscyB0cmVuZCAod2hpY2ggcmVxdWlyZXMgaGlnaC1wcmVjaXNpb24gZmxvYXRpbmcgcG9pbnQgbWFuYWdlbWVudCksIDxzdHJvbmc+bm8gcHJlY2lzaW9uIGVycm9yIGlzIGFsbG93ZWQ8XC9zdHJvbmc+LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGVzZSBhcmUgdGhlIHBpY3R1cmVzIGNvcnJlc3BvbmRpbmcgdG8gZWFjaCBzYW1wbGUgdGVzdC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTU3NzVcL2ltZzEucG5nXCIgc3R5bGU9XCJ3aWR0aDogMzkxcHg7IGhlaWdodDogMzUxcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE1Nzc1XC9pbWcyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDYwMHB4OyBoZWlnaHQ6IDM3OXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xNTc3NVwvaW1nMy5wbmdcIiBzdHlsZT1cIndpZHRoOiA0MjlweDsgaGVpZ2h0OiA0NTlweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgPGVtPk48XC9lbT4sJm5ic3A7PGVtPk08XC9lbT4gJmxlOyAyNTAsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyA8ZW0+czxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5lPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IE48XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT53PHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgPGVtPks8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgPGVtPmE8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgPGVtPk48XC9lbT48XC9saT5cclxuXHQ8bGk+R2l2ZW4gZ3JhcGggaXMgY29ubmVjdGVkLjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5UaGlzIHN1YnRhc2sgaGFzIGFkZGl0aW9uYWwgY29uc3RyYWludHMuOiAmbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5OICZsZTsgNTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPlRoaXMgc3VidGFzayBoYXMgbm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4ifV0=

출처

University > KAIST > 2018 KAIST RUN Spring Contest V번

채점

  • 예제는 채점하지 않는다.