Eraser

Time limit1sMemory limit512 MB

Summary

Pick the alphabetically last name that appears as a subsequence in every scrap and keep bitek when nothing later exists.

Level: Medium7 of 10
Topics: Greedy, String matching
Solved: No attempts yet

Problem

Bitek is fed up with his name. The class register is sorted alphabetically, so Bitek is always among the first to be called on, and no sensible student is eager to answer first.

From today everything will change. Whenever someone calls him "Bitek", he plans to hand over a business card printed with his new name. The trouble is that his only pencil has broken, so he cannot write anything new. All he can do is gather the scraps of paper on which he once scribbled all sorts of nonsense and rub out some of the letters with an eraser.

Every card must show the exact same name, and he must use every single scrap he has (he cannot risk running out of cards). In other words, by erasing some letters from the word on each scrap, all scraps must be turned into the same name. The new name does not have to make any sense. It only has to sit as far toward the end of the register as possible, that is, be as large as possible in dictionary (lexicographic) order.

Put formally: find the lexicographically largest string that is a common subsequence of all the given words. If that string is lexicographically smaller than bitek, Bitek gives up and keeps his old name.

Input

The first line contains a single integer $N$ ( $1 \le N \le 10\,000$ ), the number of scraps of paper. Each of the next $N$ lines contains the word written on one scrap; every word consists only of lowercase English letters. The total length of all words in the input does not exceed $10^7$ .

Output

Print, on a single line, Bitek's new name: the lexicographically largest string that can be obtained by erasing some letters from every word, i.e. the lexicographically largest common subsequence of all the words. If that string is lexicographically smaller than bitek, print bitek instead.

Examples3

Example 1

Input

3
zygzaki
zabawawkapitana
zgryzkamienny

Expected output

zki

Example 2
Input
```
2
blablabla
nicwaznego
```
Expected output
```
bitek
```
Example 3
Input
```
1
zapomnianywojownik
```
Expected output
```
zywwnk
```