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 {
    static long inf = (long) 1e15 + 7;


    public static void main(String[] args) throws IOException {
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int k = sc.nextInt();
        line a[] = new line[n];
        for(int i = 0;i < n;i++) a[i] = new line(sc.nextInt(), sc.nextInt(), i);

        segment_tree b = new segment_tree(200007);
        Arrays.sort(a, new line());

        TreeSet<Integer> r = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(a[o1].r, a[o2].r) * 2 + Integer.compare(a[o1].id, a[o2].id);
            }
        });

        ArrayList<Integer> ans = new ArrayList<>();
        for(int i = 0;i <= n;i++) {
            int cnt = 0;
            while(i != n && (cnt == 0 || a[i].l == a[i - 1].l)) {
                cnt++;
                r.add(i);
                b.set(a[i].l, a[i].r, 1);
                i++;
            }
            if (i != n) i--;

            while (b.get() > k) {
                int id = r.pollLast();
                ans.add(a[id].id + 1);
                b.set(a[id].l, a[id].r, -1);
            }
        }

        pw.println(ans.size());
        for(int i : ans) pw.print(i + " ");
        pw.close();
    }

    static Scanner sc;
    static PrintWriter pw;

    static class Scanner {
        BufferedReader br;
        StringTokenizer st = new StringTokenizer("");

        Scanner(InputStream in) throws FileNotFoundException {
            br = new BufferedReader(new InputStreamReader(in));
        }

        Scanner(String in) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(in));
        }

        String next() throws IOException {
            while (!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

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

class line implements Comparator<line>{
    int l, r, id;
    line(int l, int r, int id) {
        this.l = l;
        this.r = r;
        this.id = id;
    }
    line() {}

    @Override
    public int compare(line o1, line o2) {
        return Integer.compare(o1.l, o2.l);
    }
}

class segment_tree {
    int max[], push[], last;

    segment_tree(int n) {
        max = new int [4 * n];
        push = new int [4 * n];
        last = n - 1;
    }

    void pushing(int v) {
        push[v * 2 + 1] += push[v];
        push[v * 2 + 2] += push[v];
        max[v * 2 + 1] += push[v];
        max[v * 2 + 2] += push[v];
        push[v] = 0;
    }

    int get() {
        return max[0];
    }

    void set(int l, int r, int x) {
        set(0, 0, last, l, r, x);
    }

    void set(int v, int l, int r, int left, int right, int x) {
        if (l > right || r < left) return;
        if (l >= left && r <= right) {
            push[v] += x;
            max[v] += x;
            return;
        }
        pushing(v);
        int m = ((l + r) >> 1);
        set(v * 2 + 1, l, m, left, right, x);
        set(v * 2 + 2, m + 1, r, left, right, x);
        max[v] = Math.max(max[v * 2 + 1], max[v * 2 + 2]);
    }

}