ある地域的なICPC大会の運営委員会は、適切な競技環境を確保できなかったため、チームを辞書順で順位付けすることにしました。つまり、チーム名が辞書順で最も小さいチームが優勝となります。
この問題の主人公であるEtnaは、あるチームのリーダーです。そのチーム名は伏せますが、'Z'で始まる名前であるため、非常に不利な立場にあります。運営委員会との長い議論の末、Etnaはより公平な順位付けの方法を勝ち取りました。残念ながら、チームは依然として辞書順で順位付けされますが、辞書順の定義が変更されることになりました。具体的には、運営委員会が英小文字の置換（順列）をランダムに選択し、その置換に基づいて辞書順が自然に定義されます。つまり、置換における文字の順序が、そのまま辞書順の順序に対応することになります。
Etnaはすぐにノートパソコンを取り出し、各チームについて、そのチームが優勝できるような英小文字の置換を見つけるプログラムを作成しました。しかし、そのプログラムは今日に至るまで実行が完了していません。Etnaを助け、同じ機能を持つより効率的なプログラムを作成してください。
入力
1行目に、大会に参加するチームの数 $N$ が与えられます。 続く $N$ 行に、参加するチーム名が与えられます。各チーム名は英小文字のみからなる1つの単語です。もちろん、チーム名はすべて異なります。
出力
入力で与えられた順序に従い、各チームについて、そのチームが優勝できるような英小文字の置換を1行ずつ出力してください。そのような置換が存在しない場合は "nemoguce" と出力してください。そのような置換が複数存在する場合は、そのうちのどれを出力しても構いません。
小課題
$L$ を $N$ 個のチーム名の長さの合計、$K$ をすべてのチーム名に出現する異なる文字の数とします。
| 小課題 | 配点 | 制約 |
|---|---|---|
| 1 | 13 | $1 \le N \le 100, 1 \le L \le 10\,000, 1 \le K \le 6$ |
| 2 | 32 | $1 \le N \le 350, 1 \le L \le 10\,000, 1 \le K \le 26$ |
| 3 | 55 | $1 \le N \le 25\,000, 1 \le L \le 1\,000\,000, 1 \le K \le 26$ |
入出力例
入力 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