J. P-ON
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After getting bored of playing with the Rubik's Cube and submitting Wrong Answers, Ion decided to move on to more interesting activities. He decided to play a game with his good friend Mario on a one dimensional board which can be represented as an array with $$$n$$$ non-negative integers $$$a_1, a_2, a_3, ... , a_n$$$. The game is played by the following rules:

  • They play the game by moving a pawn on the board which is initially placed at position $$$k$$$.
  • Ion takes the first move, and they take moves alternatively.
  • In any move with the pawn at position $$$i$$$, the current player must move the pawn to the smallest next position $$$j$$$ such that $$$j \gt i$$$ and $$$a_j$$$ differs from $$$a_i$$$ on at most one bit in binary representation.
  • The player who can't make any legal move loses the game.

They play this game many times and the board can be modified many times. Ion wants to ask you for some initial states who will win the game.

Input

The first line of input contains $$$2$$$ integers $$$n$$$ and $$$m$$$ $$$(1 \le n,m \le 200000)$$$, denoting the length of the array and the number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2 , ... , a_n$$$ $$$(0 \le a_i \le 255)$$$, denoting the array $$$a$$$.

The next $$$m$$$ lines each contains $$$2$$$ integers $$$op$$$ $$$(1 \le op \le 2)$$$ and $$$k$$$, denoting each operation:

  • $$$op=1$$$ means a modification on the board. Ion will append an integer $$$k$$$ $$$(0 \le k \le 255)$$$ at the end of the array so the array becomes $$$a_1 , a_2 , ... , a_{n+1}$$$ where $$$n$$$ is the current length of the array before modification.
  • $$$op=2$$$ means a new game starts with the pawn at position $$$k$$$ $$$(1 \le k \le n)$$$, where $$$n$$$ is the current length of the array. You need to predict the winner of this game.
Output

For each operation with $$$op=2$$$, output one line containing "Ion" if Ion will win, or "Mario" if Mario will win.

Scoring
  • for $$$20$$$ points it is guaranteed that $$$n \le 1000$$$ and $$$m \le 1000$$$
  • for the other $$$80$$$ points, $$$n \le 200000$$$ and $$$m \le 200000$$$
Example
Input
4 6
7 6 5 4
2 4
1 5
2 4
1 2
2 3
2 2
Output
Mario
Ion
Mario
Mario