More Reclamation

In 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.

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <memory.h>

using namespace std;

int g[111][111];

int grundy(int a11, int a12, int an1, int an2, int n) {
int mask = (a11 << 3) + (a12 << 2) + (an1 << 1) + (an2 << 0);
  if (g[mask][n] != -1) return g[mask][n];
  int a[111][5];
  for (int i=1;i<=n;i++) a[i][1] = a[i][2] = 0;
  a[1][1] = a11;
  a[1][2] = a12;
  a[n][1] = an1;
  a[n][2] = an2;
  bool was[260];
  for (int i=0;i<260;i++) was[i] = false;
  bool alive[111];
  for (int i=1;i<=n;i++)
    for (int j=1;j<=2;j++)
      if (a[i][j] == 0) {
        a[i][j]++;
        a[i-1][3-j]++;
        a[i][3-j]++;
        a[i+1][3-j]++;

        for (int q=1;q<=n;q++) alive[q] = (a[q][1]*a[q][2] == 0);
        int st = 1, res = 0;
        while (st <= n) {
          while (st <= n && !alive[st]) st++;
          if (st > n) break;
int fin = st;
while (fin + 1 <= n && alive[fin + 1]) fin++;
          res ^= grundy(a[st][1], a[st][2], a[fin][1], a[fin][2], fin - st + 1);
          st = fin + 1;
        }
        was[res] = true;

        a[i][j]--;
        a[i-1][3-j]--;
        a[i][3-j]--;
        a[i+1][3-j]--;
      }
  int &ans = g[mask][n];
  ans = 0;
  while (was[ans]) ans++;
  return ans;
}

int main() {
  int n, cnt, a[111][5];
  scanf("%d %d", &n, &cnt);
  for (int i=1;i<=n;i++) a[i][1] = a[i][2] = 0;
  for (int i=0;i<cnt;i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    a[x][y] = 1;
    a[x-1][3-y] = 1;
    a[x][3-y] = 1;
    a[x+1][3-y] = 1;
  }
  memset(g, 255, sizeof(g));
  bool alive[111];

  for (int q=1;q<=n;q++) alive[q] = (a[q][1]*a[q][2] == 0);
  int st = 1, res = 0;
  while (st <= n) {
    while (st <= n && !alive[st]) st++;
    if (st > n) break;
int fin = st;
while (fin + 1 <= n && alive[fin + 1]) fin++;
    res ^= grundy(a[st][1], a[st][2], a[fin][1], a[fin][2], fin - st + 1);
    st = fin + 1;
  }

  puts(res > 0 ? "WIN" : "LOSE");
return 0;
}