Post Office 5

A circular road runs around a loop of length L, and V villages lie along it. Here the road is a circle of integers from 0 to L-1, and each village's position is an integer coordinate on the road. Several villages may share the same position. The distance between two villages at coordinates x and y is $\min(|x - y|, L - |x - y|)$.

You want to build P post offices at village locations. Not every village gets one. Choose P of the V villages and build a post office at each chosen position. The goal is to minimize the sum, over all villages, of the distance from each village to its nearest post office.

Given the village positions and the number of post offices, compute the minimum possible value of that sum, and print the positions where the post offices should be built to reach it.

The first line contains three integers V, P, and L. ($1 \le P \le V \le 250\,000$, $1 \le L \le 10^{12}$)

The next line contains V integer coordinates, one for each village, in non-decreasing order. Each coordinate is between 0 and L-1, inclusive.

On the first line, print S, the minimum possible sum of distances from each village to its nearest post office.

On the next line, print P integers in non-decreasing order: the positions of the villages where the post offices are built.