#P2252. Wythoff Nim

    ID: 15530 Type: Default 1000ms 256MiB

Wythoff Nim

Wythoff Nim

In this problem, there are two piles of stones with arbitrary, possibly different, counts. Two players take turns removing stones according to one of the following moves:

  • Remove any positive number of stones from one pile.
  • Remove the same positive number of stones from both piles simultaneously.

The player who removes the last stone wins. You are given the initial number of stones in the two piles and you move first. Assuming both players play optimally, determine whether you will win the game or not.

This game is a well-known impartial game called Wythoff Nim. It is known that the losing positions (i.e. positions from which the current player cannot force a win) are exactly those positions (a, b) (with a ≤ b) for which there exists a positive integer k such that:

[ a = \lfloor k \varphi \rfloor \qquad\text{and}\qquad b = a + k, ]

where \(\varphi = \frac{1+\sqrt{5}}{2}\) is the golden ratio. Equivalently, if we let \(a = \min(n,m)\) and \(b=\max(n,m)\) and define \(k = b - a\), the position is losing if and only if

[ a = \lfloor k \varphi \rfloor. ]

If the condition holds, then under optimal play you will lose; otherwise, you can force a win.

inputFormat

The input consists of a single line containing two integers a and b (0 ≤ a, b ≤ 109), representing the initial number of stones in the two piles.

outputFormat

Output a single word: Win if the first player (you) can force a win under optimal play; otherwise, output Lose.

sample

1 2
Lose