401785: GYM100528 B Игра в 9

B. Игра в 9ограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводstandard inputвыводstandard output

В то время как Вася все пытается реализовать свой алгоритм сортировки вещественных чисел, Петя и Гена играют в занимательную игру. Они по очереди добавляют в конец числа, записанного на доске, по цифре. Игра заканчивается после того, как на доске будет написано 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, поэтому победит Петя.