COCI '10 Contest 6 #4 Abeceda

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 32M

Problem types

A list of words written in some unknown alphabet was found. It is known, however, that these words are in lexicographic order.

Lexicographic word order is the order in which words are arranged in a dictionary. To compare two words, we look for the first position where the letters in the two words differ, and based on that we determine which word is first. If one of the words is the beginning of the other word, the first word is lexicographically before the second word.

Write a program that will find the unique alphabetic ordering of used letters, or determine that no such ordering exists or that there is more than one possible solution.

Input Specification

The first line of input contains a positive integer $N$ ~N~ $(N \leq 100)$ ~(N \leq 100)~, the number of words.

The following $N$ ~N~ lines contain the list of words found, one word per line. Each word consists of at most $10$ ~10~ lowercase letters.

Output Specification

The first and only line of output should contain all letters in alphabetic order. If no such ordering exists, output !. If there is more than one solution, output ?.

Sample Input 1

5
ula
uka
klua
kula
al

Sample Output 1

luka

Sample Input 2

4
jaja
baba
baja
beba

Sample Output 2

Sample Input 3

3
marko
darko
zarko

Sample Output 3

Comments

8

WhyEric commented on Dec. 29, 2023, 8:19 p.m.

anyone else that's getting the last subtask wrong?

0

sugo commented on Aug. 2, 2024, 10:07 p.m.

the last subtask requires you to validate that their input follows lexicographical order (e.g abcd cannot be behind abc no matter what the order of the unknown alphabet is)