CF690E2.Photographs (II)

Zombies seem to have become much more intelligent lately – a few have somehow wandered into the base through the automatic gate. Heidi has had to beef up security, and a new gate has been installed. Unfortunately, now the questions being asked are more complicated, and even humans have trouble answering them. Can you still program the robot army to do this reliably?

The new questions are of the following form: a grayscale photograph has been divided into several horizontal pieces, which have been arbitrarily rearranged. The task is to assemble the original image back from these pieces (somewhat like in a jigsaw puzzle). To further delay the zombies, significant Gaussian-distributed noise has been added to the image.

最近，僵尸似乎变得聪明了许多——有几只不知怎地通过自动门闯入了基地。海蒂不得不加强安保措施，并安装了一扇新门。不幸的是，现在提出的问题变得更加复杂，甚至连人类都难以回答。你还能为机器人军队编写可靠的程序来完成这项任务吗？

新问题的形式如下：一张灰度照片被分割成若干水平条带，这些条带被任意打乱顺序。任务是根据这些条带重新拼凑出原始图像（有点像拼图游戏）。为了进一步延缓僵尸的行动，图像中还添加了显著的、服从高斯分布的噪声。

The input format is the same as in the previous version, except that the first line of every question now contains three space-separated numbers h, w and k (1 ≤ h, w ≤ 600, 2 ≤ k ≤ 16) – the height (number of rows) and width (number of columns) of the photograph and the number of pieces, respectively. The number of pieces evenly divides the height, and each piece is of the same height h / k.

Again, there is only one input file to be processed, and the same resources are provided to you as in the previous version (except that now you are given all input images in .bmp format, rather than the first 50).

输入格式与上一版本相同，不同之处在于：每个问题的第一行现在包含三个以空格分隔的数字 $h$、$w$ 和 $k$（其中 $1 \leq h, w \leq 600$，$2 \leq k \leq 16$），分别表示照片的高度（行数）、宽度（列数）以及切分后的块数。块数 $k$ 能整除高度 $h$，且每一块的高度均为 $h/k$。

同样，仅需处理一个输入文件，且提供给你的资源与上一版本相同（唯一的区别是：本次所有输入图像均以 .bmp 格式给出，而非仅前 50 张）。

Your program should print q lines. The i-th line should contain your answer for the i-th question: a space-separated sequence of k numbers π1, π2, ..., π_k_ such that:

• π is a permutation of {1, 2, ..., k}, that is, each number from 1 to k appears exactly once in π,
• for each j = 1, ..., k, π_j_ is the position (index), in the original image, of the piece which is at position j in the input image. (See the illustration below for clarity.)

The second image from the test set. If the three pieces in the original image are numbered 1, 2, 3 from top to bottom, then the numbering in the image on the right should be 2, 3, 1. The correct answer for this image is thus 2 3 1.

Again, your answers will be accepted if they conform to this format and if at least 75% of them are correct.

Again, you may process the input locally and submit just your precomputed answers (i.e., a program which just prints your output for the input file all.in).

你的程序应输出 q 行。第 i 行应包含对第 i 个问题的答案：一个由 k 个数字 π₁, π₂, ..., πₖ 组成的、以空格分隔的序列，满足：

• π 是集合 {1, 2, ..., k} 的一个排列，即数字 1 到 k 在 π 中恰好各出现一次；
• 对每个 j = 1, ..., k，π_j 表示：在原始图像中，位于输入图像第 j 个位置上的图块，在原始图像中的位置（下标）。（参见下方示意图以明确含义。）

测试集中的第二张图像。若原始图像中的三个图块自上而下编号为 1、2、3，则右侧图像中的图块编号应为 2、3、1。因此，该图像的正确答案为 2 3 1。

再次强调：只要你的答案符合上述格式，且至少 75% 的答案正确，即被接受。

再次强调：你可在本地处理输入，并仅提交预先计算出的答案（即一个直接输出对应输入文件 all.in 的答案的程序）。

The link to download all the necessary materials is http://assets.codeforces.com/files/690/medium_contestant_package.zip

下载所有必要材料的链接为 http://assets.codeforces.com/files/690/medium_contestant_package.zip