Віслюк та Кіт у чоботях#12973

Віслюк та Кіт у чоботях

2 секунди
512 мегабайтів
Складна

У Далекому-Далекому королівстві Шрек має купок з цукерками. Він дуже любить їсти цукерки. В -тій купці є a_i цукерок.

Проте Шрек не єдиний, хто любить цукерки. Коли він засинув, Віслюк і Кіт у чоботях вирішили з’їсти його цукерки. Вони хочуть не тільки з’їсти всі цукерки, але й пограти в гру.

Кіт у чоботях, будучи благородним котом, дозволяє Віслюку ходити першим. Гра проводиться за такими правилами:

Гравець, який не може зробити хід — програє. Необхідно визначити, хто виграє.

Вхідні дані

Перший рядок містить одне ціле число — кількість купок цукерок. Це число також описує кількість ходів Кота у чоботях.

Другий рядок містить цілих чисел a_i — кількість цукерок у -тій купці.

1 \le n \le 10^5,

0 \le a_i \le 10^9.

Вихідні дані

Виведіть Donkey або Puss in Boots в залежності від того хто виграє.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі, є два варіанти:

  • Віслюк бере одну цукерку з купки. Тоді Кіт у чоботях бере другу цукерку з тієї ж купки та бере дві цукерки з іншої купки.

  • Віслюк бере дві цукерки з купки. Тоді Кіт у чоботях бере одну цукерку з іншої купки двічі.

У другому прикладі Осел бере 47 цукерок з другої купки і виграє.