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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Segment {
        int start, end, index;
        Segment(int start, int end, int index) {
            this.start = start;
            this.end = end;
            this.index = index;
        }

        @Override
        public boolean equals(Object obj) {
            return start == ((Segment) obj).start && end == ((Segment) obj).end && index == ((Segment) obj).index;
        }

        @Override
        public int hashCode() {
            return (start+" " + end + " " + index).hashCode();
        }

        @Override
        public String toString() {
            return "[" + start +", " + end + "]";
        }
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024 * 2);

        int[] v = readArrayLine(br.readLine(), 2);
        int n = v[0];
        int k = v[1];

        List<Segment> l = new ArrayList<>();
        for (int i = 0 ; i < n ; i ++) {
            int[] a = readArrayLine(br.readLine(), 2);
            l.add(new Segment(a[0], a[1], i + 1));
        }
        l.sort(Comparator.comparingInt(s -> s.start));
        List<Segment> l2 = new ArrayList<>(l);
        l2.sort(Comparator.comparingInt(s -> s.end));
        l.sort(Comparator.comparingInt(s -> s.start));

        List<Integer> toRemove = new ArrayList<>();
        int iterator = 0;
        int iteratorEndList = 0;
        TreeSet<Segment> queue = new TreeSet<>((s1, s2) -> {
            if (s2.end == s1.end) {
                if (s2.start == s1.start) {
                    return s1.index - s2.index;
                }
                return s1.start - s2.start;
            }
            return s2.end - s1.end;
        });
        for (int i = 0; i <= 200_001; i ++) {
            while (iterator < n && l.get(iterator).start <= i) {
                queue.add(l.get(iterator));
                iterator++;
            }
            while (iteratorEndList < n && l2.get(iteratorEndList).end < i) {
                queue.remove(l2.get(iteratorEndList));
                iteratorEndList++;
            }

            while (queue.size() > k) {
                Segment poll = queue.pollFirst();
                toRemove.add(poll.index);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(toRemove.size()).append('\n');
        if (toRemove.size() > 0) {
            for (int s : toRemove) {
                sb.append(s).append(' ');
            }
        }
        System.out.println(sb.toString());
    }

    private static int[] readArrayLine(String line, int n) {
        return readArrayLine(line, n, null, 0);
    }

    private static int[] readArrayLine(String line, int n, int array[], int pos) {
        int[] ret = array == null ? new int[n] : array;
        int start = 0;
        int end = line.indexOf(' ', start);
        for (int i = pos; i < pos + n; i++) {
            if (end > 0)
                ret[i] = Integer.parseInt(line.substring(start, end));
            else
                ret[i] = Integer.parseInt(line.substring(start));
            start = end + 1;
            end = line.indexOf(' ', start);
        }
        return ret;
    }

}