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

public class P595D {

   static class Segment implements Comparable<Segment>{

         int index;
         int left;
         int right;

       public Segment(int index, int left, int right) {
           this.index = index;
           this.left = left;
           this.right = right;
       }

       @Override
       public int compareTo(Segment o) {
           if(this.right < o.right){
               return 1;
           }
           if(this.right > o.right){
               return  -1;
           }
           return 0;
       }
   }

    public static void main(String args[]){
         Reader s = new Reader();
         int n = s.nextInt();
         int k = s.nextInt();


         List<Segment> lis = new ArrayList<>();

         for(int i=0;i<n;i++){
             lis.add(new Segment(i+1,s.nextInt(),s.nextInt()));
         }

         Collections.sort(lis, new Comparator<Segment>() {
             @Override
             public int compare(Segment o1, Segment o2) {
                 if(o1.left < o2.left){
                     return -1;
                 }
                 if(o1.left>o2.left){
                     return 1;
                 }
                 return 0;
             }
         });

        List<Integer> ans = new ArrayList<>();
        PriorityQueue<Segment> pq = new PriorityQueue<>();
        int range[] = new int[200002];
        int sp = 0;
        int total = 0;
        for(int i=1;i<range.length-1;i++){

             while (sp<lis.size() && i == lis.get(sp).left){
                 range[lis.get(sp).right + 1]--;
                 pq.add(lis.get(sp));
                 total++;
                 sp++;

             }

             total += range[i];

             while (total > k){
                    Segment temp = pq.remove();
                    ans.add(temp.index);
                    range[temp.right + 1]++;
                    total--;
             }

        }

        System.out.println(ans.size());

        for(int x:ans){
            System.out.print(x+" ");
        }
    }
    static class Reader {

        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public Reader() {
            this(System.in);
        }

        public Reader(InputStream is) {
            mIs = is;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();

            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.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 next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        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 boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

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

    }

}