Donkey and Puss in Boots

Обмеження: 2 сек., 512 МіБ

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.

Вхідні дані

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.

Вихідні дані

Print Donkey or Puss in Boots depending on the winner.

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 2 2	Puss in Boots

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0 47 0 0	Donkey

Примітки

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.