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

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

1 секунда

128 мегабайтів

Середня

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

Формально, розглянемо $n$ молекул з вагами $w_{0}, \dots, w_{n - 1}$ w_0, \ldots, w_{n-1}. Виявлення вважається успішним, якщо існує множина різних індексів $I = {i_{1}, \dots, i_{m}}$ I = \{i_1, \ldots, i_m\} така, що

l \leq w_{i_{1}} + \dots + w_{i_{m}} \leq u .

l \le w_{i_1} + \ldots + w_{i_m} \le u.

Через особливості пристрою, різниця між $l$ та $u$ гарантовано більша або дорівнює різниці ваг між найважчою та найлегшою молекулами. Формально,

u - l \geq w_{max} - w_{min},

u - l \ge w_{\text{max}} - w_{\text{min}},

де $w_{max} = max (w_{0}, \dots, w_{n - 1})$ w_{\text{max}} = \max(w_0, \ldots, w_{n-1}) та $w_{min} = min (w_{0}, \dots, w_{n - 1})$ w_{\text{min}} = \min(w_0, \ldots, w_{n-1}).

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

Вхідні дані

Перший рядок містить три цілі числа: кількість молекул $n$ ( $1 \leq n \leq 200000$ 1 \le n \le 200\,000) та межі інтервалу виявлення $l$ і $u$ ( $1 \leq l, u < 2^{31}$ 1 \le l, u < 2^{31}). Другий рядок містить $n$ цілих чисел: $w_{0}, \dots, w_{n - 1}$ w_0, \ldots, w_{n-1} ( $1 \leq w_{i} < 2^{31}$ 1 \le w_i < 2^{31}).

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Приклад 3