A. Последний шанс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

2969-й год. Прошло 1000 лет с момента посадки на луну. Человечество колонизировало Гиперпространство и жило в гармонии.

Жило, пока мы не поняли, что мы не одни.

Не очень далеко от Земли многочисленный космический флот инопланетян готовит атаку на Землю. Впервые за долгое время человечеству угрожает реальная опасность. Повсюду паника и кризис. Ученые со всей солнечной системы встретились и обсуждают возможный выход из ситуации. Но пока все усилия тщетны.

Последняя надежда Земли — ВЫ!

К счастью, Земля имеет мощную систему защиты, созданную специалистами из MDCS. Флот инопланетян содержит $$$N$$$ кораблей на одной линии. Система защиты состоит из трех типов вооружения:

  • SQL-ракеты: каждая SQL-ракета может уничтожить не более одного корабля инопланетян из заданного для каждой ракеты набора.
  • лучи Познания: каждому лучу Познания сопоставлен отрезок $$$[l,r]$$$, он может уничтожить не более одного корабля инопланетян из этого отрезка.
  • OMG-базука: каждая OMG-базука имеет ровно три цели и может уничтожить либо ровно ноль, либо ровно два корабля. Кроме того, система прицеливания является «умной», поэтому множества трех целей для любых двух OMG-базук не пересекаются (таким образом, каждый корабль находится под прицелом не более чем одной OMG-базуки).

Ваша задача — найти такой план атаки на корабли инопланетян, чтобы уничтожить максимально возможное количество кораблей. Каждый уничтоженный корабль должен быть уничтожен ровно одним оружием.

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

Первая строка содержит два целых числа — количество оружия $$$N$$$ $$$(1\leq N\leq 5000)$$$ и количество кораблей $$$M$$$ $$$(1\leq M\leq 5000)$$$.

Каждая из следующих $$$N$$$ строк начинается с одного целого числа, которое обозначает тип оружия (0, 1 или 2). Если тип равен 0, то это оружие — SQL-ракета, и далее эта строка содержит строго положительное число $$$K$$$ $$$(\sum{K} \leq 100 000)$$$ и массив $$$k_i$$$ $$$(1\leq k_i\leq M)$$$ из $$$K$$$ целых чисел. Если тип равен 1, то это луч Познания, а строка далее содержит целые числа $$$l$$$ и $$$r$$$ $$$(1\leq l\leq r\leq M)$$$. Если тип равен 2, то это OMG-базука, а строка далее содержит различные числа $$$a$$$, $$$b$$$ и $$$c$$$ $$$ (1 \leq a,b,c \leq M)$$$.

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

Первая строка должна содержать максимальное количество уничтоженных кораблей $$$X$$$.

Каждая из следующих $$$X$$$ строк должна содержать два целых числа $$$A$$$ и $$$B$$$, где $$$A$$$ — номер оружия, а $$$B$$$ — номер корабля, уничтоженного оружием $$$A$$$.

Пример
Входные данные
3 5
0 1 4
2 5 4 1
1 1 4
Выходные данные
4
2 1
3 2
1 4
2 5
Примечание

SQL-ракета может уничтожить только четвертый корабль. OMG-базука может уничтожить два из 1-го, 4-го или 5-го кораблей, а луч Познания может уничтожить любой корабль из отрезка $$$[1,4]$$$. Максимальное количество уничтоженных кораблей равно 4, один из возможных планов — SQL-ракета уничтожает 4-й корабль, OMG-базука уничтожает 1-й и 5-й корабли, а луч Познания уничтожает 2-й корабль.