ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1712. Шифровальная решётка

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Наш программный комитет использует для разработки задач различные инструменты: почтовую рассылку, систему контроля версий, систему администрирования сайта Timus Online Judge и многие другие. Однако председателю программного комитета постоянно приходится держать в голове пароли, дающие доступ к этим ресурсам. И он, конечно, не может допустить, чтобы какой-то из этих паролей попал в руки участников соревнований и задачи стали заранее известны кому-либо из них.
Не особенно доверяя своей памяти, председатель решил хранить один из паролей в зашифрованном виде. Для этого он решил использовать шифровальную решётку, про которую он когда-то читал в одной занимательной книге.
Шифровальной решёткой называется бумажный квадрат размера 4 × 4 клетки, в котором вырезаны четыре клетки-окошка. Наложив решётку на листок бумаги, имеющий такой же размер, председатель пишет в её окошках первые четыре символа своего пароля (см. рисунок). После этого он поворачивает решётку по часовой стрелке на 90 градусов. При таком расположении все ранее написанные буквы оказываются под решёткой, а в окошках появляется чистая бумага. Он записывает в окошках следующие четыре символа своего пароля, после чего вновь поворачивает решётку на 90 градусов. Записав очередные четыре символа, председатель делает ещё один поворот решётки и после этого пишет последние четыре символа пароля. Теперь, не имея такой же шифровальной решётки, очень трудно восстановить пароль по получившемуся квадрату с 16 символами. Таким образом, председатель программного комитета уверен, что никто из участников соревнования не получит доступа к задачам раньше времени.
Problem illustration
Предположим, в Ваши руки попала решётка, которой пользовался председатель, и получившийся в результате шифрования квадрат с 16 символами. Ваша задача — расшифровать пароль председателя программного комитета.

Исходные данные

В первых четырёх строках дана шифровальная решётка председателя. Окошки в ней обозначены символами «X», а бумага — символами «.». Положение этой решётки соответствует тому положению, с которого председатель начинает записывать свой пароль. Гарантируется, что данная решётка корректна, то есть в процессе шифрования в окошках всегда будут появляться клетки, в которых ещё ничего не записано. Кроме того, известно, что решётка связна, то есть является одним куском бумаги.
В следующих четырёх строках дан квадрат с зашифрованным паролем. Все записанные в квадрате символы — строчные и прописные латинские буквы.

Результат

Выведите строку длиной 16 символов — пароль председателя программного комитета.

Пример

исходные данныерезультат
....
X..X
.X..
...X
Pwoo
Khaa
smrs
odbk
KamkohobPassword
Автор задачи: Алексей Самсонов (подготовка — Александр Ипатов)
Источник задачи: NEERC 2009, Четвертьфинал Восточного подрегиона