#2008. 「CTS 2023」琪露诺的符卡交换

内存限制:512 MiB 时间限制:1000 ms 输入文件:cirno.in 输出文件:cirno.out
题目类型:传统 评测方式:Special Judge
上传者: HHOJ

题目描述

受异变的影响,琪露诺发现封印了自己能力的卡片正在幻想乡中流通。

琪露诺调查之后,发现一共有 种不同的卡片,每种卡片的数量总共恰好是 张,有 个人购买了这些卡片,每个人都恰好买了 张卡片,并且可能会买到相同种类的卡片。

但是琪露诺想要让每个人都正好持有 种卡片,于是她把这 个人聚集在一起,想要通过卡片交换的形式达成她的目的。

琪露诺每次会选择两个人持有的某张卡片进行交换,直到每个人都正好持有 种卡片为止。

由于每次交换都会减少卡片上的魔力,所以琪露诺想要每张卡片最多被交换一次。

但是她对如何进行交换犯了难,于是她转而寻求你的帮助。

你需要告诉她交换的过程,或者告诉她不存在这样的方案。

输入格式

第一行一个正整数 ,表示数据组数。

对于每组数据,第一行一个正整数 ,含义如题所示。

接下来 行,每行输入 个正整数,其中第 行的第 个正整数表示第 个人持有的第 张卡片的种类。

输出格式

对于每组数据,如果不存在能够让每个人都持有 种卡片的方案,输出一行

否则首先输出一行一个正整数 ,表示交换次数。

接下来 行,每行输出四个正整数 ,表示第 个人的第 张卡片,与第 个人的第 张卡片进行一次交换。

注意你需要保证不存在某张卡片被交换了两次,并且交换结束后每个人都正好持有 种卡片。

样例

样例输入

2
3
1 2 2
2 3 3
3 1 1
3
1 2 3
2 3 1
3 2 1

样例输出

2
1 3 3 1
2 3 3 2
0

样例解释

第一组数据,我们第一次交换第一个人的第三张卡牌,和第三个人的第一张卡牌;

第二次交换第二个人的第三张卡牌,和第三个人的第二张卡牌;

一共交换两次,可以使得所有人都持有三种卡牌。

输出其它方案也是被允许的。

第二组数据,因为一开始所有人都持有了三种卡牌,所以无需交换,输出一行 即可。

数据范围

子任务 分):每个人只持有一种卡片。

子任务 分):每个人持有至少 张同一种类的卡片。

子任务 分):无特殊限制。

对于所有数据,满足