Единственное ограничение между простой и сложной версиями — ограничения.
Вам задано \(n\) отрезков на координатной оси \(OX\). Отрезки могут пересекаться, вкладываться или даже совпадать. \(i\)-й отрезок равен \([l_i; r_i]\) (\(l_i \le r_i\)) и покрывает все такие целочисленные точки \(j\), что \(l_i \le j \le r_i\).
Целочисленная точка называется плохой, если она покрыта строго больше, чем \(k\) отрезками.
Ваша задача — удалить минимальное количество отрезков таким образом, чтобы плохих точек не осталось вообще.
Первая строка входных данных содержит два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — количество отрезков и максимальное количество отрезков, которым может быть покрыта каждая целочисленная точка.
Следующие \(n\) строк содержат отрезки. \(i\)-я строка содержит два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le 2 \cdot 10^5\)) — границы \(i\)-го отрезка.
В первой строке выведите одно целое число \(m\) (\(0 \le m \le n\)) — минимальное количество отрезков, которое надо удалить, чтобы не осталось плохих точек.
Во второй строке выведите \(m\) различных целых чисел \(p_1, p_2, \dots, 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач