Problem: 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.

Input

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).

Output

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.) 

<image>

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).

Note

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans = {
    {
        1,
        0,
    },
    {
        1,
        2,
        0,
    },
    {
        3,
        2,
        1,
        0,
    },
    {
        0,
        2,
        3,
        1,
        4,
    },
    {
        0,
        5,
        10,
        2,
        9,
        8,
        14,
        11,
        6,
        12,
        1,
        4,
        3,
        13,
        7,
    },
    {
        4,
        0,
        2,
        10,
        9,
        6,
        5,
        8,
        12,
        14,
        11,
        3,
        13,
        1,
        7,
    },
    {
        8,
        6,
        1,
        4,
        0,
        9,
        7,
        2,
        3,
        5,
    },
    {
        1,
        0,
        3,
        2,
    },
    {
        3,
        11,
        7,
        1,
        8,
        13,
        4,
        6,
        0,
        5,
        9,
        12,
        14,
        2,
        10,
    },
    {
        10,
        4,
        5,
        7,
        9,
        11,
        6,
        1,
        0,
        3,
        8,
        2,
        12,
        13,
        14,
    },
    {
        10,
        6,
        7,
        3,
        4,
        14,
        12,
        13,
        2,
        8,
        11,
        1,
        0,
        9,
        5,
    },
    {
        11,
        6,
        10,
        3,
        9,
        1,
        4,
        13,
        12,
        0,
        5,
        2,
        8,
        7,
        14,
        15,
    },
    {
        2,
        1,
        0,
    },
    {
        3,
        1,
        0,
        2,
        4,
    },
    {
        0,
        7,
        10,
        14,
        2,
        1,
        6,
        15,
        12,
        3,
        5,
        9,
        8,
        11,
        4,
        13,
    },
    {
        8,
        7,
        5,
        12,
        10,
        9,
        1,
        6,
        13,
        11,
        4,
        3,
        14,
        2,
        0,
    },
    {
        1,
        14,
        15,
        9,
        7,
        4,
        8,
        2,
        10,
        6,
        0,
        13,
        11,
        3,
        5,
        12,
    },
    {
        14,
        4,
        1,
        13,
        2,
        12,
        0,
        6,
        11,
        7,
        3,
        9,
        5,
        10,
        8,
    },
    {
        8,
        6,
        2,
        13,
        1,
        11,
        12,
        4,
        0,
        14,
        10,
        9,
        7,
        3,
        5,
    },
    {
        8,
        6,
        12,
        9,
        14,
        15,
        4,
        2,
        5,
        0,
        1,
        10,
        7,
        3,
        13,
        11,
    },
    {
        5,
        12,
        1,
        10,
        4,
        9,
        2,
        13,
        8,
        0,
        11,
        7,
        15,
        3,
        14,
        6,
    },
    {
        1,
        5,
        14,
        12,
        11,
        6,
        3,
        8,
        15,
        10,
        9,
        0,
        4,
        7,
        2,
        13,
    },
    {
        2,
        1,
        5,
        13,
        6,
        11,
        9,
        8,
        4,
        3,
        7,
        14,
        10,
        12,
        0,
    },
    {
        2,
        10,
        3,
        4,
        13,
        9,
        15,
        8,
        7,
        5,
        6,
        12,
        11,
        0,
        14,
        1,
    },
    {
        3,
        2,
        10,
        8,
        7,
        15,
        5,
        14,
        1,
        12,
        6,
        13,
        9,
        0,
        11,
        4,
    },
    {
        0,
        11,
        8,
        6,
        5,
        4,
        1,
        12,
        13,
        9,
        14,
        7,
        10,
        3,
        2,
    },
    {
        1,
        0,
        2,
    },
    {
        1,
        0,
    },
    {
        0,
        2,
        1,
        5,
        3,
        7,
        6,
        4,
    },
    {
        13,
        5,
        6,
        4,
        1,
        8,
        12,
        3,
        0,
        7,
        10,
        14,
        15,
        9,
        2,
        11,
    },
    {
        0,
        6,
        3,
        2,
        5,
        4,
        1,
        7,
    },
    {
        12,
        6,
        5,
        13,
        11,
        14,
        2,
        4,
        0,
        8,
        7,
        9,
        3,
        10,
        1,
    },
    {
        10,
        1,
        14,
        4,
        13,
        2,
        8,
        9,
        6,
        0,
        11,
        12,
        7,
        5,
        3,
    },
    {
        3,
        1,
        2,
        0,
    },
    {
        15,
        12,
        10,
        13,
        8,
        1,
        14,
        2,
        0,
        4,
        5,
        6,
        11,
        7,
        3,
        9,
    },
    {
        2,
        0,
        3,
        8,
        15,
        14,
        6,
        9,
        5,
        12,
        4,
        10,
        1,
        13,
        11,
        7,
    },
    {
        9,
        11,
        8,
        15,
        4,
        5,
        7,
        3,
        2,
        6,
        14,
        0,
        10,
        1,
        13,
        12,
    },
    {
        2,
        0,
        5,
        4,
        1,
        3,
    },
    {
        13,
        7,
        1,
        9,
        5,
        15,
        8,
        6,
        14,
        3,
        0,
        2,
        10,
        12,
        4,
        11,
    },
    {
        14,
        7,
        9,
        8,
        10,
        11,
        6,
        12,
        4,
        13,
        0,
        3,
        2,
        1,
        5,
    },
    {
        4,
        6,
        2,
        9,
        5,
        11,
        7,
        3,
        10,
        0,
        1,
        8,
    },
    {
        1,
        0,
    },
    {
        12,
        13,
        7,
        5,
        3,
        6,
        4,
        9,
        2,
        10,
        1,
        8,
        14,
        11,
        0,
    },
    {
        1,
        14,
        10,
        12,
        11,
        4,
        2,
        3,
        8,
        7,
        13,
        5,
        9,
        0,
        6,
    },
    {
        2,
        0,
        3,
        1,
    },
    {
        1,
        11,
        15,
        0,
        2,
        5,
        14,
        10,
        3,
        9,
        8,
        13,
        4,
        6,
        12,
        7,
    },
    {
        2,
        0,
        1,
    },
    {
        15,
        3,
        12,
        10,
        6,
        8,
        4,
        1,
        9,
        2,
        5,
        14,
        11,
        13,
        7,
        0,
    },
    {
        1,
        4,
        0,
        8,
        14,
        6,
        2,
        10,
        12,
        3,
        7,
        11,
        5,
        13,
        9,
    },
    {
        5,
        2,
        15,
        9,
        13,
        12,
        6,
        1,
        4,
        11,
        3,
        14,
        7,
        0,
        10,
        8,
    },
    {
        4,
        6,
        10,
        2,
        9,
        14,
        1,
        8,
        3,
        7,
        13,
        12,
        15,
        11,
        0,
        5,
    },
    {
        15,
        0,
        1,
        2,
        6,
        14,
        5,
        11,
        7,
        10,
        9,
        13,
        12,
        3,
        8,
        4,
    },
    {
        5,
        4,
        1,
        9,
        11,
        7,
        3,
        12,
        8,
        10,
        0,
        14,
        2,
        13,
        6,
    },
    {
        11,
        12,
        8,
        0,
        2,
        10,
        3,
        7,
        14,
        13,
        9,
        6,
        15,
        4,
        5,
        1,
    },
    {
        3,
        1,
        2,
        0,
    },
    {
        9,
        4,
        14,
        3,
        11,
        0,
        10,
        5,
        15,
        1,
        12,
        8,
        13,
        6,
        7,
        2,
    },
    {
        5,
        2,
        0,
        4,
        1,
        3,
    },
    {
        13,
        10,
        6,
        4,
        5,
        14,
        2,
        3,
        1,
        9,
        0,
        12,
        8,
        7,
        11,
    },
    {
        9,
        7,
        1,
        10,
        14,
        4,
        0,
        12,
        15,
        11,
        13,
        8,
        5,
        3,
        2,
        6,
    },
    {
        7,
        1,
        14,
        10,
        8,
        11,
        15,
        5,
        12,
        6,
        3,
        4,
        13,
        0,
        9,
        2,
    },
    {
        2,
        8,
        9,
        12,
        5,
        15,
        4,
        3,
        7,
        6,
        11,
        10,
        0,
        14,
        13,
        1,
    },
    {
        1,
        4,
        5,
        11,
        3,
        14,
        2,
        0,
        8,
        12,
        7,
        6,
        13,
        10,
        9,
    },
    {
        5,
        6,
        2,
        1,
        4,
        7,
        0,
        8,
        9,
        3,
    },
    {
        9,
        15,
        10,
        13,
        2,
        11,
        0,
        14,
        1,
        7,
        3,
        4,
        5,
        12,
        6,
        8,
    },
    {
        7,
        0,
        12,
        14,
        6,
        9,
        4,
        8,
        2,
        1,
        5,
        3,
        11,
        10,
        13,
    },
    {
        11,
        5,
        10,
        13,
        2,
        1,
        0,
        7,
        9,
        15,
        14,
        6,
        3,
        8,
        4,
        12,
    },
    {
        2,
        1,
        0,
    },
    {
        3,
        6,
        7,
        1,
        0,
        5,
        4,
        2,
    },
    {
        1,
        0,
    },
    {
        9,
        2,
        6,
        5,
        11,
        3,
        0,
        4,
        8,
        1,
        7,
        12,
        14,
        13,
        15,
        10,
    },
    {
        14,
        8,
        1,
        7,
        0,
        3,
        13,
        12,
        4,
        2,
        11,
        5,
        6,
        10,
        9,
    },
    {
        3,
        0,
        4,
        1,
        2,
    },
    {
        3,
        7,
        1,
        10,
        8,
        5,
        0,
        6,
        2,
        4,
        9,
        11,
    },
    {
        15,
        9,
        0,
        3,
        6,
        12,
        8,
        2,
        7,
        13,
        11,
        4,
        1,
        14,
        5,
        10,
    },
    {
        15,
        14,
        2,
        7,
        13,
        1,
        3,
        4,
        10,
        5,
        6,
        12,
        0,
        11,
        9,
        8,
    },
    {
        10,
        15,
        13,
        0,
        5,
        11,
        1,
        2,
        3,
        7,
        6,
        12,
        9,
        8,
        14,
        4,
    },
    {
        14,
        13,
        3,
        5,
        8,
        4,
        2,
        1,
        12,
        11,
        9,
        10,
        6,
        0,
        7,
    },
    {
        12,
        9,
        14,
        10,
        3,
        15,
        1,
        2,
        13,
        8,
        4,
        5,
        7,
        6,
        11,
        0,
    },
    {
        3,
        2,
        4,
        13,
        5,
        7,
        15,
        9,
        8,
        11,
        1,
        10,
        12,
        14,
        6,
        0,
    },
    {
        0,
        3,
        4,
        9,
        8,
        5,
        7,
        2,
        1,
        6,
    },
    {
        6,
        5,
        14,
        4,
        11,
        12,
        1,
        3,
        2,
        13,
        10,
        0,
        9,
        7,
        8,
    },
    {
        1,
        13,
        8,
        2,
        7,
        6,
        5,
        14,
        9,
        10,
        15,
        4,
        11,
        12,
        0,
        3,
    },
    {
        1,
        4,
        8,
        0,
        10,
        3,
        15,
        5,
        7,
        6,
        11,
        2,
        12,
        9,
        14,
        13,
    },
    {
        2,
        4,
        6,
        13,
        0,
        8,
        5,
        3,
        9,
        7,
        10,
        14,
        1,
        15,
        11,
        12,
    },
    {
        14,
        13,
        9,
        12,
        0,
        4,
        1,
        11,
        3,
        10,
        7,
        8,
        5,
        6,
        2,
        15,
    },
    {
        5,
        0,
        3,
        15,
        1,
        8,
        7,
        4,
        11,
        10,
        9,
        12,
        2,
        6,
        13,
        14,
    },
    {
        15,
        13,
        8,
        7,
        3,
        0,
        6,
        1,
        11,
        9,
        2,
        4,
        10,
        5,
        14,
        12,
    },
    {
        5,
        0,
        4,
        1,
        3,
        2,
    },
    {
        2,
        9,
        3,
        4,
        8,
        5,
        0,
        1,
        6,
        7,
    },
    {
        7,
        0,
        14,
        9,
        11,
        4,
        13,
        10,
        3,
        1,
        2,
        12,
        6,
        8,
        5,
    },
    {
        4,
        12,
        11,
        6,
        8,
        0,
        9,
        3,
        14,
        7,
        2,
        1,
        13,
        5,
        10,
    },
    {
        1,
        2,
        5,
        0,
        3,
        4,
    },
    {
        2,
        14,
        12,
        5,
        6,
        10,
        11,
        0,
        13,
        3,
        7,
        8,
        1,
        9,
        4,
    },
    {
        13,
        6,
        7,
        5,
        11,
        12,
        15,
        14,
        2,
        9,
        10,
        8,
        0,
        3,
        4,
        1,
    },
    {
        6,
        1,
        3,
        12,
        8,
        0,
        14,
        7,
        11,
        10,
        5,
        2,
        4,
        13,
        9,
    },
    {
        2,
        3,
        4,
        5,
        14,
        7,
        8,
        9,
        13,
        11,
        10,
        12,
        6,
        1,
        0,
    },
    {
        3,
        10,
        4,
        11,
        7,
        13,
        9,
        6,
        2,
        8,
        15,
        12,
        14,
        0,
        5,
        1,
    },
    {
        1,
        5,
        2,
        0,
        3,
        4,
    },
    {
        5,
        4,
        6,
        8,
        1,
        7,
        2,
        0,
        3,
        9,
    },
    {
        13,
        6,
        14,
        10,
        0,
        3,
        2,
        12,
        4,
        9,
        5,
        8,
        7,
        1,
        11,
    },
    {
        14,
        13,
        4,
        2,
        6,
        3,
        0,
        8,
        10,
        5,
        9,
        1,
        11,
        12,
        7,
    },
    {
        15,
        13,
        2,
        6,
        12,
        1,
        5,
        0,
        9,
        11,
        8,
        3,
        4,
        7,
        10,
        14,
    },
    {
        2,
        7,
        4,
        9,
        11,
        10,
        3,
        5,
        6,
        8,
        1,
        0,
    },
    {
        10,
        2,
        4,
        3,
        11,
        7,
        0,
        1,
        5,
        6,
        8,
        9,
    },
    {
        2,
        10,
        5,
        15,
        12,
        14,
        4,
        1,
        11,
        6,
        13,
        7,
        9,
        8,
        3,
        0,
    },
    {
        5,
        4,
        0,
        3,
        2,
        1,
    },
    {
        0,
        3,
        1,
        9,
        11,
        10,
        8,
        4,
        5,
        12,
        2,
        13,
        14,
        7,
        6,
    },
    {
        6,
        12,
        9,
        4,
        1,
        11,
        5,
        2,
        7,
        3,
        14,
        10,
        0,
        8,
        13,
    },
    {
        11,
        4,
        6,
        7,
        0,
        8,
        9,
        14,
        5,
        3,
        13,
        12,
        2,
        1,
        10,
    },
    {
        1,
        4,
        2,
        8,
        12,
        3,
        6,
        11,
        5,
        13,
        9,
        10,
        14,
        0,
        7,
    },
    {
        4,
        3,
        1,
        5,
        0,
        2,
    },
    {
        3,
        7,
        8,
        0,
        4,
        12,
        10,
        6,
        2,
        11,
        1,
        5,
        13,
        14,
        9,
    },
    {
        1,
        0,
    },
    {
        10,
        4,
        6,
        8,
        14,
        1,
        7,
        13,
        2,
        12,
        9,
        11,
        0,
        5,
        3,
    },
    {
        4,
        13,
        14,
        3,
        12,
        5,
        7,
        9,
        6,
        11,
        1,
        10,
        15,
        2,
        8,
        0,
    },
    {
        11,
        7,
        6,
        1,
        2,
        8,
        14,
        4,
        10,
        5,
        3,
        13,
        12,
        0,
        9,
    },
    {
        13,
        6,
        10,
        12,
        1,
        2,
        11,
        0,
        9,
        8,
        4,
        7,
        3,
        14,
        5,
    },
    {
        5,
        3,
        2,
        4,
        0,
        1,
        6,
        7,
    },
    {
        7,
        15,
        3,
        10,
        12,
        4,
        1,
        13,
        8,
        5,
        2,
        14,
        11,
        0,
        9,
        6,
    },
    {
        2,
        4,
        0,
        7,
        1,
        8,
        6,
        11,
        3,
        10,
        9,
        5,
    },
    {
        1,
        4,
        3,
        8,
        10,
        11,
        12,
        5,
        2,
        0,
        14,
        9,
        7,
        6,
        13,
    },
    {
        12,
        5,
        7,
        10,
        11,
        14,
        0,
        1,
        9,
        8,
        6,
        13,
        2,
        4,
        3,
    },
    {
        1,
        10,
        14,
        11,
        4,
        7,
        8,
        0,
        13,
        9,
        3,
        2,
        5,
        6,
        12,
    },
    {
        4,
        7,
        15,
        2,
        9,
        5,
        13,
        6,
        0,
        14,
        11,
        8,
        12,
        1,
        10,
        3,
    },
    {
        9,
        11,
        0,
        15,
        10,
        3,
        1,
        14,
        5,
        6,
        12,
        13,
        4,
        2,
        7,
        8,
    },
    {
        0,
        1,
        4,
        2,
        3,
    },
    {
        5,
        4,
        0,
        3,
        1,
        2,
    },
    {
        7,
        3,
        6,
        4,
        5,
        0,
        1,
        2,
    },
    {
        3,
        1,
        2,
        0,
    },
    {
        3,
        4,
        5,
        7,
        2,
        0,
        1,
        8,
        9,
        6,
    },
    {
        0,
        7,
        9,
        11,
        13,
        12,
        15,
        10,
        8,
        3,
        2,
        1,
        6,
        4,
        14,
        5,
    },
    {
        1,
        0,
    },
    {
        12,
        6,
        14,
        13,
        9,
        0,
        7,
        5,
        1,
        10,
        8,
        2,
        3,
        11,
        4,
    },
    {
        14,
        12,
        7,
        1,
        6,
        10,
        5,
        4,
        13,
        8,
        9,
        11,
        2,
        3,
        0,
    },
    {
        1,
        0,
    },
    {
        7,
        3,
        4,
        9,
        5,
        0,
        13,
        12,
        11,
        8,
        1,
        2,
        10,
        14,
        6,
    },
    {
        9,
        2,
        5,
        7,
        4,
        10,
        13,
        15,
        6,
        0,
        8,
        1,
        12,
        3,
        14,
        11,
    },
    {
        6,
        4,
        5,
        1,
        3,
        0,
        7,
        2,
    },
    {
        9,
        1,
        6,
        8,
        10,
        5,
        0,
        7,
        2,
        4,
        11,
        3,
    },
    {
        3,
        1,
        2,
        0,
    },
    {
        2,
        12,
        8,
        6,
        10,
        14,
        13,
        9,
        4,
        1,
        15,
        11,
        3,
        7,
        0,
        5,
    },
    {
        0,
        5,
        9,
        3,
        14,
        4,
        2,
        12,
        6,
        11,
        8,
        1,
        7,
        10,
        13,
    },
    {
        1,
        6,
        13,
        15,
        12,
        7,
        2,
        14,
        11,
        10,
        0,
        3,
        5,
        4,
        9,
        8,
    },
    {
        3,
        2,
        0,
        1,
        4,
    },
    {
        2,
        3,
        10,
        6,
        14,
        0,
        12,
        9,
        8,
        13,
        15,
        11,
        4,
        7,
        1,
        5,
    },
    {
        3,
        8,
        13,
        6,
        11,
        2,
        9,
        4,
        12,
        0,
        1,
        10,
        7,
        5,
        14,
    },
    {
        9,
        8,
        15,
        12,
        6,
        2,
        11,
        3,
        14,
        7,
        4,
        0,
        10,
        1,
        5,
        13,
    },
    {
        1,
        0,
    },
    {
        13,
        3,
        0,
        1,
        12,
        5,
        2,
        4,
        11,
        9,
        6,
        8,
        14,
        7,
        10,
    },
    {
        2,
        3,
        0,
        5,
        1,
        4,
    },
    {
        4,
        9,
        3,
        5,
        1,
        7,
        10,
        8,
        0,
        6,
        2,
        12,
        14,
        13,
        11,
    },
    {
        1,
        3,
        0,
        2,
    },
    {
        15,
        13,
        11,
        10,
        6,
        2,
        1,
        5,
        0,
        8,
        3,
        9,
        14,
        12,
        4,
        7,
    },
    {
        10,
        14,
        0,
        3,
        15,
        13,
        1,
        11,
        4,
        7,
        9,
        8,
        5,
        12,
        6,
        2,
    },
    {
        1,
        2,
        3,
        0,
    },
    {
        7,
        10,
        2,
        3,
        0,
        9,
        13,
        5,
        12,
        6,
        14,
        1,
        11,
        4,
        8,
    },
};
bool bz[205];
int main() {
  bz[29] = 1;
  bz[40] = 1;
  bz[45] = 1;
  bz[49] = 1;
  bz[55] = 1;
  bz[56] = 1;
  bz[57] = 1;
  bz[61] = 1;
  bz[63] = 1;
  bz[65] = 1;
  bz[69] = 1;
  bz[72] = 1;
  bz[73] = 1;
  bz[74] = 1;
  bz[92] = 1;
  bz[132] = 1;
  bz[153] = 1;
  bz[155] = 1;
  for (int i = 0; i < ((int)ans.size()); i++) {
    if (!bz[i]) {
      for (int j = 0; j < ((int)ans[i].size()); j++)
        printf("%d ", ans[i][j] + 1);
    } else {
      for (int j = 0; j < ((int)ans[i].size()); j++) printf("0 ");
    }
    printf("\n");
  }
  return 0;
}