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.util.*;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;

public class r595p8{

    private static InputReader sc;
    private static PrintWriter pw;

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        InputReader(InputStream stream) {
            this.stream = stream;
        }

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

        int nextInt() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        long nextLong() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        String nextLine() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

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

        public interface SpaceCharFilter {
            boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) {
        sc = new InputReader(System.in);
        pw = new PrintWriter(System.out);

        int t = 1;
        while(t-->0)
            solve();

        pw.flush();
        pw.close();
    }

    private static void solve(){
        int n = sc.nextInt(), k = sc.nextInt();

        TreeSet<Integer> endPoints = new TreeSet<>();
        TreeMap<Integer, HashSet<Integer>> currMap = new TreeMap<>();
        HashMap<Integer, HashSet<Integer>> beginMap = new HashMap<>(), endMap = new HashMap<>();
        TreeSet<Integer> removeSet = new TreeSet<>();
        int l[] = new int[n], r[] = new int[n], count = 0;

        for(int i=0; i<n; i++){
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();

            endPoints.add(l[i]);
            endPoints.add(r[i]+1);

            if(!beginMap.containsKey(l[i]))
                beginMap.put(l[i], new HashSet<>());
            beginMap.get(l[i]).add(i);

            if(!endMap.containsKey(r[i]+1))
                endMap.put(r[i]+1, new HashSet<>());
            endMap.get(r[i]+1).add(i);
        }

        for(int point: endPoints){
            if(beginMap.containsKey(point)){
                for(int index: beginMap.get(point)){
                    if(!currMap.containsKey(r[index]))
                        currMap.put(r[index], new HashSet<>());
                    currMap.get(r[index]).add(index);
                    count++;
                }
            }
            if(endMap.containsKey(point) && currMap.containsKey(point-1)){
                count -= currMap.get(point-1).size();
                currMap.remove(point-1);
//                for(int index: endMap.get(point)){
//                    if(currMap.get(point-1).size() > 1)
//                        currMap.get(point-1).remove(index);
//                    else
//                        currMap.remove(point-1);
//                    count--;
//                }
            }

            while(count > k){
                int lastEndPoint = currMap.lastKey();

                HashSet<Integer> toBeRemoved = new HashSet<>();
                for(int index: currMap.get(lastEndPoint)){
                    removeSet.add(index);
                    toBeRemoved.add(index);
                    count--;

                    if(count == k)
                        break;
                }

                for(int index: toBeRemoved)
                    currMap.get(lastEndPoint).remove(index);

                if(currMap.get(lastEndPoint).isEmpty())
                    currMap.remove(lastEndPoint);
            }
        }

        pw.println(+removeSet.size());

        for(int q: removeSet)
            pw.print(+(q+1)+" ");
    }
}