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.math.*;
import java.text.DecimalFormat;
import java.util.*;
 
public class MainClass
{
	
	InputStream in;
	PrintWriter out;
	
	long mod=(long)1e9+7;
	int MAX=(int)2e5+7;
	double eps=1e-6;
	String high="";
	
	void solve() 
	{
		int n = ni();
		int k = ni();
		int []cnt = new int[MAX];
		ArrayList<Pair> seg = new ArrayList<Pair>(MAX);
		ArrayList<ArrayList<Integer>> ev = new ArrayList<ArrayList<Integer>>(MAX);
		for(int i = 0; i < MAX; i++)
			ev.add(new ArrayList<Integer>());
		
		seg.add(new Pair(-1, -1));
		
		for(int i = 1; i <= n; i++) {
			int li = ni();
			int ri = ni();
			seg.add(new Pair(li, ri));
			cnt[li]++;
			cnt[ri + 1]--;
			ev.get(li).add(i);
			ev.get(ri + 1).add(-i);
		}

		for(int i = 1; i < MAX; i++)
			cnt[i] += cnt[i - 1];
		
		int curSub = 0;
		int []sub = new int[MAX];
		int []ans = new int[MAX];
		TreeSet<Pair> curSegs = new TreeSet<Pair>();
		
		for(int i = 1; i < MAX; i++) {
			curSub += sub[i];
			
			for(int it : ev.get(i)) {
				if(it > 0) {
					curSegs.add(new Pair(seg.get(it).y, it));
				} else {
					curSegs.remove(new Pair(seg.get(-it).y, -it));
				}
			}
		
			while(cnt[i] - curSub > k) {
				
				if(curSegs.isEmpty()) break;
				
				int pos = curSegs.last().y;
				curSegs.remove(curSegs.last());
				curSub++;
				--sub[seg.get(pos).y + 1];
				ans[pos] = 1;
			}
		}
		
		out.println(Arrays.stream(ans).sum());
		
		for(int i = 1; i < MAX; i++) {
			if(ans[i] > 0)
				out.print(i + " ");
		}
	}
	
	double dist(double x1,double y1,double x2,double y2)
	{
		return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	}
	
	class Pair implements Comparable<Pair>
	{
		int x;
		int y;
		Pair(int a,int b)
		{
			x=a;
			y=b;
		}
		
		@Override
		public boolean equals(Object o) 
		{
			Pair other = (Pair)o;
			return x == other.x && y == other.y;
		}
		public String toString()
		{
			return x+" "+y;
		}
		
		@Override
		public int compareTo(Pair o) 
		{
			if (x==o.x)
				return Integer.compare(y, o.y);
			else
				return Integer.compare(x, o.x);
		}
		@Override public int hashCode() 
		{
			return Objects.hash(x, y);
		}
	}
	
	long pow(long x, long n, long M) {
		x%=M;
		long result = 1;
		while (n > 0) {
			if (n % 2 == 1)
				result = (result * x) % M;
			x = (x * x) % M;
			n = n / 2;
		}
		return result;
	}
	
	long modInverse(long A, long M) {
		extendedEuclid(A, M);
		return (EEx % M + M) % M;
	}
	long EEd, EEx, EEy;
	
	void extendedEuclid(long A, long B) {
		if (B == 0) {
			EEd = A;
			EEx = 1;
			EEy = 0;
		} else {
			extendedEuclid(B, A % B);
			long temp = EEx;
			EEx = EEy;
			EEy = temp - (A / B) * EEy;
		}
	}
	
	int max(int a,int b)
	{
		if(a>b)
			return a;
		else
			return b;
	}
	
	int min(int a,int b)
	{
		if(a>b)
			return b;
		else 
			return a;
	}
	
	long max(long a,long b)
	{
		if(a>b)
			return a;
		else
			return b;
		
	}
	
	
	long min(long a,long b)
	{
		if(a>b)
			return b;
		else 
			return a;
		
	}
	
	long add(long a,long b)
	{
		long x=(a+b);
		while(x>=mod) x-=mod;
		return x;
		
	}
	
	
	long sub(long a,long b)
	{
		long x=(a-b);
		while(x<0) x+=mod;
		return x;
		
	}
	
	
	long mul(long a,long b)
	{
		a%=mod;
		b%=mod;
		long x=(a*b);
		return x%mod;
		
	}
	
	void run() throws Exception 
	{
		String INPUT = "C:/Users/tapan/OneDrive/Desktop/in.txt";
//		oj=false;
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
		
	}
	public static void main(String[] args) throws Exception 
	{
		new MainClass().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() 
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) 
		{
			ptrbuf = 0;
			try 
			{
				lenbuf = in.read(inbuf);
			}
			catch (IOException e) 
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) 
	{
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() 
	{
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() 
	{
		return Double.parseDouble(ns());
	}
	
	private char nc() 
	{
		return (char) skip();
	}
	
	private String ns() 
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) 
		{ // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) 
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) 
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) 
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) 
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() 
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			} 
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			}
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}