圣诞老人为 $$$n$$$ 孩子准备了装有礼物的盒子,每个孩子一盒。礼物的种类有$$$m$$$:气球、糖果、巧克力棒、玩具车……孩子收到两件相同种类的礼物会很失望,所以一个盒子里的各种礼物都是不同的。
包装好所有礼物后,圣诞老人意识到不同的盒子可以容纳不同数量的礼物。这对孩子们不公平,所以他决定在盒子之间移动一些礼物,并使它们的尺寸相似。经过所有移动后,盒子中的最大和最小礼物数量之间的差异必须尽可能小。每个盒子里的所有礼物仍然应该是不同的。圣诞老人希望尽快完成工作,因此他希望尽量减少完成任务所需的动作次数。
给定每个盒子中的礼物组,找到盒子之间礼物移动的最短序列,使最小和最大盒子的尺寸差异最小化,并保持每个盒子中的所有礼物不同。
输入
第一行输入包含两个整数$$$n$$$、$$$m$$$ ($$$1 \leq n, m \leq 100\ 000$$$)、盒子数量和礼物种类数量。用从 $$$1$$$ 到 $$$m$$$ 的整数表示礼物。
以下 $$$n$$$ 行中的每一行都包含一个框的描述。它以整数 $$$s_i$$$ ($$$s_i \geq 0$$$) 开头,即盒子里礼物的数量,$$$s_i$$$ 后面是 $$$1$$$ 和 $$$m$$$ 之间的不同整数,表示盒子里礼物的种类。
所有盒子中的礼物总数不超过$$$500\,000$$$。
输出
在输出的第一行打印一个整数$$$k$$$,最短序列中使框的大小最多相差一个的移动次数。然后打印 $$$k$$$ 行,以按照执行顺序描述动作。每个运动由三个整数 $$$from_i$$$、$$$to_i$$$、$$$kind_i$$$ 描述。这意味着 $$$kind_i$$$ 的礼物从编号为 $$$from_i$$$ 的盒子移动到编号为 $$$to_i$$$ 的盒子。框按照输入中给出的顺序从 1 开始编号。
在执行移动时,类型为 $$$kind_i$$$ 的礼物必须出现在编号为 $$$from_i$$$ 的框中。完成所有动作后,每个盒子不得包含两件相同类型的礼物。
如果有多个最优解,则输出其中任意一个。
示例
输入复制
3 5 5 1 2 3 4 5 2 1 2 2 3 4
输出复制
2 1 3 5 1 2 3