C. Месть студентов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Нелегка студенческая жизнь. На собственном опыте пришлось прочувствовать это некоторым студентам Берляндского университета. За два года обучения возникла у них стойкая неприязнь к заведующей одной из кафедр. В самом деле, то группы переформирует, то запретит ставить студентам автоматы, то совершит еще какой-нибудь отвратительный поступок. Решили студенты, что все это не должно сойти заведующей с рук...

Благодаря связям в ректорате студентам стало известно, что на следующем заседании ректората будет рассмотрено n приказов, касающихся заведующей, при этом принято из них будет ровно p. Для каждого приказа определено две величины: ai — количество седых волос, которое прибавится на голове у заведующей, если она выполнит этот приказ, и bi — недовольство ректората тем, что данный приказ не будет выполнен. Студенты могут добиться того, чтобы в ректорате были приняты любые выбранные ими p приказов. Студенты знают, что из числа этих p приказов заведующая выполнит ровно k, причем она будет выбирать их таким образом, чтобы минимизировать в первую очередь суммарное недовольство ректората ее действиями, а во вторую — количество седых волос, которое прибавится у нее на голове.

Студенты хотят выбрать p приказов так, чтобы на голове у заведующей прибавилось как можно больше седых волос. Если при этом есть несколько вариантов принятия приказов, то в интересах студентов максимизировать недовольство ректората действиями заведующей. Помогите им.

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

В первой строке записаны три целых числа n (1 ≤ n ≤ 105), p (1 ≤ p ≤ n), k (1 ≤ k ≤ p) — количество приказов, которые будут рассмотрены ректоратом, количество приказов, которые будут приняты ректоратом, и количество приказов, которые будут выполнены заведующей, соответственно. Каждая из следующих n строк содержит два целых числа ai и bi (1 ≤ ai, bi ≤ 109), описывающих соответствующий приказ.

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

Выведите в произвольном порядке p различных целых чисел — номера приказов, которые необходимо принять, чтобы осуществить замысел студентов. Приказы нумеруются от 1 до n согласно порядку их следования во входных данных. Если оптимальных решений несколько, можно вывести любое.

Примеры
Входные данные
5 3 2
5 6
5 8
1 3
4 3
4 11
Выходные данные
3 1 2
Входные данные
5 3 3
10 18
18 17
10 20
20 18
20 18
Выходные данные
2 4 5
Примечание

В первом примере одно из оптимальных решений — это принятие приказов 1, 2, 3. В этом случае заведующая выполнит приказы с номерами 1 и 2. У нее на голове прибавится 10 седых волос, а недовольство ректората ее действиями будет равно 3. Отметим, что такого же результата можно достичь, приняв вместо приказа 3 приказ 4.

Во втором примере заведующая сможет выполнить все приказы, поэтому студентам лучше всего принимать приказы с максимальной суммой ai. На голове у заведующей прибавится 58 седых волос, а недовольство ректората будет равно 0.