AlgoLiga 2018

Wybory

Nastał czas wyborów do Bajtoparlamentu. Większość krajów wspólnoty Bajtocji stosuje ordynację większościową, w której zwycięzca bierze wszystko. W Bitocji postanowiono to zmienić i wprowadzić nowy, bardziej sprawiedliwy system przydzielania mandatów. Bitocka Komisja Wyborcza wprowadziła kryterium Condorceta, według którego kandydat zostaje zwycięzcą, jeśli zdobędzie największą liczbę wygranych w wyborach będących bezpośrednimi pojedynkami.

W ordynacji tej wyborcy nadają własne preferencje porządkowe kandydatów. I tak np. rozpatrzmy wybory, w których startuje trzech kandydatów A, B, C. Jedni wyborcy będą preferować porządek CAB, drudzy porządek BAC, a inni będą mieli własne, odmienne preferencje. Na potrzeby przykładu załóżmy, że wyborcy zagłosowali na trzy preferencje odpowiednio w liczbie:
CAB 12
BAC 10
ABC 7
i nikt nie zagłosował na pozostałe preferencje poza wyżej wymienionymi. Chcąc sprawdzić wynik w bezpośrednim pojedynku wyborczym A przeciwko B, wystarczy usunąć C i zsumować wyniki z porządkiem AB przeciwstawiając sumę wyników z porządkiem BA. Okazuje się, że A wygrywa z B stosunkiem 19:10.
Po przeciwstawieniu wszystkich możliwych par otrzymujemy:
AB - 19:10
AC - 17:12
BC - 17:12
Według tego kryterium kandydat A wygrał dwukrotnie, dalej plasują się kandydaci B i C z wynikiem odpowiednio 1 i 0. W przypadku, gdy pewna para kandydatów ma jednakową sumę, żaden z nich nie wygrywa. Wadą tego systemu jest pewna cykliczność wyników, która nie pozwala czasami wyłonić reprezentantów. Bitocka Komisja Wyborcza postanowiła w takim przypadku przeprowadzić dodatkowe wybory, tzn. do powtórzenia wyborów dojdzie, jeśli kilku kandydatów będzie miało  taką samą liczbę wygranych, i dla któregoś z tych kandydatów zabraknie mandatu.

Bitocja podzielona jest na okręgi, gdzie n kandydatów walczy o m mandatów. Podczas wyborów każdy uprawniony Bitocjanin przedstawia swoje preferencje porządku kandydatów i na podstawie wszystkich wyników, stosując kryterium Condorceta, z każdego okręgu wybierani są Bajtoparlamentarzyści. Teraz pozostaje już tylko zinformatyzować system i to jest zadanie dla Ciebie.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę okręgów w Bitocji. Dla każdego okręgu w pierwszym wierszu podane są trzy liczby całkowite, n, m, p (2 ≤ n ≤ 10, 1 ≤ m ≤ n, 1 ≤ p ≤ n!), gdzie n to liczba kandydatów w okręgu, m - liczba mandatów do zdobycia, a p to liczba preferencji wyborców.
W kolejnych p wierszach podane są preferencje i ich liczba k (1 ≤ k ≤ 10⁹). Każda preferencja jest pewną n-permutacją ciągu złożonego z wielkich liter: A,B,C,D,E,F,G,H,I,J, które to oznaczają kandydatów w okręgu.
Dane wejściowe nie przekraczają 10 MB. Ponadto wiadomo, że liczba uprawnionych do głosowania Bitocjan w danym okręgu jest mniejsza od 2³².

Wyjście
Na wyjściu, dla każdego okręgu, należy podać ciąg m liter (kandydatów), którzy uzyskali mandat, albo wypisać słowo NIE, jeśli będzie trzeba przeprowadzić dodatkowe wybory.
Porządek liter powinien odpowiadać rankingowi kandydatów po zastosowaniu kryterium Condorceta. Jeśli co najmniej dwóch kandydatów ma jednakową liczbę rankingową, należy zastosować porządek leksykograficzny.


Przykład

Wejście
3
3 1 3
CAB 12
BAC 10
ABC 7
3 2 4
ABC 10
BCA 7
CBA 11
ACB 8
3 2 4
ABC 10
BCA 8
CBA 11
ACB 8

Wyjście
A
NIE
CB