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 java.math.*;

public class p1249D {

	public class SegmentSup implements Comparable<SegmentSup> {
		public int L;
		public int R;
		public int ind;

		public SegmentSup() {
		}

		public SegmentSup(int L, int R, int ind) {
			this.L = L;
			this.R = R;
			this.ind = ind;
		}

		public int compareTo(SegmentSup seg) {

			//System.out.println("sup compare");

			if(this.R < seg.R) {
				return 1;
			}

			if(this.R > seg.R) {
				return -1;
			}

			if(this.L < seg.L) {
				return -1;
			}

			if(this.L > seg.L) {
				return 1;
			}

			return 0;


		}

		public String toString() {
			return ind + ": " + L + ", " + R;
		}


	}

	public class SegmentSub extends SegmentSup {

		public SegmentSub(int L, int R, int ind) {
			
			this.L = L;
			this.R = R;
			this.ind = ind;
		}

		public int compareTo(SegmentSup seg) {

			//System.out.println("sub compare");

			if(this.L < seg.L) {
				return -1;
			}
			if(this.L > seg.L) {
				return 1;
			}

			if(this.R < seg.R) {
				return -1;
			}

			if(this.R > seg.R) {
				return 1;
			}

			return 0;

		}

		public String toString() {
			return ind + ": " + L + ", " + R;
		}

	}

	public void realMain() throws Exception {

		BufferedReader fin = new BufferedReader(new InputStreamReader(System.in), 1000000);

		String in = fin.readLine();

		String[] ar = in.split(" ");

		int n = Integer.parseInt(ar[0]);
		int k = Integer.parseInt(ar[1]);
		
		ArrayList<SegmentSub> segments = new ArrayList<SegmentSub>();


		for(int i = 0; i < n; i++) {
			int ret = 0;
			boolean dig = false;
			for (int ch = 0; (ch = fin.read()) != -1; ) {
        			if (ch >= '0' && ch <= '9') {
            				dig = true;
           				ret = ret * 10 + ch - '0';
        			} else if (dig) break;
    			}

			int L = ret;

			ret = 0;
			dig = false;
			for (int ch = 0; (ch = fin.read()) != -1; ) {
        			if (ch >= '0' && ch <= '9') {
            				dig = true;
           				ret = ret * 10 + ch - '0';
        			} else if (dig) break;
    			}

			int R = ret;

			SegmentSub segment = new SegmentSub(L, R, (i+1));
			segments.add(segment);

			
		}

		Collections.sort(segments);

		int[] sums = new int[200002];

		for(int i = 0; i < segments.size(); i++) {
			sums[segments.get(i).L]++;
			sums[segments.get(i).R + 1]--;
		}

		//System.out.println(segments);


		int alind = 0;
		PriorityQueue<SegmentSup> pq = new PriorityQueue<SegmentSup>();

		int cursum = 0;

		ArrayList<Integer> ans = new ArrayList<Integer>();

		for(int i = 0; i < 200001; i++) {
			cursum += sums[i];

			if(cursum > k) {
				while(alind < segments.size() && segments.get(alind).L <= i) {
					SegmentSub segment = segments.get(alind);
					//if(segment.L == i) {
						SegmentSup sup = new SegmentSup(segment.L, segment.R, segment.ind);
						//System.out.println("adding to pq: " + sup.toString());
						pq.add(sup);
					//}
					alind++;
				}
			}

			while(cursum > k) {
				SegmentSup sup = pq.remove();

				sums[sup.L]--;
				sums[sup.R + 1]++;
				cursum--;
				ans.add(sup.ind);

				//System.out.println("removing " + sup.ind + ": " + sup.L + ", " + sup.R);
			}
		}

		System.out.println(ans.size());

		StringBuilder sb = new StringBuilder("");

		for(int i = 0; i < ans.size(); i++) {
			sb.append(ans.get(i));
			sb.append(' ');
		}

		System.out.println(sb);
				
				



	}


	public static void main(String[] args) throws Exception {
		p1249D a = new p1249D();
		a.realMain();
	}
}