- Расшифровка сообщения
Недавно Пете на день рождения подарили книгу Yandex Internships: Step To Success. Пете она так понравилась, что он решил написать в Яндекс письмо. Но чтобы программистам было интереснее его читать, он решил зашифровать своё послание.
Для начала Петя взял из книги несколько слов для составления из них текста письма. После этого он независимо для каждого слова заменил буквы в нём с помощью циклического сдвига на k позиций. В качестве подсказки для расшифровки письма Петя указал текст книги, из которой взял слова, на конверте письма. Например, слово yandex при циклическом сдвиге каждого символа на k=2 позиции шифруется как acpfgz.
Теперь Яндекс доверяет вам расшифровку данного письма. Расшифруйте письмо, чтобы мы могли ответить Пете как можно скорее.
Формат ввода
В первой строке записан текст книги в виде строки s (1≤∣s∣≤106), состоящей из слов, разделенных одинарными пробелами.
В следующей строке на вход даётся число n (1≤n≤106) — количество зашифрованных слов. В следующих n строках на вход даются зашифрованные слова ti (1≤∣ti∣≤106).
Все слова состоят из строчных латинских букв. Суммарная длина всех зашифрованных слов во входных данных не превосходит 106.
Формат вывода
Выведите t строк, i-я строка содержит расшифровку слова ti. Примечание
Гарантируется, что для каждого слова зашифрованного текста существует единственный способ расшифровки.