Problem: The only difference between easy and hard versions is constraints.

You are given n segments on the coordinate axis OX. Segments can intersect, lie inside each other and even coincide. The i-th segment is [l_i; r_i] (l_i ≤ r_i) and it covers all integer points j such that l_i ≤ j ≤ r_i.

The integer point is called bad if it is covered by strictly more than k segments.

Your task is to remove the minimum number of segments so that there are no bad points at all.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next n lines contain segments. The i-th line contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 2 ⋅ 10^5) — the endpoints of the i-th segment.

Output

In the first line print one integer m (0 ≤ m ≤ n) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print m distinct integers p_1, p_2, ..., p_m (1 ≤ p_i ≤ n) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

Examples

Input


7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9


Output


3
4 6 7 


Input


5 1
29 30
30 30
29 29
28 30
30 30


Output


3
1 4 5 


Input


6 1
2 3
3 3
2 3
2 2
2 3
2 3


Output


4
1 3 5 6 

Solution (in JAVA):

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

public class Main {
    private static FastReader in;
    private static PrintWriter out;

    public static void main(String[] args) throws Exception {
        in = new FastReader(new InputStreamReader(System.in));
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n = in.nextInt();
        int k = in.nextInt();
        ArrayList[] events = new ArrayList[200002];
        ArrayList<Integer> remove = new ArrayList<>();
        for (int i = 0; i < 200002; i++) {
            events[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            events[l].add(1);
            events[l].add(r);
            events[l].add(i + 1);
            events[r + 1].add(0);
            events[r + 1].add(0);
            events[r + 1].add(0);
        }
        in.close();
        int cover = 0;
        PriorityQueue<Trio> heap = new PriorityQueue<>();
        int[] post = new int[200002];
        for (int ind = 0; ind < events.length; ind++) {
            for (int i = 0; i < events[ind].size(); i += 3) {
                if ((Integer) events[ind].get(i) > 0) {
                    cover++;
                    heap.offer(new Trio((Integer) events[ind].get(i + 1), ind, (Integer) events[ind].get(i + 2)));
                } else if (post[ind] > 0) {
                    post[ind]--;
                } else {
                    cover--;
                }
            }
            while (cover > k) {
                Trio a = heap.remove();
                post[a.a + 1]++;
                remove.add(a.c);
                cover--;
            }
        }
        out.println(remove.size());
        for (int i : remove) {
            out.print(i + " ");
        }
        out.println();
        out.close();
    }
}

class FastReader extends BufferedReader {
    FastReader(Reader in) {
        super(in);
    }

    char nextChar() throws Exception {
        int c;
        while ((c = read()) < 33);
        return (char) c;
    }

    double nextDouble() throws Exception {
        int c;
        double div = 1;
        double ret = 0;
        while ((c = read()) < 33);
        boolean neg = c == 45;
        if (neg) {
            c = read();
        }
        do {
            ret = ret * 10 + c - 48;
        } while ((c = read()) > 47 && c < 58);
        if (c == 46) {
            while ((c = read()) > 47 && c < 58) {
                ret += (c - 48) / (div *= 10);
            }
        }
        return neg ? -ret : ret;
    }

    int nextInt() throws Exception {
        int c;
        int ret = 0;
        while ((c = read()) < 33);
        boolean neg = c == 45;
        if (neg) {
            c = read();
        }
        do {
            ret = ret * 10 + c - 48;
        } while ((c = read()) > 47 && c < 58);
        return neg ? -ret : ret;
    }

    long nextLong() throws Exception {
        int c;
        long ret = 0;
        while ((c = read()) < 33);
        boolean neg = c == 45;
        if (neg) {
            c = read();
        }
        do {
            ret = ret * 10 + c - 48;
        } while ((c = read()) > 47 && c < 58);
        return neg ? -ret : ret;
    }
}

class Trio implements Comparable<Trio> {
    int a, b, c;

    Trio(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public int compareTo(Trio o) {
        if (this.a == o.a) {
            return 1;
        }
        return o.a - this.a;
    }
}