CF1045A.Last chance

It is the year 2969. 1000 years have passed from the moon landing. Meanwhile, the humanity colonized the Hyperspace™ and lived in harmony.

Until we realized that we were not alone.

Not too far away from the Earth, the massive fleet of aliens' spaceships is preparing to attack the Earth. For the first time in a while, the humanity is in real danger. Crisis and panic are everywhere. The scientists from all around the solar system have met and discussed the possible solutions. However, no progress has been made.

The Earth's last hope is YOU!

Fortunately, the Earth is equipped with very powerful defense systems made by MDCS. There are $N$ aliens' spaceships which form the line. The defense system consists of three types of weapons:

• SQL rockets – every SQL rocket can destroy at most one spaceship in the given set.
• Cognition beams – every Cognition beam has an interval $[l,r]$ and can destroy at most one spaceship in that interval.
• OMG bazooka – every OMG bazooka has three possible targets, however, each bazooka can destroy either zero or exactly two spaceships. In addition, due to the smart targeting system, the sets of the three possible targets of any two different OMG bazookas are disjoint (that means that every ship is targeted with at most one OMG bazooka).

Your task is to make a plan of the attack which will destroy the largest possible number of spaceships. Every destroyed spaceship should be destroyed with exactly one weapon.

现在是公元2969年，距离人类首次登月已过去1000年。在此期间，人类成功殖民了“超空间™”（Hyperspace™），并和谐地生活着。

直到我们意识到：我们并不孤单。

在距地球不远的地方，一支庞大的外星飞船舰队正准备进攻地球。人类许久以来首次真正陷入危机。恐慌与危难席卷各地。太阳系内所有科学家齐聚一堂，共同商讨可能的应对方案，却始终毫无进展。

地球最后的希望——就是你！

幸运的是，地球配备了由MDCS公司研制的极为强大的防御系统。目前共有 $N$ 艘外星飞船排成一条直线。该防御系统包含三种武器：

• SQL火箭：每枚SQL火箭最多可摧毁给定集合中的一艘飞船；
• 认知光束（Cognition beams）：每道认知光束对应一个区间 $[l,r]$，最多可摧毁该区间内的一艘飞船；
• OMG火箭筒（OMG bazooka）：每支OMG火箭筒有三个可能的攻击目标，但每支火箭筒只能摧毁零艘或恰好两艘飞船。此外，得益于智能瞄准系统，任意两支不同的OMG火箭筒的三目标集合互不相交（即：每艘飞船至多被一支OMG火箭筒瞄准）。

你的任务是制定一项攻击计划，在满足以下约束的前提下，摧毁尽可能多的飞船：
每艘被摧毁的飞船必须且仅能被一种武器摧毁。

The first line contains two integers: the number of your weapons $N$ $(1\leq N\leq 5000)$ and the number of spaceships $M$ $(1\leq M\leq 5000)$.

In the next $N$ lines, each line starts with one integer that represents type (either 0, 1 or 2). If the type is 0, then the weapon is SQL rocket, the rest of the line contains strictly positive number $K$ $(\sum{K} \leq 100 000)$ and array $k_i$ $(1\leq k_i\leq M)$ of $K$ integers. If the type is 1, then the weapon is Cognition beam, the rest of the line contains integers $l$ and $r$ $(1\leq l\leq r\leq M)$. If the type is 2 then the weapon is OMG bazooka, the rest of the line contains distinct numbers $a$, $b$ and $c$ $ (1 \leq a,b,c \leq M)$.

第一行包含两个整数：你的武器数量 $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$ 个整数构成的数组 $k_i$（其中 $1\leq k_i\leq M$）；
• 若类型为 1，则该武器为认知光束，该行其余部分包含两个整数 $l$ 和 $r$（满足 $1\leq l\leq r\leq M$）；
• 若类型为 2，则该武器为 OMG 便携式火箭筒，该行其余部分包含三个互不相同的整数 $a$、$b$ 和 $c$（满足 $1 \leq a,b,c \leq M$）。

The first line should contain the maximum number of destroyed spaceships — $X$.

In the next $X$ lines, every line should contain two numbers $A$ and $B$, where $A$ is an index of the weapon and $B$ is an index of the spaceship which was destroyed by the weapon $A$.

第一行应包含被摧毁的飞船的最大数量 — $X$。

接下来的 $X$ 行中，每行应包含两个数字 $A$ 和 $B$，其中 $A$ 是武器的编号，$B$ 是被武器 $A$ 摧毁的飞船的编号。

SQL rocket can destroy only 4th spaceship. OMG Bazooka can destroy two of 1st, 4th or 5th spaceship, and Cognition beam can destroy any spaceship from the interval $[1,4]$. The maximum number of destroyed spaceship is 4, and one possible plan is that SQL rocket should destroy 4th spaceship, OMG bazooka should destroy 1st and 5th spaceship and Cognition beam should destroy 2nd spaceship.

SQL 火箭只能摧毁第 4 号飞船。OMG 巴祖卡火箭可摧毁第 1、第 4 或第 5 号飞船中的任意两艘，而认知光束可摧毁区间 $[1,4]$ 内的任意一艘飞船。最多可摧毁 4 艘飞船，一种可行方案是：SQL 火箭摧毁第 4 号飞船，OMG 巴祖卡火箭摧毁第 1 号和第 5 号飞船，认知光束摧毁第 2 号飞船。