CSES - Lukupeli
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevi ja Maija pelaavat seuraavaa peliä:

Pelin alussa on joukko, jossa on n eri kokonaislukua. Joka vuorolla pelaaja valitsee kaksi lukua a ja b, jotka ovat joukossa, ja lisää luvun |a-b| joukkoon. Tämän saa tehdä, jos kyseinen luku ei ole vielä joukossa. Pelin voittaja on se, joka pystyy lisäämään viimeisen luvun joukkoon.

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

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: lukujen määrä alussa.

Tämän jälkeen syötteessä on n kokonaislukua x_1,x_2,\ldots,x_n: joukossa olevat luvut.

Tuloste

Ohjelmasi tulee tulostaa "Maija" tai "Uolevi" sen mukaan, kumpi pelaaja voittaa pelin.

Rajat

  • 1 \le n \le 10^5
  • 1 \le x_i \le 10^9

Esimerkki

Syöte:

2
4 5

Tuloste:

Maija

Selitys: Tässä tapauksessa joka siirrolla on vain yksi vaihtoehto. Ensin Maija lisää luvun |4-5|=1, ja tämän jälkeen Uolevi lisää luvun |1-4|=3. Lopuksi Maija lisää luvun |1-3|=2, minkä seurauksena Uolevi ei pysty lisäämään mitään lukua, joten Maija voittaa pelin.