Uolevi and Maija have $n$ cups numbered from $0$ to $n - 1$. Cup $i$ contains $a_i$ candies and there is an integer $c_i$ written on its side.

Uolevi and Maija will play a game:

• In each turn, the player chooses a candy from one of the cups except for the cup $0$.
• If he chooses a candy from the cup $i$, he must move it to one of the cups $i - c_i, \ldots, i-1$.
• The players take turns alternately. Uolevi plays first. The player that can't choose a candy loses.

Who will win if both Uolevi and Maija play optimally?

Input

The first line contains integer $n$. The next $n-1$ lines each contain two integers, $c_i$ and $a_i$ for $1 \le i \le n-1$.

Output

Output Uolevi if Uolevi wins, otherwise output Maija

Constraints

• $2 \le n \le 10^5$
• $1 \le c_i \le i$
• $0 \le a_i \le 10^9$

Examples

Input:

3
1 0
1 1

Output:

Maija

Input:

7
1 1
2 0
1 0
2 0
4 1
3 0

Output:

Uolevi

Input:

7
1 1
2 0
1 9
2 10
4 3
3 5

Output:

Maija