POLSKI SPOJ

Ranking

Tym razem trzeba napisać program, który na podstawie informacji podanych przed turniejem oraz wyników poszczególnych gier, wygeneruje ranking turnieju warcabowego. Na początku każdego turnieju podawane są informacje o uczestnikach turnieju. Są to kolejno: przypisany numer porządkowy, unikalna nazwa zawodnika, składająca się małych liter alfabetu łacińskiego i/lub cyfr o długości nieprzekraczającej 20 znaków oraz siła zawodnika - liczba z przedziału [0-2500]. Dla uproszczenia zakładamy, że wartość siły podczas turnieju nie ulega zmianie. Dalej następuje parowanie uczestników i to co najistotniejsze - gry bezpośrednie, które wymagają od zawodnika skupienia i dostarczają dużo emocji. Wynik każdego pojedynku bezpośredniego zapisywany jest za pomocą dwóch liczb całkowitych a i b oraz litery ze zbioru {W,R,P}. Liczby a i b oznaczają, że zawodnik z przypisanym numerem porządkowym a rozegrał partię z zawodnikiem z przypisanym numerem b. Litera zaś oznacza wynik gry. I tak litera W oznacza, że wygrał zawodnik z numerem porządkowym a. Litera R oznacza remis, a litera P informuje o przegranej zawodnika a i jednocześnie wygranej zawodnika b. W przypadku nieparzystej liczby uczestników, w każdej z rund, jeden z uczestników otrzymuje bonus. Wówczas wartość b równa 0 oznacza, że zawodnik z numerem a otrzymuje w tej rundzie bonus równoważny wygranej. Za wygraną w pojedynku bezpośrednim, zawodnik otrzymuje punkt rankingowy, w przypadku remisu zawodnicy otrzymują po 0.5 punktu każdy, przegrana - to brak punków. Po rozegraniu wszystkich partii wszystkich zaplanowanych rund, trzeba podliczyć punkty i wygenerować ranking. Uczestników turnieju należy sklasyfikować w rankingu według priorytetów:
1. Liczba punktów rankingowych.
2. Liczba wygranych gier bezpośrednich.
3. Siła zawodnika sprzed turnieju.
4. Porządek leksykograficzny nazwy zawodnika.
W przypadku, gdy dwóch lub więcej uczestników ma taką sam liczbę punktów, o jego pozycji w rankingu decyduje kolejno punkt 2, 3 i w ostateczności punkt 4.
Ostatnia informacja to taka, że ranking powinien zawierać trzy kolumny: numer porządkowy listy rankingowej, nazwa zawodnika oraz liczba jego punktów, zapisana z dokładnością do jednej cyfry po kropce dziesiętnej.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego, w pierwszym wierszu podane są dwie liczby całkowite n i r (2 ≤ n ≤ 1000, 1 ≤ r ≤ 11) oznaczające liczbę uczestników turnieju oraz liczbę rund. W kolejnych n wierszach podane są rekordy zawierające informacje o uczestnikach turnieju, przed jego rozpoczęciem. Numery porządkowe są różnowartościowe z przedziału [1,n]. W następnych ((n+1)>>1)*r wierszach podane są informacje o bezpośrednich pojedynkach między uczestnikami turnieju. Należy założyć, że dane są poprawne, tzn. zgodne z zasadami sztuki parowania.

Wyjście
Dla każdego przypadku testowego należy wypisać n wierszy składających się na ranking określony według specyfikacji podanej wyżej. Pomiędzy wydrukowanymi rankingami dozwolony jest dodatkowy znak końca linii.

Przykład

Wejście
1
11 8
1 xyzbartek 1203
2 xyzagata6 1257
5 copyright 1608
3 xyzkarolm4 1136
4 xyz4martyna 1068
11 xyzkalina 981
6 xyz3ziemekxd 987
7 xyzkornel6 1071
8 xyz6marcin 1345
9 xyz5julka 1196
10 xyz4dominik 949
1 7 W
2 10 P
3 5 P
4 0 W
6 9 P
8 11 W
1 5 P
2 11 P
3 7 W
4 10 W
6 0 W
8 9 R
1 9 R
2 3 R
4 5 P
6 8 P
7 0 W
10 11 W
1 10 P
2 0 W
3 11 W
4 9 W
5 8 W
6 7 P
1 6 W
2 7 W
3 9 W
4 8 P
5 10 W
11 0 W
1 4 P
2 5 P
3 8 W
6 11 P
7 10 W
9 0 W
1 0 W
2 6 W
3 4 P
5 9 W
7 11 R
8 10 W
1 8 P
2 4 W
3 6 W
5 7 W
9 11 W
10 0 W

Wyjście
1 copyright 8.0
2 xyz6marcin 5.5
3 xyzkarolm4 5.5
4 xyz4martyna 5.0
5 xyzagata6 4.5
6 xyz4dominik 4.0
7 xyz5julka 4.0
8 xyzbartek 3.5
9 xyzkornel6 3.5
10 xyzkalina 3.5
11 xyz3ziemekxd 1.0