You, as the newly recruited mad scientist at Aperture Laboratories, has been challenged by GLaDOS to a game that will test a new type of Portal! The invention is a series of portals, to each of which is assigned a priority.

One can only move from a portal with higher priority to another with lower priority. The game consists of moving the test subjects through the rooms of Aperture Science Enrichment Center. You and GLaDOS alternate turns: at each turn a player must move one of the subjects to a new room using the new portal prototype. Since her disastrous experiment with Chell, GLaDOS has decided not to hand over handheld portal devices to guinea pigs, so the portals have already been placed in the rooms, and their priority is the same priority associated to their room. This way, one can only move from a room to another if there are portals connecting them and the priority of the destiny room is lower than the current room's. The loser will be the player who has no valid move and thus, is doomed to receive no cake and possibly die in a fire.

Input

The input consists of several test cases.

The first line of each test case will begin with two integers N, M denoting the number of rooms and the number of portal connections, 0 < N ≤ 1000 and 0 ≤ M ≤ N (N − 1)/2. Rooms are numbered from 0 to N − 1, and their priority is the same as their number.

Then follows M lines describing the connections between two rooms. Each line contains two integers corresponding to rooms connected by portals.

The next line contains an integer K , 1 ≤ K < N , denoting the number of test subjects. Two or more subjects may occupy the same room.

Next K lines contain the room numbers where the subjects have been allocated.

Output

For each test case, assuming both you and GLaDOS play perfectly and you are the first player to make a move, print "I win" if you are victorious and "I lose" otherwise.

Example

Input:
9 14
0 1
0 2
0 3
1 2
2 3
1 4
2 5
5 3
4 5
4 3
5 6
6 7
7 8
8 6
3
3
5
8

Output:
I lose