Game of rectangles P66768


Statement
 

pdf   zip

html

Consider a two-player game with n rectangles. Initially, each reactangle i has ri rows and ci columns. Alternating moves, each player chooses any rectangle i (that has not been fully removed yet), and removes the top row or the left column from it, thus reducing the size to either (ri − 1) × ci or ri × (ci − 1), respectively. The player that eventually cannot make any move loses the game.

Please write a program that tells if, with perfect play, the first player can win a given game.

Input

Input consists of several cases. Every case begins with the number of rectangles n, followed by n pairs of integer numbers ri and ci. Assume 1 ≤ n ≤ 105 and 1 ≤ ri, ci ≤ 109.

Output

For every case, print “wins” or “loses”.

Public test cases
  • Input

    1  1 5
    1  2 2
    1  5 9
    1  5 4
    2  1 5  5 4
    2  1 6  5 4
    3  1000000000 1  999999999 2  999999996 999999998
    

    Output

    wins
    loses
    loses
    wins
    loses
    wins
    loses
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Final
    Date
    2012-09-15