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:
//Created by Aminul on 10/22/2019.

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class D_3 {
    public static void main(String[] args)throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), k = in.nextInt();
        Pair pairs[] = new Pair[n];
        for (int i = 0; i < n; i++) {
            pairs[i] = new Pair(i + 1, in.nextInt(), in.nextInt());
        }
        Arrays.sort(pairs);
        ArrayDeque<Integer> res = new ArrayDeque<>();
        SegTree segTree = new SegTree((int)2e5 + 10);
        for(Pair p : pairs) {
            if(segTree.query(p.f, p.s) < k) {
                segTree.update(p.f, p.s, 1);
            } else {
                res.addLast(p.idx);
            }
        }
        pw.println(res.size());
        for (int i : res) pw.print(i + " ");
        pw.println();
          
        pw.close();
    }

    static class Pair implements Comparable<Pair> {
        int idx, f, s;

        Pair(int idx, int F, int S) {
            this.idx = idx;
            f = F;
            s = S;
        }

        public int compareTo(Pair p) {
            if (s != p.s) return s - p.s;
            if (f != p.f) return f - p.f;
            return idx - p.idx;
        }

        public String toString() {
            return f + " " + s;
        }
    }

    static class SegTree {
        int n, seg[], lazy[];
        int DEFAULT_VALUE = 0; // change here

        SegTree(int N) {
            n = N;
            seg = new int[4 * n];
            lazy = new int[4 * n];
        }

        int op(int a, int b) { // change here
            return max(a, b);
        }

        void pushDown(int p, int l, int r) {
            if (lazy[p] == 0) return;
            seg[l] += lazy[p];
            lazy[l] += lazy[p];
            seg[r] += lazy[p];
            lazy[r] += lazy[p];
            lazy[p] = 0;
        }

        void update(int l, int r, int val) {
            update(1, 1, n, l, r, val);
        }

        void update(int p, int s, int e, int a, int b, int val) {
            if (s >= a && e <= b) {
                seg[p] += val;
                lazy[p] += val;
                return;
            }
            if (s > b || s > e || e < a) return;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            pushDown(p, l, r);
            update(l, s, m, a, b, val);
            update(r, m + 1, e, a, b, val);
            seg[p] = op(seg[l], seg[r]);
        }

        int query(int l, int r) {
            return query(1, 1, n, l, r);
        }

        int query(int p, int s, int e, int a, int b) {
            if (s >= a && e <= b) {
                return seg[p];
            }
            if (s > e || s > b || e < a) return DEFAULT_VALUE;
            int m = (s + e) / 2, l = 2 * p, r = 2 * p + 1;
            pushDown(p, l, r);
            return op(query(l, s, m, a, b), query(r, m + 1, e, a, b));
        }
    }


    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}