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

public class _1249_D2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer line = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(line.nextToken());
        int k = Integer.parseInt(line.nextToken());
        Point[][] segs = new Point[n][2];
        TreeSet<Point> sorted = new TreeSet<Point>(new Comparator<Point>(){
            @Override
            public int compare(Point a, Point b) {
                if(a.x == b.x) {
                    if(a.t == b.t) {
                        return a.i - b.i;
                    }
                    return b.t - a.t;
                }
                return a.x - b.x;
            }
        });
        for(int i = 0; i < n; i++) {
            line = new StringTokenizer(in.readLine());
            int l = Integer.parseInt(line.nextToken());
            int r = Integer.parseInt(line.nextToken());
            segs[i][0] = new Point(0, l, i);
            segs[i][1] = new Point(1, r + 1, i);
            sorted.add(segs[i][0]);
            sorted.add(segs[i][1]);
        }
        TreeSet<Point> active = new TreeSet<Point>(new Comparator<Point>() {
            @Override
            public int compare(Point a, Point b) {
                int aend = segs[a.i][1].x;
                int bend = segs[b.i][1].x;
                if(aend == bend) {
                    return a.i - b.i;
                }
                return bend - aend;
            }
        });
        ArrayList<Integer> remove = new ArrayList<Integer>();
        for(Point p : sorted) {
            if(p.t == 0) {
                active.add(p);
                if(active.size() > k) {
                    remove.add(active.pollFirst().i);
                }
            }else {
                Point start = segs[p.i][0];
                if(active.contains(start)) active.remove(start);
            }
        }
        out.println(remove.size());
        StringBuilder sb = new StringBuilder();
        for(int i : remove) {
            sb.append(i + 1);
            sb.append(' ');
        }
        out.println(sb.toString());
        in.close();
        out.close();
    }
    static class Point {
        int t, x, i;
        Point(int tt, int xx, int ii) {
            t = tt;
            x = xx;
            i = ii;
        }
    }
}