Description

Peter works at a company that has built a machine to detect molecules. The weight of each molecule is a positive integer. The detection range of the machine is $[l,u]$, where both $l$ and $u$ are positive integers. The machine can detect a set of molecules if and only if this set contains a subset whose total weight lies within the detection range.

Consider $n$ molecules with weights $w_0,\cdots,w_{n-1}$. If there exists a set of indices (and all indices in the set are distinct) $I=\{i_1,\cdots,i_m\}$ such that $l\le w_{i_1}+\cdots+w_{i_m}\le u$, then the detection succeeds.

Due to the details of the machine, the difference between $l$ and $u$ is guaranteed to be at least the difference between the heaviest and the lightest molecule, i.e. $u-l \ge w_{max}-w_{min}$, where $w_{max}=\max(w_0,\cdots,w_{n-1})$ and $w_{min}=\min(w_0,\cdots,w_{n-1})$.

Your task is to write a program that finds a subset whose total weight lies within the detection range, or determines that no such subset exists.

Sample 1

 4 15 17
 6 8 8 7

In this example, we have four molecules with weights $6,8,8$ and $7$. The machine can detect a subset whose total weight is between $15$ and $17$ (including $15$ and $17$). Note that $17-15 \ge 8-6$. The sum of the weights of molecule $1$ and molecule $3$ is $w_1+w_3=8+7=15$, so the output should be

2
1 3

Other possible correct answers are

2 
1 2

($w_1+w_2=8+8=16$)

and

2
2 3

($w_2+w_3=8+7=15$).

Sample 2

4 14 15
5 5 6 6

In this example, we have four molecules with weights $5,5,6$ and $6$. We want to find a subset whose total weight is between $14$ and $15$ (including $14$ and $15$). Note that $15-14 \ge 6-5$. Since there is no subset whose total weight is between $14$ and $15$, output 0.

Input Format

• The first line: integers $n,l$ and $u$.

• The second line: $n$ integers: $w_0,\cdots,w_{n-1}$.

Output Format

If there is a subset that satisfies the condition:

• The first line: output the size of the subset $x$.

• The second line: $x$ integers, the indices of the molecules in a valid subset.

If not, output 0.

1 10 12
9

0

2 5 10
4 2

2
0 1

Hint

Constraints: for $100\%$ of the data, $n \le 2 \times 10^5$, $w_i \le 2^{31}-1$, and $l,u \le 2^{31}-1$.

Translated by ChatGPT 5