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) \times c_i$ or $r_i \times (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 \le n \le 10^5$ and $1 \le r_i, c_i \le 10^9$.

Output

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