CERN the Lean Tree is a Dryad who likes Physics a lot (Why do you think he is called CERN? Because he likes particle physics!). He wants to join the Incredibly Pro holy Oracles (IPhO) team, as he is told that the IPhO members are all extremely pro in physics and can use their extremely incredible physics skills to predict the future (and find the Higgs Boson). However, he can only enter the IPhO team if he can pass the selection test set by Barr the Bear.
Barr the Bear has given CERN the Lean Tree N strings, filled with only numbers and alphabets, and has told him that he needs to decode the name of the Chosen One from the strings. After asking Kang the Penguin for help (ok, this is cheating, but who cares?), CERN the Lean Tree has found out that the name of the Chosen One is the longest prefix that is common to all the strings.
Sadly, CERN the Lean Tree does not know THAT much programming (he has been spending his whole life on Physics you see), so he needs your help again (ok, this is cheating again, but who cares?). Can you help him solve the riddle and make his dream come true?
Input
The first line contains N, denoting the number of strings given in the input.
The next N lines contains an alphanumeric string each.
Output
Output on a single line a string that is the name of the Chosen One, i.e. the longest common prefix of all the strings.
Constraints
For 30% of test data, N ≤ 10.
For 70% of test data, N ≤ 100.
For 100% of test data, N ≤ 1,000.
For 100% of test data, the length of each string is at most 1,000 characters.
Sample Input 1
3
zrOzrOLinSenOrzOrz
zrOzrOLinSenOwnsOrzOrz
zrOzrOLinSenSoProOrzOrz
Sample Output 1
zrOzrOLinSen
Explanation for Sample Output 1
Clearly, the string "zrOzrOLinSen" is the longest prefix that is common to all the given strings:
- zrOzrOLinSenOrzOrz
- zrOzrOLinSenOwnsOrzOrz
- zrOzrOLinSenSoProOrzOrz