Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. More Reclamation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn a far away land, there are two cities near a river. One day, the cities decide that they have too little space and would like to reclaim some of the river area into land.

The river area can be represented by a grid with *r* rows and exactly two columns — each cell represents a rectangular area. The rows are numbered 1 through *r* from top to bottom, while the columns are numbered 1 and 2.

Initially, all of the cells are occupied by the river. The plan is to turn some of those cells into land one by one, with the cities alternately choosing a cell to reclaim, and continuing until no more cells can be reclaimed.

However, the river is also used as a major trade route. The cities need to make sure that ships will still be able to sail from one end of the river to the other. More formally, if a cell (*r*, *c*) has been reclaimed, it is not allowed to reclaim any of the cells (*r* - 1, 3 - *c*), (*r*, 3 - *c*), or (*r* + 1, 3 - *c*).

The cities are not on friendly terms, and each city wants to be the last city to reclaim a cell (they don't care about how many cells they reclaim, just who reclaims a cell last). The cities have already reclaimed *n* cells. Your job is to determine which city will be the last to reclaim a cell, assuming both choose cells optimally from current moment.

Input

The first line consists of two integers *r* and *n* (1 ≤ *r* ≤ 100, 0 ≤ *n* ≤ *r*). Then *n* lines follow, describing the cells that were already reclaimed. Each line consists of two integers: *r* _{ i} and *c* _{ i} (1 ≤ *r* _{ i} ≤ *r*, 1 ≤ *c* _{ i} ≤ 2), which represent the cell located at row *r* _{ i} and column *c* _{ i}. All of the lines describing the cells will be distinct, and the reclaimed cells will not violate the constraints above.

Output

Output "WIN" if the city whose turn it is to choose a cell can guarantee that they will be the last to choose a cell. Otherwise print "LOSE".

Examples

Input

3 1

1 1

Output

WIN

Input

12 2

4 1

8 1

Output

WIN

Input

1 1

1 2

Output

LOSE

Note

In the first example, there are 3 possible cells for the first city to reclaim: (2, 1), (3, 1), or (3, 2). The first two possibilities both lose, as they leave exactly one cell for the other city.

However, reclaiming the cell at (3, 2) leaves no more cells that can be reclaimed, and therefore the first city wins.

In the third example, there are no cells that can be reclaimed.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 06:40:06 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|