C - 怪文書 / Dubious Document

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

すぬけ君は、文字列の書かれた紙から文字をいくつか切り抜いて、並び替えて別の文字列を作るのが好きです。

明日になると、すぬけ君は文字列 S_1,...,S_n のうちどれか 1 つが書かれた紙がもらえます。 すぬけ君は文字列を作る事をとても楽しみにしているので、どんな文字列を作るか計画を立てることにしました。 ただし、すぬけ君はまだどの文字列が書かれた紙がもらえるかを知らないため、 どの文字列が書かれていた場合にも作れる文字列を考えることにしました。

S_1,...,S_n のどの文字列が書かれていても作れる文字列のうち、最長のものを求めてください。 最長のものが複数ある場合は、辞書順で最小のものを求めてください。

制約

  • 1 \leq n \leq 50
  • i = 1, ... , n に対して、 1 \leq |S_i| \leq 50
  • i = 1, ... , n に対して、 S_i は小文字のアルファベット( a - z )からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

n
S_1
...
S_n

出力

条件を満たす最長の文字列のうち、辞書順で最小のものを出力せよ。 そのような文字列が空文字列である場合は、空行を出力せよ。


入力例 1

3
cbaa
daacc
acacac

出力例 1

aac

cbaa, daacc, acacac のどの文字列からも aa, aac, aca, caa などが作れます。 そのうち最も長いものは aac, aca, caa です。 この中で辞書順で最小のものは aac なので、 aac が答えになります。


入力例 2

3
a
aa
b

出力例 2



条件を満たす文字列は空文字列のみです。

Score : 300 points

Problem Statement

Snuke loves "paper cutting": he cuts out characters from a newspaper headline and rearranges them to form another string.

He will receive a headline which contains one of the strings S_1,...,S_n tomorrow. He is excited and already thinking of what string he will create. Since he does not know the string on the headline yet, he is interested in strings that can be created regardless of which string the headline contains.

Find the longest string that can be created regardless of which string among S_1,...,S_n the headline contains. If there are multiple such strings, find the lexicographically smallest one among them.

Constraints

  • 1 \leq n \leq 50
  • 1 \leq |S_i| \leq 50 for every i = 1, ..., n.
  • S_i consists of lowercase English letters (a - z) for every i = 1, ..., n.

Input

Input is given from Standard Input in the following format:

n
S_1
...
S_n

Output

Print the lexicographically smallest string among the longest strings that satisfy the condition. If the answer is an empty string, print an empty line.


Sample Input 1

3
cbaa
daacc
acacac

Sample Output 1

aac

The strings that can be created from each of cbaa, daacc and acacac, are aa, aac, aca, caa and so forth. Among them, aac, aca and caa are the longest, and the lexicographically smallest of these three is aac.


Sample Input 2

3
a
aa
b

Sample Output 2



The answer is an empty string.