题目描述

我们称一个非空的正整数序列为奇异序列，如果其元素之和是一个质数。

给定一个长度为 $n$ 的数组 $a$，其中的元素均为质数。同时给定一个整数 $k$。

请将数组 $a$ 分割成 $k$ 个非空子序列$^1$，使得：

• 数组 $a$ 的每个元素恰好属于其中一个子序列；
• 在这些子序列中，奇异序列的数量尽可能少。

本题每个测试包含多组输入数据，你需要分别独立处理每组数据。

注意：本题没有"无额外限制"的评分 Subtask。

输入格式

第一行包含一个整数 $T$ $(1\le T\le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$, $k$ $(1 \le k \le n \le 10^5)$ —— 数组 $a$ 的长度和需要分割成的子序列数量。

每组数据的第二行包含 $n$ 个质数 $a_1, a_2, \ldots, a_n$ $(2\le a_i\le 10^5, a_i\le a_{i+1})$ —— 数组 $a$ 的元素。

保证单个测试中所有数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组数据，按照以下格式输出最优分割方案：

• 第一行输出一个整数 $m$ —— 分割后得到的奇异序列数量；
• 接下来的 $k$ 行，每行输出整数 $s_i$ 和 $b_1, b_2, \ldots, b_{s_i}$ $(1\le s_i\le n)$ —— 对应子序列的元素个数及其元素。

子序列及其元素的输出顺序可以任意。

如果存在多个正确答案，输出任意一个即可。

4
3 1
5 5 13
4 2
2 3 5 7
5 3
3 3 5 5 13
6 5
2 2 2 3 3 3

1
3 13 5 5
0
2 2 7
2 3 5
1
1 13
2 3 3
2 5 5
4
1 2
1 2
1 2
1 3
2 3 3

提示

$^1$ 序列 $c$ 称为数组 $b$ 的子序列，如果可以通过从数组 $b$ 中删除若干元素（可能为零个）来得到序列 $c$。

评分标准

• （$2$ 分）：$T \leq 20$，$k=1$；
• （$5$ 分）：$n \leq 4$，所有 $1\le i\le n$ 满足 $a_i \leq 10^4$；
• （$8$ 分）：$T \leq 20$，$n \leq 10$，所有 $1\le i\le n$ 满足 $a_i \leq 10^4$；
• （$4$ 分）：$n$ 为偶数，所有 $1\le i\le n$ 满足 $a_i > 2$；
• （$18$ 分）：$n$ 为奇数，所有 $1\le i\le n$ 满足 $a_i > 2$；
• （$10$ 分）：$2\cdot k \ge n + 1$；
• （$29$ 分）：$n$ 为偶数；
• （$24$ 分）：$n$ 为奇数。

翻译由 DeepSeek V3 完成