[COTS 2019] 排名 Vezuv

题目背景

译自 [Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2019/) D2T3。$\texttt{1.5s,0.5G}$。

题目描述

在某场 ICPC Regional 中，组委会决定用队伍名的字典序来决定排名。不幸的是，对于队名以字母 $\texttt{z}$ 开头的队伍，这是相当不公平的。经过讨论，组委会决定：随机抽取一个 $26$ 个字母的排列，用字母的排列对应的字典序来决定排名。有 $N$ 支队伍参加了这场比赛，队伍名都为小写英文字母。 Etna 写了一个程序枚举了 $26!$ 个排列，以期找到能使每个队伍夺冠的排列。但是这个程序至今都没有跑出结果。所以她找来了你，为每个队伍构造一个排列，使得这支队伍夺冠。

输入输出格式

输入格式

第一行，一个正整数 $N$；接下来 $N$ 行，第 $i$ 行一个字符串，表示第 $i$ 支队伍的队伍名。保证队伍名两两不同。

输出格式

输出 $N$ 行： - 如果可能使得这支队伍获胜，输出一个 $26$ 个字母的排列； - 否则，输出 `nemoguce`（克罗地亚语「不可能」）。

输入输出样例

输入样例 #1

3
war
zag
wro

输出样例 #1

agorwzbcdefhijklmnpqstuvxy
agorzwbcdefhijklmnpqstuvxy
gorawzbcdefhijklmnpqstuvxy

输入样例 #2

3
b
ab
aa

输出样例 #2

bacdefghijklmnopqrstuvwxyz
nemoguce
abcdefghijklmnopqrstuvwxyz

输入样例 #3

7
bcada
dbaab
bbabc
ababb
aacdf
bcdff
baddb

输出样例 #3

cbadfeghijklmnopqrstuvwxyz
cdabfeghijklmnopqrstuvwxyz
bacdfeghijklmnopqrstuvwxyz
nemoguce
abcdfeghijklmnopqrstuvwxyz
cbdafeghijklmnopqrstuvwxyz
nemoguce

说明

令 $L$ 为字符串总长度，$|\Sigma|$ 为字符串字符集大小。对于 $100\%$ 的数据，保证： - $1\le N\le 25\, 000$； - $1\le L\le 10^6$； - 队伍名两两不同； - $1\le |\Sigma|\le 26$。 | 子任务编号 | $N\le $ | $L\le $ | $\vert\Sigma\vert\le$ | 得分 | | :--: | :--: |:--: | :--: | :--: | | $ 1 $ | $ 100 $ | $ 10^4 $ | $6$ | $13$ | | $ 2 $ | $ 350 $ | $ 10^4 $ | $26 $ | $32$ | | $ 3 $ | $ 25\, 000 $ | $ 10^6 $ | $26$ | $55$ |