---

Номер задачи - 17

Задача Решетка

Ограничение: 3 сек. на один тест  

         В античной Греции основным ключевым моментом победы в войне было знание местоположения и действий врага. Поэтому очень много усилий было затрачено на перехват сообщений разведчика. Естественно другая сторона старалась максимально затаить истинный смысл сообщения. В этот процесс были включены все умы государств. Евклид, гениальный математик разработал способ шифрования сообщений с помощью решетки. Расшифровать исходное сообщение можно было только имея при себе экземпляр такой решетки. Всего решеток было 2е – у автора сообщения и получателя. Сообщения делались такими, чтобы их можно было уместить в такой решетке.

Пусть исходное сообщение выглядело так:

«всем отрядам надо атаковать»

Длина этого сообщения – менее 25 символов (не включая пробелы). Для его зашифровки можно использовать решетку – квадрат 5 на 5. Выглядеть она может так:

Зашифровывается исходное сообщение с помощью следующих действий:

1) Сначала изготавливается решетка на основе ее рисунка – на квадратного листе вычерчивается линиями, и вырезаются ячейки черного цвета;

2) Решетка накладывается на новый чист лист бумаги и слева - направо записывается исходное сообщение в вырезанные ячейки. По одному символу в новую ячейку.

3) Когда закончатся пустые ячейки – решетка поворачивается на 90º и повторяется пп2.

4) Если сообщение заканчивается прежде чем, закончатся пустые ячейки – то в свободные места записываются любые символы.

Так, после 1го наложения решетки и записи сообщения оно будет выглядеть так:

в
			с
	е
м				о
		т

После поворота и второго наложения :

в	р			я
		д	с
а	е
м			м	о
	а	т

После поворота и третьего наложения решетки:

в	р	т		я
а		д	с	к
а	е		о
м	в		м	о
	а	т		а

Четвертого наложения:

в	р	т	т	я
а	ь	д	с	к
а	е		о
м	в		м	о
	а	т		а

В оставшиеся клетки записываются любые буквы – получим зашифрованное сообщение для решетки с размером 5:

врття

аьдск

аейой

мвймо

йатйа

Формат входных данных

Входные данные состоят из 2х блоков. Каждый блок отделяется от другого пустой строкой. В первом блоке записан квадратный тестовый блок – исходное сообщение. Во втором блоке – кодирующая решетка. “.” – означает белая клетка, “x” – черная клетка. Ваша задача – расшифровать сообщение.

Формат выходных данных

Расшифрованное сообщение, записанное в одну строку.

Примеры

Вход	Выход
ab cd .x ..	bdca

Дополнительная информация:

Размер решетки N: 2<=N<=10

Всегда существует единственное решение.