29003번 - Рейнджеры в автобусе 다국어

문제

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

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

Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса $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$ в том порядке, в котором они заданы во входном файле).

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

제한

노트

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