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 remove one stone from each of them. The player who can't make a move loses. Who will win the game if both play optimally?
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$$$).
Print "Alice" or "Dmitry", depending on who wins the game. In the names, letter case does matter.
51 2 3 4 5
Alice
22 2
Dmitry