{"raw_statement":[{"iden":"statement","content":"В то время как Вася все пытается реализовать свой алгоритм сортировки вещественных чисел, Петя и Гена играют в занимательную игру. Они по очереди добавляют в конец числа, записанного на доске, по цифре. Игра заканчивается после того, как на доске будет написано N цифр. Если получившееся число делится на 9, то выигрывает Гена, в противном случае — Петя.\n\nМальчики договорились, что могут использовать не все 10 цифр, а только некоторые из них. Определите, кто выиграет при правильной игре обоих игроков.\n\nПеред началом игры на доске не написано ни одной цифры. Петя ходит первым. Число на доске не должно содержать ведущих нулей. Гарантируется, что нет теста, в котором единственной допустимой цифрой является 0.\n\nПервая строка содержит целое число N (1 ≤ N ≤ 10 000).\n\nВторая строка содержит количество цифр M (1 ≤ M ≤ 10), которые ребята договорились использовать.\n\nТретья строка содержит M различных цифр.\n\nЕдинственное слово — _Petya_, если выиграет Петя, и _Gena_ в случае победы Гены.\n\nВ первом примере, ребята договорились использовать только цифру 9. В конце игры на доске будет записано число 9999, которое делится на 9, поэтому победителем будет Гена.\n\nВо втором примере, если Петя сначала напишет 4, то Гена допишет 5 и получится 45, которое делится на 9. Если же Петя первым ходом напишет 5, то Гена допишет 4 и получится 54, которое также делится на 9. Таким образом, всегда побеждает Гена.\n\nВ третьем примере, могут получиться следующие числа: 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222. Ни одно из них не делится на 9, поэтому победит Петя.\n\n"},{"iden":"входные данные","content":"Первая строка содержит целое число N (1 ≤ N ≤ 10 000).Вторая строка содержит количество цифр M (1 ≤ M ≤ 10), которые ребята договорились использовать.Третья строка содержит M различных цифр."},{"iden":"выходные данные","content":"Единственное слово — _Petya_, если выиграет Петя, и _Gena_ в случае победы Гены."},{"iden":"примеры","content":"Входные данные419Выходные данныеGenaВходные данные224 5Выходные данныеGenaВходные данные421 2Выходные данныеPetya"},{"iden":"примечание","content":"В первом примере, ребята договорились использовать только цифру 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, поэтому победит Петя."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the total number of digits to be written ($1 \\leq N \\leq 10000$).  \nLet $ M \\in \\mathbb{Z} $ be the number of allowed digits ($1 \\leq M \\leq 10$).  \nLet $ 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).  \n\nLet 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).  \n\nLet $ s \\in \\mathbb{Z} $ be the sum of the digits of the final $ N $-digit number.  \n\n**Constraints**  \n1. $ N \\geq 1 $  \n2. $ D $ contains at least one non-zero digit.  \n3. The game ends after exactly $ N $ moves.  \n\n**Objective**  \nDetermine the winner under optimal play:  \n- Gena wins if $ s \\equiv 0 \\pmod{9} $  \n- Petya wins otherwise  \n\nSince 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.  \n\nLet $ 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.  \n\nThe total digit sum is $ s = \\sum_{i=1}^N d_i $, where each $ d_i \\in D $.  \n\nThe outcome depends on whether Gena can force $ s \\equiv 0 \\pmod{9} $ regardless of Petya’s play, or Petya can prevent it.  \n\n**Formal Objective**  \nDetermine if Gena has a winning strategy in the game where:  \n- Players alternately choose digits from $ D $, Petya first.  \n- After $ N $ moves, if the sum of digits $ \\equiv 0 \\pmod{9} $, Gena wins; else, Petya wins.  \n\nOutput:  \n- “Gena” if Gena has a winning strategy  \n- “Petya” otherwise","simple_statement":"Two players, Petya and Gena, take turns adding one digit from a given set to the end of a number, starting from empty. Petya goes first. After N digits are added, if the number is divisible by 9, Gena wins; otherwise, Petya wins. No leading zeros allowed. Given the set of allowed digits, determine the winner with perfect play.","has_page_source":false}