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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class div3 {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n=sc.nextInt();
		int k=sc.nextInt();
		line[] s=new line[n];
		line[] e=new line[n];
		line[] original=new line[n];
		
		for(int i=0;i<n;i++) {
			original[i]=s[i]=e[i]=new line(sc.nextInt(), sc.nextInt(), i);
			}
		Arrays.sort(s,(x,y)->x.l-y.l);
		Arrays.sort(e,(x,y)->x.r-y.r);
		TreeSet<Integer> cand=new TreeSet<>((x,y)->(original[x].r==original[y].r)?(original[x].idx-original[y].idx):(original[y].r-original[x].r));
		int fireEvent=0;
		int delEvent=0;
		ArrayList<Integer> ans=new ArrayList<Integer>();
		for(int i=1;i<=200000;i++) {
			while(fireEvent<n&&s[fireEvent].l<=i) {
				cand.add(s[fireEvent++].idx);
			}
			while(cand.size()>k) {
				ans.add(cand.pollFirst()+1);
			}
			while(delEvent<n&&e[delEvent].r<=i) {
				if(cand.contains(e[delEvent++].idx))
						cand.remove(e[delEvent-1].idx);
			}
		}
		
		pw.println(ans.size());
		for(int i:ans)
			pw.print(i+" ");
		pw.println();
		
		pw.flush();
	}
	
	static class line implements Comparable<line>{
		int l,r,prob,idx;
		public line(int l ,int r, int idx) {
			this.l=l
				;
			this.r=r;
			this.idx=idx;
		}
		public int compareTo(line line) {
			return prob-line.prob;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + idx;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			line other = (line) obj;
			if (idx != other.idx)
				return false;
			return true;
		}
	}
	static int dp(boolean isElev,int floor) {
		if(floor==0)return 0;
		int elev=0;
		if(isElev)elev=1;
		if(memo[elev][floor]!=-1)return memo[elev][floor];
		int stair=a[floor-1]+dp(false,floor-1);
		int elevator=Integer.MAX_VALUE;
		if(isElev) {
			elevator=b[floor-1]+dp(true,floor-1);
		}else {
			elevator=c+b[floor-1]+dp(true, floor-1);
		}
		return memo[elev][floor]=Math.min(stair, elevator);
	
		
	}
	static int[][] memo;
	static int[] a,b;
	static int n,c;
		static class UDS {
	int[] parent,rank,setSize;
	int n;//number of sets

	public UDS(int n) {

		this.n=n;
		parent=new int[n];
		rank=new int[n];
		setSize=new int[n];
		Arrays.fill(setSize, 1);
		for(int i=0;i<n;i++)parent[i]=i;
	}

	public  void unionSet(int i, int j) {//it can be boolean to tell me if i made the union or not
	if(!isSameSet(i, j)) {
		n--;
		int p1=findSet(i);
		int p2=findSet(j);
	if(rank[p1]<rank[p2]) {
			parent[p1]=p2;
			setSize[p2]+=setSize[p1];
		}else {
			parent[p2]=p1;
			setSize[p1]+=setSize[p2];
			if(rank[p1]==rank[p2])rank[p1]++;
		}
		
	}
	}

	public int sizeOfSet(int i) {return setSize[findSet(i)];}

	public int numDisjointSets() {return n;}

	public boolean isSameSet(int i,int j) {
		return findSet(i)==findSet(j);
	}

	public int findSet(int i) {
		return (parent[i]==i)? i : (parent[i]=findSet(parent[i]));
	}
		
	}

	

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}