Ціни на акції#2753

Ціни на акції

1 секунда

64 мегабайти

Легка

Купуй дешево, продавай дорого. Це головний принцип отримання прибутку на фондовому ринку (тут ми ігноруємо короткі продажі). Звичайно, ніхто не може передбачити майбутню ціну акцій, тому важко визначити, коли саме купувати і продавати, і який прибуток можна отримати, багаторазово купуючи й продаючи акції.

Проте, якщо у вас є історія цін на акції за останні $n$ днів, можна визначити максимально можливий прибуток. У цій задачі, натомість, нас цікавить знаходження $k_{1}$ k_1 найнижчих та $k_{2}$ k_2 найвищих цін із цієї історії.

Вхідні дані

Вхідні дані складаються з кількох тестових випадків. Кожен випадок починається з рядка, що містить додатні цілі числа $n$ , $k_{1}$ k_1 та $k_{2}$ k_2 ( $n \leq 1000000$ n \leq 1000000, $k_{1} + k_{2} \leq n$ k_1 + k_2 \leq n, $k_{1}, k_{2} \leq 100$ k_1, k_2 \leq 100). Наступний рядок містить $n$ цілих чисел — ціни акцій за останні $n$ днів: $i$ -те число ( $1 \leq i \leq n$ 1 \leq i \leq n) відповідає ціні акцій у $i$ -й день. Усі ціни невід'ємні. Вхідні дані завершуються рядком, що містить $n = k_{1} = k_{2} = 0$ n = k_1 = k_2 = 0; цей випадок обробляти не потрібно.

Вихідні дані

Для кожного випадку виведіть три рядки. У першому рядку — номер випадку (починаючи з $1$ ). У другому рядку — дні, у які спостерігалися $k_{1}$ k_1 найнижчих цін на акції, у порядку зростання. У третьому рядку — дні, у які спостерігалися $k_{2}$ k_2 найвищих цін на акції, у порядку спадання. Елементи кожного списку розділяйте одним пробілом. Якщо існує кілька правильних списків для найнижчих цін, оберіть лексикографічно найменший список. Якщо існує кілька правильних списків для найвищих цін, оберіть лексикографічно найбільший список.

Приклади

Приклад 1