F. Пакет вопросов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александр уже долгое время является ведущим турниров по спортивной версии игры «Что? Где? Когда?».

В спортивное «Что? Где? Когда?» играют одновременно несколько команд по 6 человек. Ведущий задаёт вопрос, после чего в течение 60 секунд команды должны придумать на него ответ и записать в бланке ответа. По истечении минуты на размышление, у игроков есть 10 секунд на то, чтобы сдать бланки ведущему.

Саша собирает вопросы на новую игру. Игра состоит из $$$R$$$ туров, в каждом туре по $$$Q$$$ вопросов. Есть база из $$$N$$$ вопросов, по каждому вопросу известно, сколько команд пытались ответить на вопрос и сколько команд ответили на него неправильно. На основе этих данных для каждого вопроса рассчитывается рейтинг вопроса: считается доля неправильных ответов на вопрос, умножается на 10000 и округляется вниз до целого. Самый простой вопрос имеет наименьший рейтинг. Саша хочет сформировать пакет вопросов на игру по следующим правилам:

  • В пакете должен быть хотя бы один вопрос, который имеет рейтинг меньше $$$L$$$. Такой вопрос называется «свечка» и на него правильно отвечают почти все команды. Если кандидатов на такой вопрос несколько, то «свечкой» называется вопрос с минимальным среди кандидатов рейтингом. Вопрос с минимальным рейтингом в базе может не быть «свечкой».
  • В пакете должен быть хотя бы один вопрос, который имеет рейтинг больше $$$C$$$. Такой вопрос называется «гроб» и на него правильно отвечают только самые лучшие команды. Если кандидатов на такой вопрос несколько, то «гробом» называется вопрос с максимальным среди кандидатов рейтингом. Вопрос с максимальным рейтингом в базе может не быть «гробом».
  • Вопрос-свечка должен быть в первой половине игры.
  • Вопрос-гроб должен быть в середине игры. Если число вопросов в игре — чётное, то гроб может быть любым находящимся посередине.
  • Рейтинги туров должны строго увеличиваться до середины (в первой половине игры), затем строго уменьшаться (во второй половине игры). Рейтингом каждого тура называется округлённое вниз среднее арифметическое рейтингов вопросов тура.
  • Игру нужно сделать разнообразной. Если упорядочить все вопросы в игре по рейтингу $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, то сложность любых двух соседних вопросов $$$Q_i$$$ и $$$Q_{i+1}$$$ удовлетворяет неравенству $$$Q_{i+1} - Q_i \ge D$$$, где $$$D$$$ — коэффициент разнообразия.
  • Если вопросов в туре больше 2, то рейтинги вопросов не могут строго увеличиваться или строго уменьшаться.
  • Если упорядочить все вопросы в игре по рейтингу $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, то сложность любых двух соседних вопросов $$$Q_i$$$ и $$$Q_{i+1}$$$ не должна отличаться больше, чем на $$$S$$$.

Помогите Саше: сформируйте пакет вопросов на игру так, чтобы правила были выполнены.

Входные данные

В первой строке выходных данных содержатся целые неотрицательные числа $$$N, R, Q, L, C, D, S$$$ в соответствии с условием ($$$1 \le N, R, Q \le 10^6$$$, $$$1 \le R \cdot Q \le 10^6$$$, $$$2 \le L, C \le 9999$$$, $$$L \lt C$$$, $$$1 \le D, S \le 10000$$$).

Во следующих $$$N$$$ строках содержатся по два целых неотрицательных числа $$$A_i, B_i$$$ — скольким командам задали вопрос и сколько команд ответили на вопрос неправильно ($$$0 \le B_i \le A_i \le 10^9$$$)

Выходные данные

Если сформировать пакет, не нарушив правила, возможно, то выведите $$$R \cdot Q$$$ целых чисел — номера вопросов из базы в том порядке, в котором они должны быть заданы в игре. Если вариантов пакетов несколько, выведите любой из них.

Если сформировать пакет невозможно, выведите 0.

Пример
Входные данные
10 3 2 4000 6000 100 5000
1000 100
1000 200
1000 300
1000 400
1000 500
1000 550
1000 600
1000 700
1000 850
1000 950
Выходные данные
4 3 8 7 6 5