### IOI '16 - Kazan, Russia

## Molecules

Petr is working for a company that has built a machine for detecting molecules. Each molecule has a positive integer weight. The machine has a *detection range* [`l`, `u`], where `l` and `u` are positive integers. The machine can detect a set of molecules if and only if this set contains a subset of the molecules with total weight belonging to the machine's detection range.

Formally, consider `n` molecules with weights `w`_{0}, …, `w`_{n − 1}. The detection is successful if there is a set of distinct indices `I` = {`i`_{1}, … , `i _{m}`} such that

`l`≤

`w`

_{i1}+ … +

`w`≤

_{im}`u`.

Due to specifics of the machine, the gap between `l` and `u` is guaranteed to be greater than or equal to the weight gap between the heaviest and the lightest molecule. Formally, `u` − `l` ≥ `w`_{max} − `w`_{min}, where `w`_{max} = max(`w`_{0}, …, `w`_{n − 1}) and `w`_{min} = min(`w`_{0}, …, `w`_{n − 1}).

Your task is to write a program which either finds any one subset of molecules with total weight within the detection range, or determines that there is no such subset.

You should implement one operation `find_subset`

:

`find_subset(n, l, u, w[])`

`n`

: the number of elements in`w`(i.e, the number of molecules),`l`

and`u`

: the endpoints of the detection range,`w`

: weights of the molecules.- if the required subset exists, then output an array
`I`of indices of molecules that form any one such subset. If there are several correct answers, output any of them. - if the required subset does not exist, then output a single number 0.

Your program may output the indices in any order.

### Input Format

The input will be given in the following format:

- Line 1: three space-separated integers
`n`,`l`,`u` - Line 2:
`n`space-separated integers`w`_{0}, …,`w`_{n − 1}

### Output Format

The output should be in the following format:

- Line 1: a single integer
`m` - Line 2:
`m`space-separated integers`i`_{1}, …,`i`_{m}

### Sample Input 1

4 15 17 6 8 8 7

### Sample Output 1

2 1 2

### Explanation 1

In this example we have four molecules with weights 6, 8, 8 and 7. The machine can detect subsets of molecules with total weight between 15 and 17, inclusive. Note, that 17 − 15 ≥ 8 − 6. The total weight of molecules 1 and 3 is `w`_{1} + `w`_{3} = 8 + 7 = 15, so the program can output [1, 3]. Other possible correct answers are [1, 2] (`w`_{1} + `w`_{2} = 8 + 8 = 16) and [2, 3] (`w`_{2} + `w`_{3} = 8 + 7 = 15).

### Sample Input 2

4 14 15 5 5 6 6

### Sample Output 2

0

### Explanation 2

In this example we have four molecules with weights 5, 5, 6 and 6, and we are looking for a subset of them with total weight between 14 and 15, inclusive. Again, note that 15 − 14 ≥ 6 − 5. There is no subset of molecules with total weight between 14 and 15 so the function should return an empty array.

### Sample Input 3

4 10 20 15 17 16 18

### Sample Output 3

1 0

### Explanation 3

In this example we have four molecules with weights 15, 17, 16 and 18, and we are looking for a subset of them with total weight between 10 and 20, inclusive. Again, note that 20 − 10 ≥ 18 − 15. Any subset consisting of exactly one element has total weight between 10 and 20, so the possible correct answers are: [0], [1], [2] and [3].

### Subtasks

- (9% of points): 1 ≤
`n`≤ 100, 1 ≤`w`≤ 100, 1 ≤_{i}`u`,`l`≤ 1000, all`w`are equal._{i} - (10% of points): 1 ≤
`n`≤ 100, 1 ≤`w`,_{i}`u`,`l`≤ 1000 and max(`w`_{0}, …,`w`_{n − 1}) − min(`w`_{0}, …,`w`_{n − 1}) ≤ 1. - (12% of points): 1 ≤
`n`≤ 100 and 1 ≤`w`,_{i}`u`,`l`≤ 1000. - (15% of points): 1 ≤
`n`≤ 10 000 and 1 ≤`w`,_{i}`u`,`l`≤ 10 000. - (23% of points): 1 ≤
`n`≤ 10 000 and 1 ≤`w`,_{i}`u`,`l`≤ 500 000. - (31% of points): 1 ≤
`n`≤ 200 000 and 1 ≤`w`,_{i}`u`,`l`≤ 2^{31}.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 2048M

**Added:** Aug 10, 2017

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...