/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
机の上に N 枚のクッキーがあります。クッキーの表面にはそれぞれ正の整数 A_1, A_2, \dots, A_N が書かれており、これらはすべて異なります。
このクッキーを使って 2 人でゲームを行います。このゲームでは、各プレイヤーは次の行動を交互に行います。
机にあるクッキーを 1 枚選んで食べる。
その際に、机に残ったクッキーに書かれた整数の \mathrm{XOR} が 0 になったならば、そのプレイヤーは勝利し、ゲームは終了する。
あなたは E869120 君に対戦を申し込みました。あなたは先手で、E869120 君は後手です。さて、両者が最適に行動したときに、あなたは E869120 君に勝ちますか？
\mathrm{XOR} とは
整数 A, B のビット単位 XOR、A\ \mathrm{XOR}\ B は、以下のように定義されます。
- A\ \mathrm{XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に、k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 XOR は (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。特に k = 0 の場合、\mathrm{XOR} は 0 となります。
制約
- 1 \leq N \leq 400000
- 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
- A_1, A_2, \dots, A_N はすべて異なる
- A_1, A_2, \dots, A_N の \mathrm{XOR} は 0 ではない
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
両者が最適に行動したときにあなたが勝つなら Win、負けるなら Lose と出力してください。
入力例 1
6 9 14 11 3 5 8
出力例 1
Lose
この例では、あなたがどんな方法を使っても、E869120 君が最適に行動し続ければ負けてしまいます。
例えば、最初に 11 が書かれたクッキーを食べるとしましょう。すると、次に E869120 君が 9 が書かれたクッキーを食べることで、残ったクッキーに書かれた数 14, 3, 5, 8 の \mathrm{XOR} が 0 になるので、E869120 君が勝ちます。
それ以外の行動をとっても、最終的には E869120 君が勝ちます。
入力例 2
1 131
出力例 2
Win
この例では、あなたは最初のターンで 131 が書かれたクッキーを食べることしかできません。すると、机の上からクッキーがなくなるので、残ったクッキーに書かれた数の \mathrm{XOR} は 0 になります。したがって、E869120 君が何もできないまま、あなたが勝ちます。
入力例 3
8 12 23 34 45 56 78 89 98
出力例 3
Win
Score : 600 points
Problem Statement
There are N cookies on a desk. Each cookie has a positive integer on its surface: A_1, A_2, \dots, A_N, which are all different.
Let us play a game with two players using these cookies. In this game, the players alternately do the following action.
Choose a cookie on the desk and eat it. Then, if the \mathrm{XOR} of the integers written on the remaining cookies on the desk becomes 0, the player wins, and the game ends.
You have asked the boy E869120 to play this game with you. You go first, and E869120 goes second. Are you going to win if both players play optimally?
What is \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k. Particularly, when k = 0, the \mathrm{XOR} is 0.
Constraints
- 1 \leq N \leq 400000
- 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
- A_1, A_2, \dots, A_N are all different.
- The \mathrm{XOR} of A_1, A_2, \dots, A_N is not 0.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
If you are going to win if both players play optimally, print Win; if you are going to lose, print Lose.
Sample Input 1
6 9 14 11 3 5 8
Sample Output 1
Lose
In this case, regardless of what choices you make, you will lose if E869120 keeps playing optimally.
For example, let us say you first eat the cookie with 11 written on it. Then, E869120 will eat the cookie with 9 so that the \mathrm{XOR} of the numbers written on the remaining cookies, 14, 3, 5, 8, is 0, making him win.
Even if you make other choices, E869120 will win eventually.
Sample Input 2
1 131
Sample Output 2
Win
In this case, your only choice in your first turn is to eat the cookie with 131. Then, there is no more cookie on the desk, making the \mathrm{XOR} of the numbers written on the remaining cookies 0. Therefore, before E869120 gets to do anything, you win.
Sample Input 3
8 12 23 34 45 56 78 89 98
Sample Output 3
Win