CSES - Numeropeli
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Uolevi ja Maija pelaavat seuraavaa peliä:

Pelin alussa on kokonaisluku $n$. Pelaajat vähentävät vuorotellen lukua $k$:lla, jossa $k$ on mikä tahansa luvussa esiintyvä positiivinen numero. Pelin voittaja on se, jonka siirron jälkeen luku on 0.

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

Syöte

Syötteessä on yksi kokonaisluku $n$: pelin alussa oleva luku.

Tuloste

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

Rajat
  • $1 \le n \le 10^6$
Esimerkki

Syöte:
17

Tuloste:
Maija

Selitys: Maija poistaa luvusta ensin numeron 7, jolloin siitä tulee 10. Uolevin on pakko poistaa 1, ja luvusta tulee 9. Nyt Maija voittaa pelin poistamalla luvusta 9.