Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D2. Too Many Segments (hard version)

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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 \le r_i$$$) and it covers all integer points $$$j$$$ such that $$$l_i \le j \le 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 \le k \le n \le 2 \cdot 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 \le l_i \le r_i \le 2 \cdot 10^5$$$) — the endpoints of the $$$i$$$-th segment.

Output

In the first line print one integer $$$m$$$ ($$$0 \le m \le 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, \dots, p_m$$$ ($$$1 \le p_i \le 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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/29/2020 10:25:17 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|