markdown

A. 最后的机会

每个测试的时间限制：$2$ 秒
每个测试的内存限制：$128$ 兆字节
输入：标准输入
输出：标准输出

题目描述

现在是公元 $2969$ 年，距离人类首次登月已经过去了 $1000$ 年。在此期间，人类殖民了超空间™，并过着和谐的生活。

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

在距离地球不远的地方，一支庞大的外星飞船舰队正准备攻击地球。这是人类许久以来第一次面临真正的危险。危机和恐慌无处不在。来自整个太阳系的科学家们聚集在一起，讨论可能的解决方案。然而，没有任何进展。

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

幸运的是，地球配备了由 MDCS 制造的非常强大的防御系统。共有 $M$ 艘外星飞船排成一条线。防御系统由三种类型的武器组成：

• SQL 火箭：每枚 SQL 火箭最多可以摧毁给定集合中的一艘飞船。
• 认知光束：每束认知光束有一个区间 $[l, r]$，最多可以摧毁该区间内的一艘飞船。
• OMG 火箭筒：每个 OMG 火箭筒有三个可能的目标，但每个火箭筒要么摧毁零艘，要么恰好摧毁两艘飞船。此外，由于智能瞄准系统，任意两个不同 OMG 火箭筒的三个可能目标集合互不相交（也就是说，每艘飞船最多被一个 OMG 火箭筒瞄准）。

你的任务是制定一个攻击计划，以摧毁尽可能多的飞船。每艘被摧毁的飞船必须恰好由一种武器摧毁。

输入

第一行包含两个整数：武器数量 $N$（$1 \le N \le 5000$）和飞船数量 $M$（$1 \le M \le 5000$）。

接下来的 $N$ 行中，每行以一个整数开头，表示武器类型（$0$、$1$ 或 $2$）。

• 如果类型是 $0$，则该武器是 SQL 火箭，该行剩余部分包含一个严格正数 $K$（$\sum K \le 100000$）和一个由 $K$ 个整数组成的数组 $a_i$（$1 \le a_i \le M$）。
• 如果类型是 $1$，则该武器是认知光束，该行剩余部分包含两个整数 $l$ 和 $r$（$1 \le l \le r \le M$）。
• 如果类型是 $2$，则该武器是 OMG 火箭筒，该行剩余部分包含三个不同的整数 $a$、$b$ 和 $c$（$1 \le a, b, c \le M$）。

输出

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

接下来的 $D$ 行中，每行应包含两个数字 $w$ 和 $s$，其中 $w$ 是武器的索引，$s$ 是被武器 $w$ 摧毁的飞船的索引。

样例

输入

3 5
0 1 4
2 5 4 1
1 1 4

输出

4
2 1
3 2
1 4
2 5

注释

SQL 火箭只能摧毁第 $4$ 艘飞船。OMG 火箭筒可以摧毁第 $1$、$4$ 或 $5$ 艘飞船中的两艘，认知光束可以摧毁区间 $[1, 4]$ 内的任意一艘飞船。被摧毁飞船的最大数量是 $4$，一种可行的方案是：SQL 火箭摧毁第 $4$ 艘飞船，OMG 火箭筒摧毁第 $1$ 艘和第 $5$ 艘飞船，认知光束摧毁第 $2$ 艘飞船。