POLSKI SPOJ

Opis

W sklepach brakuje pieluch. Bajdocja jest już największym importerem smoczków, a wózki dziecięce drożeją szybciej niż mieszkania. W tempie dotąd niespotykanym rośnie nam nowe pokolenie. A wszystko to przez zarządzenia wprowadzone przez charyzmatycznego Ministra Dedukcji Bajdockiej:

• Bajdockie becikowe
• Codzienne wyłączenia prądu w godzinach od 21:00 do 23:00
• Sprowadzenie dużej liczby bocianów z Polski

Chodzą także plotki, że za zgodą najwyższych władz dokonano sabotażu w fabrykach baloników na terenie całego kraju. Na prawdziwe oblężenie szykują się przedszkola, dlatego zaczęto opracowywać już programy komputerowe wspomagające panie przedszkolanki. Jeden z nich ma pomagać w ocenie jakości słów pisanych przez dzieci w zeszytach. Pani przedszkolanka zapisuje dane słowo na tablicy, a każde z kilkuset dzieci znajdujących się na sali przepisuje je do zeszytu. Następnie, rozproszony system kamer umieszczonych w suficie przedszkola robi zdjęcia, które poddawana są dalszej obróbce. Jej wynikiem jest słowo w postaci tekstowej odczytane przez OCR. Dziecko otrzymuje ocenę proporcjonalną do tego, jak bardzo słowo odczytane przez OCR jest podobne do słowa napisanego przez panią przedszkolankę. Reguły oceny podobieństwa słów są następujące. Jeśli słowa mają różną długość, to podobieństwo wynosi 0. Jeśli słowa mają taką samą długość, to podobieństwo słów jest równe sumie podobieństw kolejnych odpowiadających sobie literek. Jeśli literki są takie same, to ich podobieństwo wynosi 1. Jeśli literki różnią się tylko wielkością (np. "k" i "K"), to podobieństwo wynosi 0.7 (wyjątek: podobieństwo pomiędzy "t", a "T" wynosi 0.4). Ponadto, podobieństwo pomiędzy parami małych liter "w", "n", "m", "u", "r" wynosi 0.5. Podobieństwo pomiędzy parami małych liter "b", "d", "g" wynosi 0.45. Podobieństwo pomiędzy małymi "x" i "r" wynosi 0.3. Inne pary liter nie są do siebie podobne (ich podobieństwo wynosi 0). Twoim zadaniem jest uporządkowanie dzieci zgodnie z oceną otrzymaną za napisanie danego słowa.

Specyfikacja wejścia

W pierwszym wierszu wejścia znajduje się liczba następujących testów. W pierwszym wierszu każdego testu jest słowo napisane przez przedszkolankę, składające się z liter alfabetu angielskiego. Maksymalna długość słowa wynosi 15 liter. W kolejnym wierszu jest dodatnia liczba całkowita N - liczba dzieci w klasie. Klasy nie przekraczają 1000 osób. W kolejnych N wierszach znajdują się słowa napisane przez kolejne dzieci (1-wsze, 2-gie, n-te). Słowa składają się z maksymalnie 15 liter alfabetu angielskiego. Kolejne testy są oddzielone pojedynczą pustą linią.

Specyfikacja wyjścia

Dla każdego testu, w wierszu należy podać numery dzieci uporządkowane nierosnąco zgodnie z oceną otrzymaną za napisanie danego słowa. W przypadku, gdy dwoje lub więcej dzieci otrzymało tę samą ocenę, dziecko z niższym numerem powinno znaleźć się pierwsze.

Przykład

2
Odgrzybiacz
3
Odbrzybiacz
Odgrzybiacz
odgrzybiacz

Ministerstwo
4
Ninisterstwo
Mimisterstwo
inisterstwom
inisterstwoo

2 3 1
2 1 4 3