| Codeforces Round 342 (Div. 2) |
|---|
| Закончено |
Недавно великий комбинатор посетил лягушачьи бои и, поразившись несистемностью правил боёв, решил создать своё увлекательное зрелище, но подчинённое строгим правилам.
Итак, лягушек выставляют на поле, имеющее форму кольца, разделённого на m клеток. Клетки пронумерованы от 1 до m по кругу, после клетки номер m идёт клетка номер 1. i-я лягушка изначально может прыгнуть на ai клеток вперёд.
Лягушки ходят по очереди, начиная с лягушки с номером 1. На своём ходу i-я лягушка прыгает на 
клеток вперёд, сбрасывая с поля всех других лягушек на своём пути, в том числе и ту, которая находится в конечной клетке текущего прыжка. После этого её значение ai уменьшается на количество удалённых во время данного прыжка лягушек. Если ai становится равным нулю или отрицательным, то i-я лягушка не сможет прыгать в дальнейшем.
После того, как лягушка с номером 1 заканчивает свой ход, ходит лягушка с номером 2, затем лягушка с номером 3 и так далее. После того, как сходит лягушка с номером n, снова ходит лягушка с номером 1. Если лягушка с каким-то номером уже была сброшена с поля, то считается, что она всегда пропускает свой ход.
Великому комбинатору уже не терпится узнать, какие из лягушек в конце концов останутся на поле. Помогите ему узнать это.
В первой строке содержатся два числа n и m (1 ≤ n ≤ 100 000, 2 ≤ m ≤ 109, n ≤ m) — количество лягушек и размер поля соответственно.
В следующих n строках содержатся описания лягушек. Каждое описание состоит из двух чисел pi и ai (1 ≤ pi, ai ≤ m) — номер клетки, на которой стоит лягушка, и изначальная длина её прыжка соответственно.
Гарантируется, что все значения pi различны.
В первой строке выведите количество лягушек, которые всегда будут на поле.
В следующей строке выведите номера этих лягушек в любом порядке.
3 5
2 1
5 3
4 3
1
3
5 6
1 2
3 4
2 5
5 1
6 1
2
1 4
В первом примере первая лягушка прыгает на одну клетку и оказывается в клетке номер 3. Затем вторая прыгает на 3 клетки и также оказывается в клетке номер 3, удаляя при этом первую лягушку с поля. Величина следующего прыжка у неё теперь равна 2. Третья лягушка прыгает в клетку номер 2. Затем вторая лягушка прыгает в клетку 5. Третья догоняет её и удаляет с поля. На поле осталась только она.
Во втором примере первая лягушка прыгает на две клетки, удаляя с поля лягушек, стоящих на клетках 2 и 3. Величина её следующего прыжка при этом становится равной нулю. Затем прыгает четвёртая лягушка, удаляет с поля пятую и тоже останавливается. В итоге на поле остаются две лягушки.
