Рейнджеры в автобусе

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!

Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.

Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса $n$ рядов сидений, в каждом из которых по два места --- слева и справа от прохода. Ряды пронумерованы от $1$ до $n$, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли $k$ человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

• Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
• Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
• Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
• Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
• Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

Про каждого из рейнджеров Рита хочет узнать, кто из $k$ пассажиров мог бы быть им. По известным местам, куда садились пассажиры, выведите эту информацию. Обратите внимание, что совсем не обязательно все рейнджеры ехали на этом автобусе.

В первой строке входного файла заданы числа $n$ и $k$ --- количество рядов в автобусе и количество пассажиров ($1\leq n\leq 10^9$, $1\leq k\leq min(2\cdot10^5,2n)$).

В следующих $k$ строках описаны пассажиры в том порядке, в котором они заходили в автобус.

В $i$-й из этих строк заданы числа $x\_i$ и $y\_i$ --- место, на которое сел $i$-й пассажир ($1\leq x\_i\leq n$, $1\leq y\_i\leq 2$), $x\_i$ --- это номер ряда, $y\_i=1$, если это место слева от прохода, и $y\_i=2$, если справа.

Все места, на которые сели пассажиры, различны.

В первой строке выходного файла выведите число $s\_1$ --- количество пассажиров, которые могли бы быть красным рейнджером, а затем, через пробел, $s\_1$ чисел --- номера этих пассажиров в порядке возрастания (пассажиры нумеруются с $1$ по $k$ в том порядке, в котором они заданы во входном файле).

В следующих четырёх строках выведите в том же формате информацию об остальных рейнджерах: синем, чёрном, жёлтом и розовом соответственно.

На этой картинке показаны места, на которые садились пассажиры в примере.