Cunning Friends

Time limit2sMemory limit64 MB

Summary

Three players take turns removing stones from piles; Ben and Chris cooperate to make Anthony lose, so decide whether Anthony can avoid defeat.

Level: Hard8 of 10
Topics: Game theory, Greedy, Math, Combinatorics
Solved: No attempts yet

Problem

Anthony plays a stone game with his friends Ben and Chris. There are $N$ piles of stones, and pile $i$ holds $A_i$ stones. On a turn the player to move picks one pile and takes any number of stones from it, at least one. The turn order is Anthony, then Ben, then Chris, and it repeats. The player who has no stone left to take on their turn loses.

Ben and Chris agreed in advance to make Anthony lose. Neither of them cares which of the two ends up losing, they only want Anthony to lose. Anthony does not want to lose. All three play optimally. Decide whether Anthony can avoid defeat.

Input

The first line contains the number of piles $N$ ( $1 \le N \le 10^5$ ).

The second line contains the integers $A_1, A_2, \dots, A_N$ separated by spaces ( $1 \le A_i \le 10^9$ ).

Output

Print Lose if Anthony loses, and Win if he can avoid defeat.

Examples2

Example 1
Input
```
3
2 2 1
```
Expected output
```
Win
```
Example 2
Input
```
2
4 7
```
Expected output
```
Lose
```