Рейнджеры в автобусе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
seats.in
вывод
seats.out

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

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

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

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

Входные данные

В первой строке входного файла заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 109, 1 ≤ k ≤ min(2·105, 2n)).

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

В i-й из этих строк заданы числа xi и yi — место, на которое сел i-й пассажир (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2), xi — это номер ряда, yi = 1, если это место слева от прохода, и yi = 2, если справа.

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

Выходные данные

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

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

Система оценки

Первая группа тестов состоит из тестов, для которых выполняются ограничения n, k ≤ 5000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 25 баллов.

Вторая группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 5000. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 25 баллов.

Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 50 баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Запросить информацию о проверке» на вкладке «Решения».

Пример

Входные данные
3 4
1 1
1 2
3 2
2 1
Выходные данные
3 1 2 4
1 2
0
1 3
4 1 2 3 4

Примечание

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