题目描述

简单难度与困难难度的唯一差别是 $n,k$ 的范围。

给予 $n$ 条线段，这些线段可以有重叠部分甚至完全重叠在一起。第 $i$ 条线段 $[l_i,r_i](l_i\le r_i)$ 覆盖了所有整数点 $j$ 满足 $l_i\le j\le r_i$。

如果一个整数点被超过 $k$ 条线段覆盖，那么就称之为 bad point（下文以坏点代替）。

你的任务是去掉最少的线段使得没有坏点的存在。

输入格式

输入第一行是两个正整数，$n$ 和 $k$ $(1\le k\le n\le 2\times 10^5)$。

然后有 $n$ 行，每行两个正整数，其中的第 $i$ 行表示第 $i$ 条线段的两个端点 $l_i$ 和 $r_i$ $(1\le l_i\le r_i\le 2\times 10^5)$。

输出格式

输出的第一行为一个整数 $m$ $(0\le m\le n)$，表示最少去掉多少条线段可以不再存在坏点。

第二行输出 $m$ 个不同的正整数 $p_1,p_2,\cdots p_m$ $(1\le p_i\le n)$ 表示你移除了的线段的编号。如果有不止一个答案，可以输出任意一个满足条件的答案。

样例

7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

3
4 6 7 

5 1
29 30
30 30
29 29
28 30
30 30

3
1 4 5 

6 1
2 3
3 3
2 3
2 2
2 3
2 3

4
1 3 5 6