시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 (추가 시간 없음) 1024 MB 35 21 4 26.667%

문제

원형으로 큰 길(순환로)이 뻗어 있고, 길 옆으로 V개의 마을이 자리잡고 있다. 큰 길의 둘레 길이는 정수 L이다. 이 문제에서 큰 길은 0 이상 L-1 이하의 정수가 늘어져 있는 원이고, 각 마을의 위치는 길 상의 정수 좌표로 표현된다. 한 위치에 여러 마을이 있을 수 있다. 좌표가 x, y인 두 마을의 거리는 min(|x - y|, L - |x - y|) 이다. 

우리는 이들 마을이 있는 곳에 우체국을 P개 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에 우체국을 짓게 된다. 우리는 그 때 각 마을과 그 마을과 가장 가까운 우체국 사이의 거리의 합이 최소가 되게 하고 싶다.

각 마을의 위치와 짓고자 하는 우체국 개수를 입력받아서, 각 마을과 그 마을과 가장 가까운 우체국 사이 거리의 합으로 있을 수 있는 최소값을 계산하고, 그런 결과를 낼 수 있도록 각 우체국을 지을 위치를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 세 정수 V, P, L이 주어진다. (1 ≤ P ≤ V ≤ 250 000, 1 ≤ L ≤ 1012

다음 줄에는 각 마을의 위치를 나타내는 V개의 정수 좌표가 나온다. 좌표는 비내림차순으로 정렬되어 있다. 각 좌표의 범위는 0 이상 L-1 이하이다.

출력

첫째 줄에는, 각 마을과 거기서 가장 가까운 우체국 사이 거리들의 합의 최소값을 나타내는 정수 S를 출력한다.

다음 줄에는, 우체국을 지을 마을들을 골라, 그 마을의 위치를 나타내는 P개의 정수를 비내림차순으로 출력한다.

예제 입력 1

10 5 200
1 2 3 6 7 9 11 22 44 50

예제 출력 1

9
2 7 22 44 50

예제 입력 2

10 5 51
1 2 3 6 7 9 11 22 44 50

예제 출력 2

8
1 6 9 22 44
W3sicHJvYmxlbV9pZCI6IjE4NDQ2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmIwXHVjY2I0XHVhZDZkIDUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMFx1ZDYxNVx1YzczY1x1Yjg1YyBcdWQwNzAgXHVhZTM4KFx1YzIxY1x1ZDY1OFx1Yjg1YylcdWM3NzQgXHViZWQ3XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHVhZTM4IFx1YzYwNlx1YzczY1x1Yjg1YyBWXHVhYzFjXHVjNzU4IFx1YjljOFx1Yzc0NFx1Yzc3NCBcdWM3OTBcdWI5YWNcdWM3YTFcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQwNzAgXHVhZTM4XHVjNzU4IFx1YjQ1OFx1YjgwOCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjODE1XHVjMjE4IExcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVkMDcwIFx1YWUzOFx1Yzc0MCAwIFx1Yzc3NFx1YzBjMSBMLTEgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWIyOThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YzZkMFx1Yzc3NFx1YWNlMCwgXHVhYzAxIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVhZTM4IFx1YzBjMVx1Yzc1OCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC4gXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHVjNzQ0XHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwO1x1Yzg4Y1x1ZDQ1Y1x1YWMwMCB4LCB5XHVjNzc4IFx1YjQ1MCBcdWI5YzhcdWM3NDRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IG1pbih8eCAtIHl8LCBMIC0gfHggLSB5fCkgXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0XHViNGU0IFx1YjljOFx1Yzc0NFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNWQwIFx1YzZiMFx1Y2NiNFx1YWQ2ZFx1Yzc0NCBQXHVhYzFjIFx1YzljMFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWJhYThcdWI0ZTAgXHViOWM4XHVjNzQ0XHViOWM4XHViMmU0IFx1YjJlNCBcdWM5ZDNcdWIyOTQgXHVhYzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjODA0XHVjY2I0IFx1YjljOFx1Yzc0NCBcdWM5MTEgXHViYTg3IFx1YWNmM1x1Yzc0NCBcdWFjZThcdWI3N2MsIFx1YWRmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNmIwXHVjY2I0XHVhZDZkXHVjNzQ0IFx1YzlkM1x1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWFkZjggXHViNTRjIFx1YWMwMSBcdWI5YzhcdWM3NDRcdWFjZmMgXHVhZGY4IFx1YjljOFx1Yzc0NFx1YWNmYyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YzZiMFx1Y2NiNFx1YWQ2ZCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWI5YzhcdWM3NDRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzlkM1x1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHVjNmIwXHVjY2I0XHVhZDZkIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDRcdWMxMWMsIFx1YWMwMSBcdWI5YzhcdWM3NDRcdWFjZmMgXHVhZGY4IFx1YjljOFx1Yzc0NFx1YWNmYyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YzZiMFx1Y2NiNFx1YWQ2ZCBcdWMwYWNcdWM3NzQgXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI3ZjAgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YjBiYyBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YWMwMSBcdWM2YjBcdWNjYjRcdWFkNmRcdWM3NDQgXHVjOWMwXHVjNzQ0IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBWLCBQLCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQICZsZTsgViAmbGU7IDI1MCAwMDAsIDEgJmxlOyBMICZsZTsgMTA8c3VwPjEyPFwvc3VwPikmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YjA5OFx1YzYyOFx1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IFx1YmU0NFx1YjBiNFx1YjliY1x1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjODhjXHVkNDVjXHVjNzU4IFx1YmM5NFx1YzcwNFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSBMLTEgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1YWMwMSBcdWI5YzhcdWM3NDRcdWFjZmMgXHVhYzcwXHVhZTMwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjNmIwXHVjY2I0XHVhZDZkIFx1YzBhY1x1Yzc3NCBcdWFjNzBcdWI5YWNcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0LCBcdWM2YjBcdWNjYjRcdWFkNmRcdWM3NDQgXHVjOWMwXHVjNzQ0IFx1YjljOFx1Yzc0NFx1YjRlNFx1Yzc0NCBcdWFjZThcdWI3N2MsIFx1YWRmOCBcdWI5YzhcdWM3NDRcdWM3NTgmbmJzcDtcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1YmU0NFx1YjBiNFx1YjliY1x1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTg0NDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJT0kgUHJvYmxlbSBSZXZpc2VkIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSB3YXMgYW4gSU9JIHByb2JsZW0gNjEwMiB5ZWFycyBhZ286PFwvcD5cclxuXHJcbjxwPjxlbT5UaGVyZSBpcyBhIHN0cmFpZ2h0IGhpZ2h3YXkgd2l0aCB2aWxsYWdlcyBhbG9uZ3NpZGUgdGhlIGhpZ2h3YXkuIFRoZSBoaWdod2F5IGlzIHJlcHJlc2VudGVkIGFzIGFuIGludGVnZXIgYXhpcywgYW5kIHRoZSBwb3NpdGlvbiBvZiBlYWNoIHZpbGxhZ2UgaXMgaWRlbnRpZmllZCB3aXRoIGEgJm5ic3A7c2luZ2xlIGludGVnZXIgY29vcmRpbmF0ZS4gVGhlcmUgYXJlIG5vIHR3byB2aWxsYWdlcyBpbiB0aGUgc2FtZSBwb3NpdGlvbi4gVGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHBvc2l0aW9ucyBpcyB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlaXIgaW50ZWdlciBjb29yZGluYXRlcy48XC9lbT48XC9wPlxyXG5cclxuPHA+PGVtPlBvc3Qgb2ZmaWNlcyB3aWxsIGJlIGJ1aWx0IGluIHNvbWUsIGJ1dCBub3QgbmVjZXNzYXJpbHkgYWxsIG9mIHRoZSB2aWxsYWdlcy4gQSB2aWxsYWdlIGFuZCB0aGUgcG9zdCBvZmZpY2UgaW4gaXQgaGF2ZSB0aGUgc2FtZSBwb3NpdGlvbi4gRm9yIGJ1aWxkaW5nIHRoZSBwb3N0IG9mZmljZXMsICZuYnNwO3RoZWlyIHBvc2l0aW9ucyBzaG91bGQgYmUgY2hvc2VuIHNvIHRoYXQgdGhlIHRvdGFsIHN1bSBvZiBhbGwgZGlzdGFuY2VzIGJldHdlZW4gZWFjaCB2aWxsYWdlIGFuZCBpdHMgbmVhcmVzdCBwb3N0IG9mZmljZSBpcyBtaW5pbXVtLjxcL2VtPjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGlzIHByb2JsZW0gaXMgdG9vIHNpbXBsZSBmb3IgYW4gSUNQQyBjb250ZXN0IGluIHRoZSB5ZWFyIDgxMDIuIFlvdSBhcmUgc3VwcG9zZWQgdG8gc29sdmUgYSBoYXJkZXIgdmVyc2lvbi48XC9wPlxyXG5cclxuPHA+VGhlcmUgaXMgYSA8c3Ryb25nPmNpcmN1bGFyPFwvc3Ryb25nPiZuYnNwO2hpZ2h3YXkgd2l0aCBsZW5ndGggJEwkLiBUaGVyZSBhcmUgJG4kIHZpbGxhZ2VzIGFsb25nc2lkZSB0aGUgaGlnaHdheS4gVGhlIHBvc2l0aW9uIG9mIGVhY2ggdmlsbGFnZSBpcyBpZGVudGlmaWVkIHdpdGggYSBzaW5nbGUgaW50ZWdlciBjb29yZGluYXRlLiBUaGVyZSA8c3Ryb25nPmNhbiBiZTxcL3N0cm9uZz4mbmJzcDt0d28gb3IgbW9yZSB2aWxsYWdlcyBpbiB0aGUgc2FtZSBwb3NpdGlvbi4gVGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHBvc2l0aW9ucyBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGFsb25nIHRoZSBoaWdod2F5LiBJZiB0aGVyZSBhcmUgdHdvIHZpbGxhZ2VzIHdpdGggY29vcmRpbmF0ZXMgJGEkIGFuZCAkYiQsIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZW0gaXMgJFxcbWluKHxhIC0gYnwsIEwgLSB8YSAtIGJ8KSQuPFwvcD5cclxuXHJcbjxwPllvdSB3YW50IHRvIGJ1aWxkICRrJCBwb3N0IG9mZmljZXMgb24gdGhlIGhpZ2h3YXkgYW5kIG1pbmltaXplIHRoZSB0b3RhbCBzdW0gb2YgYWxsIGRpc3RhbmNlcyBiZXR3ZWVuIGVhY2ggdmlsbGFnZSBhbmQgaXRzIG5lYXJlc3QgcG9zdCBvZmZpY2UuIEVhY2ggcG9zdCBvZmZpY2UgaGFzIHRvIGJlIHBsYWNlZCBhdCBhbiBpbnRlZ2VyIGNvb3JkaW5hdGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyAkbiQsICRrJCwgYW5kICRMJCAoJDEgXFxsZXEgbiBcXGxlcSAyIFxcY2RvdCAxMF41JCwgJDEgXFxsZXEgayBcXGxlcSBuJCwgJDEgXFxsZXEgTCBcXGxlcSAxMF57MTJ9JCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkbiQgaW50ZWdlcnMgJGFfMSwgYV8yLCBcXGxkb3RzLCBhX24kICgkMCBcXGxlcSBhXzEgXFxsZXEgYV8yIFxcbGVxIFxcbGRvdHMgXFxsZXEgYV9uICZsdDsgTCQpIGluZGljYXRpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHZpbGxhZ2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCBvdXRwdXQgdGhlIGFuc3dlci4gT24gdGhlIHNlY29uZCBsaW5lLCBvdXRwdXQgJGskIGludGVnZXJzICRjXzEsIGNfMiwgXFxsZG90cywgY19rJCAoJDAgXFxsZXEgY19pICZsdDsgTCQsICRjX2kgXFxsZXEgY197aSArIDF9JCkgaW5kaWNhdGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBvc3Qgb2ZmaWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=