402595: GYM100814 J Game

Salah and Marzo were reading a research paper, when they found a very large string A contains only lower case English letters. They decided to play a game with it. In the beginning, they agreed on a mapping that maps each pair of characters into a new character, for example:

(a, a) -  > b

(a, b) -  > d

(a, c) -  > a

...

(z, y) -  > r

(z, z) -  > o

Then they start playing the game on the string, each move is either LEFT or RIGHT:

LEFT Move takes each two consecutive characters and combines them into a single character starting from the last two characters (two rightmost characters). For example if we have the transformation (a, a) -  > d, (c, a) -  > e and we have the string acaa it becomes ed.

RIGHT Move takes each two consecutive characters and combines them into a single character starting from the first two characters (two leftmost characters). For example if we have the transformation (a, a) -  > d, (d, a) -  > f and we have the string aadaa it becomes dfa. Notice that the last character couldn't be combined with any other character so it's left as is.

They start making moves and alternating turns until they end up with a single character, Salah wins if this character is a vowel, otherwise Marzo wins. Salah always plays first. If both of them are playing in an optimal way, can you determine the winner?

The first line contains T, the number of test cases, then T test cases follow:

Each test case begins with 26 lines, the i^th line contains a string S_i of 26 lowercase english letters. S_i, j is the mapping of letters i and j ('a'=1,'b'=2,...,'z'=26) e.g. S_3, 2 is the mapping of letters 'c' and 'b'. (You can assume that S_i, j = S_j, i for all 1 ≤ i, j ≤ 26 ) The next line of each test case contains the string A ( 1 ≤ |A| ≤ 10, 000 )

The output should consist of T lines, the i^th line is "Salah" if Salah wins in the i^th test case, or "Marzo" otherwise.

1
daeaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
eaaaaaaaaaaaaaaaaaaaaaaaaa
aaaahaaaaaaaaaaaaaaaaaaaaa
aaahaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
acaa

Marzo

Vowel letters are : a, e, i, o, u