По темам/Строки


5. Крипто-войны

Автор задачи: Колотаев Илья
Источник: Первый внутривузовский тур Региональной студенческой предметной олимпиады по программированию 13 марта 2016
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Воин криптографического фронта Антон вчера получил новое задание. Работники института крипторазведки, где Антон работает, выяснили новый способ шифрования, применяемый гадкими врагами для безопасного обмена сообщениями.

Способ этот такой. Все сообщения для обмена должны состоять из латинских строчных букв, без пробелов, знаков препинания и прочих символов. Букве a присваивается код 0, букве b — код 1, и так далее до буквы z с кодом 25. Для того чтобы зашифровать передаваемый текст берется несколько слов из букв строчных латинского алфавита одинаковой длины. Эти слова называются шифробазой. Слова выписываются в круг, так чтобы первый буквы слов шли по вертикальной линии от центра круга вверх. Такой круг называется шифрокруг. Для шифробазы abcde, fghij и klmno приведен пример шифрокруга на первом рисунке.

Далее каждое кольцо круга поворачивается на несколько символов по или против часовой стрелки. Значения таких поворотов называется паролем. Далее выписываются буквы по прямой с верхней части до центра шифрокруга, после чего весь шифрокруг поворачивается на один символ против часовой стрелки и выписывается новый ряд букв по прямой с верхней части до центра шифрокруга, и так далее. Полученная последовательность называется шифропотоком.

Для непосредственного шифрования берут шифропоток такой же длины, что и шифруемое сообщение. Код первой буквы исходного сообщения складывают с кодом первой буквы шифропотока, от суммы берут остаток от деления на 26. Этот остаток и будет кодом первой буквы зашифрованного сообщения. Аналогичным образом поступают со второй, третьей и т.д. буквой исходного сообщения и шифропотока, получая в результате зашифрованное сообщение полностью.

На втором рисунке показан процесс получения шифропотока ajlbfmcgn длиной 9 символов из шифрокруга первого рисунка с использованием пароля (0, -1, 1).

У криптовоина Антона есть несколько пар исходный текст — зашифрованный текст и пароли к ним. Он знает количество и длину слов шифробазы, знает, что для каждой пары исходный текст — зашифрованный текст использовалась одна и та же шифробаза. Также у него есть зафишрованный с помощью этой же шифробазы текст и пароль от него. Этот текст вы и поможете Антону расшифровать.

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

В первой строке входных данных дано целое число N (1 ≤ N ≤ 10) - количество пар исходный текст — зашифрованный текст, находящихся у Антона.

Во второй строке даны два целых числа через пробел: A и B (3 ≤ A ≤ 30, 1 ≤ B ≤ 10) - длина слов шифробазы и их количество соответственно.

Далее дано N троек строк. На первой строке тройки дан исходный текст, Во второй - зашифрованный текст. В третьей B целых чисел через пробел - пароль тройки. Каждый элемент пароля соответствует сдвигу кольца шифрокруга: первый - для внешнего кольца, второй - для кольца внутри внешнего и т.д. Отрицательное значение означает сдвиг кольца против часовой стрелки, положительное - по часовой. Каждое число пароля лежит в диапазоне [ - A + 1..A - 1]. Длина исходного и зашифрованного текстов для каждой тройки совпадают и не превосходят A·B символов.

В предпоследней строке дана единственная строка - зашифрованный текст, который надо расшифровать. Его длина также не превосходит A·B символов.

В последней строке дано B целых чисел через пробел - пароль зашифрованного текста.

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

В единственно строке выходных данных вывести расшифрованный текст или "IMPOSSIBLE" (без кавычек), если расшифровать текст не представляется возможности.

Примеры
Стандартный вводСтандартный вывод
1
5 3
oxwmzjugdhvfryl
odkngtwookervdy
0 -1 1
yfcfita
2 -1 4
vzrbbha
Пояснения к примерам

В тесте из примера использовалась та же шифробаза, что и в примерах в тексте задачи.