B. Mercury
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On Mount Olympus, gods love to send each other encoded messages. Each message consists of a ciphertext made of lowercase English letters along with $$$n$$$ phrases. To decipher the message, a Caesar$$$^\dagger$$$ cipher is applied to the ciphertext such that the $$$n$$$ phrases all appear as substrings of the resulting string.

Being the one who is always delivering these secret messages, Mercury wants to read these messages, but he cannot figure out how to decipher the text correctly. Your task is to help Mercury decipher the messages. It is guaranteed that an answer exists. If there are multiple possible answers, any valid answer will be accepted.

$$$^\dagger$$$To apply a Caesar cipher to a letter, first convert the letter to a number from 0 to 25 (A=0, B=1, C=2, ..., Z=25), and call this number $$$x$$$. When shifting by $$$k$$$, find $$$(x+k)\bmod 26$$$, and convert this number back to a letter (0=A, 1=B, 2=C, ..., 25=Z). This means that shifting Y (25) by 4 gives a result of C (3). To apply a Caesar cipher to a string, just apply the cipher for every individual letter, keeping the same $$$k$$$ each time.

Input

The first line of input contains $$$s$$$, the ciphertext ($$$1\leq\left|s\right|\leq10^3$$$). It is guaranteed that the ciphertext consists of only lowercase English letters.

The next line contains $$$n$$$, the number of phrases ($$$1\leq n\leq 10^3$$$).

The $$$i$$$th of the next $$$n$$$ lines contains the $$$i$$$th phrase, $$$p_i$$$ ($$$1\leq\left|p_i\right|\leq 30$$$). It is guaranteed that all phrases consist of only lowercase English letters.

Output

Output a single line, the correct deciphered phrase. It is guaranteed that an answer exists. If there are multiple possible answers, print out any valid answer.

Example
Input
ebiiltloia
5
hello
world
hellow
ell
owo
Output
helloworld