Code Submission Evaluation System Login

Datatähti-valmennus

Porraspeli


Task | Statistics


CSES - Porraspeli

Time limit:1.00 s Memory limit:128 MB

Uolevi ja Maija pelaavat porraspeliä, jossa on $n$ porrasta. Portaat on numeroitu $1,2,\ldots,n$. Jokaisella portaalla on alussa tietty määrä palloja $p_1,p_2,\ldots,p_n$. Pelaajat siirtävät palloja alaspäin portaikossa ja voittaja on se, joka siirtää viimeisen pallon.

Joka vuorolla pelaaja valitse portaan $k$, jolla on ainakin yksi pallo ja $k \neq 1$. Sitten pelaaja siirtää valitsemansa määrän palloja portaalta $k$ portaalle $k-1$. Alimmalta portaalta ei voi siirtää palloja, vaan pallot kasautuvat sinne.

Tehtäväsi on selvittää, kumpi pelaaja voittaa pelin, kun Uolevi aloittaa pelin ja molemmat pelaavat optimaalisesti.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $t$: testien määrä. Sitten syötteessä on $t$ testin kuvaus:

Ensimmäisellä rivillä on kokonaisluku $n$: portaiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: pallojen määrä alussa kullakin portaalla.

Tuloste

Tulosta jokaiseen testitapaukseen "Uolevi" tai "Maija" sen mukaan, kumpi voittaa pelin.

Rajat
Esimerkki

Syöte:
3
3
0 2 1
4
1 1 1 1
2
5 3


Tuloste:
Uolevi
Maija
Uolevi