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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1249D
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[] left = new int[N];
         int[] right = new int[N];
         for(int i=0; i < N; i++)
         {
            st = new StringTokenizer(infile.readLine());
            left[i] = Integer.parseInt(st.nextToken());
            right[i] = Integer.parseInt(st.nextToken());
         }
         Range[] arr = new Range[N];
         for(int i=0; i < N; i++)
            arr[i] = new Range(left[i],right[i],i);
         Arrays.sort(arr);
         //store right boundaries
         TreeMap<Integer, ArrayList<Integer>> mset = new TreeMap<Integer, ArrayList<Integer>>();
         int res = 0;
         int size = 0;
         ArrayList<Integer> ls = new ArrayList<Integer>();
         for(Range curr: arr)
         {
            if(!mset.containsKey(curr.r))
               mset.put(curr.r, new ArrayList<Integer>());
            mset.get(curr.r).add(curr.dex);
            size++;
            while(mset.firstKey() < curr.l)
            {
               size -= mset.get(mset.firstKey()).size();
               mset.remove(mset.firstKey());
            }
            if(size > K)
            {
               res += size-K;
               while(mset.size() > 0 && size > K)
               {
                  int key = mset.lastKey();
                  if(mset.get(key).size() > size-K)
                  {
                     for(int i=0; i < (size-K); i++)
                     {
                        ls.add(mset.get(key).get(0)+1);
                        mset.get(key).remove(0);
                     }
                     size = K;
                  }
                  else
                  {
                     size -= mset.get(key).size();
                     for(int x: mset.get(key))
                        ls.add(x+1);
                     mset.remove(key);
                  }
               }
            }
         }
         System.out.println(res);
         for(int x: ls)
            sb.append(x+" ");
         System.out.println(sb);
      }
   }
   class Range implements Comparable<Range>
   {
      public int l;
      public int r;
      public int dex;
      
      public Range(int a, int b, int c)
      {
         l = a;
         r = b;
         dex = c;
      }
      public int compareTo(Range oth)
      {
         return l-oth.l;
      }
   }