Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 17 24 de maio
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #08]


[DAA 029] Ordem rara
(este problema é essencialmente uma tradução/adaptação de um problema do UVA Online Judge)

Um coleccionador de livros raros descobriu recentemente um livro escrito numa língua pouco familiar mas que usa o mesmo conjunto de caracteres usados na língua inglesa. O livro possui um pequeno índice, contudo a ordem dos itens do índice é diferente da que se esperaria encontrar caso os caracteres estivessem ordenados da mesma forma que no alfabeto inglês (composto por 26 letras). O coleccionador tentou usar o índice para determinar a ordem dos caractéres (i.e. a sequência de junção) do alfabeto estranho, mas acabou por desistir atendendo a que a tarefa se revelava frustante e fastidiosa.

O índice é constituído por um conjunto de palavras que sabemos que vêm ordenadas na "ordem que queremos descobrir". Por exemplo, o indíce poderia ser:

XWY
ZX
ZXY
ZXW
YWWX

Com isto consegue-se descobrir as relações entre letras. Por exemplo, como a palavra XWY vem antes de ZX, sabemos que na língua do livro a letra 'X' vem antes da letra 'Z'. Sabemos também que a letra 'Y' vem depois de 'Z' porque ZXW aparece antes de YWWX. Finalmente, sabemos que a letra 'W' vem depois de 'Y', porque a palavra ZXW vem depois de ZXY.

Com todas estas considerações, sabemos que a ordem correcta das letras da lingua "estranha" só pode ser XZYW.

O Problema

A tua tarefa é escrever um programa para completar o trabalho do coleccionador. Em particular, o teu programa deverá receber um conjunto de palavras ordenadas associadas a uma dada sequência de ordem das letras e determinar qual é essa sequência.

Input

Na primeira linha vem um número inteiro N indicando o número de palavras a ler. Seguem-se N linhas, cada uma com uma palavra Pi contendo apenas letras maiúsculas.

As linhas vêm ordenada pela ordem que pretende descobrir.

Output

Deve ser imprimida uma única linha contendo as letras maiúsculas na ordem determinada pela sequência de junção usada para produzir o input. Apenas devem aparecer os caracteres que aparecem no input.

Para os casos de teste dados, é garantido que existe uma e só uma ordem para a qual o input faz sentido.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 100     Número de palavras
1 ≤ |Pi| ≤ 10     Tamanho de cada palavra

Exemplo de Input

5
XWY
ZX
ZXY
ZXW
YWWX

Exemplo de Output

XZYW

 


Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto