Programmers and Stones

시간 제한2초메모리 제한2048 MB

요약

n개의 돌무더기가 주어지고, 매 턴 비어 있지 않은 무더기 중 임의의 부분집합에서 돌을 하나씩 제거하며, 최적으로 둘 때 승자를 판정한다.

난이도: 어려움10점 중 8점
유형: 게임 이론, 수학, 비트 연산
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
5
1 2 3 4 5
```
예상 출력
```
Alice
```
예제 2
입력
```
2
2 2
```
예상 출력
```
Dmitry
```