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.*;
import static java.lang.Math.*;

public class D{
	
	static class Point implements Comparable<Point>{
		int i, val;
		boolean open;
		public Point(int a, int b, boolean c) {
			i=a;
			val=b;
			open=c;
		}
		public int compareTo(Point o) {
			if (val==o.val) {
				if(open==o.open) {
					return i-o.i;
				}
				if (open) return -1;
				return 1;
			}
			return val-o.val;
		}
	}
	
	public static void main(String[] args) throws IOException {
		// br = new BufferedReader(new FileReader(".in"));
		// out = new PrintWriter(new FileWriter(".out"));
		//new Thread(null, new (), "peepee", 1<<28).start();
		
		// Consider which point ends further out, as that will cause the most problems. Remove that and continue.
		int n = readInt();
		int k= readInt();
		int[] l = new int[n];
		int[] r = new int[n];
		Point[] p = new Point[n*2];
		List<Integer> seg = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			p[i]= new Point(i,l[i]= readInt(),true);
			p[i+n] = new Point(i, r[i]=readInt(), false);
		}
		Arrays.sort(p);
		TreeSet<Integer> ts = new TreeSet<Integer>((i,j)-> r[i]==r[j] ? i-j:r[i]-r[j]);
		for (int f = 0; f < p.length; f++) {
			if (p[f].open) ts.add(p[f].i);
			else ts.remove(p[f].i);
			if (ts.size() > k) {
				seg.add(ts.pollLast());
			}
		}
		out.println(seg.size());
		for (int x: seg) out.print(x+1 + " ");
		out.println();
		
		out.close();
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static StringTokenizer st = new StringTokenizer("");
	static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
	static int readInt() throws IOException{return Integer.parseInt(read());}
	static long readLong() throws IOException{return Long.parseLong(read());}
	static double readDouble() throws IOException{return Double.parseDouble(read());}
}