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


public class Solution {
    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i, j, MAXN = 200001, ind = 0, x, y, c = 0;
        int n = in.nextInt();
        int k = in.nextInt();
        Integer arr[][] = new Integer[n][2];
        for (i = 0; i < n; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }
        Integer pos[] = new Integer[n];
        int ans[] = new int[n];
        for (i = 0; i < n; i++)
            pos[i] = i;
        Arrays.sort(pos, (a, b) -> Integer.compare(arr[a][0], arr[b][0]));
        TreeSet<Integer> set = new TreeSet<>((a, b) -> (int)arr[a][1] != arr[b][1] ?
                Integer.compare(arr[a][1], arr[b][1]) : Integer.compare(a, b));
        SegmentTree st = new SegmentTree(new long[MAXN]);
        for (i = 0; i < MAXN; i++) {
            while (ind < n && arr[pos[ind]][0] <= i) {
                st.update(arr[pos[ind]][0], arr[pos[ind]][1], 1);
                set.add(pos[ind]);
                ind++;
            }
            y = (int) st.query(i, i);
            while (y > k) {
                x = set.pollLast();
                st.update(arr[x][0], arr[x][1], -1);
                ans[c++] = x + 1;
                y--;

            }
            if (ind >= n)
                break;
        }
        sb.append(c).append("\n");
        for (i = 0; i < c; i++)
            sb.append(ans[i]).append(" ");
        System.out.println(sb);

    }
}
class SegmentTree {
    long tree[], lazy[];
    int N;

    public SegmentTree(long arr[]) {
        N = 1;
        while (N < arr.length)
            N = N * 2;
        tree = new long[2 * N - 1];
        lazy = new long[2 * N - 1];
        for (int i = 0; i < arr.length; i++)
            tree[i + N - 1] = arr[i];
        for (int i = N - 2; i >= 0; i--)
            tree[i] = tree[2 * i + 1] + tree[2 * i + 2];

    }

    public void push(int i, int s, int e) {
        if (lazy[i] != 0) {
            tree[i] += (s - e + 1) * lazy[i];
            if (s != e) {
                lazy[2 * i + 1] += lazy[i];
                lazy[2 * i + 2] += lazy[i];
            }
            lazy[i] = 0;
        }
    }

    public long query(int l, int r) {
        return query(0, 0, N - 1, Math.min(l, r), Math.max(l, r));
    }

    public long query(int i, int s, int e, int l, int r) {
        push(i, s, e);
        if (l > e || r < s || s > e)
            return 0;
        if (s >= l && e <= r) {
            return tree[i];
        }
        int mid = (s + e) / 2;
        return query(2 * i + 1, s, mid, l, r) + query(2 * i + 2, mid + 1, e, l, r);

    }

    public void update(int l, int r, long v) {
        update(0, 0, N - 1, Math.min(l, r), Math.max(l, r), v);
    }

    public void update(int i, int s, int e, int l, int r, long v) {
        push(i, s, e);
        if (l > e || r < s || s > e)
            return;
        if (s >= l && e <= r) {
            lazy[i] += v;
            push(i, s, e);
            return;
        }
        int mid = (s + e) / 2;
        update(2 * i + 1, s, mid, l, r, v);
        update(2 * i + 2, mid + 1, e, l, r, v);

    }
}
class Node{
    int val,pos;
    public Node(int a,int b)
    {
        this.val=a;
        this.pos=b;
    }
}
class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}