Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Heaven Tour

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe story was not finished as PMP thought. God offered him one more chance to reincarnate and come back to life. But before he can come back, God told him that PMP should ask *n* great men including prominent programmers about their life experiences.

The men are standing on a straight line. They are numbered 1 through *n* from left to right. The coordinate of the *i*-th man is *x*_{i} (*x*_{i} < *x*_{i + 1}, *i* < *n*). PMP should visit all these people one by one in arbitrary order. Each men should be visited exactly once. At the beginning of his tour, he starts at location of *s*-th man and asks him about his experiences.

Each time PMP wants to change his location, he should give a ticket to an angel and the angel carries him to his destination. Angels take PMP from one location, fly to his destination and put him down there. Nobody else is visited in this movement. Moving from *i*-th man to *j*-th man, takes |*x*_{i} - *x*_{j}| time. PMP can get back to life as soon as he visits all men.

There are two types of angels: Some angels are going to the right and they only accept right tickets. Others are going the left and they only accept left tickets. There are an unlimited number of angels of each type. PMP has *l* left tickets and *n* - 1 - *l* right tickets.

PMP wants to get back to life as soon as possible to be able to compete in this year's final instead of the final he missed last year. He wants to know the quickest way to visit all the men exactly once. He also needs to know the exact sequence moves he should make.

Input

The first line of input contains three space-separated integers *n*, *l*, *s* (2 ≤ *n* ≤ 10^{5}, 0 ≤ *l* < *n*, 1 ≤ *s* ≤ *n*) — the number of people to visit, the number left tickets PMP got, and initial location of PMP. Next line contains *n* space-separated integers. The *i*-th integer in this line is *x*_{i} (0 = *x*_{1} < *x*_{2} < ... < *x*_{n} ≤ 10^{9}) — the location of *i*-th man.

Output

If PMP cannot visit all men with the tickets he got print -1 in the only line of output. Otherwise, in the first line you should print the minimum time PMP can visit all men. In the second line you should print *n* - 1 integers that are the numbers of the men that PMP should visit in order in one optimal solution. If there are multiple answers, output any of them.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples

Input

5 2 2

0 10 11 21 22

Output

33

1 3 5 4

Input

4 3 1

0 1 2 3

Output

-1

Input

7 3 2

0 100 200 201 301 303 305

Output

409

1 3 4 7 6 5

Note

Let us remind here, a great contestant of all times, who left us about a year ago. May Renat Mullakhanov rest in peace.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 15:03:41 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|