Lühisõnum 7

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

요약

주어진 소문자 단어들을 모두 부분 문자열로 포함하는 가장 짧은 문자열을 구한다.

난이도: 어려움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
```