401785: GYM100528 B Игра в 9
Description
В то время как Вася все пытается реализовать свой алгоритм сортировки вещественных чисел, Петя и Гена играют в занимательную игру. Они по очереди добавляют в конец числа, записанного на доске, по цифре. Игра заканчивается после того, как на доске будет написано N цифр. Если получившееся число делится на 9, то выигрывает Гена, в противном случае — Петя.
Мальчики договорились, что могут использовать не все 10 цифр, а только некоторые из них. Определите, кто выиграет при правильной игре обоих игроков.
Перед началом игры на доске не написано ни одной цифры. Петя ходит первым. Число на доске не должно содержать ведущих нулей. Гарантируется, что нет теста, в котором единственной допустимой цифрой является 0.
Входные данныеПервая строка содержит целое число N (1 ≤ N ≤ 10 000).
Вторая строка содержит количество цифр M (1 ≤ M ≤ 10), которые ребята договорились использовать.
Третья строка содержит M различных цифр.
Выходные данныеЕдинственное слово — Petya, если выиграет Петя, и Gena в случае победы Гены.
ПримерыВходные данные4Выходные данные
1
9
GenaВходные данные
2Выходные данные
2
4 5
GenaВходные данные
4Выходные данные
2
1 2
PetyaПримечание
В первом примере, ребята договорились использовать только цифру 9. В конце игры на доске будет записано число 9999, которое делится на 9, поэтому победителем будет Гена.
Во втором примере, если Петя сначала напишет 4, то Гена допишет 5 и получится 45, которое делится на 9. Если же Петя первым ходом напишет 5, то Гена допишет 4 и получится 54, которое также делится на 9. Таким образом, всегда побеждает Гена.
В третьем примере, могут получиться следующие числа: 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222. Ни одно из них не делится на 9, поэтому победит Петя.