Programmers and Stones

Time limit2sMemory limit2048 MB

Summary

Two players alternately pick any nonempty set of nonempty piles and remove one stone from each; determine the winner under optimal play.

Level: Medium5 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Programmers Alice and Dmitry invented a new game. In this game, there are $n$ piles of stones on the table. The players take turns starting from Alice. On their turn, a player picks an arbitrary non-empty set of non-empty piles, and then removes one stone from each of them. The player who cannot make a move loses. Who will win the game if both play optimally?

Input

The first line contains an integer $n$ ( $1 \le n \le 100\,000$ ).

The second line contains $n$ numbers $a_1, a_2, \ldots, a_n$ : the initial sizes of the piles of stones ( $1 \le a_i \le 10^9$ ).

Output

Print "Alice" or "Dmitry", depending on who wins the game. Letter case does matter.

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
Alice
```
Example 2
Input
```
2
2 2
```
Expected output
```
Dmitry
```