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

public class D {

    public static void main(String[] args) {
        InputReader inputReader = new InputReader();

        int n = inputReader.nextInt();
        int k = inputReader.nextInt();

        Segment[] segments = new Segment[n*2];

        for(int i=0, j=0; i<n; i++) {
            int l = inputReader.nextInt();
            int r = inputReader.nextInt();
            segments[j++]=new Segment(l, r, 0, i);
            segments[j++]=new Segment(r, r, 1, i);
        }

        Arrays.sort(segments);
        int ans=0;
        Set<Integer> removed = new LinkedHashSet<>();
        Queue<int[]> openSegments = new PriorityQueue<>((a, b)-> b[0]-a[0]);

        int open=0;
        for(int i=0; i<segments.length; i++) {
            if(segments[i].type==0) {
                open++;
                openSegments.add(new int[]{segments[i].end, segments[i].idx});
                if(open>k) {
                    ans++;
                    removed.add(openSegments.poll()[1]);
                    open--;
                }
            } else {
                if(!removed.contains(segments[i].idx)) {
                    open--;
                }
            }
        }

        System.out.println(ans);
        StringBuilder sb = new StringBuilder();
        for (int num : removed) {
            sb.append(num + 1);
            sb.append(" ");
        }
        System.out.println(sb);
    }

    static class OpenSegment implements Comparable<OpenSegment> {
        int end;
        int idx;

        public OpenSegment(int end, int idx) {
            this.end = end;
            this.idx = idx;
        }

        @Override
        public int compareTo(OpenSegment o) {
            if(this.end!=o.end) return this.end-o.end;
            return this.idx-o.idx;
        }
    }

    static class Segment implements Comparable<Segment> {
        int val;
        int end;
        int type;
        int idx;

        public Segment(int val, int end, int type, int idx) {
            this.val = val;
            this.end = end;
            this.type = type;
            this.idx = idx;
        }

        @Override
        public int compareTo(Segment o) {
            if(this.val != o.val) return this.val - o.val;
            if(this.type != o.type) return this.type-o.type;
            return o.end-this.end;
        }
    }

    static class InputReader {
        private byte[] buf = new byte[16384];
        private int    curChar;
        private int    numChars;

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

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

        public String nextString() {
            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 long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

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

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