Codeforces Round 290 (Div. 2) |
---|
Закончено |
Лиса Ciel собирается опубликовать статью по ЛИС (Лисооперируемым Интеллектуальным Системам). Она слышала, что список авторов научной статьи всегда сортируется в лексикографическом порядке.
После изучения примеров оформления, лиса обнаружила, что иногда это утверждение не верно. В некоторых статьях имена авторов не сортируются в лексикографическом порядке в обычном понимании. Но, оказывается, верно то, что после некоторого изменения порядка букв в алфавите, порядок авторов становится лексикографическим!
Лиса хочет знать, существует ли такой порядок букв латинского алфавита, что имена авторов предлагаемой ею статьи следуют в лексикографическом порядке. Если да, то требуется также найти любой такой порядок.
Лексикографический порядок определяется следующим образом. Мы сравниваем s и t, сперва находя крайнюю левую позицию с различающимися символами: si ≠ ti. Если такой позиции нет (то есть, s — это префикс t или наоборот), то более короткая строка меньше. В противном случае мы сравниваем символы si и ti согласно их порядку в алфавите.
В первой строке записано целое число n (1 ≤ n ≤ 100), количество имен.
В каждой из следующих n строк записано по одному слову namei (1 ≤ |namei| ≤ 100), обозначающему i-е имя. Каждое имя содержит только строчные буквы латинского алфавита. Все имена различны.
Если существует такой порядок букв, при котором имена в данном списке следуют в лексикографическом порядке, выведите любой такой порядок в виде перестановки символов 'a'–'z' (иными словами, выведите сначала первую букву модифицированного алфавита, затем вторую, и так далее).
В противном случае выведите единственное слово «Impossible» (без кавычек).
3
rivest
shamir
adleman
bcdefghijklmnopqrsatuvwxyz
10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer
Impossible
10
petr
egor
endagorion
feferivan
ilovetanyaromanova
kostka
dmitriyh
maratsnowbear
bredorjaguarturnik
cgyforever
aghjlnopefikdmbcqrstuvwxyz
7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck
acbdefhijklmnogpqrstuvwxyz
Название |
---|