Game of rectangles P66768

Consider a two-player game with n rectangles. Initially, each reactangle i has r_i rows and c_i 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 (r_i − 1) × c_i or r_i × (c_i − 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 r_i and c_i. Assume 1 ≤ n ≤ 10⁵ and 1 ≤ r_i, c_i ≤ 10⁹.

Output

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