409531: GYM103625 E Dead Man's Chest

Jack Sparrow thinks that he has found the legendary Dead Man's Chest and hopes to use it to find the long-lost treasure of its owner, Davy Jones. Before he can open the chest however the ghost of Davy Jones comes and challenges Sparrow to an eccentric game to determine if he is worthy of the treasure he seeks.

Sparrow unfurls a scroll containing $$$n$$$ distinct positive integers. The game goes as follows: on each pirate's turn, they must choose a distinct $$$x$$$ and $$$y$$$ from the integers currently on the scroll such that $$$|x - y|$$$ is not on the scroll. The pirate then writes the integer $$$|x - y|$$$ on the scroll and the game continues until one of them no longer has a number they can write at which point that pirate loses and must walk the plank to eternal shame.

Davy Jones, being supremely confident, tells Sparrow that he can move first. Given the $$$n$$$ starting integers and the fact that both players play optimally, determine who will be the winner.

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^{4})$$$ representing the number of positive integers originally on the scroll.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ where for each $$$i$$$ we have $$$1 \leq a_i \leq 10^{9}$$$, representing the $$$n$$$ positive integers originally on the scroll. It is guaranteed that all $$$n$$$ numbers will be unique.

Output Jack Sparrow if Sparrow is able to win the game and thus get his treasure and Davy Jones otherwise.

2
3 9

Jack Sparrow

3
5 6 7

Davy Jones

In the first sample, Jack Sparrow is forced to choose the only two numbers there and writes the absolute value of its difference $$$6$$$ on the scroll. The scroll now has $$$\{3, 6, 9\}$$$ on it and there is no pair of elements such that the absolute difference is not already on the scroll which means that Davy Jones cannot move so Jack Sparrow wins.