Problem G. Game of 10

Author:ACM ICPC NEERC 2010 Jury   Time limit:3 sec
Input file:standard input   Memory limit:256 Mb
Output file:standard output  

Statement

The Game of 10 is played by two players on a 4 × 4 field. Initially all 16 cells of the field are empty. Players make alternating moves. On each move a player writes a number from 1 to 4 into an empty cell. The first player that makes any row or column filled with four numbers with a sum of 10 wins. If all cells are filled but no row or column has a sum of 10, then a draw is declared.

You have to write a program that plays for the second player and always wins.

The table below shows the field after the sample game that is shown in the «Sample input and output» section. Subscripts denote the number of the move in the game starting from the first one, with 14-th being the last and winning move by the second player. The last move in the game had filled the second column with a sum of 10.

\Interaction

The interaction starts with your program reading the first player's move from the standard input. Then your program must write its move to the standard output, wait for the first player's move in the standard input and so on.

Your program must exit after writing the last, winning move to the standard output. Your program must write end-of-line sequence and flush the standard output after each move, including the last, winning move.

Input file format

The standard input consists of the first player's moves. Each move is represented by a single line that contains three integer numbers r, c, and k (1 ≤ r, c, k ≤ 4) separated by spaces, where r and c are row and column numbers, and k is the number that the first player writes into the cell (r, c).

Output file format

The standard output consists of the second player's moves. Each move is represented by a single line of the same format as in the standard input. The last, winning move, shall have an extra word "WIN" (without quotes) on the same line after the three numbers that denote the move, separated from them by a space.

Sample tests

No. Input file (standard input) Output file (standard output)
1
2 2 2
1 1 1
2 4 2
2 1 1
3 4 4
3 1 3
1 2 4
3 3 3
4 4 4
4 2 3
1 3 2
1 4 2
4 1 3
3 2 1 WIN

2.667s 2.500s 15