Maximizing the Union Area of Circles on a Ring

You are given (n) circles, each with radius (r), drawn on a circular strip (a paper ring) of circumference (L). The center of each circle is specified by a point on a number line that is wrapped into a circle (i.e. the endpoints of the line are identified). All circle centers lie on the same horizontal line. When a circle is drawn, its center is at the given coordinate (modulo (L)) and the circle extends (r) units to the left and right. Two circles overlapping results in a smaller area for their union. It can be proved that if no two chosen circles overlap (i.e. the circular distance between every two chosen centers is at least (2r)), then the union area attains its maximum value of (k\pi r^2).

Your task is to choose exactly (k) circles (by their given indices) such that the union area of the chosen circles is maximized. In other words, under the guarantee that there exists at least one selection of (k) circles that do not overlap (i.e. the circular distance between any two chosen centers is at least (2r)), you must output one such selection. If there are multiple solutions, output the one with the lexicographically smallest list of indices (when indices are considered in increasing order).

Recall that the circular (or modular) distance between two points (a) and (b) on a circle of circumference (L) is defined as (\min(|a-b|, L-|a-b|)).

(\textbf{Note:}) It is guaranteed that there exists at least one valid selection of (k) circles that are pairwise non–overlapping.

(\textbf{Example Explanation:}) For instance, if (n=5,;k=3,;L=100,;r=10) and the positions are given as

0 20 40 60 80

one valid answer is to choose circles with indices 1, 2, and 3. Their centers are at positions 0, 20, and 40 respectively. Notice that the circular distances are (20) (between 0 and 20), (20) (between 20 and 40), and (100 - 40 + 0 = 60) (between 40 and 0, wrapping around), each at least (2r = 20). In this case, the union area is (3\pi 10^2 = 300\pi), which is the maximum possible over all selections.

inputFormat

The input consists of two lines. The first line contains four integers (n), (k), (L), and (r) where:

• (n) ((1 \le n \le 20)) is the number of circles, • (k) ((1 \le k \le n)) is the number of circles to choose, • (L) ((L \ge 2kr)) is the circumference of the ring, • (r) is the radius of each circle.

The second line contains (n) integers (x_1, x_2, \ldots, x_n) (each in the range ([0, L))) representing the positions of the circle centers on the ring. The positions are given in arbitrary order.

outputFormat

Output (k) distinct integers (separated by spaces), which are the 1-indexed positions of the chosen circles in the input that maximize the union area. If multiple answers exist, output the one which is lexicographically smallest (when sorted in increasing order).

sample

5 3 100 10
0 20 40 60 80

1 2 3