The Duke of Death suffers from the horrible condition of killing anything that he touches. Thus, to pass time, he likes to play games involving inanimate objects with his maid Alice. One such game involves piles of stones, with stones in the -th pile. The Duke and Alice take turns making moves, with the Duke going first:

On the Duke's turn, if there is at least one non-empty pile with an even number of stones, then he should choose one of those piles and remove any positive number of stones from that pile. Otherwise, he does nothing and passes the turn to Alice.

Similarly, on Alice's turn, if there is at least one non-empty pile with an odd number of stones, then she should choose one of those piles and remove any positive number of stones from that pile. Otherwise, she does nothing and passes the turn to the Duke.

The game ends when there are no stones left in any pile, and the player who took the last stone is declared the winner. If both players play optimally, who has a winning strategy? A player has a winning strategy if they can guarantee their win regardless of what their opponent chooses to do. In this game, we can prove that one of the players always has a winning strategy.

#### Constraints

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

#### Input Specification

The first line contains an integer , the number of piles.

The next line contains integers , the number of stones in each pile.

#### Output Specification

Output `Duke`

if the Duke has a winning strategy, or `Alice`

if Alice has a winning strategy.

#### Sample Input 1

```
4
2 1 2 2
```

#### Sample Output 1

`Duke`

#### Explanation for Sample 1

For example, one instance of a game could go as follows:

- The Duke takes stone from pile , changing the number of stones in each pile to .
- Alice takes stone from pile , changing the number of stones in each pile to .
- The Duke takes stones from pile , changing the number of stones in each pile to .
- Alice takes stone from pile , changing the number of stones in each pile to .
- The Duke takes stones from pile , changing the number of stones in each pile to .

In this case, the Duke took the last stone, so he is the winner. In general, we can prove that the Duke has a winning strategy here, so we output `Duke`

.

#### Sample Input 2

```
3
1 4 1
```

#### Sample Output 2

`Alice`

#### Explanation for Sample 2

As another example, the game could proceed as follows:

- The Duke takes stone from pile , changing the number of stones in each pile to .
- Alice takes stone from pile , changing the number of stones in each pile to .
- The Duke takes stones from pile , changing the number of stones in each pile to .
- Alice takes stone from pile , changing the number of stones in each pile to .
- The Duke passes the turn to Alice.
- Alice takes stone from pile , changing the number of stones in each pile to .

In this case, Alice took the last stone, so she is the winner. In general, we can prove that Alice has a winning strategy here, so we output `Alice`

.

## Comments

If you require assistance on this problem, it happens to have an editorial readily available if you are stuck.

It's also recommended to join the slack or discord for further assistance as wait times are often less and it does not clog the comments section.

you might have to use long for the second part

What do you mean? I’m trying to solve this so it could be helpful.

They are referring to using 64-bit integers instead of 32-bit integers to prevent integer overflow. This isn't a concern if you are using a language that handles this automatically like Python or JavaScript, but it does matter for (among many others) Java and C++.

What is wrong with my Batch #2 Case #2?