406194: GYM102307 H Hardest Challenge

Memory Limit:256 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Hardest Challengetime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Today is the final and hardest challenge for the prestigious Unlimited National Algorithmic League (UNAL) contest. In the contest we have a passionate clash between two old rivals the Owls and the Goats.

Each team is composed by 3 participants, the members of the Owls participated in $$$A$$$ challenges and for each one, each member received a rating from 'A' to 'Z'. In the same way, the members of the Goats participated in $$$B$$$ challenges and for each one, each member received a rating from 'A' to 'Z'.

For today's challenge each participant will have the rating string resulting from previous challenges and the team must use them to build an unique string of length $$$A$$$ for Owls and $$$B$$$ for Goats. Each position $$$i$$$ of this string must contain a character of the position $$$i$$$ of some team member's string, i.e., if $$$P$$$, $$$Q$$$ and $$$R$$$ are the strings of the team members, the resulting string $$$S$$$ holds $$$S[i] = P[i] \ or \ S[i] = Q[i] \ or \ S[i] = R[i]$$$ for all $$$i = 1,...,n$$$ , where $$$n = A$$$ for Owls and $$$n = B$$$ for Goats.

The string $$$S$$$ of size $$$n$$$ generated by each team will obtain a score calculated as follows:

$$$Score (S) = (\sum_{i=1}^{n} val \langle S[i] \rangle * 127^{\ n - i -1 }) \% \ MOD$$$

Where $$$val \langle S[i] \rangle$$$ corresponds to the ASCII code of the $$$i$$$-th character of the string $$$S$$$ and $$$MOD = 10^{15} + 37$$$.

Then the team with the lowest score will be the winner, if both teams have the same score the game ends in a tie.

Given the rating strings of each participant, calculate who will be the winner of the competition if both build the string with the lowest possible score

Input

The first line contains 2 numbers $$$A$$$ and $$$B$$$ $$$(1 \leq A, B \leq 28)$$$ the length of the Owls and Goats team strings, respectively.

Following 3 lines contains each a string of length $$$A$$$ $$$-$$$ The strings of Owls members.

Following 3 lines contains each a string of length $$$B$$$ $$$-$$$ The strings of Goats members.

Output

Output a line with the winner of the competition "Owls", "Goats" or "Tie" (without quotes)

ExamplesInput
6 6
ANDRES
FELIPE
MANUEL
VICTOR
IVANSS
DIEGOS
Output
Owls
Input
1 28
E
L
I
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCCCCCCCCCC
Output
Goats

加入题单

上一题 下一题 算法标签: