eolymp
bolt
Try our new interface for solving problems
Problems

Нечесна гра

Нечесна гра

Time limit 1 second
Memory limit 64 MiB

Максим та Юрко грають у гру. На початку гри кожному гравцю говорять певний масив чисел. Кожен гравець знає і свій масив, і масив супротивника. Є купка з n камінців. Гравці ходять по черзі. В свій хід можна забрати з купи k камінців, де k - це будь-яке число з масиву, який цьому гравцю дали на початку гри. Програв той, хто не зміг зробити хід. Визначити гравця, який виграє, при оптимальній грі обох гравців.

Input data

В першому рядку вводяться числа 0 ≤ n ≤ 1000(розмір масиву Максима), 0 ≤ m ≤ 1000(розмів масиву Юрка), 0 ≤ s ≤ 1000(кількість камінців у купці на початку гри). В другому рядку вводяться n чисел - масив Максима. В третьому рядку вводяться m чисел - масив Юрка. В четввертому рядку вводиться єдиний символ, що означає гравця, який ходитиме першим. "M" - Максим, "Y" - Юрко.

Output data

Символ, що означає переможця. "M" - Максим, "Y" - Юрко.

Examples

Input example #1
2 3 6
1 2
1 3 4
M
Output example #1
M