Единственное ограничение между простой и сложной версиями — ограничения.
Вам задано \(n\) отрезков на координатной оси \(OX\). Отрезки могут пересекаться, вкладываться или даже совпадать. \(i\)-й отрезок равен \([l_i; r_i]\) (\(l_i \le r_i\)) и покрывает все такие целочисленные точки \(j\), что \(l_i \le j \le r_i\).
Целочисленная точка называется плохой, если она покрыта строго больше, чем \(k\) отрезками.
Ваша задача — удалить минимальное количество отрезков таким образом, чтобы плохих точек не осталось вообще.
Выходные данные
В первой строке выведите одно целое число \(m\) (\(0 \le m \le n\)) — минимальное количество отрезков, которое надо удалить, чтобы не осталось плохих точек.
Во второй строке выведите \(m\) различных целых чисел \(p_1, p_2, \dots, p_m\) (\(1 \le p_i \le n\)) — индексы отрезков, которые вы удаляете, в любом порядке. Если существует несколько возможных ответов, вы можете вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9
|
3
4 6 7
|
|
2
|
5 1
29 30
30 30
29 29
28 30
30 30
|
3
1 4 5
|
|
3
|
6 1
2 3
3 3
2 3
2 2
2 3
2 3
|
4
1 3 5 6
|