CHGROOM - Room Change

no tags 

It's the end of the semester and best friends Anne and Marian have finally gotten permission from the hostel supervisor to swap rooms and become room mates. Both of them are extremely happy to hear this, but one problem still remains. Although Anne and Marian definitely want to be room mates, both of them are also very attached to their current rooms and neither of them wants to move out.

After a lot of discussion regarding who should be the one to shift rooms, they decide to settle the matter in the following manner:

Both Anne and Marian write down, independently, 2 positive integers k1 and k2. Then, the value q = ( k1 + k2 - 1 ) is written down on a piece of a paper. Anne is the first person to make a move. During each move, the current player writes down any integer number that is a non-trivial divisor of the last written number. The first person who can't make a move wins, and the other person is the one who needs to shift into the winner's room.

Given that both players play optimally, output the name of the person who wins the game for a given value of q.

NOTE: A number's divisor is said to be non-trivial if it is different from one and from the divided number itself.

Input

The input contains a single integer q (1 <= q <= 1013). 

Output

On a single line output "ANNE" if Anne wins. Else output "MARIAN". Note that the quotes are just for clarity, and that the output is case-sensitive.

Example

Input #1:
6
 
Output #1:
MARIAN
Input #2:
30

Output #2:
ANNE
Input #3:
1

Output #3:
ANNE

Explanation

Input #1: 6 has exactly 2 non-trivial divisors - { 2, 3 }. But neither of these numbers have any non-trivial divisors. So no matter which one Anne writes down, Marian will win since she cannot make any move

Input #2: Since 6 is a non-trivial divisor of 30, Anne writes down 6. Now, as can be seen from input #1, no matter what move Marian makes, Anne will win.

Input #3: Since 1 has no non-trivial divisors, Anne wins.


hide comments
David: 2022-06-27 22:09:49

Agree with @nadstratosfer. For other problem solvers, setup # of test cases. Java start-up time is horrendous.
@akshayvenkat - Of course O(sqrt(n)*sqrt(n)) is TLE. O(sqrt(n)*sqrt(n)) = O(n), which is 10^13!

nadstratosfer: 2020-02-05 00:23:35

With 60+ 1-integer testfiles, measured runtime mostly covers server instability or interpreter startup lag. My Py2 solution comes at 1.67s total, probably less than half of it being actual computation. Poor setup giving no room for any magic, possible with this concept, to work.

geeta: 2016-07-08 20:47:20

wrong ans @58!! pls provide some more test cases!!

akshayvenkat: 2016-07-08 20:06:27

O(sqrt(n)*sqrt(n)) giving TLE :(

Last edit: 2016-07-08 20:25:47
hodobox: 2015-12-12 02:51:45

Good question about game theory :)

785227: 2014-06-24 18:33:40

Good question formation :)
+1 to author

Satyam Kumar Shivam: 2013-12-16 20:12:04

getting WA in 63rd test case.. any help ???

joud zouzou: 2013-03-28 08:41:54

My code is giving WA after running(60) :(
what could the problem be??
what is the answer for 10^13??

Last edit: 2013-03-28 08:42:33
Ehor Nechiporenko: 2013-03-27 20:21:39

Yahoo!! The good one task! 1-st one!

rafiki93: 2013-03-26 12:10:54

can you please see why my code is is giving tle?any suggestion would be helpful


Added by:Gowri Sundaram
Date:2013-01-28
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64