A Alice e o
Bernardo são dois amigos que adoram trocar mensagens e estão sempre a
enviar papelinhos um para o outro. O Carlos, curioso como é, decidiu
descobrir de que é que a Alice e o Bernardo tanto falam e começou a
interceptar alguns dos papelinhos. A Alice e o Bernardo
contra-atacaram, complicando-lhe a tarefa de compreender as mensagens.
As mensagens são trocadas em forma de texto, usando um conjunto restrito de palavras. Para que o Carlos não descubra facilmente as palavras da mensagem, os dois amigos resolveram que ao invés de escreverem as palavras completas, iriam escrever apenas um fragmento de cada palavra. Um fragmento é uma subsequência contígua de letras da palavra. Por exemplo, na palavra "garfo", alguns fragmentos são "a", "rf", "gar", "fo" ou "garfo", mas há outros, claro.
Para que seja possível depois descodificar a mensagem, os dois amigos pretendem usar fragmentos que identifiquem univocamente as palavras respetivas. Isto quer dizer que qualquer fragmento usado não pode ser um fragmento de mais que uma palavra. Como o Carlos não conhece o conjunto das palavras usadas pela Alice e pelo Bernardo, não vai conseguir entender o que eles escrevem! Preguiçosos como são, os dois amigos acharam que seria boa ideia usar como representante de cada palavra o menor fragmento possível. Se existirem vários fragmentos de comprimento mínimo, então escolherão aquele que for alfabeticamente menor.
Imagina por exemplo que a Alice e o Bernardo trocam mensagens usando um conjunto de cinco palavras: "garfo", "gato", "casa", "foca" e "tocar". Então, eles precisam de descobrir para cada uma dessas cinco palavras um fragmento mínimo de acordo com o que atrás foi descrito. Para "garfo", o menor fragmento que interessa é "rf", com 2 letras. Todos os fragmentos mais curtos, como por exemplo "g" ou "f" aparecem noutras palavras, e todos os outros fragmentos de comprimento 2 também aparecem em pelo menos uma das outras palavras. Já para "tocar", existem dois fragmentos de comprimento mínimo: "toc" e "car". Neste caso devem usar "car", que é alfabeticamente o menor dos dois.
Só que a Alice e o Bernardo perdem imenso tempo a descobrir qual o fragmento que devem usar para cada palavra... Será que podes ajudá-los a despacharem-se?
Dado um conjunto de N palavras, a tua tarefa é descobrir, para cada palavra, qual o seu fragmento unívoco de comprimento mínimo, ou seja, uma subsequência contígua de letras que não aparece em nenhuma das outras palavras. Se para uma mesma palavra existirem vários possíveis fragmentos mínimos, deves escolher aquele que seja alfabeticamente menor. Deves também descobrir as palavras para as quais não existe um fragmento nas condições indicadas.
A primeira linha contém um número inteiro N, o número de palavras a considerar. Seguem-se N linhas indicando as palavras Pi, uma em cada linha. Cada uma das palavras é constituída unicamente por letras minúsculas.
O output é constituído por N linhas, uma por cada palavra, indicando o respectivo fragmento unívoco de comprimento mínimo, tal como atrás descrito. Se não existir nenhum fragmento unívoco, ou seja, se todos os fragmentos aparecem em pelo menos uma das outras palavras, deves escrever "IMPOSSIVEL".
São garantidos os seguintes limites em todos os casos de teste:
| 1 ≤ N ≤ 1 000 | Número de palavras | |
| 1 ≤ comprimento(Pi) ≤ 100 | Tamanho das palavras |
Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N≤40 e comprimento(Pi) ≤ 20.
Para um conjunto de casos de teste valendo 75% dos pontos, acontece sempre que N≤200 e comprimento(Pi) ≤ 50.
5 garfo gato casa foca tocar
rf at s foc car
6 finalistas olimpiadas nacionais informatica final nacional
st d ai r IMPOSSIVEL onal