Problem Background

• Original Problem: P5617 [MtOI2019] Invisible Boundary Line

Note: Information about the SPJ and data for this problem

If you encounter issues such as precision errors or data problems, please contact the problem setter.

Problem Description

There are $n$ circles with radius $r$ drawn on a paper ring of length $L$.

All the centers of the circles are at the same height and can be considered as points on a number line that is wrapped around the paper ring.

If you cannot understand the distribution of circles on the paper ring, refer to the sample explanation and subproblems.

You are required to select $k$ circles such that the union area of these circles is maximized.

Note that you need to provide the exact selection scheme, not just the maximum union area.

Input Format

The first line contains four integers $n, k, r, L$, as described in the problem.

The second line contains $n$ integers, where the $i$-th integer $p[i]$ describes the position of the $i$-th circle's center on the paper ring (coordinate on the number line).

For $2 < i < n$, $p[i-1] < p[i]$.

Output Format

One line containing $k$ integers, representing the indices of the selected circles, which will be used by the SPJ to calculate the union area.

You need to ensure that these indices are strictly increasing and within the range $[1, n]$, otherwise, it will be considered invalid and you will not receive any points.

The answer is considered correct if the relative error is within $10^{-9}$ and the absolute error is within $0.1$.

The answer is estimated to be no more than $10^{12}$ in magnitude.

Sample Input and Output

Input Sample #1

5 3 10 30
0 7 14 21 28

Output Sample #1

2 3 5

Input Sample #2

10 3 10 65
0 7 15 24 30 36 41 49 57 63

Output Sample #2

3 6 9

Input Sample #3

30 10 50 169
0 7 14 21 28 35 42 45 51 55 61 65 68 75 79 83 87 94 97 105 113 118 126 133 140 147 151 156 163 167

Output Sample #3

3 5 8 11 15 19 21 24 27 30

Notes

Sample Explanation:

• Sample 1: The final union area is approximately $565.871835$.

The distribution of circles is shown in the figure, where $⊙A$ and $⊙A2$ are the same circle, and $⊙B$ and $⊙B2$ are the same circle.

It can be considered as a rightward translation by $L=30$ units, essentially wrapping around the paper ring back to the starting point.

Since they are the same circle, the area covered by the red part should not be counted twice, and the maximum union area is the area of the blue part.

• Sample 2: The final union area is approximately $942.477796$.

• Sample 3: The final union area is approximately $16817.058547$.

Data Range and Constraints:

The time limit is more than twice the time taken by the std.

For all data, $n \leq 10^5$, $10 \leq r \leq 2000$, $0 \leq p[i] < L \leq 10^8$, $4r < L$, $3 \leq k \leq n$.

All values in the table are upper bounds. Note that some lower bound constraints may help eliminate certain edge cases in the problem.

见题面 Input 部分

见题面 Output 部分