시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 1 1 20.000%

문제

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?

입력

The first line of input contains an integer N, the number of strains of the virus, with 1 ≤ N ≤ 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 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.

예제 입력 1

3
GACCAT
CACAT
ACCA

예제 출력 1

AC

예제 입력 2

4
ACG
ACGT
ACGT
TTTT

예제 출력 2


						

예제 입력 3

2
AGGAGAAG
GAAGAGGA

예제 출력 3

AGGA