题目描述

You may have heard of Google's Tensor Processing Units, which are used to build neural networks. However, there is one research area that is even deeper and more important than machine learning: sorting!

We are working on a special new chip called the Sorting Permutation Unit, which is very fast at applying permutations to arrays of integers. Formally, a permutation is an ordering of the first $\mathbf{n}$ positive integers

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

and applying it to an array of $\mathbf{n}$ integers

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

yields the new array

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

For example, applying the permutation 3, 1, 2, 4 to the array 99, 234, 45, 800 would yield the new array 45, 99, 234, 800.

However, permutations are expensive to represent in the hardware, so the unit can only have access to at most $\mathbf{P}$ distinct permutations. We need your help figuring out what those permutations should be!

Given $\mathbf{K}$ arrays of $\mathbf{N}$ integers each, you must first specify up to $\mathbf{P}$ permutations (of size $\mathbf{N}$) of your choice. Then, for each of those $\mathbf{K}$ input arrays, you must provide one sequence of up to $\mathbf{S}$ instructions (each of which is a permutation from your specified set). When the instructions in this sequence are applied, in the given order, to the array, they must yield an array sorted in nondecreasing order. In each of your $\mathbf{K}$ sequences of instructions, you may use each of your $\mathbf{P}$ permutations zero or more times (not necessarily consecutively).

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each begins with one line with four integers $\mathbf{P}$, $\mathbf{S}$, $\mathbf{K}$, and $\mathbf{N}$: the maximum number of permutations allowed, the maximum number of instructions you are allowed to use to sort each array, the number of arrays, and the number of integers in each array. Then, there are $\mathbf{K}$ more lines of $\mathbf{N}$ integers $\mathbf{A}_{\mathbf{i}1}$, $\mathbf{A}_{\mathbf{i}2}$, ..., $\mathbf{A}_{\mathbf{iN}}$ each, where the j-th integer on the i-th line, $\mathbf{A}_{\mathbf{ij}}$, represents the j-th value of the i-th array.

输出格式

For each test case, first output the following, in this order:

• One line containing Case #x:, where $\mathbf{x}$ is the test case number (starting from 1).
• One line containing one integer $\mathbf{P}'$, where $1 \leq \mathbf{P}' \leq \mathbf{P}$: the number of permutations you have chosen to use.
• $\mathbf{P}'$ lines, the i-th of which contains $\mathbf{N}$ integers $\mathbf{p}_{\mathbf{i}1}$ $\mathbf{p}_{\mathbf{i}2}$ ... $\mathbf{p}_{\mathbf{iN}}$, where $\mathbf{p}_{\mathbf{ij}}$ is the j-th element of the i-th permutation.

Then, output $\mathbf{K}$ more lines. The i-th of these gives the instructions that you will apply to the i-th array given in the input. Each such line must begin with one integer $\mathbf{S}'$, where $0 \leq \mathbf{S}' \leq \mathbf{S}$, and must continue with $\mathbf{S}'$ integers $\mathbf{X}_{1}$, $\mathbf{X}_{2}$, ..., $\mathbf{X}_{\mathbf{S}'}$, where $1 \leq \mathbf{X}_{\mathbf{k}} \leq \mathbf{P}'$ for all $\mathbf{k}$. Here, $\mathbf{X}_{\mathbf{k}}$ represents that the k-th instruction you apply to the i-th array is the $\mathbf{X}_{\mathbf{k}}$-th permutation (counting starting from 1) in your list of permutations. These instructions must yield an array with the elements of the i-th input array, sorted in nondecreasing order.

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

提示

Sample Explanation

In Sample Case #1, we can define up to $\mathbf{P} = 20$ permutations. One viable strategy uses only these two:

1. 3 1 2
2. 2 1 3

We can handle the four arrays as follows:

• 10 10 11: This is already sorted in nondecreasing order, so we do not need to do anything.
• 17 4 1000: We can apply permutation #2 to yield 4 17 1000.
• 999 998 997: One option is to first apply permutation #2 to turn the array into 998 999 997, then apply permutation #1 to turn the array into 997 998 999.
• 10 10 11: This is the same as the first array. Applying permutation #2 also yields array sorted in nondecreasing order. (But we could have used the line 0 as we did before.)

In Sample Case #2, notice that we can use the same permutation instruction more than once on the same array, if desired.

Limits

• $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$, for all $\mathbf{i}$ and $\mathbf{j}$.

Test set 1 (5 Pts, Visible)

• $\mathbf{P} = 20$.

Test set 2 (22 Pts, Hidden)

• $\mathbf{P} = 5$.