The game of Nim (2) P49499


Statement
 

pdf   zip

html

This is another problem about the game of Nim, which is thoroughly explained in problem P17438: “The game of Nim”. But here, we may have a huge number of sets, each with a huge number of marbles.

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.

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
    0
    4  0 3 3 0
    5  1000 43210 17 123456 42
    5  1000 43210 17 43801 42
    

    Output

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