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

Uolevi ja Maija pelaavat seuraavaa peliä:

Pelin alussa on joukko, jossa on nn eri kokonaislukua. Joka vuorolla pelaaja valitsee kaksi lukua aa ja bb, jotka ovat joukossa, ja lisää luvun ab|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 nn: lukujen määrä alussa.

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

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1xi1091 \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 45=1|4-5|=1, ja tämän jälkeen Uolevi lisää luvun 14=3|1-4|=3. Lopuksi Maija lisää luvun 13=2|1-3|=2, minkä seurauksena Uolevi ei pysty lisäämään mitään lukua, joten Maija voittaa pelin.