시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 58 33 27 56.250%

문제

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+XHVjNjA4XHVjODFjIDIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTQyIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JIFx1NTZmZFx1MzA2ZVx1MzA0YVx1Nzk2ZFx1MzA4YVx1NGU4Ylx1NjBjNSIsImRlc2NyaXB0aW9uIjoiPHA+Sk9JIFx1NTZmZFx1MzA2Ylx1MzA2ZiBOIFx1NTAwYlx1MzA2ZVx1ODg1N1x1MzA0Y1x1MzA0Mlx1MzA4YVx1ZmYwY1x1MzA1ZFx1MzA4Y1x1MzA4OVx1MzA2ZVx1OTU5M1x1MzA2ZiBNIFx1NjcyY1x1MzA2ZVx1NTNjY1x1NjViOVx1NTQxMVx1MzA2Ylx1OTAxYVx1ODg0Y1x1NTNlZlx1ODBmZFx1MzA2YVx1OTA1M1x1OGRlZlx1MzA2N1x1N2Q1MFx1MzA3MFx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NTZmZFx1NmMxMVx1MzA2Zlx1OTA1M1x1OGRlZlx1MzA5Mlx1OTAxYVx1MzA2M1x1MzA2Nlx1MzA1ZFx1MzA4Y1x1MzA4OVx1MzA2ZVx1ODg1N1x1MzA5Mlx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5KT0kgXHU1NmZkXHUzMDZlXHU1NmZkXHU2YzExXHUzMDZiXHUzMDZmXHVmZjBjXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU1OTdkXHUzMDRkXHUzMDZhXHU0ZWJhXHUzMDRjXHU1OTFhXHUzMDRmXHVmZjBjXHU3M2ZlXHU1NzI4XHVmZjBjSyBcdTUwMGJcdTMwNmVcdTg4NTdcdTMwNjdcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTk3NWVcdTVlMzhcdTMwNmJcdThjZDFcdTMwOGZcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTRlMDBcdTY1YjlcdTMwNjdcdWZmMGNcdTRlMDBcdTkwZThcdTMwNmVcdTU2ZmRcdTZjMTFcdTMwNmZcdTMwNGFcdTc5NmRcdTMwOGFcdTMwOTJcdTlhMTJcdTMwNGNcdTMwNTdcdTMwNDRcdTMwNjhcdTMwNTdcdTMwNjZcdTVhY2NcdTMwNDRcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNmJcdTMwNjdcdTMwNGRcdTMwOGJcdTMwNjBcdTMwNTFcdThmZDFcdTMwNjVcdTMwNGRcdTMwNWZcdTMwNGZcdTMwNmFcdTMwNDRcdTMwNjhcdTYwMWRcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMDVkXHUzMDUzXHUzMDY3XHU1NmZkXHU3MzhiXHUzMDZmXHVmZjBjXHU1MTJhXHU3OWMwXHUzMDZhXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGRlXHUzMGZjXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZiXHVmZjBjXHUzMDVkXHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZhXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDkyXHU1YWNjXHUzMDQ2XHU1NmZkXHU2YzExXHUzMDZlXHUzMDVmXHUzMDgxXHVmZjBjXHUzMDQyXHUzMDhiXHU4ODU3XHUzMDRiXHUzMDg5XHUzMDQyXHUzMDhiXHU4ODU3XHUzMDZiXHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDVmXHUzMDgxXHUzMDZiXHVmZjBjXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU4ODU3XHUzMDZiXHUzMDY5XHUzMDhjXHUzMDYwXHUzMDUxXHU4ZmQxXHUzMDY1XHUzMDRiXHUzMDVhXHUzMDZiXHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHUzMDRiXHUzMDkyXHU5YWQ4XHU5MDFmXHUzMDZiXHU4YWJmXHUzMDc5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZlXHUzMDY3XHUzMDRkXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDZlXHU0ZjVjXHU2MjEwXHUzMDkyXHU0ZjlkXHU5ODNjXHUzMDU3XHUzMDVmXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1OTA1M1x1OGRlZlx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA2OFx1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ODg1N1x1MzA2ZVx1NjBjNVx1NTgzMVx1ZmYwY1x1MzA0YVx1MzA4OFx1MzA3MyBRIFx1NTAwYlx1MzA2ZVx1MzBhZlx1MzBhOFx1MzBlYVx1ZmYwOFx1NTFmYVx1NzY3YVx1MzA1OVx1MzA4Ylx1ODg1NyBTPHN1Yj5pPFwvc3ViPiBcdTMwNjhcdTg4NGNcdTMwNGRcdTMwNWZcdTMwNDRcdTg4NTcgVDxzdWI+aTxcL3N1Yj4gXHUzMDZlXHU3ZDQ0XHVmZjA5XHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHVmZjBlXHU1NDA0XHUzMGFmXHUzMGE4XHUzMGVhIGkgXHUzMDZiXHU1YmZlXHUzMDU3XHVmZjBjXHU4ODU3IFM8c3ViPmk8XC9zdWI+IFx1MzA0Ylx1MzA4OVx1ODg1NyBUPHN1Yj5pPFwvc3ViPiBcdTMwNzhcdTMwNmVcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTdkNGNcdThkZWZcdTMwNmVcdTMwNDZcdTMwNjFcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNGNcdTY3MDBcdTU5MjdcdTMwNjhcdTMwNmFcdTMwOGJcdTdkNGNcdThkZWZcdTMwNmVcdWZmMGNcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTMwNDJcdTMwOGJcdTdkNGNcdThkZWZcdTMwNmVcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNjhcdTMwNmZcdWZmMGNcdTdkNGNcdThkZWZcdTRlMGFcdTMwNmVcdTg4NTdcdTMwNGJcdTMwODlcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTg4NTdcdTMwN2VcdTMwNjdcdTMwNmVcdTc5ZmJcdTUyZDVcdThkZGRcdTk2ZTJcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwNmVcdTMwNTNcdTMwNjhcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4sIE0sIEssIFEgXHUzMDRjXHU3YTdhXHU3NjdkXHUzMDkyXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY4XHUzMDU3XHUzMDY2XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlTiBcdTMwNmYgSk9JIFx1NTZmZFx1MzA2ZVx1ODg1N1x1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1ZmYwY00gXHUzMDZmIEpPSVx1NTZmZFx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1NjcyY1x1NjU3MFx1MzA5Mlx1ZmYwY0sgXHUzMDZmXHUzMDRhXHU3OTZkXHUzMDhhXHUzMDRjXHU5NThiXHU1MGFjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU4ODU3XHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHVmZjBjUSBcdTMwNmZcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTJcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTg4NjhcdTMwNTlcdWZmMGVcdTg4NTdcdTMwNmJcdTMwNmYgMSwgMiwgJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgLCBOIFx1MzA2ZVx1NzU2YVx1NTNmN1x1MzA0Y1x1MzA2NFx1MzA1MVx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgTSBcdTg4NGNcdTMwNmZcdTkwNTNcdThkZWZcdTMwNmVcdTYwYzVcdTU4MzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVpICsgMSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgTSkgXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiwgTDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyBCPHN1Yj5pPFwvc3ViPiAmbGU7IE4pIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY2kgXHU3NTZhXHU3NmVlXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDRjXHU4ODU3IEE8c3ViPmk8XC9zdWI+IFx1MzA2OFx1ODg1NyBCPHN1Yj5pPFwvc3ViPiBcdTMwOTJcdTdkNTBcdTMwOTNcdTMwNjdcdTMwNGFcdTMwOGFcdWZmMGNcdTk1NzdcdTMwNTVcdTMwNGMgTDxzdWI+aTxcL3N1Yj4gXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlXHU5MDUzXHU4ZGVmXHUzMDZlXHU0ZTIxXHU3YWVmXHUzMDRjXHU1NDBjXHUzMDU4XHU4ODU3XHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjXHU0ZWZiXHU2MTBmXHUzMDZlIDIgXHUzMDY0XHUzMDZlXHU4ODU3IHAsIHEgXHUzMDZiXHU1YmZlXHUzMDU3XHVmZjBjcCBcdTMwNjggcVx1MzA5Mlx1N2Q1MFx1MzA3Nlx1OTA1M1x1OGRlZlx1MzA2ZiAyIFx1NjcyY1x1NGVlNVx1NGUwYVx1NWI1OFx1NTcyOFx1MzA1N1x1MzA2YVx1MzA0NFx1ZmYwZVx1MzA2OVx1MzA2ZVx1ODg1N1x1MzA0Ylx1MzA4OVx1MzA2OVx1MzA2ZVx1ODg1N1x1MzA3OFx1MzA4Mlx1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA5Mlx1MzA1Zlx1MzA2OVx1MzA2M1x1MzA2Nlx1ODg0Y1x1MzA0Zlx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgSyBcdTg4NGNcdTMwNmZcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTg4NTdcdTMwNmVcdTYwYzVcdTU4MzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVpICsgTSArIDEgXHU4ODRjXHU3NmVlICgxICZsZTsgaSAmbGU7IEspIFx1MzA2Ylx1MzA2ZiAxIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBGPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEY8c3ViPmk8XC9zdWI+ICZsZTsgTikgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHU4ODU3IEY8c3ViPmk8XC9zdWI+IFx1MzA2N1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZUY8c3ViPjE8XC9zdWI+LCAmbWlkZG90OyAmbWlkZG90OyAmbWlkZG90OyAsIEY8c3ViPks8XC9zdWI+IFx1MzA2ZVx1NGUyZFx1MzA2Ylx1NTQwY1x1MzA1OFx1NTAyNFx1MzA0YyAyIFx1NTZkZVx1NGVlNVx1NGUwYVx1NzNmZVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgUSBcdTg4NGNcdTMwNmZcdTMwYWZcdTMwYThcdTMwZWFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVpICsgTSArIEsgKyAxIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBRKSBcdTMwNmJcdTMwNmYgMiBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgUzxzdWI+aTxcL3N1Yj4sIFQ8c3ViPmk8XC9zdWI+ICgxICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyBOLCAxICZsZTsgVDxzdWI+aTxcL3N1Yj4gJmxlOyBOLCBTPHN1Yj5pPFwvc3ViPiAmbmU7IFQ8c3ViPmk8XC9zdWI+KSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmYgaSBcdTc1NmFcdTc2ZWVcdTMwNmVcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmVcdTUxZmFcdTc2N2FcdTMwNTlcdTMwOGJcdTg4NTdcdTMwNGMgUzxzdWI+aTxcL3N1Yj4gXHUzMDY3XHUzMDQyXHUzMDhhXHU4ODRjXHUzMDRkXHUzMDVmXHUzMDQ0XHU4ODU3XHUzMDRjIFQ8c3ViPmk8XC9zdWI+IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1NTIzNlx1OTY1MDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjIgJmxlOyBOICZsZTsgMTAwMDAwICg9IDEwPHN1cD41PFwvc3VwPikgSk9JIFx1NTZmZFx1MzA2ZVx1ODg1N1x1MzA2ZVx1NTAwYlx1NjU3MDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDIwMDAwMCAoPSAyICZ0aW1lczsgMTA8c3VwPjU8XC9zdXA+KSBKT0kgXHU1NmZkXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDZlXHU2NzJjXHU2NTcwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBLICZsZTsgTiBcdTMwNGFcdTc5NmRcdTMwOGFcdTMwNGNcdTk1OGJcdTUwYWNcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTg4NTdcdTMwNmVcdTUwMGJcdTY1NzA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFEgJmxlOyAxMDAwMDAgKD0gMTA8c3VwPjU8XC9zdXA+KSBcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmVcdTUwMGJcdTY1NzA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEw8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMCBpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1OTU3N1x1MzA1NTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MWZhXHU1MjliXHUzMDZiXHVmZjBjXHU1MTY4XHUzMGFmXHUzMGE4XHUzMGVhXHUzMDc4XHUzMDZlXHU3YjU0XHUzMDQ4XHUzMDkyIFEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlXHUzMDU5XHUzMDZhXHUzMDhmXHUzMDYxXHVmZjBjaSBcdTg4NGNcdTc2ZWVcdTMwNmJcdWZmMGNcdTg4NTcgUzxzdWI+aTxcL3N1Yj4gXHUzMDRiXHUzMDg5XHU4ODU3IFQ8c3ViPmk8XC9zdWI+IFx1MzA3OFx1MzA2ZVx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1N2Q0Y1x1OGRlZlx1MzA2ZVx1MzA0Nlx1MzA2MVx1ZmYwY1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA3ZVx1MzA2N1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA0Y1x1NjcwMFx1NTkyN1x1MzA2OFx1MzA2YVx1MzA4Ylx1N2Q0Y1x1OGRlZlx1MzA2ZVx1ZmYwY1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA3ZVx1MzA2N1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD42IFx1MzA2NFx1MzA2ZVx1ODg1N1x1MzA0YyA2IFx1NjcyY1x1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2N1x1N2Q1MFx1MzA3MFx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA2Zlx1ODg1NyAxLCA2IFx1MzA2ZSAyIFx1MzA2NFx1MzA2ZVx1ODg1N1x1MzA2N1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzBhZlx1MzBhOFx1MzBlYVx1MzA2Zlx1NGVlNVx1NGUwYlx1MzA2ZTMgXHUzMDY0XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTMwNjRcdTc2ZWVcdTMwNmVcdTMwYWZcdTMwYThcdTMwZWFcdTMwNmZcdTg4NTcgMyBcdTMwNGJcdTMwODlcdTg4NTcgNCBcdTMwNzhcdTg4NGNcdTMwNGZcdTMwNjhcdTMwNDRcdTMwNDZcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTg4NTcgMiBcdTMwOTJcdTdkNGNcdTc1MzFcdTMwNTlcdTMwOGJcdTdkNGNcdThkZWZcdTMwNjdcdTMwNmZcdTMwNGFcdTc5NmRcdTMwOGFcdTMwN2VcdTMwNjdcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNmYgNVx1ZmYwY1x1ODg1NyA1IFx1MzA5Mlx1N2Q0Y1x1NzUzMVx1MzA1OVx1MzA4Ylx1N2Q0Y1x1OGRlZlx1MzA2N1x1MzA2Zlx1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA3ZVx1MzA2N1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA2ZiA3IFx1MzA2OFx1MzA2YVx1MzA4Ylx1MzA1Zlx1MzA4MVx1ZmYwY1x1N2I1NFx1MzA0OFx1MzA2ZiA3IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4yIFx1MzA2NFx1NzZlZVx1MzA2ZVx1MzBhZlx1MzBhOFx1MzBlYVx1MzA2Zlx1ODg1NyA1IFx1MzA0Ylx1MzA4OVx1ODg1NyAyIFx1MzA3OFx1ODg0Y1x1MzA0Zlx1MzA2OFx1MzA0NFx1MzA0Nlx1MzA4Mlx1MzA2ZVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1ODg1NyAzIFx1MzA2OFx1ODg1NyA0IFx1MzA2ZVx1MzA2OVx1MzA2MVx1MzA4OVx1MzA5Mlx1N2Q0Y1x1NzUzMVx1MzA1N1x1MzA2Nlx1MzA4Mlx1ZmYwY1x1ODg1NyAyIFx1MzA2N1x1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA3ZVx1MzA2N1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA0Y1x1NjcwMFx1NWMwZlx1MzA2OFx1MzA2YVx1MzA4YVx1ZmYwY1x1N2I1NFx1MzA0OFx1MzA2ZiA1IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4zIFx1MzA2NFx1NzZlZVx1MzA2ZVx1MzBhZlx1MzBhOFx1MzBlYVx1MzA2Zlx1ODg1NyAxIFx1MzA0Ylx1MzA4OVx1ODg1NyA0IFx1MzA3OFx1ODg0Y1x1MzA0Zlx1MzA2OFx1MzA0NFx1MzA0Nlx1MzA4Mlx1MzA2ZVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1ODg1NyAxIFx1MzA2Zlx1MzA0YVx1Nzk2ZFx1MzA4YVx1MzA0Y1x1OTU4Ylx1NTBhY1x1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ODg1N1x1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1Zlx1MzA4MVx1ZmYwY1x1N2I1NFx1MzA0OFx1MzA2ZiAwIFx1MzA2OFx1MzA2YVx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczNcL2tpbmcxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjkycHg7IHdpZHRoOjM5MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1NTZmMyAxOiBcdTUxNjVcdTUyOWJcdTRmOGIgMTxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMzXC9raW5nMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgd2lkdGg6Mzc1cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHU1NmYzIDI6IFx1NTE2NVx1NTI5Ylx1NGY4YiAyPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: koosaga