Description

你可能听说过 Google 的张量处理单元（Tensor Processing Units），它们被用于构建神经网络。然而，有一个比机器学习更深奥、更重要的研究领域：排序！

我们正在研发一种名为“排序置换单元”（Sorting Permutation Unit）的特殊芯片，它能非常快速地对整数数组应用置换。形式化地说，置换是对前 $n$ 个正整数的一种排列：

$$\mathbf{p}_{1}, \mathbf{p}_{2}, \ldots, \mathbf{p}_{\mathbf{n}}$$

将其应用于一个包含 $n$ 个整数的数组

$$\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{\mathbf{n}}$$

会得到新的数组

$$\mathbf{a}_{\mathbf{p}_{1}}, \mathbf{a}_{\mathbf{p}_{2}}, \ldots, \mathbf{a}_{\mathbf{p}_{\mathbf{n}}}$$

例如，将置换 3, 1, 2, 4 应用于数组 99, 234, 45, 800，会得到新数组 45, 99, 234, 800。

然而，硬件中表示置换的代价很高，因此该单元最多只能使用 $\mathbf{P}$ 个不同的置换。我们需要你的帮助，来确定这些置换应该是什么！

给定 $\mathbf{K}$ 个长度为 $\mathbf{N}$ 的整数数组，你首先需要指定至多 $\mathbf{P}$ 个你选择的置换（每个置换长度为 $\mathbf{N}$）。然后，对于每一个输入数组，你需要给出一组最多包含 $\mathbf{S}$ 条指令的序列（每条指令是你指定的置换之一）。当按顺序对该数组应用这些指令后，最终得到的数组必须是非递减有序的。在每个数组的指令序列中，你可以对每个置换使用零次或多次（不要求连续）。

Input Format

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为四个整数 $\mathbf{P}$、$\mathbf{S}$、$\mathbf{K}$ 和 $\mathbf{N}$，分别表示最多允许的置换数、对每个数组最多允许的指令数、数组的数量以及每个数组中的整数个数。接下来有 $\mathbf{K}$ 行，每行包含 $\mathbf{N}$ 个整数 $\mathbf{A}_{\mathbf{i}1}$、$\mathbf{A}_{\mathbf{i}2}$、...、$\mathbf{A}_{\mathbf{iN}}$，其中第 $i$ 行的第 $j$ 个整数 $\mathbf{A}_{\mathbf{ij}}$ 表示第 $i$ 个数组的第 $j$ 个值。

Output Format

对于每个测试用例，按以下顺序输出：

• 首先输出一行 Case #x:，其中 $x$ 是测试用例编号（从 1 开始）。
• 输出一行一个整数 $\mathbf{P}'$，表示你选择使用的置换数量，$1 \leq \mathbf{P}' \leq \mathbf{P}$。
• 接下来输出 $\mathbf{P}'$ 行，每行包含 $\mathbf{N}$ 个整数 $\mathbf{p}_{\mathbf{i}1}$ $\mathbf{p}_{\mathbf{i}2}$ ... $\mathbf{p}_{\mathbf{iN}}$，表示第 $i$ 个置换的内容。

然后，再输出 $\mathbf{K}$ 行。第 $i$ 行表示你将应用于输入中第 $i$ 个数组的指令序列。每行首先是一个整数 $\mathbf{S}'$，$0 \leq \mathbf{S}' \leq \mathbf{S}$，接着是 $\mathbf{S}'$ 个整数 $\mathbf{X}_{1}$、$\mathbf{X}_{2}$、...、$\mathbf{X}_{\mathbf{S}'}$，其中 $1 \leq \mathbf{X}_{\mathbf{k}} \leq \mathbf{P}'$。这里，$\mathbf{X}_{\mathbf{k}}$ 表示对第 $i$ 个数组应用的第 $k$ 条指令是你置换列表中第 $\mathbf{X}_{\mathbf{k}}$ 个置换（从 1 开始编号）。这些指令应用后，得到的数组必须是输入数组元素的非递减排列。

2
20 450 4 3
10 10 11
17 4 1000
999 998 997
10 10 11
20 450 5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

Case #1:
2
3 1 2
2 1 3
0
1 2
2 2 1
1 2
Case #2:
1
5 1 2 3 4
0
1 1
2 1 1
3 1 1 1
4 1 1 1 1

Hint

样例解释

在样例 1 中，我们最多可以定义 $\mathbf{P} = 20$ 个置换。一种可行的策略只用到了以下两个：

1. 3 1 2
2. 2 1 3

我们可以这样处理四个数组：

• 10 10 11：已经是非递减有序，无需操作。
• 17 4 1000：可以应用第 2 个置换，得到 4 17 1000。
• 999 998 997：可以先应用第 2 个置换，得到 998 999 997，再应用第 1 个置换，得到 997 998 999。
• 10 10 11：与第一个数组相同，也可以应用第 2 个置换得到有序数组（当然也可以直接输出 0）。

在样例 2 中，注意同一个置换指令可以在同一个数组上多次使用。

数据范围

• $1 \leq \mathbf{T} \leq 10$。
• $\mathbf{S} = 450$。
• $1 \leq \mathbf{K} \leq 30$。
• $2 \leq \mathbf{N} \leq 50$。
• $1 \leq \mathbf{A}_{\mathbf{ij}} \leq 1000$，对于所有 $i$ 和 $j$。

测试点 1（5 分，可见）

• $\mathbf{P} = 20$。

测试点 2（22 分，隐藏）

• $\mathbf{P} = 5$。

由 ChatGPT 4.1 翻译