시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 24 22 51.163%

문제

JOI 국에는 N개의 도시가 있다. 이 도시들 사이에는 M개의 도로가 있는데 이 도로는 양방향으로 통행이 가능한 도로이다. 모든 도시들은 연결되어 있다.

현재 JOI국의 K개의 도시들에서 축제가 벌어지고 있다. JOI국의 국민들은 축제를 좋아하는 사람들도 있지만 그 분위기를 매우 싫어하는 국민들도 제법 있다.

축제를 싫어하는 사람 Q명이 도시들 사이를 이동하려고 한다. 출발도시와 도착도시가 주어질 때, 가능한 한 축제를 하는 도시와의 거리를 멀게하여 원하는 도시로 가는 방법을 구하여라. 단, 축제하는 도시와 임의의 도시와의 거리는 두 지점간의 최단경로로 계산한다.

입력

첫째 줄에 도시의 수 N, 도로의 수 M, 축제를 여는 도시의 수 K, 축제를 싫어하는 사람의 수 Q가 공백으로 구분되어 입력된다.

다음 줄부터 M줄에 걸쳐서 각 도로의 정보 시작점, 출발점, 거리가 공백으로 구분되어 입력된다. 거리는 1000을 넘지 않는다.

다음 줄 부터 K줄에 걸쳐서 축제를 하는 도시의 번호가 한 줄에 하나씩 입력된다.

다음 줄부터 Q줄에 걸쳐서 축제를 싫어하는 사람이 출발하는 출발지와 도착지가 한 줄에 하나씩 공백으로 구분되어 입력된다.

  • 2 ≤ N ≤ 100000
  • 1 ≤ M ≤ 200000
  • 1 ≤ K ≤ N
  • 1 ≤ Q ≤ 100000

출력

Q줄에 걸쳐서 입력받은 순서대로 각 사람이 이동하는데 축제하는 도시와의 최대거리를 출력한다.

예제 입력 1

6 6 2 3
1 2 5
2 3 4
2 4 6
3 5 9
4 5 3
5 6 7
1
6
3 4
5 2
1 4

예제 출력 1

7
5
0

예제 입력 2

12 17 2 5
1 3 6
1 6 7
2 3 8
2 4 4
2 8 11
2 12 2
3 6 3
3 7 8
3 11 2
4 12 2
5 10 3
6 10 5
8 9 6
8 12 7
9 10 6
11 9 10
12 9 5
8
7
2 6
5 2
1 10
8 9
9 4

예제 출력 2

8
8
11
0
6

힌트

예제 1. 3에서 4로 가는 경우는 3-5-4로 이동하면 가장 가까운 축제가 6번이고 거리는 7이다. 이 값이 최대이고, 5에서 2로 가는 경우는 5-3-2, 5-4-2 모두 1번 축제와 거리 5가 되므로 이 값을 출력한다. 마지막으로 1에서 4로 가는 경우는 1이 축제지 이므로 축제지와의 최대거리는 0이된다.

 

예제 2.

W3sicHJvYmxlbV9pZCI6IjU1NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJKT0kgXHVhZDZkXHVhYzAwXHVjNzU4IFx1ZDU4OVx1YzBhYyIsImRlc2NyaXB0aW9uIjoiPHA+Sk9JIFx1YWQ2ZFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIzYzRcdWMyZGNcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWM3NzQgXHViM2M0XHViODVjXHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQxYjVcdWQ1ODlcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjNjNFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgSk9JXHVhZDZkXHVjNzU4IEtcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHViNGU0XHVjNWQwXHVjMTFjIFx1Y2Q5NVx1YzgxY1x1YWMwMCBcdWJjOGNcdWM1YjRcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBKT0lcdWFkNmRcdWM3NTggXHVhZDZkXHViYmZjXHViNGU0XHVjNzQwIFx1Y2Q5NVx1YzgxY1x1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHViM2M0IFx1Yzc4OFx1YzljMFx1YjljYyBcdWFkZjggXHViZDg0XHVjNzA0XHVhZTMwXHViOTdjIFx1YjllNFx1YzZiMCBcdWMyZWJcdWM1YjRcdWQ1NThcdWIyOTQgXHVhZDZkXHViYmZjXHViNGU0XHViM2M0IFx1YzgxY1x1YmM5NSBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Q5NVx1YzgxY1x1Yjk3YyBcdWMyZWJcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjIFFcdWJhODVcdWM3NzQgXHViM2M0XHVjMmRjXHViNGU0IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWNkOWNcdWJjMWNcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHVjYzI5XHViM2M0XHVjMmRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjZDk1XHVjODFjXHViOTdjIFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM2NDBcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YmE0MFx1YWM4Y1x1ZDU1OFx1YzVlYyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHViODVjIFx1YWMwMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLiBcdWIyZTgsIFx1Y2Q5NVx1YzgxY1x1ZDU1OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM2NDAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViNDUwIFx1YzljMFx1YzgxMFx1YWMwNFx1Yzc1OCBcdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWI4NWMgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE4sIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMTggTSwgXHVjZDk1XHVjODFjXHViOTdjIFx1YzVlY1x1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IEssIFx1Y2Q5NVx1YzgxY1x1Yjk3YyBcdWMyZWJcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOCBRXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIE1cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0IFx1YzJkY1x1Yzc5MVx1YzgxMCwgXHVjZDljXHViYzFjXHVjODEwLCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YWM3MFx1YjlhY1x1YjI5NCAxMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDQgXHViZDgwXHVkMTMwIEtcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1Y2Q5NVx1YzgxY1x1Yjk3YyBcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVjZDk1XHVjODFjXHViOTdjIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDljXHViYzFjXHVkNTU4XHViMjk0IFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YzY0MCBcdWIzYzRcdWNjMjlcdWM5YzBcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MiAmbGU7IE4gJmxlOyAxMDAwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAyMDAwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEsgJmxlOyBOPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBRICZsZTsgMTAwMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5RXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1Y2Q5NVx1YzgxY1x1ZDU1OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM2NDBcdWM3NTggXHVjZDVjXHViMzAwXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC91cGxvYWRcL2ltYWdlczNcL2tpbmcxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjkycHg7IHdpZHRoOjM5MXB4XCIgdGl0bGU9XCJcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIDEuIDNcdWM1ZDBcdWMxMWMgNFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IDMtNS00XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1Y2Q5NVx1YzgxY1x1YWMwMCA2XHViYzg4XHVjNzc0XHVhY2UwIFx1YWM3MFx1YjlhY1x1YjI5NCA3XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3NFx1YWNlMCwgNVx1YzVkMFx1YzExYyAyXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgNS0zLTIsIDUtNC0yIFx1YmFhOFx1YjQ1MCAxXHViYzg4IFx1Y2Q5NVx1YzgxY1x1YzY0MCBcdWFjNzBcdWI5YWMgNVx1YWMwMCBcdWI0MThcdWJiYzBcdWI4NWMgXHVjNzc0IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyAxXHVjNWQwXHVjMTFjIDRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCAxXHVjNzc0IFx1Y2Q5NVx1YzgxY1x1YzljMCBcdWM3NzRcdWJiYzBcdWI4NWMgXHVjZDk1XHVjODFjXHVjOWMwXHVjNjQwXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWM3MFx1YjlhY1x1YjI5NCAwXHVjNzc0XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvdXBsb2FkXC9pbWFnZXMzXC9raW5nMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgd2lkdGg6Mzc1cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHVjNjA4XHVjODFjIDIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTQyIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JIFx1NTZmZFx1MzA2ZVx1MzA0YVx1Nzk2ZFx1MzA4YVx1NGU4Ylx1NjBjNSAiLCJkZXNjcmlwdGlvbiI6IjxwPkpPSSBcdTU2ZmRcdTMwNmJcdTMwNmYgTiBcdTUwMGJcdTMwNmVcdTg4NTdcdTMwNGNcdTMwNDJcdTMwOGFcdWZmMGNcdTMwNWRcdTMwOGNcdTMwODlcdTMwNmVcdTk1OTNcdTMwNmYgTSBcdTY3MmNcdTMwNmVcdTUzY2NcdTY1YjlcdTU0MTFcdTMwNmJcdTkwMWFcdTg4NGNcdTUzZWZcdTgwZmRcdTMwNmFcdTkwNTNcdThkZWZcdTMwNjdcdTdkNTBcdTMwNzBcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTU2ZmRcdTZjMTFcdTMwNmZcdTkwNTNcdThkZWZcdTMwOTJcdTkwMWFcdTMwNjNcdTMwNjZcdTMwNWRcdTMwOGNcdTMwODlcdTMwNmVcdTg4NTdcdTMwOTJcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+Sk9JIFx1NTZmZFx1MzA2ZVx1NTZmZFx1NmMxMVx1MzA2Ylx1MzA2Zlx1ZmYwY1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1NTk3ZFx1MzA0ZFx1MzA2YVx1NGViYVx1MzA0Y1x1NTkxYVx1MzA0Zlx1ZmYwY1x1NzNmZVx1NTcyOFx1ZmYwY0sgXHU1MDBiXHUzMDZlXHU4ODU3XHUzMDY3XHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjXHU5NzVlXHU1ZTM4XHUzMDZiXHU4Y2QxXHUzMDhmXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU0ZTAwXHU2NWI5XHUzMDY3XHVmZjBjXHU0ZTAwXHU5MGU4XHUzMDZlXHU1NmZkXHU2YzExXHUzMDZmXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDkyXHU5YTEyXHUzMDRjXHUzMDU3XHUzMDQ0XHUzMDY4XHUzMDU3XHUzMDY2XHU1YWNjXHUzMDQ0XHVmZjBjXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDZiXHUzMDY3XHUzMDRkXHUzMDhiXHUzMDYwXHUzMDUxXHU4ZmQxXHUzMDY1XHUzMDRkXHUzMDVmXHUzMDRmXHUzMDZhXHUzMDQ0XHUzMDY4XHU2MDFkXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA1ZFx1MzA1M1x1MzA2N1x1NTZmZFx1NzM4Ylx1MzA2Zlx1ZmYwY1x1NTEyYVx1NzljMFx1MzA2YVx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBkZVx1MzBmY1x1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Ylx1ZmYwY1x1MzA1ZFx1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2YVx1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA5Mlx1NWFjY1x1MzA0Nlx1NTZmZFx1NmMxMVx1MzA2ZVx1MzA1Zlx1MzA4MVx1ZmYwY1x1MzA0Mlx1MzA4Ylx1ODg1N1x1MzA0Ylx1MzA4OVx1MzA0Mlx1MzA4Ylx1ODg1N1x1MzA2Ylx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2Ylx1ZmYwY1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ODg1N1x1MzA2Ylx1MzA2OVx1MzA4Y1x1MzA2MFx1MzA1MVx1OGZkMVx1MzA2NVx1MzA0Ylx1MzA1YVx1MzA2Ylx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1MzA0Ylx1MzA5Mlx1OWFkOFx1OTAxZlx1MzA2Ylx1OGFiZlx1MzA3OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2ZVx1MzA2N1x1MzA0ZFx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA2ZVx1NGY1Y1x1NjIxMFx1MzA5Mlx1NGY5ZFx1OTgzY1x1MzA1N1x1MzA1Zlx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTkwNTNcdThkZWZcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNjhcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTg4NTdcdTMwNmVcdTYwYzVcdTU4MzFcdWZmMGNcdTMwNGFcdTMwODhcdTMwNzMgUSBcdTUwMGJcdTMwNmVcdTMwYWZcdTMwYThcdTMwZWFcdWZmMDhcdTUxZmFcdTc2N2FcdTMwNTlcdTMwOGJcdTg4NTcgUzxzdWI+aTxcL3N1Yj4gXHUzMDY4XHU4ODRjXHUzMDRkXHUzMDVmXHUzMDQ0XHU4ODU3IFQ8c3ViPmk8XC9zdWI+IFx1MzA2ZVx1N2Q0NFx1ZmYwOVx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1ZmYwZVx1NTQwNFx1MzBhZlx1MzBhOFx1MzBlYSBpIFx1MzA2Ylx1NWJmZVx1MzA1N1x1ZmYwY1x1ODg1NyBTPHN1Yj5pPFwvc3ViPiBcdTMwNGJcdTMwODlcdTg4NTcgVDxzdWI+aTxcL3N1Yj4gXHUzMDc4XHUzMDZlXHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU3ZDRjXHU4ZGVmXHUzMDZlXHUzMDQ2XHUzMDYxXHVmZjBjXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDdlXHUzMDY3XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDRjXHU2NzAwXHU1OTI3XHUzMDY4XHUzMDZhXHUzMDhiXHU3ZDRjXHU4ZGVmXHUzMDZlXHVmZjBjXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDdlXHUzMDY3XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlXHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjXHUzMDQyXHUzMDhiXHU3ZDRjXHU4ZGVmXHUzMDZlXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDdlXHUzMDY3XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDY4XHUzMDZmXHVmZjBjXHU3ZDRjXHU4ZGVmXHU0ZTBhXHUzMDZlXHU4ODU3XHUzMDRiXHUzMDg5XHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU4ODU3XHUzMDdlXHUzMDY3XHUzMDZlXHU3OWZiXHU1MmQ1XHU4ZGRkXHU5NmUyXHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDZlXHUzMDUzXHUzMDY4XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBOLCBNLCBLLCBRIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZU4gXHUzMDZmIEpPSSBcdTU2ZmRcdTMwNmVcdTg4NTdcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTJcdWZmMGNNIFx1MzA2ZiBKT0lcdTU2ZmRcdTMwNmVcdTkwNTNcdThkZWZcdTMwNmVcdTY3MmNcdTY1NzBcdTMwOTJcdWZmMGNLIFx1MzA2Zlx1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ODg1N1x1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1ZmYwY1EgXHUzMDZmXHUzMGFmXHUzMGE4XHUzMGVhXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHU4ODY4XHUzMDU5XHVmZjBlXHU4ODU3XHUzMDZiXHUzMDZmIDEsIDIsICZtaWRkb3Q7ICZtaWRkb3Q7ICZtaWRkb3Q7ICwgTiBcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTMwNjRcdTMwNTFcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU3ZDlhXHUzMDRmIE0gXHU4ODRjXHUzMDZmXHU5MDUzXHU4ZGVmXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlaSArIDEgXHU4ODRjXHU3NmVlICgxICZsZTsgaSAmbGU7IE0pIFx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEw8c3ViPmk8XC9zdWI+ICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmxlOyBOLCAxICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmxlOyBOKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA0Y1x1ODg1NyBBPHN1Yj5pPFwvc3ViPiBcdTMwNjhcdTg4NTcgQjxzdWI+aTxcL3N1Yj4gXHUzMDkyXHU3ZDUwXHUzMDkzXHUzMDY3XHUzMDRhXHUzMDhhXHVmZjBjXHU5NTc3XHUzMDU1XHUzMDRjIEw8c3ViPmk8XC9zdWI+IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZVx1OTA1M1x1OGRlZlx1MzA2ZVx1NGUyMVx1N2FlZlx1MzA0Y1x1NTQwY1x1MzA1OFx1ODg1N1x1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY1x1NGVmYlx1NjEwZlx1MzA2ZSAyIFx1MzA2NFx1MzA2ZVx1ODg1NyBwLCBxIFx1MzA2Ylx1NWJmZVx1MzA1N1x1ZmYwY3AgXHUzMDY4IHFcdTMwOTJcdTdkNTBcdTMwNzZcdTkwNTNcdThkZWZcdTMwNmYgMiBcdTY3MmNcdTRlZTVcdTRlMGFcdTViNThcdTU3MjhcdTMwNTdcdTMwNmFcdTMwNDRcdWZmMGVcdTMwNjlcdTMwNmVcdTg4NTdcdTMwNGJcdTMwODlcdTMwNjlcdTMwNmVcdTg4NTdcdTMwNzhcdTMwODJcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdTkwNTNcdThkZWZcdTMwOTJcdTMwNWZcdTMwNjlcdTMwNjNcdTMwNjZcdTg4NGNcdTMwNGZcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU3ZDlhXHUzMDRmIEsgXHU4ODRjXHUzMDZmXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU4ODU3XHUzMDZlXHU2MGM1XHU1ODMxXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlaSArIE0gKyAxIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBLKSBcdTMwNmJcdTMwNmYgMSBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgRjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBGPHN1Yj5pPFwvc3ViPiAmbGU7IE4pIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ODg1NyBGPHN1Yj5pPFwvc3ViPiBcdTMwNjdcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVGPHN1Yj4xPFwvc3ViPiwgJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgLCBGPHN1Yj5LPFwvc3ViPiBcdTMwNmVcdTRlMmRcdTMwNmJcdTU0MGNcdTMwNThcdTUwMjRcdTMwNGMgMiBcdTU2ZGVcdTRlZTVcdTRlMGFcdTczZmVcdTMwOGNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU3ZDlhXHUzMDRmIFEgXHU4ODRjXHUzMDZmXHUzMGFmXHUzMGE4XHUzMGVhXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlaSArIE0gKyBLICsgMSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgUSkgXHUzMDZiXHUzMDZmIDIgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIFM8c3ViPmk8XC9zdWI+LCBUPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IFM8c3ViPmk8XC9zdWI+ICZsZTsgTiwgMSAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgTiwgUzxzdWI+aTxcL3N1Yj4gJm5lOyBUPHN1Yj5pPFwvc3ViPikgXHUzMDRjXHU3YTdhXHU3NjdkXHUzMDkyXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY4XHUzMDU3XHUzMDY2XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmIGkgXHU3NTZhXHU3NmVlXHUzMDZlXHUzMGFmXHUzMGE4XHUzMGVhXHUzMDZlXHU1MWZhXHU3NjdhXHUzMDU5XHUzMDhiXHU4ODU3XHUzMDRjIFM8c3ViPmk8XC9zdWI+IFx1MzA2N1x1MzA0Mlx1MzA4YVx1ODg0Y1x1MzA0ZFx1MzA1Zlx1MzA0NFx1ODg1N1x1MzA0YyBUPHN1Yj5pPFwvc3ViPiBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTUyMzZcdTk2NTA8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4yICZsZTsgTiAmbGU7IDEwMDAwMCAoPSAxMDxzdXA+NTxcL3N1cD4pIEpPSSBcdTU2ZmRcdTMwNmVcdTg4NTdcdTMwNmVcdTUwMGJcdTY1NzA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAyMDAwMDAgKD0gMiAmdGltZXM7IDEwPHN1cD41PFwvc3VwPikgSk9JIFx1NTZmZFx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1NjcyY1x1NjU3MDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgSyAmbGU7IE4gXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU4ODU3XHUzMDZlXHU1MDBiXHU2NTcwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBRICZsZTsgMTAwMDAwICg9IDEwPHN1cD41PFwvc3VwPikgXHUzMGFmXHUzMGE4XHUzMGVhXHUzMDZlXHU1MDBiXHU2NTcwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBMPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAgaSBcdTc1NmFcdTc2ZWVcdTMwNmVcdTkwNTNcdThkZWZcdTMwNmVcdTk1NzdcdTMwNTU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY1x1NTE2OFx1MzBhZlx1MzBhOFx1MzBlYVx1MzA3OFx1MzA2ZVx1N2I1NFx1MzA0OFx1MzA5MiBRIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZVx1MzA1OVx1MzA2YVx1MzA4Zlx1MzA2MVx1ZmYwY2kgXHU4ODRjXHU3NmVlXHUzMDZiXHVmZjBjXHU4ODU3IFM8c3ViPmk8XC9zdWI+IFx1MzA0Ylx1MzA4OVx1ODg1NyBUPHN1Yj5pPFwvc3ViPiBcdTMwNzhcdTMwNmVcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTdkNGNcdThkZWZcdTMwNmVcdTMwNDZcdTMwNjFcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNGNcdTY3MDBcdTU5MjdcdTMwNjhcdTMwNmFcdTMwOGJcdTdkNGNcdThkZWZcdTMwNmVcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHA+NiBcdTMwNjRcdTMwNmVcdTg4NTdcdTMwNGMgNiBcdTY3MmNcdTMwNmVcdTkwNTNcdThkZWZcdTMwNjdcdTdkNTBcdTMwNzBcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNmZcdTg4NTcgMSwgNiBcdTMwNmUgMiBcdTMwNjRcdTMwNmVcdTg4NTdcdTMwNjdcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmZcdTRlZTVcdTRlMGJcdTMwNmUzIFx1MzA2NFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHUzMDY0XHU3NmVlXHUzMDZlXHUzMGFmXHUzMGE4XHUzMGVhXHUzMDZmXHU4ODU3IDMgXHUzMDRiXHUzMDg5XHU4ODU3IDQgXHUzMDc4XHU4ODRjXHUzMDRmXHUzMDY4XHUzMDQ0XHUzMDQ2XHUzMDgyXHUzMDZlXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHU4ODU3IDIgXHUzMDkyXHU3ZDRjXHU3NTMxXHUzMDU5XHUzMDhiXHU3ZDRjXHU4ZGVmXHUzMDY3XHUzMDZmXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDdlXHUzMDY3XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDZmIDVcdWZmMGNcdTg4NTcgNSBcdTMwOTJcdTdkNGNcdTc1MzFcdTMwNTlcdTMwOGJcdTdkNGNcdThkZWZcdTMwNjdcdTMwNmZcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNmYgNyBcdTMwNjhcdTMwNmFcdTMwOGJcdTMwNWZcdTMwODFcdWZmMGNcdTdiNTRcdTMwNDhcdTMwNmYgNyBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+MiBcdTMwNjRcdTc2ZWVcdTMwNmVcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmZcdTg4NTcgNSBcdTMwNGJcdTMwODlcdTg4NTcgMiBcdTMwNzhcdTg4NGNcdTMwNGZcdTMwNjhcdTMwNDRcdTMwNDZcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTg4NTcgMyBcdTMwNjhcdTg4NTcgNCBcdTMwNmVcdTMwNjlcdTMwNjFcdTMwODlcdTMwOTJcdTdkNGNcdTc1MzFcdTMwNTdcdTMwNjZcdTMwODJcdWZmMGNcdTg4NTcgMiBcdTMwNjdcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNGNcdTY3MDBcdTVjMGZcdTMwNjhcdTMwNmFcdTMwOGFcdWZmMGNcdTdiNTRcdTMwNDhcdTMwNmYgNSBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+MyBcdTMwNjRcdTc2ZWVcdTMwNmVcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmZcdTg4NTcgMSBcdTMwNGJcdTMwODlcdTg4NTcgNCBcdTMwNzhcdTg4NGNcdTMwNGZcdTMwNjhcdTMwNDRcdTMwNDZcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTg4NTcgMSBcdTMwNmZcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTg4NTdcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNWZcdTMwODFcdWZmMGNcdTdiNTRcdTMwNDhcdTMwNmYgMCBcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMzXC9raW5nMS5wbmdcIiBzdHlsZT1cImhlaWdodDo5MnB4OyB3aWR0aDozOTFweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdTU2ZjMgMTogXHU1MTY1XHU1MjliXHU0ZjhiIDE8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzM1wva2luZzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE5cHg7IHdpZHRoOjM3NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1NTZmMyAyOiBcdTUxNjVcdTUyOWJcdTRmOGIgMjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2012 5번

  • 문제를 번역한 사람: koosaga

채점

  • 제출한 후 다른 소스를 제출하려면 3초가 지나야 한다.