Problem: A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore...

The students pulled some strings on the higher levels and learned that the next University directors' meeting is going to discuss n orders about the chairperson and accept exactly p of them. There are two values assigned to each order: ai is the number of the chairperson's hairs that turn grey if she obeys the order and bi — the displeasement of the directors if the order isn't obeyed. The students may make the directors pass any p orders chosen by them. The students know that the chairperson will obey exactly k out of these p orders. She will pick the orders to obey in the way that minimizes first, the directors' displeasement and second, the number of hairs on her head that turn grey.

The students want to choose p orders in the way that maximizes the number of hairs on the chairperson's head that turn grey. If there are multiple ways to accept the orders, then the students are keen on maximizing the directors' displeasement with the chairperson's actions. Help them.

Input

The first line contains three integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ n), k (1 ≤ k ≤ p) — the number of orders the directors are going to discuss, the number of orders to pass and the number of orders to be obeyed by the chairperson, correspondingly. Each of the following n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109), describing the corresponding order.

Output

Print in an arbitrary order p distinct integers — the numbers of the orders to accept so that the students could carry out the revenge. The orders are indexed from 1 to n in the order they occur in the input. If there are multiple solutions, you can print any of them.

Examples

Input

5 3 2
5 6
5 8
1 3
4 3
4 11


Output

3 1 2 

Input

5 3 3
10 18
18 17
10 20
20 18
20 18


Output

2 4 5 

Note

In the first sample one of optimal solutions is to pass orders 1, 2, 3. In this case the chairperson obeys orders number 1 and 2. She gets 10 new grey hairs in the head and the directors' displeasement will equal 3. Note that the same result can be achieved with order 4 instead of order 3.

In the second sample, the chairperson can obey all the orders, so the best strategy for the students is to pick the orders with the maximum sum of ai values. The chairperson gets 58 new gray hairs and the directors' displeasement will equal 0.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.List;


/**
 * Created by Katushka on 11.03.2020.
 */
public class Main {

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    static int[] readArray(int size, InputReader in, boolean subOne) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt() + (subOne ? -1 : 0);
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    private static final boolean DEBUG = false;
    private static final long MOD = 1000000007;


    private static int[] getBinary(long a, int size) {
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = (int) ((a >> i) & 1);
        }
        return result;
    }

    private static long fastPow(long x, long y, long mod) {
        if (x == 1) {
            return 1;
        }
        if (y == 0) {
            return 1;
        }
        long p = fastPow(x, y / 2, mod) % mod;
        p = p * p % mod;
        if (y % 2 == 1) {
            p = p * x % mod;
        }
        return p;
    }

    private static long inv(long x, long mod) {
        return fastPow(x, mod - 2, mod);

    }

    private static long addMod(long x, long y, long mod) {
        long res = x + y;
        if (res >= mod) {
            return res - mod;
        }
        return res;
    }

    private static long multMod(long x, long y, long mod) {
        long res = x * y;
        if (res >= mod) {
            return res % mod;
        }
        return res;
    }

    private static long subMod(long x, long y, long mod) {
        long res = x - y;
        if (res < 0) {
            return res + mod;
        }
        return res;
    }

    public static void main(String[] args) throws FileNotFoundException {
//        InputReader in = new InputReader(new FileInputStream("input.txt"));
//        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("seating.out")));

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = in.nextInt();
        int p = in.nextInt();
        int k = in.nextInt();

        long[][] ab = new long[n][];
        for (int i = 0; i < n; i++) {
            ab[i] = new long[]{in.nextLong(), in.nextLong(), i};
        }

        Arrays.sort(ab, (o1, o2) -> o1[1] == o2[1] ? -Long.compare(o1[0], o2[0]) : Long.compare(o1[1], o2[1]));
        Set<Long> notTaken = new HashSet<>();
        for (int i = 0; i < p - k; i++) {
            notTaken.add(ab[i][2]);
        }
        Set<Long> taken = new HashSet<>();
        long[][] ab2 = Arrays.copyOf(ab, n);
        Arrays.sort(ab2, (o1, o2) -> o1[0] == o2[0] ? Long.compare(o1[1], o2[1]) : -Long.compare(o1[0], o2[0]));
        int j = 0;
        for (; taken.size() < k; j++) {
            if (!notTaken.contains(ab2[j][2])) {
                taken.add(ab2[j][2]);
            }
        }
        if (p > k) {
            for (int i = p - k; i < n; i++) {
                if (taken.contains(ab[i][2])) {
                    boolean found = false;
                    while (ab[i][0] == ab2[j - 1][0] && j < n && ab2[j][0] == ab2[j - 1][0]) {
                        if (!notTaken.contains(ab2[j][2])) {
                            found = true;
                            taken.add(ab2[j][2]);
                            j++;
                            break;
                        }
                        j++;
                    }
                    if (!found) {
                        break;
                    }
                    taken.remove(ab[i][2]);
                }
                notTaken.remove(ab[(i - (p - k))][2]);
                notTaken.add(ab[i][2]);
            }
        }

        StringBuilder ans = new StringBuilder();
        for (Long aLong : notTaken) {
            ans.append(aLong + 1).append(" ");
        }
        for (Long aLong : taken) {
            ans.append(aLong + 1).append(" ");
        }
        out.println(ans.toString());


        out.close();
    }


    private static void outputArray(long[] ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            long an = ans[i] + (addOne ? 1 : 0);
            str.append(an).append('\t');
        }
        out.println(str);
        out.flush();
    }

    private static void outputArray(List<Long> ans, PrintWriter out) {
        StringBuilder str = new StringBuilder();
        for (long an : ans) {
            str.append(an).append(' ');
        }
        out.println(str);
        out.flush();
    }


    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < n - 1; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

    }
}