现在是 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$$$摧毁的宇宙飞船的索引。
示例
输入 #1
3 5 0 1 4 2 5 4 1 1 1 4
输出 #1
4 2 1 3 2 1 4 2 5
注意
SQL火箭只能摧毁第四艘宇宙飞船。 OMG 火箭筒可以摧毁第 1、第 4 或第 5 艘宇宙飞船中的两艘,而认知光束可以摧毁 $$$[1,4]$$$ 区间内的任何宇宙飞船。摧毁飞船的最大数量为 4 艘,一种可能的计划是 SQL 火箭摧毁第 4 艘飞船,OMG 火箭筒摧毁第 1 艘和第 5 艘飞船,认知光束摧毁第 2 艘飞船。