Змагання#481

Змагання

1 секунда
256 мегабайтів
Легка

Є команд, запрошених на змагання. Під час виступу спонсора кожна команда повинна бути присутня більшу частину часу. Якщо команда відсутня більше ніж безперервних хвилин у будь-який момент, ця команда буде дискваліфікована.

Виступ спонсора починається о . Спочатку, о , всі команди присутні.

Вам дано подій. Кожна подія описується двома цілими числами time та idx:

Коли відбувається подія (\texttt{time}, \texttt{idx}):

Між подіями стан кожної команди (присутня чи відсутня) не змінюється.

Нехай — максимальний час серед усіх подій. Виступ спонсора закінчується о . Для кожної команди розгляньте всі її безперервні інтервали відсутності протягом часового сегмента . Якщо існує такий інтервал, довжина якого є суворо більшою за , то ця команда дискваліфікована. Відсутність протягом точно безперервних хвилин дозволена.

Визначте, які команди дискваліфіковані.

Вхідні дані

Перший рядок містить три цілі числа , та (1 \le N \le 200000, 0 \le Q \le 200000, 1 \le X \le 10^9).

Кожен з наступних рядків містить два цілі числа time та idx (0 \le \texttt{time} \le 10^9, 1 \le \texttt{idx} \le N) — одна подія.

Події подані в довільному порядку. Для кожної команди жодні дві події не мають однакового часу.

Вихідні дані

У першому рядку виведіть кількість дискваліфікованих команд.

У другому рядку виведіть індекси всіх дискваліфікованих команд у зростаючому порядку, розділені пробілами.

Приклади

Приклад 1

Loading
Loading

Примітка

У прикладі, N = 3, X = 4. Усі команди присутні о . Події в хронологічному порядку:

  • час , команда йде;

  • час , команда йде;

  • час , команда повертається;

  • час , команда повертається.

Останній час події T = 8, тому ми розглядаємо інтервал .

  • Команда відсутня з часу до часу (тривалість ). Оскільки 5 > X = 4, команда дискваліфікована.

  • Команда відсутня з часу до часу (тривалість ). Це також більше ніж , тому команда дискваліфікована.

  • Команда ніколи не йде, тому вона завжди присутня і не дискваліфікована.

Отже, дискваліфікованими командами будуть 1 і 2.