Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2014 - командный тур


8. Шпионские игры

Ограничение по времени: 4 с.
Ограничение по памяти: 64 МБ

Источник: командный тур межвузовской олимпиады 2014 года

Эдвард Сноуден узнал тайный шифр американского правительства. Слово W с использованием пароля шифруется следующим образом:

  1. Пусть X - первая буква пароля
  2. Заменить все символы в слове Wпо следующей формуле: Wi = A[N(X)][N(Wi)]
  3. Циклически сдвинуть слово W вправо на одну позицию
  4. Повторить предыдущие шаги для остальных букв пароля

Где функция N(c) — номер буквы c в латинском алфавите (N('a') = 1, N('b') = 2, ...)

Сноуден знает, что пароль может состоять только из букв a, b, c или d. Также он знает, что алгоритм работает только со словами, составленными из строчных латинских букв. Сноуден даже знает длину пароля. Чего Сноуден не знает, так это секретный правительственный пароль, но зато он знает одно зашифрованное слово и его же, но незашифрованное.

Помогите Сноудену подобрать пароль по известной паре слов.

Входные данные

В первой строке дано целое число N (2 ≤ N ≤ 19) — длина пароля.

В следующих четырех строках дана матрица букв A. В одной строке матрицы все буквы различны. В одной строке матрицы присутствуют все буквы латинского алфавита.

В предпоследней строке дано слово (его длина не превосходит 10).

В последней строке дано зашифрованное слово из предпоследней строки.

Выходные данные

Вывести пароль, если возможных паролей несколько, вывести их все в лексикографическом порядке по одному на строке.

Пример

Стандартный вводСтандартный вывод
2
bcdefghijklmnopqrstuvwxyza
cdefghijklmnopqrstuvwxyzab
defghijklmnopqrstuvwxyzabc
efghijklmnopqrstuvwxyzabcd
hello
qtmjq
ad
bc
cb
da