B - Uporządkowany NIM 2

Uporządkowany NIM to gra dwuosobowa. Grę stanowi rząd [asciimath]n[/asciimath] stosów kamieni. W [asciimath]i[/asciimath]-tym stosie znajduje się  [asciimath]a_i[/asciimath] kamieni. Stosy są uporządkowane od lewej do prawej strony, gdzie [asciimath]a_1[/asciimath] to rozmiar pierwszego stosu od lewej strony. Gracze wykonują swoje ruchy na przemian. Pojedynczy ruch polega na wybraniu pierwszego niepustego stosu po lewej stronie i usunięciu z niego dowolnej niezerowej liczby kamieni. Wygrywa ten, kto usunie ostatni kamień w grze.

Ola wykryła podstęp Mariusza! Przypomnijmy, że Mariusz tak ustalał kolejność gry, żeby zawsze mógł wygrać. Za karę Ola postanowiła, że Mariusz może dalej grać w Uporządkowany Nim, ale w swoim ruchu może wziąć co najwyżej 10 kamieni. Ola nadal może w swoim ruchu wziąć dowolną ilość kamieni. Co więcej, Ola zawsze zaczyna. Kto teraz będzie miał strategię wygrywającą?

Wejście

W pierwszej linii znajduje się liczba testów [asciimath]T (1<=T<=100)[/asciimath]. W kolejnych liniach znajduje się  [asciimath]T[/asciimath] zestawów testowych.

W pierwszej linii zestawu testowego znajduje się liczba [asciimath]n (1<=n<=10000)[/asciimath]. W drugiej linii zestawu testowego znajduje się n liczb [asciimath]a_1,...,a_n (1<=a_i<=1000)[/asciimath].

Wyjście

Dla każdego zestawu testowego należy wypisać jedną linię:

  • "OLA" - jeżeli Ola może wygrać grę, niezależnie od ruchów Mariusza
  • "MARIUSZ" - jeżeli Mariusz może wygrać grę, niezależnie od ruchów Oli

Przykład

Wejście:
6
1
5
2
3 4
2
1 2
2
1 11
2
1 10
4
3 4 3 4

Wyjście:
OLA
OLA
MARIUSZ
OLA
MARIUSZ
OLA

Objaśnienie przykładu:

W pierwszej grze znajduje się jeden stos z 5 kamieniami. Wygrywa Ola biorąc w pierwszym ruchu wszystkie kamienie.

W drugiej grze są dwa stosy z 3 i 4 kamieniami. Ruchem wygrywającym jest wzięcie dwóch kamieni z pierwszego stosu. To wymusza na Mariuszu wzięcie jednego kamienia. W kolejnym ruchu Ola bierze wszystkie cztery kamienie z drugiego stosu i wygrywa grę.

W trzeciej grze Ola musi wziąć jeden kamień z pierwszego stosu. Mariusz wygrywa biorąc wszystkie pozostałe kamienie.

Please log in to submit your solution.