後続文字列を探す
リストとして
n 個の文字列が与えられます。リスト内の各文字列 s について、同じリストの中から後続文字列 t を見つけることが目的です（t が s と同じ場合も含まれます）。入力
最初の行に整数
n (1 ≤ n ≤ 100 000) が与えられ、これはリストに含まれる文字列の数を表します。続く
n 行には、各文字列がそれぞれ1行ずつ与えられます。文字列はいずれも英小文字のみで構成されています。入力全体に含まれる文字数の合計は を超えないことが保証されています。
出力
入力で与えられた各文字列
s に対して、対応する後続文字列 t を1行に出力してください。Examples
入力 | 出力 |
5
abaca
aba
abacaba
bacab
dabacaba | aba
aba
aba
bacab
dabacaba |
Explanation
たとえば “abaca” の場合、後続文字列は “aba” です。
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB