Taco Game

You are given a sequence of n positive integers. Two players, Mark and Sam, play a game based on the greatest common divisor (gcd) of the sequence. The rules are simple: compute the greatest common divisor of all numbers in the sequence. If the overall gcd is 1, then the winner is SAM. Otherwise, the winner is MARK.

In mathematical terms, if the sequence is \(a_1, a_2, \dots, a_n\), then let \(g=\gcd(a_1, a_2, \dots, a_n)\). The winner is determined as:

[ \text{Winner} = \begin{cases} SAM & \text{if } g = 1, \ MARK & \text{otherwise.} \end{cases} ]

Your task is to determine the winner given the input sequence.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n which indicates the number of elements in the sequence.
• The second line contains n positive integers separated by spaces.

For example, the input "2\n3 6\n" represents a sequence with two numbers: 3 and 6.

outputFormat

Output the winner's name to the standard output (stdout) as a single line. The output should be either SAM or MARK according to the rule:

• If the overall gcd is 1, output SAM.
• Otherwise, output MARK.

## sample

2
3 6

MARK