Donkey and Puss in Boots#12973

Donkey and Puss in Boots

2 seconds
512 megabytes
Hard

In the land of Far Far Away, Shrek has piles of candies. He likes eating candies so much. There are a_i candies in -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:

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

Input

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

Second line contains integers a_i — number of candies in -th pile.

1 \le n \le 10^5,

0 \le a_i \le 10^9.

Output

Print Donkey or Puss in Boots depending on the winner.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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.