Похоже зомби в последнее время сильно поумнели — некоторые из них всё-таки пробрались на охраняемую базу с автоматическими воротами. Хайди пришлось нарастить охрану и установить новые автоматические ворота. К сожалению, теперь они задают более сложные вопросы, так что и у людей могу возникнуть проблемы с ответами на них. Сможете ли вы снова решить вопрос с безопасностью армии роботов?
Теперь задаются вопросы следующего вида: фотография в оттенках серого была разбита на несколько горизонтальных кусков, которые были переупорядочены случайным образом. Задача состоит в том, чтобы обратно собрать картинку из данных кусков (нечто наподобие пазла). Для того чтобы ещё сильнее задержать зомби, к картинкам дополнительно применялся гауссов шум.
Формат входных данных совпадает с предыдущей версией задачи, за исключением того что в первой строке каждого запроса записаны три целых числа h, w и k (1 ≤ h, w ≤ 600, 2 ≤ k ≤ 16) — высота (количество строк) и ширина (количество столбцов) фотографии, а также количество кусков соответственно. Количество кусков делит высоту, высота каждого куска равна h / k.
Снова, вам потребуется обработать только один файл входных данных, и вам предоставлены такие же файлы, как и в предыдущей версии задачи.
Выведите q строк. В i-й из этих строк выведите ответ на i-й вопрос: последовательность из k чисел π1, π2, ..., πk такую что:
- π является перестановкой {1, 2, ..., k}, то есть каждое число от 1 до k встречается ровно один раз,
- Для всех j = 1, ..., k, πj является позицией (индексом) в оригинальном изображении куска на позиции j во входном изображении (обратите внимание на картинку для большей ясности).
Вторая картинка из набора. Если три куска в оригинальном изображении пронумерованы 1, 2, 3 сверху вниз, то нумерация в картинке справа будет 2, 3, 1. Правильным ответом для данной картинки является 2 3 1.
Как и в предыдущей версии задачи, ваш ответ будет засчитан если он соответствует формату и хотя бы 75% ответов являются правильными. Можно предпосчитать ответы локально и отправить только программу, которая их печатает.
Ссылка для скачивания всех необходимых материалов: http://assets.codeforces.com/files/690/medium_contestant_package.zip
