Problem Background

Updated on 2024/5/12: Two additional hack data sets were added, located at Subtask #5, #31 and #32.

Updated on 2024/5/13: Due to significant controversy, the difficulty has been reduced to green. No further changes to the difficulty of this problem are currently considered.

Problem Description

For this competition, to ensure contestants can easily complete the check-in task, there are $n$ check-in points set up. You and these points are all on a straight highway, which we can consider as a number line. You are currently at the origin (coordinate $0$), and the $i$-th check-in point is at coordinate $x_i$. You can move at most 1 unit length per time unit.

You need to visit as many check-in points as possible and return to the origin within $m$ time units. The time taken to check in can be ignored, and you can instantly check in at multiple different check-in points at the same location.

To make checking in more convenient and smooth for contestants, a check-in gift is placed at the $p$-th check-in point. If you check in here, the time limit to return to the origin can be extended to $m+5$ time units. Note: You can receive the gift after the $m$-th time unit, but you must return to the origin before the $m+5$-th time unit.

Determine the maximum number of different check-in points you can visit, and under this premise, minimize the lexicographical order of the set of checked-in point indices (if there are multiple solutions, output any one).

Note: The lexicographical order of a set is equivalent to the lexicographical order of the sequence obtained by sorting the elements of the set in ascending order.

Input Format

The first line contains three integers $n, m, p$.

The second line contains $n$ integers, where the $i$-th integer represents $x_i$.

Output Format

The first line contains an integer $ans$, representing the maximum number of check-in points you can visit.

The second line contains $ans$ positive integers, representing the sequence of check-in points to visit.

This problem uses a Special Judge. If there are multiple solutions, output any one.

Sample Input and Output

Sample Input #1

3 11 3
1 -3 4

Sample Output #1

3
1 2 3

Sample Input #2

5 15 3
-5 -10 0 5 10

Sample Output #2

3
2 1 3

Notes

Sample #1 Explanation

It is obvious that you can visit all check-in points. Output any action plan that takes no more than 16 time units.

Sample #2 Explanation

There are 3 different choices to visit 3 check-in points: $1$ $2$ $3$, $1$ $3$ $4$, $3$ $4$ $5$. Clearly, the first choice is the best. Any of the following action plans are acceptable: $1$ $2$ $3$, $2$ $1$ $3$, $3$ $1$ $2$, $3$ $2$ $1$.

Data Size and Constraints

This problem uses bundled testing.

This problem uses a Special Judge.

Please be aware of the impact of large data input and output on program efficiency.

The time limit for this problem is sufficiently long.

For $100\%$ of the data, $1 \leq p \leq n \leq 10^6$, $0 \leq m \leq 10^{18}$, $-10^{18} \leq x_i \leq 10^{18}$.

见题面 Input 部分

见题面 Output 部分