Longest Common Suffix Queries

(Rap battle)

You are given a list of n distinct words: , and a list of q query words , your task is to find the lexicographically smallest word from the list a that is different from w and has the longest common suffix with w.

Input

The first line of the input contains a single integer, n (2 ≤ n ≤ 25 000), representing the number of strings in the list.

The following n lines contain the strings. Each string consists of lowercase English letters and the length of each string does not exceed 30 characters.

The next line contains a single integer, q (1 ≤ q ≤ 25000), representing the number of query strings.

The following q lines contain the query strings.

Each string consists of lowercase English letters and the length of each string does not exceed 30 characters.

Output

For each query, output a single line containing the lexicographically smallest word from the list that is different from the query word and has the longest common suffix with the query word.

Examples