DCEPC14G  God of Nim
Amit is a big fan of Nim Game. Literally! He doesn’t just play the game, he fantasizes it. He follows the simple mantra – Eat, Sleep, Nim. His fantasy is overgrown over time that he has starting thinking of himself as God of Nim. Legend has that if you meet him, more often than not he is imagining a game played between you both and how he beats you with comfort.
Frustrated with his never ending Nim fantasy, Mishra decides to give him a taste of his own medicine. Mishra devises a game which looks similar to Nim but is not in reality. Here’s how the game looks:

Game is played between 2 players, taking turns alternatively. Both play optimally.

There are N plies of coins, each containing exactly Pi coins.

There are N integers given. Let’s denote each of them by Ki.

In a single turn, a player can choose a pile Pi and can discard “x” coins from the pile Pi where 1<=x<=Ki. For example – if pile P1 is chosen by a player, then he can discard x coins such that 1<=x<=K1.

Amit always starts the game. The player who cannot make a move loses the game.
If Mishra beats Amit in this game, Amit will have no option but to shed his Nim ego and so we all will be saved. Can you find out if Mishra succeeds?
Input
First line contains T, the number of test cases. Each test cases starts with an integer N in first line. Next line consists of N integers, P1 to PN. Next line consists of N integers, K1 to KN.
1<=T<=10
1<=N<=10000
0<=Pi<=10^9
1<=Ki<=10^9
Output
Output exactly one string per test case, “Mishra” if Mishra wins the game or “Amit” if Amit wins the game.
Example
Input:2
1
5
2
2
4 7
1 3
Output:Amit
Amit
Explanation:
For second test case, one possible way of winning for Amit is – Amit and Mishra discard 1 coin alternatively from first pile, starting from Amit. Then Amit picks up 3 from second pile, Mishra picks up 1 from second pile and Amit finishes the game by picking up 3 coins left in the second pile.
hide comments
nimphy:
20180517 04:46:39
SG 

faceless_man:
20160628 13:33:23
It seems that now i am the God Of Nim :p 

Ankit Sultana:
20150611 22:08:44
Good one! 

Pagan Min:
20150609 09:56:22
good understanding of grundy numbers :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150606 00:52:39
I'm surprised when I see the optimal strategy for "general" nim game is very short to code :O

Added by:  dce coders 
Date:  20150426 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP CPP14 C99 GOSU JAVA PASGPC PASFPC PYTHON PYPY PYTHON3 PY_NBC 