eolymp
Змагання

Жадібні алгоритми

Виявлення молекул

Петро працюєт в компанії, яка створює прилад для виявлення молекул. Кожна молекула має цілу додатнб вагу. Пристрій характеризується інтервалом виявлення [l; u], де l і u цілі додатнічисла. Пристрій може виявити множину молекул тоді і тільки тоді, коли ця множина містить таку підмножину, що сумарна вага молекул в ній належить інтервалу виявлення пристрою.

Більш формально, разглянемо n молекул з вагою w0, ..., wn-1. Виявлення вважається успешним, якщо існує множина різних індексів I = {i1, ..., im} така що lwi1 + .. + wimu.

В силу особливості роаботи пристрою різниця між l і u гарантовано більша або дорівнює різниці мас між самою важкою і самою легкою молекулами. Більш формально u - lwmax - wmin, де wmax = max(w0, ..., wn-1) і wmin = min(w0, ..., wn-1).

Потрібно написати програму, яка або знаходит будь-яку підмножину молекул з сумарною вагою, що належить інтервалу виявлення пристрою, або визначає, що такогї підмножини не існує.

Вхідні дані

Перший рядок містить три цілих числа: кількість молекул n (1n200000) і границі інтервалу виявлення l і u (1l, u < 231). Другий рядок містить n ціелих чисел: w0, ..., wn-1 (1wi < 231).

Вихідні дані

В першому рядку вивести розмір подмножини m. У другому рядку вивести індекси молекул, які формують будь-яку таку підмножину. Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 15 17
6 8 8 7
Вихідні дані #1
2
2 1 
Вхідні дані #2
4 14 15
5 5 6 6
Вихідні дані #2
0

Вхідні дані #3
4 10 20
15 17 16 18
Вихідні дані #3
1
3 
Джерело 2016 IOI Казань, Россия, День 1