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.