Префикс на еден збор претставува збор кој ги содржи првите неколку букви од почетниот збор, во истиот редослед. На пример, префикси на зборот кокошка се к, ко, кок, коко, кокош, кокошк, па дури, како краен случај, и кокошка.

За дадена листа од зборови, секој од нив да се "поткастри" од крајот така што ќе се најде најкраткиот префикс кој не е префикс и на некој од останатите зборови во листата.

Влез

Во првиот ред е даден еден цел број N (1 <= N <= 50), кој го означува бројот на зборови. Во секој од следните N редови е даден по еден збор, составен од најмногу 50 мали букви од латиницата. Нема да постои збор кој е префикс на некој друг збор од листата (т.е., секогаш ќе биде можно да се поткастрат зборовите).

Излез

На стандарден излез отпечатете ги бараните префикси, во истиот редослед како што се дадени соодветните зборови на влез (по еден во ред).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
4
ab
de
gh
aab

излез
ab
d
g
aa

влез
1
edenzbor

излез
e