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  gym{
	static class segment{
		int l,r,i;
		segment(int x,int y,int z){
			l=x;r=y;i=z;
		}
		public String toString() {
			return "("+l+" "+r+" "+i+")";
		}
	}
	public static void main(String[] args) throws Exception{
		MScanner sc=new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt(),k=sc.nextInt();
		segment[]segs=new segment[n];;
		for(int i=1;i<=n;i++) {
			segs[i-1]=(new segment(sc.nextInt(), sc.nextInt(),i));
		}
		Arrays.sort(segs,((x,y)->(x.l-y.l)));
		int c=0;
		TreeSet<segment>cur=new TreeSet<gym.segment>((x,y)->(y.r==x.r?y.i-x.i:y.r-x.r));
		TreeSet<segment>ranges=new TreeSet<gym.segment>((x,y)->(y.r==x.r?y.i-x.i:x.r-y.r));
		LinkedList<Integer>removed=new LinkedList<Integer>();
		while(true) {
			if(c==n)break;
			int i=Math.min(segs[c].l, ranges.isEmpty()?1000000:ranges.first().r);
			while(c<n && segs[c].l==i) {
				segment x=segs[c++];
				cur.add(x);
				ranges.add(x);
			}
			while(cur.size()>k) {
				segment x=cur.pollFirst();
				removed.add(x.i);
				ranges.remove(x);
			}
			while(!ranges.isEmpty() && ranges.first().r==i) {
				segment x=ranges.pollFirst();
				cur.remove(x);
			}
			//System.out.println(cur);
		}
		pw.println(removed.size());
		while(!removed.isEmpty())pw.print(removed.removeFirst()+" ");
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] takearr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] takearrl(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public Integer[] takearrobj(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] takearrlobj(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}