POLSKI SPOJ

Zadanie dotyczy zmodyfikowanej wersji gry w kółko i krzyżyk.

Zasady gry

Według Międzynarodowej Federacji Kółka i Krzyżyk Bis (MFKiKB) zasady są następujące: w grze bierze udział dwóch graczy. Na płaskiej planszy w formie prostokąta podzielonego równomiernie na w wierszy i k kolumn, tworzących w sumie wk ≤ 24 pól, gracze na przemian umieszczają znaki graficzne. Jeden z graczy posługuje się krzyżykiem - znakiem zbliżonym do "X" (wielka litera iks), z kolei drugi gracz posługuje się kółkiem - znakiem zbliżonym do "O" (wielka litera o).

Gracze wykonują ruchy na przemian. Wykonując ruch, gracz wybiera jedno z niewykorzystanych jeszcze pól, a następnie umieszcza w nim swój znak graficzny.

Gra kończy się, gdy wszystkie pola na planszy są już wykorzystane. Rezultat gry, oznaczany symbolem r, jest liczbą całkowitą spełniającą nierówność: -m ≤ r ≤ m, m < 100. Interpretacja wyniku jest następująca:

• Jeśli r > 0, to gracz posługujący się krzyżykiem zwyciężył.
• Jeśli r = 0, to gra zakończyła się remisem
• Jeśli r < 0, to gracz posługujący się kółkiem zwyciężył.

Niestety, MFKiKB nie udostępniła do tej pory pełnej informacji, jak należy ocenić wynik zakończonej gry - do tej pory rozgrywki przebiegają w taki sposób, że gracze po zakończonej partii składają do MFKiKB podanie o werdykt. Następnie organizacja ocenia jej wynik. Wiadomo, że werdykt nie zależy od kolejności wykonywanych ruchów, a jedynie od końcowego rozmieszczenia znaków graficznych. A więc w przypadku, gdy gra zakończy się w sytuacji identycznej jak partia oceniana już wcześniej, nie trzeba zwracać się do MFKiKB o werdykt, co pozwala graczom obniżyć nieco koszta tej niebanalnej rozrywki (niektórzy uważają, że opłaty pobierane przez MFKiKB przy wydawaniu werdyktów są zbyt wysokie). Wiadomo również, że jeśli cyklicznie przestawimy wiersze lub kolumny, to werdykt będzie identyczny.

Zadanie

Z powodów wspomnianych wcześniej, grupa graczy zrzeszonych w "LCG Pseudolosovia" kolekcjonuje zapisy swoich rozgrywek i werdyktów wydanych przez MFKiKB. Z biegiem czasu nazbierało się ich dość sporo tak, że bez pomocy komputera trudno stwierdzić czy dana sytuacja już kiedyś wystąpiła, czy też nie. I tu pojawia się zadanie dla programisty. Na podstawie znanych przebiegów rozgrywek należy określić wynik gry.

Opis Wejścia

Na wstępie należy zaznaczyć, że styl gry członków Pseudolosovii jest dość specyficzny. Mianowicie każdy z graczy obiera sobie trzy liczby, które nazywa swoją "strategią": 0 ≤ x, a, c < wk, a pola planszy numeruje liczbami od 0 do wk-1.

Mając ponumerowane pola planszy i obraną swoją "strategię" gracz wykonuje swój pierwszy ruch stawiając znak na polu o numerze x (jeśli jest zajęte, to na kolejnym), a następnie oblicza nową wartość x = (ax+c) % wk (reszta z dzielenia przez liczbę pól sumy c oraz iloczynu a i poprzedniej wartości x). W kolejnych ruchach każdy z graczy wykonuje ruch na polu o obliczonym numerze x, lub na pierwszym wolnym (jeśli aż do końca planszy wszystkie pola są zajęte, to zaczynamy szukać pierwszego wolnego od początku), a następnie oblicza nową wartość x. Zazwyczaj na jednej grze się nie kończy i gracze po zakończeniu jednej rozgrywki zaczynają kolejną używając jako x wartości obliczonej na podstawie ostatnio użytej w zakończonej właśnie partii. Mówimy wtedy o meczu rozegranym pomiędzy dwoma zawodnikami. Pierwszą z rozgrywek danego meczu rozpoczyna gracz stawiający krzyżyki. Jeśli plansza ma parzystą liczbę pól to tak jest do końca meczu, w przeciwnym razie co drugą rozgrywkę rozpoczyna gracz posługujący się kółkiem.

Na wejściu dane jest t - liczba testów i dalej dla każdego testu:

• najpierw w, k i m - parametry gry
• następnie M - liczba meczy,
• dla każdego meczu:
  • najpierw siedem liczb: "strategie" dwóch graczy oraz l - liczba rozegranych partii w meczu, a następnie
  • l liczb - werdyktów MFKiKB.
• następnie q - liczba zapytań
• i q zapytań, z których każde opisuje końcową sytuację na planszy. Zapytanie składa się z jednego wiersza składającego się z ciągu o długości wk złożonego ze znaków 'X' i 'O' odpowiadających znakom graficznym umieszczonym na kolejnych polach planszy.

  Uwaga: Zapytania mogą pochodzić od graczy z innych klubów, można jednak założyć, że liczba kółek i krzyżyków różni się o co najwyżej jeden, to znaczy każda sytuacja pochodzi z partii rozegranej zgodnie z zasadami.

Opis wyjścia

Dla każdego testu, dla każdego zapytania jedna liczba będąca znanym werdyktem dla tej sytuacji lub znak '?', jeśli nie da się określić werdyktu. Kolejne odpowiedzi należy oddzielać spacją, a wyniki dla kolejnych testów znakiem nowej linii.

Przykład

Wejście:

1
2 3 1
3
0 5 4 3 5 2 3
1 1 1
2 0 1 4 0 0 2
1 -1
0 3 4 3 2 1 2
1 1
2
XOOXXO
XXXOOO

Wyjście:

-1 ? 

Interpretacja wejścia

Jeden przypadek testowy, w którym gra odbywa się na planszy o dwóch wierszach i trzech kolumnach pól (w=2, k=3). Możliwe wyniki zakończenia gry, to -1, 0 i +1 (m=1). Odbywają się trzy mecze.

W pierwszym biorą udział zawodnicy o strategiach: 0 5 4 i 3 5 2. Rozgrywają trzy partie wykonując ruchy odpowiednio na polach:
0 3 4 5 1 2 (pierwsza partia)
4 5 0 3 1 2 (druga partia)
0 3 4 5 1 2 (trzecia partia)
Wszystkie gry wygrał gracz posługujący się krzyżykiem.
itd...
W kolejnych partiach wystąpiły następujące sytuacje końcowe:

XXO
OXO
r=1

XXO
OXO
r=1

XXO
OXO
r=1

OXX
XOO
r=1

OXX
OXO
r=-1

XOO
OXX
r=1

XOO
OXX
r=1

Interpretacja wejścia

Dla pierwszego zapytania wynik można określić na podstawie werdyktu drugiej partii drugiego meczu:

OXX
OXO

cykliczne przesunięcie kolumn w lewo

XXO
XOO

a następnie cykliczne przesunięcie wierszy do góry (lub na dół)

XOO
XXO

daje żądaną sytuację.

W drugim zapytaniu określenie wyniku nie jest możliwe.

Sugerowane rozwiązanie

Wszystkie ocenione sytuacje można zapamiętać wraz z wynikami w jednej tablicy w taki sposób, że numer elementu jednoznacznie identyfikuje sytuację powstałą na planszy, a jego wartość opisuje znany wynik. Odpowiadając na zapytanie trzeba wtedy przeliczyć podaną sytuację na planszy na odpowiedni numer elementu i sprawdzić jego wartość w tablicy.

Przykład dla w=1 i k=3. Traktujemy ciąg trzech znaków jako liczby binarne traktując 'O' jako 0 i 'X' jako 1. Nasza tablica miałaby wtedy 8 elementów, w tym dwa o numerach 0 i 7 niemożliwe do uzyskania.

Przykładowe dane

Przykładowe dane testowe są tu