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

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

Благодаря связям в ректорате студентам стало известно, что на следующем заседании ректората будет рассмотрено 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.