#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 423456;
const ll inf = 1ll << 60;
struct info {
ll value;
int cnt;
int pre;
info(ll value = 0, int cnt = 0, int pre = 0): value(value), cnt(cnt), pre(pre) {
}
} dpl[N], dpr[N];
ll len, ans, a[N], f[2][N], sum[N];
pair<int, int> ql[N], qr[N];
int n, m, pos[N], pre[2][N];
vector<int> pl, pr, pans;
ll get(int l, int r) {
int mid = l + r + 1 >> 1;
return (mid - l) * a[mid] - (sum[mid] - sum[l]) + (sum[r] - sum[mid]) - (r - mid) * a[mid];
}
void solve(ll cost) {
int qlh = 1, qlt = 1;
int qrh = 1, qrt = 1;
ql[1] = qr[1] = make_pair(1, 0);
auto go = [&](info* dp, int from, int to, int diff) {
return make_pair(dp[from].value + get(from, to) + cost, dp[from].cnt + diff);
};
auto trans = [&](info* dp, pair<int, int>* q, int &h, int &t, int i, int c) {
pair<ll, int> w = go(dp, q[h].second, i, c);
dp[i] = info(w.first, w.second, q[h].second);
if (i == n) {
return;
}
++q[h].first;
if (h < t && q[h].first == q[h + 1].first) {
++h;
}
while (h <= t && go(dp, i, q[t].first, c) <= go(dp, q[t].second, q[t].first, c)) {
--t;
}
if (h > t) {
q[++t] = make_pair(i + 1, i);
} else {
if (go(dp, i, n, c) <= go(dp, q[t].second, n, c)) {
int low = q[t].first, high = n;
while (low < high) {
int mid = low + high >> 1;
if (go(dp, i, mid, c) <= go(dp, q[t].second, mid, c)) {
high = mid;
} else {
low = mid + 1;
}
}
q[++t] = make_pair(high, i);
}
}
};
for (int i = 1; i <= n; ++i) {
trans(dpl, ql, qlh, qlt, i, 1);
trans(dpr, qr, qrh, qrt, i, -1);
}
}
ll solve() {
ll l = 0, r = inf;
while (true) {
ll mid = l + r >> 1;
solve(mid);
if (dpl[n].cnt <= m && -dpr[n].cnt >= m) {
vector<int> posl(dpl[n].cnt + 1);
for (int i = n, j = dpl[i].cnt; ~j; i = dpl[i].pre, --j) {
posl[j] = i;
}
vector<int> posr(-dpr[n].cnt + 1);
for (int i = n, j = -dpr[i].cnt; ~j; i = dpr[i].pre, --j) {
posr[j] = i;
}
for (int i = 0, j = -dpr[n].cnt - m; i < dpl[n].cnt; ++i, ++j) {
pos[i] = posl[i];
if (posl[i] <= posr[j] && posl[i + 1] >= posr[j + 1]) {
while (i + 1 <= m) {
pos[++i] = posr[++j];
}
return dpl[n].value - mid * m;
}
}
} else if (dpl[n].cnt > m) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
void work(int cur, int l, int r, int ql, int qr) {
if (l > r) {
return;
}
int mid = l + r >> 1;
f[cur][mid] = inf;
for (int i = ql; i <= qr; ++i) {
if (f[cur][mid] > f[!cur][i] + get(i, mid)) {
f[cur][mid] = f[!cur][i] + get(i, mid);
pre[cur][mid] = i;
}
}
work(cur, l, mid - 1, ql, pre[cur][mid]);
work(cur, mid + 1, r, pre[cur][mid], qr);
}
ll dp(int s) {
f[0][s] = 0;
int gl = s, gr = s;
for (int i = 1; i <= m; ++i) {
work(i & 1, pl[i], pr[i], gl, gr);
gl = pl[i];
gr = pr[i];
}
for (int i = m, j = s + n; ~i; j = pre[i & 1][j], --i) {
pos[i] = j;
}
return f[m & 1][s + n];
}
void divide(int l, int r) {
if (l > r) {
return;
}
vector<int> fl = pl, fr = pr;
int mid = l + r >> 1;
ll w = dp(mid);
if (w < ans) {
ans = w;
pans = vector<int>(pos, pos + m + 1);
}
vector<int> fd = vector<int>(pos, pos + m + 1);
pl = fl;
pr = fd;
divide(l, mid - 1);
pl = fd;
pr = fr;
divide(mid + 1, r);
pl = fl;
pr = fr;
}
int main() {
#ifdef wxh010910
freopen("input.txt", "r", stdin);
#endif
scanf("%d %d %lld", &n, &m, &len);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
a[i + n] = a[i] + len;
}
for (int i = 1; i <= n * 2; ++i) {
sum[i] = sum[i - 1] + a[i];
}
ans = solve();
int p = 1;
for (int i = 1; i <= m; ++i) {
if (pos[i] - pos[i - 1] < pos[p] - pos[p - 1]) {
p = i;
}
}
for (int i = p; i <= m; ++i) {
pl.push_back(pos[i - 1]);
pr.push_back(pos[i]);
}
for (int i = 1; i <= p; ++i) {
pl.push_back(pos[i - 1] + n);
pr.push_back(pos[i] + n);
}
pans = vector<int>(pos, pos + m + 1);
divide(pl[0], pr[0]);
printf("%lld\n", ans);
vector<ll> res(m);
for (int i = 0; i < m; ++i) {
res[i] = (a[pans[i] + pans[i + 1] + 1 >> 1]) % len;
}
sort(res.begin(), res.end());
for (int i = 0; i < m; ++i) {
printf("%lld%c", res[i], i == m - 1 ? '\n' : ' ');
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7Cgpjb25zdCBpbnQgTiA9IDQyMzQ1NjsKY29uc3QgbGwgaW5mID0gMWxsIDw8IDYwOwoKc3RydWN0IGluZm8gewogIGxsIHZhbHVlOwogIGludCBjbnQ7CiAgaW50IHByZTsKCiAgaW5mbyhsbCB2YWx1ZSA9IDAsIGludCBjbnQgPSAwLCBpbnQgcHJlID0gMCk6IHZhbHVlKHZhbHVlKSwgY250KGNudCksIHByZShwcmUpIHsKICB9Cn0gZHBsW05dLCBkcHJbTl07CgpsbCBsZW4sIGFucywgYVtOXSwgZlsyXVtOXSwgc3VtW05dOwpwYWlyPGludCwgaW50PiBxbFtOXSwgcXJbTl07CmludCBuLCBtLCBwb3NbTl0sIHByZVsyXVtOXTsKdmVjdG9yPGludD4gcGwsIHByLCBwYW5zOwoKbGwgZ2V0KGludCBsLCBpbnQgcikgewogIGludCBtaWQgPSBsICsgciArIDEgPj4gMTsKICByZXR1cm4gKG1pZCAtIGwpICogYVttaWRdIC0gKHN1bVttaWRdIC0gc3VtW2xdKSArIChzdW1bcl0gLSBzdW1bbWlkXSkgLSAociAtIG1pZCkgKiBhW21pZF07Cn0KCnZvaWQgc29sdmUobGwgY29zdCkgewogIGludCBxbGggPSAxLCBxbHQgPSAxOwogIGludCBxcmggPSAxLCBxcnQgPSAxOwogIHFsWzFdID0gcXJbMV0gPSBtYWtlX3BhaXIoMSwgMCk7CiAgYXV0byBnbyA9IFsmXShpbmZvKiBkcCwgaW50IGZyb20sIGludCB0bywgaW50IGRpZmYpIHsKICAgIHJldHVybiBtYWtlX3BhaXIoZHBbZnJvbV0udmFsdWUgKyBnZXQoZnJvbSwgdG8pICsgY29zdCwgZHBbZnJvbV0uY250ICsgZGlmZik7CiAgfTsKICBhdXRvIHRyYW5zID0gWyZdKGluZm8qIGRwLCBwYWlyPGludCwgaW50PiogcSwgaW50ICZoLCBpbnQgJnQsIGludCBpLCBpbnQgYykgewogICAgcGFpcjxsbCwgaW50PiB3ID0gZ28oZHAsIHFbaF0uc2Vjb25kLCBpLCBjKTsKICAgIGRwW2ldID0gaW5mbyh3LmZpcnN0LCB3LnNlY29uZCwgcVtoXS5zZWNvbmQpOwogICAgaWYgKGkgPT0gbikgewogICAgICByZXR1cm47CiAgICB9CiAgICArK3FbaF0uZmlyc3Q7CiAgICBpZiAoaCA8IHQgJiYgcVtoXS5maXJzdCA9PSBxW2ggKyAxXS5maXJzdCkgewogICAgICArK2g7CiAgICB9CiAgICB3aGlsZSAoaCA8PSB0ICYmIGdvKGRwLCBpLCBxW3RdLmZpcnN0LCBjKSA8PSBnbyhkcCwgcVt0XS5zZWNvbmQsIHFbdF0uZmlyc3QsIGMpKSB7CiAgICAgIC0tdDsKICAgIH0KICAgIGlmIChoID4gdCkgewogICAgICBxWysrdF0gPSBtYWtlX3BhaXIoaSArIDEsIGkpOwogICAgfSBlbHNlIHsKICAgICAgaWYgKGdvKGRwLCBpLCBuLCBjKSA8PSBnbyhkcCwgcVt0XS5zZWNvbmQsIG4sIGMpKSB7CiAgICAgICAgaW50IGxvdyA9IHFbdF0uZmlyc3QsIGhpZ2ggPSBuOwogICAgICAgIHdoaWxlIChsb3cgPCBoaWdoKSB7CiAgICAgICAgICBpbnQgbWlkID0gbG93ICsgaGlnaCA+PiAxOwogICAgICAgICAgaWYgKGdvKGRwLCBpLCBtaWQsIGMpIDw9IGdvKGRwLCBxW3RdLnNlY29uZCwgbWlkLCBjKSkgewogICAgICAgICAgICBoaWdoID0gbWlkOwogICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgbG93ID0gbWlkICsgMTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcVsrK3RdID0gbWFrZV9wYWlyKGhpZ2gsIGkpOwogICAgICB9CiAgICB9CiAgfTsKICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgIHRyYW5zKGRwbCwgcWwsIHFsaCwgcWx0LCBpLCAxKTsKICAgIHRyYW5zKGRwciwgcXIsIHFyaCwgcXJ0LCBpLCAtMSk7CiAgfQp9CgpsbCBzb2x2ZSgpIHsKICBsbCBsID0gMCwgciA9IGluZjsKICB3aGlsZSAodHJ1ZSkgewogICAgbGwgbWlkID0gbCArIHIgPj4gMTsKICAgIHNvbHZlKG1pZCk7CiAgICBpZiAoZHBsW25dLmNudCA8PSBtICYmIC1kcHJbbl0uY250ID49IG0pIHsKICAgICAgdmVjdG9yPGludD4gcG9zbChkcGxbbl0uY250ICsgMSk7CiAgICAgIGZvciAoaW50IGkgPSBuLCBqID0gZHBsW2ldLmNudDsgfmo7IGkgPSBkcGxbaV0ucHJlLCAtLWopIHsKICAgICAgICBwb3NsW2pdID0gaTsKICAgICAgfQogICAgICB2ZWN0b3I8aW50PiBwb3NyKC1kcHJbbl0uY250ICsgMSk7CiAgICAgIGZvciAoaW50IGkgPSBuLCBqID0gLWRwcltpXS5jbnQ7IH5qOyBpID0gZHByW2ldLnByZSwgLS1qKSB7CiAgICAgICAgcG9zcltqXSA9IGk7CiAgICAgIH0KICAgICAgZm9yIChpbnQgaSA9IDAsIGogPSAtZHByW25dLmNudCAtIG07IGkgPCBkcGxbbl0uY250OyArK2ksICsraikgewogICAgICAgIHBvc1tpXSA9IHBvc2xbaV07CiAgICAgICAgaWYgKHBvc2xbaV0gPD0gcG9zcltqXSAmJiBwb3NsW2kgKyAxXSA+PSBwb3NyW2ogKyAxXSkgewogICAgICAgICAgd2hpbGUgKGkgKyAxIDw9IG0pIHsKICAgICAgICAgICAgcG9zWysraV0gPSBwb3NyWysral07CiAgICAgICAgICB9CiAgICAgICAgICByZXR1cm4gZHBsW25dLnZhbHVlIC0gbWlkICogbTsKICAgICAgICB9CiAgICAgIH0KICAgIH0gZWxzZSBpZiAoZHBsW25dLmNudCA+IG0pIHsKICAgICAgbCA9IG1pZCArIDE7CiAgICB9IGVsc2UgewogICAgICByID0gbWlkIC0gMTsKICAgIH0KICB9Cn0KCnZvaWQgd29yayhpbnQgY3VyLCBpbnQgbCwgaW50IHIsIGludCBxbCwgaW50IHFyKSB7CiAgaWYgKGwgPiByKSB7CiAgICByZXR1cm47CiAgfQogIGludCBtaWQgPSBsICsgciA+PiAxOwogIGZbY3VyXVttaWRdID0gaW5mOwogIGZvciAoaW50IGkgPSBxbDsgaSA8PSBxcjsgKytpKSB7CiAgICBpZiAoZltjdXJdW21pZF0gPiBmWyFjdXJdW2ldICsgZ2V0KGksIG1pZCkpIHsKICAgICAgZltjdXJdW21pZF0gPSBmWyFjdXJdW2ldICsgZ2V0KGksIG1pZCk7CiAgICAgIHByZVtjdXJdW21pZF0gPSBpOwogICAgfQogIH0KICB3b3JrKGN1ciwgbCwgbWlkIC0gMSwgcWwsIHByZVtjdXJdW21pZF0pOwogIHdvcmsoY3VyLCBtaWQgKyAxLCByLCBwcmVbY3VyXVttaWRdLCBxcik7Cn0KCmxsIGRwKGludCBzKSB7CiAgZlswXVtzXSA9IDA7CiAgaW50IGdsID0gcywgZ3IgPSBzOwogIGZvciAoaW50IGkgPSAxOyBpIDw9IG07ICsraSkgewogICAgd29yayhpICYgMSwgcGxbaV0sIHByW2ldLCBnbCwgZ3IpOwogICAgZ2wgPSBwbFtpXTsKICAgIGdyID0gcHJbaV07CiAgfQogIGZvciAoaW50IGkgPSBtLCBqID0gcyArIG47IH5pOyBqID0gcHJlW2kgJiAxXVtqXSwgLS1pKSB7CiAgICBwb3NbaV0gPSBqOwogIH0KICByZXR1cm4gZlttICYgMV1bcyArIG5dOwp9Cgp2b2lkIGRpdmlkZShpbnQgbCwgaW50IHIpIHsKICBpZiAobCA+IHIpIHsKICAgIHJldHVybjsKICB9CiAgdmVjdG9yPGludD4gZmwgPSBwbCwgZnIgPSBwcjsKICBpbnQgbWlkID0gbCArIHIgPj4gMTsKICBsbCB3ID0gZHAobWlkKTsKICBpZiAodyA8IGFucykgewogICAgYW5zID0gdzsKICAgIHBhbnMgPSB2ZWN0b3I8aW50Pihwb3MsIHBvcyArIG0gKyAxKTsKICB9CiAgdmVjdG9yPGludD4gZmQgPSB2ZWN0b3I8aW50Pihwb3MsIHBvcyArIG0gKyAxKTsKICBwbCA9IGZsOwogIHByID0gZmQ7CiAgZGl2aWRlKGwsIG1pZCAtIDEpOwogIHBsID0gZmQ7CiAgcHIgPSBmcjsKICBkaXZpZGUobWlkICsgMSwgcik7CiAgcGwgPSBmbDsKICBwciA9IGZyOwp9CgppbnQgbWFpbigpIHsKI2lmZGVmIHd4aDAxMDkxMAogIGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwojZW5kaWYKICBzY2FuZigiJWQgJWQgJWxsZCIsICZuLCAmbSwgJmxlbik7CiAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICBzY2FuZigiJWxsZCIsICZhW2ldKTsKICAgIGFbaSArIG5dID0gYVtpXSArIGxlbjsKICB9CiAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbiAqIDI7ICsraSkgewogICAgc3VtW2ldID0gc3VtW2kgLSAxXSArIGFbaV07CiAgfQogIGFucyA9IHNvbHZlKCk7CiAgaW50IHAgPSAxOwogIGZvciAoaW50IGkgPSAxOyBpIDw9IG07ICsraSkgewogICAgaWYgKHBvc1tpXSAtIHBvc1tpIC0gMV0gPCBwb3NbcF0gLSBwb3NbcCAtIDFdKSB7CiAgICAgIHAgPSBpOwogICAgfQogIH0KICBmb3IgKGludCBpID0gcDsgaSA8PSBtOyArK2kpIHsKICAgIHBsLnB1c2hfYmFjayhwb3NbaSAtIDFdKTsKICAgIHByLnB1c2hfYmFjayhwb3NbaV0pOwogIH0KICBmb3IgKGludCBpID0gMTsgaSA8PSBwOyArK2kpIHsKICAgIHBsLnB1c2hfYmFjayhwb3NbaSAtIDFdICsgbik7CiAgICBwci5wdXNoX2JhY2socG9zW2ldICsgbik7CiAgfQogIHBhbnMgPSB2ZWN0b3I8aW50Pihwb3MsIHBvcyArIG0gKyAxKTsKICBkaXZpZGUocGxbMF0sIHByWzBdKTsKICBwcmludGYoIiVsbGRcbiIsIGFucyk7CiAgdmVjdG9yPGxsPiByZXMobSk7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpIHsKICAgIHJlc1tpXSA9IChhW3BhbnNbaV0gKyBwYW5zW2kgKyAxXSArIDEgPj4gMV0pICUgbGVuOwogIH0KICBzb3J0KHJlcy5iZWdpbigpLCByZXMuZW5kKCkpOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CiAgICBwcmludGYoIiVsbGQlYyIsIHJlc1tpXSwgaSA9PSBtIC0gMSA/ICdcbicgOiAnICcpOwogIH0KICByZXR1cm4gMDsKfQo=