Lühisõnum 5

시간 제한1초메모리 제한1024 MB

요약

N개의 문자열이 주어질 때, 모든 문자열을 부분 문자열로 포함하는 가장 짧은 문자열을 출력한다.

난이도: 어려움10점 중 8점
유형: 문자열, 그리디, 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

Kosmoseuurimiskeskus on tuvastanud $N$ planeeti, mille nimed $S\_i$ koosnevad kõik väikestest ladina tähtedest. Keskuse teadurid arvavad, et kui mõnel neist planeetidest on mõistusega elu, siis nad vastavad sõnumile, milles sisaldub nende planeedi nimi.

Kuna kosmiliste sõnumite saatmine on kallis, on vaja koostada võimalikult lühike teade, mis sisaldab alamsõnedena kõigi $N$ planeedi nimesid.

Tuletame meelde, et sõne $s$ on sõne $t$ alamsõne, kui sõne $s$ on võimalik saada sõne $t$ algusest ja lõpust mingi hulga sümbolite kustutamise teel.

입력

Sisendfaili esimesel real on planeetide arv $N$ ja järgmisel $N$ real igaühel ühe planeedi nimi $S\_i$ .

출력

Väljundfaili ainsale reale väljastada väikestest ladina tähtedest koosnev sõnum, mis sisaldab alamsõnedena kõiki sisendis antud planeetide nimesid.

예제1

예제 1
입력
```
4
aba
ac
ba
caab
```
예상 출력
```
abaaccaaba
```