最長共通接尾辞 (Longest Common Suffix) クエリ

(ラップバトル)

n 個の異なる単語リスト と、q 個のクエリ単語 が与えられています。ここでの課題は、各クエリ単語 w に対して、リスト a の中から「w と異なる単語のうち、w との共通する末尾部分が最も長く、かつ辞書順で最小の単語」を見つけることです。

入力

入力の最初の行には、文字列の数を表す整数 n (2 ≤ n ≤ 25 000) が与えられます。

続く n 行には、単語が与えられます。各単語は小文字の英字からなり、その長さは最大 30 文字です。

次の行には、クエリ単語の数を表す整数 q (1 ≤ q ≤ 25000) が与えられます。

続く q 行には、クエリ単語が与えられます。

クエリ単語も小文字の英字からなり、その長さは最大 30 文字です。

出力

各クエリについて、クエリ単語と異なり、共通接尾辞が最も長く、かつ辞書順で最小となるリスト内の単語を 1 行に 1 つ出力してください。

例