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.ByteArrayInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class d {

	static class Solver {

		int N, K;
		Seg segs[];
		
		void solve(FastScanner s, PrintWriter out) {
			N = s.nextInt(); K = s.nextInt(); segs = new Seg[N];
			PriorityQueue<Event> q = new PriorityQueue<>();
			for(int i = 0, l, r; i < N; i++) {
				l = s.nextInt() - 1; r = s.nextInt() - 1;
				segs[i] = new Seg(l, r);
				q.add(new Event(l, 1, segs[i]));
				q.add(new Event(r + 1, -1, segs[i]));
			}
			TreeSet<Seg> cur = new TreeSet<>();
			int idx = 0;
			Event ee;
			ArrayList<Integer> removed = new ArrayList<>();
			while(!q.isEmpty()) {
				while(!q.isEmpty() && q.peek().at == idx) {
					ee = q.poll();
					if(ee.type == 1)
						cur.add(ee.s);
					else
						cur.remove(ee.s);
				}
				while(cur.size() > K)
					removed.add(cur.pollFirst().id);
				idx++;
			}
			out.println(removed.size());
			for(int x : removed) out.print(x + " ");
			out.println();
		}
		
		static class Event implements Comparable<Event> {
			int at, type; Seg s;
			Event(int aa, int t, Seg ss) { at = aa; type = t; s = ss; }
			public int compareTo(Event E) { return at - E.at; }
		}
		
		static class Seg implements Comparable<Seg> {
			int l, r, id; static int ID = 1;
			Seg(int ll, int rr) { l = ll; r = rr; id = ID++; }
			public int compareTo(Seg S) {
				if (r == S.r)
					return id - S.id;
				return S.r - r;
			}
		}

	}

	public static void main(String[] args) {
		FastScanner s = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		new Solver().solve(s, out);
		out.close();
		s.close();
	}

	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1 << 22];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		public FastScanner(File f) throws FileNotFoundException {
			this(new FileInputStream(f));
		}

		public FastScanner(String s) {
			this.stream = new ByteArrayInputStream(s.getBytes(StandardCharsets.UTF_8));
		}

		void close() {
			try {
				stream.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		public int[] nextIntArray(int N) {
			int[] ret = new int[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextInt();
			return ret;
		}

		public int[][] next2DIntArray(int N, int M) {
			int[][] ret = new int[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextIntArray(M);
			return ret;
		}

		public long[] nextLongArray(int N) {
			long[] ret = new long[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextLong();
			return ret;
		}

		public long[][] next2DLongArray(int N, int M) {
			long[][] ret = new long[N][];
			for (int i = 0; i < N; i++)
				ret[i] = nextLongArray(M);
			return ret;
		}

		public double[] nextDoubleArray(int N) {
			double[] ret = new double[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDouble();
			return ret;
		}

		public double[][] next2DDoubleArray(int N, int M) {
			double[][] ret = new double[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDoubleArray(M);
			return ret;
		}

	}

}