GameGame
Contest: Codeforces Round 659 (Div. 1)
Difficulty rating: 1900
Tags: bitmasks, constructive algorithms, dp, games, greedy, math

Koa the Koala and her best friend want to play a game.

The game starts with an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers. Koa and her best friend move in turns and each have initially a score equal to $$$0$$$. Koa starts.

Let's describe a move in the game:

- During his move, a player chooses any element of the array and removes it from this array, xor-ing it with the current score of the player. More formally: if the current score of the player is $$$x$$$ and the chosen element is $$$y$$$, his new score will be $$$x \oplus y$$$. Here $$$\oplus$$$ denotes bitwise XOR operation. Note that after a move element $$$y$$$ is removed from $$$a$$$.
- The game ends when the array is empty.

At the end of the game the winner is the player with the maximum score. If both players have the same score then it's a draw.

If both players play optimally find out whether Koa will win, lose or draw the game.

Input format:
Each test contains multiple test cases. The first line contains $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print:

- WIN if Koa will win the game.
- LOSE if Koa will lose the game.
- DRAW if the game ends in a draw.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In testcase $$$1$$$ of the first sample we have:

$$$a = [1, 2, 2]$$$. Here Koa chooses $$$1$$$, other player has to choose $$$2$$$, Koa chooses another $$$2$$$. Score for Koa is $$$1 \oplus 2 = 3$$$ and score for other player is $$$2$$$ so Koa wins.

Example input:
3
3
1 2 2
3
2 2 3
5
0 0 0 2 2

Example output:
WIN
LOSE
DRAW

Example input:
4
5
4 1 5 1 3
4
1 0 1 6
1
0
2
5 4

Example output:
WIN
WIN
DRAW
WIN

Editorial:
Let $$$x$$$ be the number of ones and $$$y$$$ be the numbers of zeros in the most significant bit of the numbers:
• if $$$x$$$ is even, whatever decision players take, both will end with the same score in that bit, so go to the next bit (if it doesn't exist the game ends in a draw). Indeed, the parity of the result of both players will be the same, since $$$x$$$ is even.
• if $$$x$$$ is odd, one of the players ends with $$$0$$$ in this bit and the other with $$$1$$$, the player with $$$1$$$ in this bit wins the game because the well know inequality $$$2^k > \sum\limits_{i=0}^{k-1} 2^i$$$ for $$$k \ge 1$$$, so the game is equivalent to play on an array of $$$x$$$ ones and $$$y$$$ zeros. Lemma: The second player wins iff $$$x \bmod 4 = 3$$$ and $$$y \bmod 2 = 0$$$ otherwise the first player wins. Proof: We know that $$$x \bmod 2 = 1$$$ so $$$x \bmod 4$$$ can be $$$1$$$ or $$$3$$$   if $$$x \bmod 4 = 1$$$ the first player can choose one $$$1$$$ and the remaining number of $$$1$$$ is a multiple of $$$4$$$, if the first player always repeats the last move of the second player (if $$$y \bmod 2 = 1$$$ and the second player takes the last $$$0$$$ both players start taking all the remaining ones), then both ends with the same number of ones which divided by $$$2$$$ is even and therefore the first player wins.  if $$$x \bmod 4 = 3$$$   if $$$y \bmod 2 = 0$$$ the second player can repeat the last move of the first player always so the first ends with a even numbers of $$$1$$$ and therefore the second player wins.  if $$$y \bmod 2 = 1$$$ the first player takes one $$$0$$$ and the game now is exactly the previous case with the first player as the second player.
• if $$$x \bmod 4 = 1$$$ the first player can choose one $$$1$$$ and the remaining number of $$$1$$$ is a multiple of $$$4$$$, if the first player always repeats the last move of the second player (if $$$y \bmod 2 = 1$$$ and the second player takes the last $$$0$$$ both players start taking all the remaining ones), then both ends with the same number of ones which divided by $$$2$$$ is even and therefore the first player wins.
• if $$$x \bmod 4 = 3$$$   if $$$y \bmod 2 = 0$$$ the second player can repeat the last move of the first player always so the first ends with a even numbers of $$$1$$$ and therefore the second player wins.  if $$$y \bmod 2 = 1$$$ the first player takes one $$$0$$$ and the game now is exactly the previous case with the first player as the second player.
• if $$$y \bmod 2 = 0$$$ the second player can repeat the last move of the first player always so the first ends with a even numbers of $$$1$$$ and therefore the second player wins.
• if $$$y \bmod 2 = 1$$$ the first player takes one $$$0$$$ and the game now is exactly the previous case with the first player as the second player.
Time complexity: $$$O(n)$$$ per testcase