286. Расшифровка сообщения

Недавно Пете на день рождения подарили книгу Yandex Internships: Step To Success. Пете она так понравилась, что он решил написать в Яндекс письмо. Но чтобы программистам было интереснее его читать, он решил зашифровать своё послание.

Для начала Петя взял из книги несколько слов для составления из них текста письма. После этого он независимо для каждого слова заменил буквы в нём с помощью циклического сдвига на $k$ позиций. В качестве подсказки для расшифровки письма Петя указал текст книги, из которой взял слова, на конверте письма. Например, слово yandex при циклическом сдвиге каждого символа на $k=2$ позиции шифруется как acpfgz.

Теперь Яндекс доверяет вам расшифровку данного письма. Расшифруйте письмо, чтобы мы могли ответить Пете как можно скорее.

В первой строке записан текст книги в виде строки $s$ ($1 \leq |s| \leq 10^6$), состоящей из слов, разделенных одинарными пробелами.

В следующей строке на вход даётся число $n$ ($1 \leq n \leq 10^6$) — количество зашифрованных слов. В следующих n строках на вход даются зашифрованные слова $t_i$ ($1 \leq |t_i| \leq 10^6$).

Все слова состоят из строчных латинских букв. Суммарная длина всех зашифрованных слов во входных данных не превосходит $10^6$.

Выведите $t$ строк, $i$-я строка содержит расшифровку слова $t_i$.

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