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

我们正在研发一种名为“排序置换单元”（Sorting Permutation Unit）的特殊新芯片，它在对整数数组应用置换方面速度极快。形式上，一个置换是对前 $n$ 个正整数的排序： $p_1, p_2, \dots, p_n$ 将其应用于一个包含 $n$ 个整数的数组： $a_1, a_2, \dots, a_n$ 会产生新数组： $a_{p_1}, a_{p_2}, \dots, a_{p_n}$

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

然而，置换在硬件中的表示成本很高，因此该单元最多只能访问 $P$ 个不同的置换。我们需要你帮忙确定这些置换应该是什么！

给定 $K$ 个包含 $N$ 个整数的数组，你必须首先指定最多 $P$ 个你选择的（大小为 $N$ 的）置换。然后，对于这 $K$ 个输入数组中的每一个，你必须提供一个最多包含 $S$ 条指令的序列（每条指令都是你指定集合中的一个置换）。当这些指令按给定顺序应用于数组时，它们必须产生一个非递减排序的数组。在你的 $K$ 个指令序列中，你可以将你的 $P$ 个置换中的每一个使用零次或多次（不一定连续）。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含四个整数 $P, S, K$ 和 $N$：允许的最大置换数量、允许用于排序每个数组的最大指令数量、数组数量以及每个数组中整数的数量。然后是 $K$ 行，每行包含 $N$ 个整数 $A_{i1}, A_{i2}, \dots, A_{iN}$，其中第 $i$ 行的第 $j$ 个整数 $A_{ij}$ 表示第 $i$ 个数组的第 $j$ 个值。

输出格式

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

• 一行包含 Case #x:，其中 $x$ 是测试用例编号（从 1 开始）。
• 一行包含一个整数 $P'$，其中 $1 \le P' \le P$：你选择使用的置换数量。
• $P'$ 行，第 $i$ 行包含 $N$ 个整数 $p_{i1}, p_{i2}, \dots, p_{iN}$，其中 $p_{ij}$ 是第 $i$ 个置换的第 $j$ 个元素。

然后，输出 $K$ 行。第 $i$ 行给出你将应用于输入中第 $i$ 个数组的指令。每行必须以一个整数 $S'$ 开头，其中 $0 \le S' \le S$，并接续 $S'$ 个整数 $X_1, X_2, \dots, X_{S'}$，其中对于所有 $k$ 均有 $1 \le X_k \le P'$。这里，$X_k$ 表示你应用于第 $i$ 个数组的第 $k$ 条指令是你置换列表中第 $X_k$ 个置换（从 1 开始计数）。这些指令必须使第 $i$ 个输入数组的元素变为非递减排序。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1GB。 $1 \le T \le 10$。 $S = 450$。 $1 \le K \le 30$。 $2 \le N \le 50$。 $1 \le A_{ij} \le 1000$，对于所有 $i$ 和 $j$。

测试集 1（可见）： $P = 20$。

测试集 2（隐藏）： $P = 5$。

样例

样例输入 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

样例输出 1

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

说明

在样例 #1 中，我们可以定义最多 $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 中，请注意如果需要，我们可以在同一个数组上多次使用相同的置换指令。