Dinny and Walrus are working on an arts and crafts project! They have $$$n$$$ popsicle sticks, where the $$$i$$$-th stick has a non-negative integer $$$a_i$$$ written on it.
To decide who gets to keep their masterpiece, they play a game. Dinny goes first, and the two players alternate turns until all popsicle sticks have been removed.
On each turn, the current player performs the following actions in order:
Both players start with a score of $$$0$$$. After all popsicle sticks have been removed, the player with the higher score wins. If both players have the same score, the game ends in a tie.
Assuming both players play optimally, determine whether Dinny wins, Walrus wins, or the game ends in a tie.
$$$^\dagger$$$The $$$\mathrm{MEX}$$$ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of popsicle sticks.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers written on the popsicle sticks.
Output "Dinny", "Walrus", or "Tie", according to the winner. The capitalization of these names does not matter.
40 0 1 2
Dinny
31 2 3
Tie
In the first test case, one possible sequence of moves is:
Dinny finishes with $$$4$$$ points, while Walrus finishes with $$$1$$$ point. Therefore, Dinny wins.
In the second test case, since there is no stick labeled $$$0$$$, the MEX remains $$$0$$$ throughout the game. Neither player earns any points, so the game ends in a tie.
| Название |
|---|


