Mutant Vaccine

Time limit2sMemory limit512 MB

Summary

Given up to 100 DNA strings, find the longest substring common to all of them, breaking ties by earliest position in the first string.

Level: Hard8 of 10
Topics: String, String matching, Binary search, Hash map
Solved: No attempts yet

Problem

Dr. Icey Peacie is working on a vaccine for Covid-19. One difficulty with vaccines is that viruses mutate, so there are many different strains circulating. Dr. Peacie wants the vaccine to target a part of the genetic sequence of the virus that all the strains have in common. Can you find the longest piece of RNA that occurs in all of the strains?

Input

The first line of input contains an integer $N$ , the number of strains of the virus, with $1 \le N \le 100$ . The next $N$ lines each contain the genetic sequence of a strain of the virus, a string of the letters A, C, G, and T. Each string has length between 1 and 10 000.

Output

Output a single line containing the longest string that occurs as a substring of all of the strains. If there is more than one such longest string, output the one that occurs earliest in the first strain.

Examples3

Example 1
Input
```
3
GACCAT
CACAT
ACCA
```
Expected output
```
AC
```
Example 2
Input
```
4
ACG
ACGT
ACGT
TTTT
```
Expected output
Example 3
Input
```
2
AGGAGAAG
GAAGAGGA
```
Expected output
```
AGGA
```