Członkowie komisji pewnego regionalnego konkursu ICPC nie byli w stanie zapewnić odpowiednich warunków zawodów, więc zdecydowali się uszeregować drużyny leksykograficznie. Zatem zwycięzcą zostanie ogłoszona drużyna, której nazwa jest leksykograficznie najmniejsza.
Bohaterka tego zadania, Etna, jest liderką drużyny, której tożsamość zachowamy w tajemnicy, ale wystarczy powiedzieć, że jest to drużyna, której nazwa zaczyna się na literę „Z”, co stawia ją w dość trudnej sytuacji. Po długich dyskusjach z komisją, Etna zdołała wywalczyć nieco sprawiedliwszy sposób rangowania drużyn. Niestety, drużyny nadal będą szeregowane leksykograficznie, ale definicja porządku leksykograficznego ulegnie zmianie. Dokładniej mówiąc, komisja losowo wybierze pewną permutację liter alfabetu angielskiego, a porządek leksykograficzny zostanie naturalnie zdefiniowany za pomocą tej permutacji. Innymi słowy, kolejność liter w permutacji będzie odpowiadać ich porządkowi leksykograficznemu.
Etna natychmiast wyjęła swój laptop i napisała program, który dla każdej drużyny znajduje taką permutację liter, dzięki której właśnie ta drużyna wygra zawody. Niestety, program do dziś nie zakończył działania. Pomóż Etnie i napisz wydajniejszy program o tej samej funkcjonalności.
Wejście
W pierwszym wierszu znajduje się liczba naturalna $N$, oznaczająca liczbę drużyn biorących udział w zawodach.
W kolejnych $N$ wierszach znajdują się nazwy drużyn biorących udział w zawodach. Nazwa każdej drużyny składa się z jednego słowa, które z kolei składa się z małych liter alfabetu angielskiego. Oczywiście nazwy drużyn są parami różne.
Wyjście
Dla każdej drużyny, w kolejności podanej w danych wejściowych, należy w osobnym wierszu wypisać permutację liter alfabetu angielskiego, dzięki której ta drużyna wygra zawody. Jeśli taka permutacja nie istnieje, należy wypisać słowo „nemoguce”, a jeśli istnieje wiele takich permutacji, wystarczy wypisać dowolną z nich.
Podzadania
Niech $L$ będzie sumą długości słów wszystkich $N$ drużyn, a $K$ liczbą różnych liter występujących w nazwach wszystkich drużyn.
| podzadanie | liczba punktów | ograniczenia |
|---|---|---|
| 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$ |
Przykład
Wejście 1
3 war zag wro
Wyjście 1
agorwzbcdefhijklmnpqstuvxy agorzwbcdefhijklmnpqstuvxy gorawzbcdefhijklmnpqstuvxy
Wejście 2
3 b ab aa
Wyjście 2
bacdefghijklmnopqrstuvwxyz nemoguce abcdefghijklmnopqrstuvwxyz
Wejście 3
7 bcada dbaab bbabc ababb aacdf bcdff baddb
Wyjście 3
cbadfeghijklmnopqrstuvwxyz cdabfeghijklmnopqrstuvwxyz bacdfeghijklmnopqrstuvwxyz nemoguce abcdfeghijklmnopqrstuvwxyz cbdafeghijklmnopqrstuvwxyz nemoguce