Longest Common Suffix Queries
(Rap battle)
You are given a list of
n distinct words: q query words 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
Input | Output |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB