Holmes and Peanut’s Prime Factor Game

Holmes and Peanut are playing a math‐related game. Initially, there are \(n\) integers \(a_1, a_2, \dots, a_n\) on the board. They take turns performing exactly one of the following two operations on any number \(a_i\) on the board:

• Operation 1: Replace \(a_i\) with \(\frac{a_i}{p}\), where \(p\) is the largest prime factor of \(a_i\).
• Operation 2: Replace \(a_i\) with \({a_i}^2\). However, at any moment the total number of times a player has used this operation cannot exceed his current total score.

After a player makes his move, if there exists any number on the board equal to \(1\), such numbers are removed from the board and the player who made the move gains \(1\) point for each removed number. Both players start with a score of \(0\). The game ends when there are no numbers left on the board. Under optimal play from both sides, determine which player wins, or report a draw if their scores are equal. Holmes makes the first move.

Note: In the absence of any use of Operation 2 (which is unavailable until a player has scored), every number \(a_i\) will eventually be reduced to \(1\) by repeated application of Operation 1. For any integer \(x\), let \(f(x)\) be the number of Operation 1 moves required to reduce \(x\) to \(1\). It can be computed as follows:

[ \begin{aligned} f(x) &= 0 \quad \text{if } x=1, \ f(x) &= 1 + f\Bigl(\frac{x}{\text{LPF}(x)}\Bigr) \quad \text{if } x>1, \end{aligned} ]

where \(\text{LPF}(x)\) denotes the largest prime factor of \(x\).

It turns out that if Operation 2 is never used (and indeed, it won’t be available at the start because both players initially have a score of 0), the fate of each number depends solely on the parity of \(f(a_i)\); specifically, if \(f(a_i)\) is odd then the player who first operates on that number can eventually secure the point, while if \(f(a_i)\) is even, the point will eventually go to his opponent. Under optimal play, each number is an independent "subgame". Let the value of a number be \(+1\) if \(f(a_i)\) is odd and \(-1\) if it is even. The final outcome is determined by the sum of these values:

[ \text{diff} = \sum_{i=1}^{n} \begin{cases} +1, & f(a_i) \text{ is odd},\ -1, & f(a_i) \text{ is even}. \end{cases} ]

If \(\text{diff} > 0\), Holmes (the first player) wins; if \(\text{diff} < 0\), Peanut (the second player) wins; and if \(\text{diff} = 0\), the game results in a draw.

inputFormat

The first line contains a single integer \(n\) (the number of integers on the board).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single line containing one of the following: "Holmes" if the first player wins, "Peanut" if the second player wins, or "Draw" if the game ends in a tie.

sample

1
2

Holmes