Donkey and Puss in Boots

Limits: 2 sec., 512 MiB

In the land of Far Far Away, Shrek has \(n\) piles of candies. He likes eating candies so much. There are \(a_i\) candies in \(i\)-th pile.

Shrek is not the only one who likes eating candies. When he falls asleep, Donkey and Puss in Boots decide to eat his candies. Not only do they want to eat all the candies but also to play the game.

Puss in Boots being an honorable cat, lets Donkey go first. The game will be held by the following rules:

• On Donkey’s turn, he must select one pile of candies and eat a positive number of candies from that pile.

• On Puss in Boots’ turn, he must make \(n\) moves similar to those of Donkey (being much trickier).

The player who cannot make a move loses. You need to identify the winner.

Input

First line contains one integer \(n\) — number of piles of candies. This integer describes the number of Puss in Boots’ moves as well.

Second line contains \(n\) integers \(a_i\) — number of candies in \(i\)-th pile.

Output

Print Donkey or Puss in Boots depending on the winner.

Constraints

\(1 \le n \le 10^5\),

\(0 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2 2 2	Puss in Boots

Input (stdin) сopy	Output (stdout) сopy
4 0 47 0 0	Donkey

Notes

In the first example, there are two options:

• The Donkey takes one candy from a pile. Then, the Puss in Boots takes the second candy from the same pile and takes two candies from another pile.

• The Donkey takes two candies from a pile. Then, the Puss in Boots takes one candy from another pile twice.

In the second example, Donkey takes 47 candies from a second pile and wins.