Given strings of lowercase letters, compute the lexicographically largest string that is a
subsequence of all
strings.
String is a subsequence of string
if
can be obtained by deleting some of the letters in
.
It is not required to delete any letters.
String is lexicographically larger than
if
is a prefix of
or, given that index
is the first
mismatch in strings
and
, the
th character of
is larger than the
th character of
.
Constraints
The sum of the lengths of all strings will be at most .
All strings will only contain lowercase letters.
Input Specification
The first line contains a single positive integer, .
The next lines each contain a string of lowercase letters. The string is guaranteed to contain at least one letter.
Output Specification
Output the lexicographically largest common subsequence. In the event no nonempty such subsequence exists, output -1
.
Sample Input 1
2
quantum
xyene
Sample Output 1
n
Sample Input 2
1
cba
Sample Output 2
cba
Sample Input 3
3
a
ab
c
Sample Output 3
-1
Comments