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

public class TooManySegments {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = 1;
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }

    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt(), k = in.nextInt();
        int[][] arr = new int[n][];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[]{in.nextInt(), in.nextInt(), i};
        }
        Arrays.sort(arr, (a, b) -> (a[0] - b[0]));
        int cnt = 0;
        TreeMap<Integer, List<Integer>> mp = new TreeMap<>();
        List<Integer> ans = new ArrayList<>();
        int tot = 0;
        for (int i = 0; i < n; i++) {
            tot++;
//            System.out.println(mp);
            if (mp.size() == 0){
                List<Integer> ls = new ArrayList<>();
                ls.add(arr[i][2]);
                mp.put(arr[i][1], ls);
            }else{
                while (mp.size() > 0 && mp.firstKey() < arr[i][0]) {
//                    System.out.println("shit");
                    tot -= mp.get(mp.firstKey()).size();
                    mp.remove(mp.firstKey());
                }
                if (mp.containsKey(arr[i][1])){
                    mp.get(arr[i][1]).add(arr[i][2]);
                }else{
                    List<Integer> ls = new ArrayList<>();
                    ls.add(arr[i][2]);
                    mp.put(arr[i][1], ls);
                }
                if (tot > k){
                    Integer key = mp.lastKey();
                    List<Integer> ls = mp.get(key);
                    int idx = ls.get(ls.size() - 1);
                    ans.add(idx);
                    ls.remove(ls.size() - 1);
                    if (ls.size() == 0) mp.remove(key);
//                    System.out.println(arr[idx][0]+" "+arr[idx][1]);
                    cnt++;
                    tot--;
                }
            }
//            System.out.println(mp);
        }
        out.println(cnt);
        for(int x : ans){
            out.print((x + 1)+" ");
        }
    }
}