DCEPC14G - God of Nim

no tags 

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:

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

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

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

  4. 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.

  5. 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: 2018-05-17 04:46:39

SG

faceless_man: 2016-06-28 13:33:23

It seems that now i am the God Of Nim :p

Ankit Sultana: 2015-06-11 22:08:44

Good one!

Pagan Min: 2015-06-09 09:56:22

good understanding of grundy numbers :)

(Tjandra Satria Gunawan)(曾毅昆): 2015-06-06 00:52:39

I'm surprised when I see the optimal strategy for "general" nim game is very short to code :-O
this one is short to code too by the way ;-)


Added by:dce coders
Date:2015-04-26
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 PAS-GPC PAS-FPC PYTHON PYPY PYTHON3 PY_NBC