1249_D2. Too Many Segments (hard version)_16236
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 
# <editor-fold desc="Fast IO">
# !/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

BUFFER_SIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFER_SIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFER_SIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip('\r\n')


def read_int_list():
    return [int(x) for x in sys.stdin.readline().split()]


def read_int_iter():
    return (int(x) for x in sys.stdin.readline().split())


def read_int():
    return int(input())


def print_int_list(a):
    print(' '.join((str(x) for x in a)))


# </editor-fold>

import heapq


def solve(segs, k):
    deleted = set()

    n = len(segs)
    start = []
    end = []
    for i, seg in enumerate(segs):
        start.append((seg[0], i))
        end.append((seg[1], i))

    start.sort()
    end.sort()

    i = j = 0

    pq = []
    ret = []

    overlap = 0
    while i < n or j < n:
        if i < n and start[i][0] <= end[j][0]:
            if start[i][1] not in deleted:
                overlap += 1
                seg_ind = start[i][1]
                heapq.heappush(pq, (-segs[seg_ind][1], seg_ind))

            i += 1
        else:
            if end[j][1] not in deleted:
                while overlap > k:
                    while True:
                        seg_end, seg_ind = heapq.heappop(pq)
                        if seg_ind not in deleted:
                            break
                    deleted.add(seg_ind)
                    ret.append(seg_ind + 1)
                    overlap -= 1

                if end[j][1] not in deleted:
                    overlap -= 1
                deleted.add(end[j][1])

            j += 1

    ret.sort()
    return len(ret), ret


def main():
    n, k = read_int_iter()

    segs = []
    for _ in range(n):
        segs.append(read_int_list())

    size, ret = solve(segs, k)
    print(size)
    print_int_list(ret)


# DEBUG = True
DEBUG = False

if not DEBUG:
    main()
else:
    # print(solve([[1, 5], [1, 5], [1, 5]], 2))
    # print(solve([[1, 5], [1, 5], [5, 10]], 2))
    print(solve([[2, 2], [1, 2], [1, 1], [2, 2]], 1))
    print(solve([
        [23, 24],
        [24, 24],
        [23, 23],
        [23, 24],
        [23, 24],
        [25, 25],
        [21, 21],
    ], 1))

# Code starts here
