CSES - Porraspeli
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi ja Maija pelaavat porraspeliä, jossa on nn porrasta. Portaat on numeroitu 1,2,,n1,2,\ldots,n. Jokaisella portaalla on alussa tietty määrä palloja p1,p2,,pnp_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 kk, jolla on ainakin yksi pallo ja k1k \neq 1. Sitten pelaaja siirtää valitsemansa määrän palloja portaalta kk portaalle k1k-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 tt: testien määrä. Sitten syötteessä on tt testin kuvaus:

Ensimmäisellä rivillä on kokonaisluku nn: portaiden määrä.

Seuraavalla rivillä on nn kokonaislukua p1,p2,,pnp_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

  • 1t100001 \le t \le 10000
  • 1n1051 \le n \le 10^5
  • 0pi1090 \le p_i \le 10^9
  • lukujen nn summa on yhteensä enintään 10510^5

Esimerkki

Syöte:

3
3
0 2 1
4
1 1 1 1
2
5 3

Tuloste:

Uolevi
Maija
Uolevi