The organizers of a regional ICPC competition failed to provide suitable conditions for the contest, so they decided to rank the teams lexicographically. Thus, the team whose name is lexicographically smallest will be declared the winner.

The heroine of this task, Etna, is the leader of a team whose identity we will hide, but it is enough to say that it is a team whose name starts with the letter 'Z', which puts it in a rather poor position. After long discussions with the committee, Etna managed to fight for a somewhat fairer way of ranking the teams. Unfortunately, the teams will still be ranked lexicographically, but the definition of lexicographical order will change. More precisely, the committee will randomly choose a permutation of the English alphabet, and the lexicographical order will be naturally defined using that permutation. In other words, the order of letters in the permutation will correspond to their lexicographical order.

Etna immediately took out her laptop and wrote a program that finds, for each team, a permutation of letters according to which that specific team will win the competition. Unfortunately, the program has not finished running to this day. Help Etna and write a more efficient program with the same functionality.

Input

The first line contains a natural number $N$, representing the number of teams participating in the competition.

The next $N$ lines contain the names of the teams participating in the competition. Each team's name consists of a single word, which in turn consists of lowercase English letters. Naturally, the team names are distinct.

Output

For each team, in the order they are listed in the input, you need to print in a separate line a permutation of the English alphabet according to which that team will win the competition. If no such permutation exists, you need to print the word "nemoguce", and if there are multiple such permutations, it is sufficient to print any one of them.

Subtasks

Let $L$ be the sum of the lengths of the words of all $N$ teams, and $K$ be the number of distinct letters that appear in the names of all teams.

Examples

Input 1

3
war
zag
wro

Output 1

agorwzbcdefhijklmnpqstuvxy
agorzwbcdefhijklmnpqstuvxy
gorawzbcdefhijklmnpqstuvxy

Input 2

3
b
ab
aa

Output 2

bacdefghijklmnopqrstuvwxyz
nemoguce
abcdefghijklmnopqrstuvwxyz

Input 3

7
bcada
dbaab
bbabc
ababb
aacdf
bcdff
baddb

Output 3

cbadfeghijklmnopqrstuvwxyz
cdabfeghijklmnopqrstuvwxyz
bacdfeghijklmnopqrstuvwxyz
nemoguce
abcdfeghijklmnopqrstuvwxyz
cbdafeghijklmnopqrstuvwxyz
nemoguce