The game of Nim (3) P63146


Statement
 

pdf   zip

thehtml

This is another problem about the game of Nim, which is thoroughly explained in problem ‍. But here, we may have a huge number of sets, each with a huge number of marbles. Furthermore, now we assume that the player to make the last move loses, instead of winning.

Input

Input consists of several cases. Every case begins with the number of sets n, followed by the number of marbles of each set, all between 0 and 109. Assume 0 ≤ n ≤ 105. At least one set has one or more marbles.

Output

For every case, tell if it is a winning or a losing configuration.

Hint

You should use a mathematical trick to solve this problem.

Public test cases
  • Input

    6  1 1 0 0 5 0
    1  2
    4  0 3 3 0
    5  1000 43210 17 123456 42
    5  1000 43210 17 43801 42
    4  1 1 1 1
    

    Output

    winning
    winning
    losing
    winning
    losing
    winning
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++