Bacteria II
By Lucas Maciel, UFMG 
Brazil
By Lucas Maciel, UFMG Brazil
Recently hired for ICPC (Institute of Computing Scientific Research), Doctor Henrique is needing your help again! Heading a project super secret for the Kingdom of Syldavia, Dr. Henrique face a big problem. The bacteria in the project are being destroyed after been contaminated by one type of virus very rare. This virus is capable to destruct each part of genetic code that is the same of its RNA (virus genetic code). Knowing that, Dr. Henrique want create a new type of bacteria that is resistant to this virus, however, he want preserve the largest amount of genetic code of his originals bacteria.
Your objective is to find the largest genetic substring (composed only by proteins A, C, G, T) among all contaminated bacteria groups. Follow an example:
Suppose the RNA of virus is the sequence TCGA. And also suppose that Dr. Henrique has 3 bacteria's DNA:
After the infection, the virus will search for the first part of code from begin of the bacteria's DNA that is the same of its RNA and destruct that. And he will repeat the process until there is no more genetic code to be destructed.
After that all bacteria are infected, we gonna find the largest common substring of all of them. This substring is the DNA of the bacteria that Dr. Henrique want find:
DNA result: GCT
Observations
It's important to say that the virus always search the DNA from beginning. There is always one answer.
The input is composed of many test cases. Each test case have one line with the integer N that means how many bacteria are in the Dr. Henrique project. (1 ≤ N ≤ 20). Following are N lines having one string Si (1 ≤ |Si| ≤ 10000) that are the genetic code of each infected bacteria. The N+2 line have one string R (1 ≤ |R| ≤ 1000) that is the virus RNA. All strings are composed only by the characters: A, C, G, T.
One string by line for each test case that represent the final bacteria DNA. If have more than on possible solution, output the smallest lexicographically.
| Input Sample | Output Sample |
|
3 |
GCT |