Description
Doraemon's favorite video game is Tetris (俄羅斯方塊).
In Tetris, players complete lines by moving differently shaped pieces (tetrominoes), which descend onto the playing field. The completed lines disappear and grant the player points, and the player can proceed to fill the vacated spaces. The game ends when the uncleared lines reach the top of the playing field. - Wikipedia
You may refer to the gif for more detail demonstrating this game.
In this problem, we want to simulate the gaming process of Tetris, and several rules differ from the original Tetris:
- The playing field width is 5, and we have only four types of tetromino shapes.
- When the tetrominoes form a horizontal line, the line won't be disappeared but remains in the same place.
- You can only rotate the tetrominoes before you drop them into the field; you must decide the directions of the tetrominoes first and choose the place you want to put them in. The tetromino would fall until it touches the ground or the other tetrominoes.
The following figure shows the four types of tetrominoes.
Given a sequence of the tetromino type, you must put it into the playing field by order.
If we put a tetromino into the field that the height of the stacked tetromino would exceed the top of the playing field, then the game would fail. In this problem, you only need to determine whether the game will end successfully; we can put all the tetrominoes into the field, and no tetromino exceeds the top of the playing field. (Notice: exactly reaching the top is acceptable in this problem)
If the game failed in the end, tell the game would end at x-th tetromino. Since we want to maximize the possible game time, please output the largest x.
Input
The first line contains a positive integer T ≦ 10, representing the number of test cases.
For each test case:
The first line contains two positive integers N, W ≦ 20, representing the tetrominoes' sequence length and the playing field's height.
The second line contains N integers, each a number from 1 to 4, representing the type of each tetromino.
Output
For each test case, output one line.
- If there exists a way that the game would end successfully, print "Win\n".
- Otherwise, the game would end at x-th tetromino, print "Lose at x\n".