当前没有测试数据。

题目背景

IOI 2025 中国国家队选拔 d1t2。

题目描述

小 w 被迫卷入了一场决定一切的 Nim 游戏！

有 $n$ 堆石子摆在小 w 面前，从 $1$ 到 $n$ 编号，其中编号为 $i$ 的石子堆中有 $a_i$ 个石子。在 Nim 游戏中，小 w 和一位绝顶聪明的对手轮流操作，小 w 后手。每次操作中，操作方可以选择一堆石子，将这一堆石子中任意多的石子扔掉，但不能不扔。如果某个人操作时，所有 $n$ 堆石子中都没有石子了，那么他就无法操作，从而失败。

熟练掌握 OI 知识的小 w 知道 Nim 游戏的最优策略，还知道两个玩家都以最优策略操作时，后手获胜当且仅当所有 $a_i$ 的按位异或和为 $0$。然而初始局面不一定满足这个条件，于是小 w 决定用些盘外招让所有 $a_i$ 的异或和为 $0$，然后赢下这盘游戏。为此小 w 准备了很多石子，他可以在游戏开始前在每个石子堆上添加任意多（也可以不添加）石子。然而小 w 不能从石子堆里取走石子，也不能创建新的石子堆。

小 w 请你提供添加石子的方案。为了保持隐蔽，小 w 希望添加尽可能少的石子，所以他首先想要知道最少需要添加多少石子。除此之外他还希望准备 $m$ 套不同的添加石子数最少的方案，以备不时之需。我们认为两种方案不同，当且仅当存在某堆石子，在这两种方案中该堆石子所添加的石子数量不同。如果这样的方案没有 $m$ 种，则你需要全部告诉他；如果这样的方案大于 $m$ 种，则你任意给出 $m$ 种即可。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c,T$，分别表示测试点编号与测试数据组数。对于样例有 $c = 0$。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$，分别表示石子堆的数量以及小 w 需要的方案数量。

第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots , a_n$，描述每堆石子的石子数量。

输出格式

对于每组测试数据：

• 输出的第一行包含一个整数 $k$，表示小 w 最少需要添加多少石子。
• 输出的第二行包含一个整数 $m'$，表示你提供给小 w 的方案数量。如果添加石子最少的方案数不少于 $m$，你需要保证 $m' = m$，否则你需要保证 $m'$ 恰好是添加石子最少的方案数。
• 接下来依次输出 $m'$ 个不同的方案，对于每个方案输出三行，其中：
  • 第一行包含一个整数 $n'$，表示该方案中添加了石子的石子堆数量。
  • 第二行包含 $n'$ 个整数 $x_1, x_2,\cdots , x_n'$，描述该方案中添加了石子的石子堆编号。你需要保证 $1 \le x_1 \lt x_2 \lt \cdots \lt x_{n'} \le n$。当 $n' = 0$ 时，这一行需要为空行。
  • 第三行包含 $n'$ 个整数 $w_1,w_2,\cdots ,w_{n'}$，其中 $w_j(1 \le j \le n')$ 表示该方案中在编号为 $x_j$ 的石子堆中添加的石子数量。你需要保证对于任意的 $1 \le j \le n'$，有 $w_j \ge 1$ 且 $\sum_{j=1}^{n'} w_j=k$。当 $n' = 0$ 时，这一行需要为空行。

你需要保证在单个测试点内输出的整数数量不超过 $10^7$，可以保证总是存在这样的输出满足题目条件。

输入输出样例 #1

输入 #1

0 2
3 1
4 2 3
2 2
1 3

输出 #1

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

输入输出样例 #2

输入 #2

见附件

输出 #2

见附件

说明/提示

样例解释

样例 $1$ 解释

对于第一组数据，小 w 共有两种使添加石子总数最小的方案：

• 给编号为 $1$ 的石子堆添加 $2$ 个石子，给编号为 $3$ 的石子堆添加 $1$ 个石子。此时三堆石子数分别是 $6, 2, 4$，后手必胜。
• 给编号为 $3$ 的石子堆添加 $3$ 个石子。此时三堆石子数分别是 $4, 2, 6$，后手必胜。

由于小 w 只需要一种方案，输出任意一种方案均可，样例输出为第一种。

对于第二组数据，小 w 只有一种使添加石子总数最小的方案：

• 给编号为 $1$ 的石子堆添加 $2$ 个石子。此时两堆石子的石子分别是 $3, 3$，此时后手必胜。

尽管小 w 需要两种方案，但由于总方案只有一种，故输出唯一的一种方案即可。

数据范围

设 $\sum n$ 和 $\sum m$ 分别表示单个测试点的所有测试数据中 $n$ 和 $m$ 的和。

对于所有测试数据，保证：

• $1 \le T \le 2 \times 10^4$；
• $2 \le n \le 10^5$，$2 \le \sum n \le 2 \times 10^5$，$1 \le m,\sum m \le 2 \times 10^4$；
• 对于任意的 $1 \le i \le n$，有 $0 \le a_i \le 2^{60} − 1$；
• $\displaystyle \sum_{i=1}^{n} a_i \ge 1$。

子任务编号	分值	$n\le$	$\sum n\le$	$m\le$	$\sum m\le$	$a_i\le$	特殊性质
$1$	$4$	$2$	$10^5$	$10^4$	$10^4$	$2^{30}-1$	无
$2$	$12$	$5$	$25$			$2^{4}-1$	B
$3$		$6$	$30$			$2^{10}-1$
$4$		$10^5$	$2\times 10^5$			$2^{30}-1$	A
$5$				$1$			B
$6$	$16$	$10^3$	$2\times 10^3$	$10^2$
$7$		$10^5$	$2\times 10^5$	$10^4$
$8$	$8$						无
$9$				$2\times 10^4$		$2^{60}-1$

• 特殊性质 A：对于任意的 $1\le i\le n$，$a_i$ 都是 $2$ 的非负整数幂次。
• 特殊性质 B：$a_1=0$。

评分方式

对于每个测试点，如果你在所有测试数据中都正确地输出了小 w 需要的最小石子 数量（即输出格式中的 $k$），你将获得该测试点 $50\%$ 的分数。在此基础上，如果你在所有测试数据中都按照要求给出了方案，你将获得该测试点 $100\%$ 的分数。

注意，即使你只想回答小 w 需要的最小石子数量，也需要在回答的小 w 需要的最小石子数量后按照给定的格式输出方案数量以及对应数量的，正确的，不重复的方案。简单地输出 $m' = 0$ 即可完成这一点。