後続文字列を探す

リストとして n 個の文字列が与えられます。リスト内の各文字列 s について、同じリストの中から後続文字列 t を見つけることが目的です（t が s と同じ場合も含まれます）。

入力

最初の行に整数 n (1 ≤ n ≤ 100 000) が与えられ、これはリストに含まれる文字列の数を表します。

続く n 行には、各文字列がそれぞれ1行ずつ与えられます。文字列はいずれも英小文字のみで構成されています。

入力全体に含まれる文字数の合計は を超えないことが保証されています。

出力

入力で与えられた各文字列 s に対して、対応する後続文字列 t を1行に出力してください。

Examples

Explanation

たとえば “abaca” の場合、後続文字列は “aba” です。