Detecting Molecules#7975
Peter is working for a company that has built a device for detecting molecules. Each molecule has a positive integer weight. The device is characterized by a detection range , where and are positive integers. The device can detect a set of molecules if and only if this set contains a subset of molecules whose total weight lies within the device's detection range.
Formally, consider molecules with weights w_0, \ldots, w_{n-1}. Detection is considered successful if there exists a set of distinct indices I = \{i_1, \ldots, i_m\} such that
Due to the specifics of the device, the difference between and is guaranteed to be greater than or equal to the difference in weights between the heaviest and the lightest molecule. Formally,
where w_{\text{max}} = \max(w_0, \ldots, w_{n-1}) and w_{\text{min}} = \min(w_0, \ldots, w_{n-1}).
Your task is to write a program that either finds any subset of molecules with a total weight within the detection range, or determines that no such subset exists.
The first line contains three integers: the number of molecules (1 \le n \le 200\,000), and the endpoints of the detection range and (1 \le l, u < 2^{31}). The second line contains integers: w_0, \ldots, w_{n-1} (1 \le w_i < 2^{31}).
Print the size of the subset in the first line. In the second line, print the indices of the molecules that form any such subset. If there are multiple valid answers, print any of them.
Example 1
Example 2
Example 3