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