В то время как Вася все пытается реализовать свой алгоритм сортировки вещественных чисел, Петя и Гена играют в занимательную игру. Они по очереди добавляют в конец числа, записанного на доске, по цифре. Игра заканчивается после того, как на доске будет написано N цифр. Если получившееся число делится на 9, то выигрывает Гена, в противном случае — Петя.
Мальчики договорились, что могут использовать не все 10 цифр, а только некоторые из них. Определите, кто выиграет при правильной игре обоих игроков.
Перед началом игры на доске не написано ни одной цифры. Петя ходит первым. Число на доске не должно содержать ведущих нулей. Гарантируется, что нет теста, в котором единственной допустимой цифрой является 0.
Первая строка содержит целое число N (1 ≤ N ≤ 10 000).
Вторая строка содержит количество цифр M (1 ≤ M ≤ 10), которые ребята договорились использовать.
Третья строка содержит M различных цифр.
Единственное слово — _Petya_, если выиграет Петя, и _Gena_ в случае победы Гены.
В первом примере, ребята договорились использовать только цифру 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, поэтому победит Петя.
## Входные Данные
Первая строка содержит целое число N (1 ≤ N ≤ 10 000).Вторая строка содержит количество цифр M (1 ≤ M ≤ 10), которые ребята договорились использовать.Третья строка содержит M различных цифр.
## Выходные Данные
Единственное слово — _Petya_, если выиграет Петя, и _Gena_ в случае победы Гены.
## Примеры
Входные данные419Выходные данныеGenaВходные данные224 5Выходные данныеGenaВходные данные421 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, поэтому победит Петя.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the total number of digits to be written ($1 \leq N \leq 10000$).
Let $ M \in \mathbb{Z} $ be the number of allowed digits ($1 \leq M \leq 10$).
Let $ D \subseteq \{0,1,\dots,9\} $ be the set of allowed digits, with $ |D| = M $, and $ 0 \notin D $ or $ |D| > 1 $ (no test with only digit 0).
Let the game proceed over $ N $ moves: Player Petya moves first, then Gena, alternating. Each player appends one digit from $ D $ to the right of the current number. The number must not have leading zeros (but since the first digit cannot be 0 by guarantee, this is enforced).
Let $ s \in \mathbb{Z} $ be the sum of the digits of the final $ N $-digit number.
**Constraints**
1. $ N \geq 1 $
2. $ D $ contains at least one non-zero digit.
3. The game ends after exactly $ N $ moves.
**Objective**
Determine the winner under optimal play:
- Gena wins if $ s \equiv 0 \pmod{9} $
- Petya wins otherwise
Since the divisibility by 9 depends only on the digit sum modulo 9, and players alternate moves with Petya starting, the game is a finite deterministic two-player zero-sum game with perfect information.
Let $ p = \lceil N/2 \rceil $ be the number of moves by Petya, and $ g = \lfloor N/2 \rfloor $ be the number of moves by Gena.
The total digit sum is $ s = \sum_{i=1}^N d_i $, where each $ d_i \in D $.
The outcome depends on whether Gena can force $ s \equiv 0 \pmod{9} $ regardless of Petya’s play, or Petya can prevent it.
**Formal Objective**
Determine if Gena has a winning strategy in the game where:
- Players alternately choose digits from $ D $, Petya first.
- After $ N $ moves, if the sum of digits $ \equiv 0 \pmod{9} $, Gena wins; else, Petya wins.
Output:
- “Gena” if Gena has a winning strategy
- “Petya” otherwise