BRICKGM

Let's consider the tetris like game. The rules are very easy, there is board of width 10 and height 20. Colour bricks fall down the board. Every brick contains 3 colours. Player can rotate colours in the brick and determine the column, in which to place current brick. The goal is to construct horizontal, vertical or diagonal lines of length 3 or more in the same colour. After every brick falls down, the cleaning up algorithm is executed.

Single step of cleaning up algorithm searchs for lines constructed from cells with the same colour (there can be more than one such line). If no line is found, the algorithm finishes. Otherwise all cells in all found lines disappear, then the cells above this dissapeared cells fall down. The cleaning up algorithm executes single steps as long, as there are any changes on the board.

The brick can be rotated. When the brick contains colours A, B, C (from top to bottom), then single rotation makes the brick with colours C, A, B, and double rotation makes the brick with colours B, C, A.

Task

Your task is to write the program, which can play in Colour Brick Game. You will receive the consecutive bricks and for each of them have to determine the correct column and rotation. For each cleaned line You got points (according to scoring section). The goal is to maximize the score.

Input

The first line of input contains single-space separated integers n and k (3 ≤ k ≤ 9, 1 ≤ n*k ≤ 10⁶), where n is the number of bricks in the game and k is the number of different colours, that can appear in the game. The next n lines contain bricks description, one line per brick. Each brick is represented as string of length 3, containing digits (every digit is from 1 to k).

Output

For every brick from the input, You should write a line with two single-space separated integers x and r (1 ≤ x ≤ 10, 0 ≤ r ≤ 2), where x is the number of column to place the brick and r is the rotation of the brick (0 for no rotation, 1 for single rotation, 2 for double rotation).

If after falling down the brick is located outside the board (the higher brick cell is higher than the highest board row), the game finishes immediately. The judge doesn't read the remaining moves, so You don't need to output them. You can also stop, when there is no valid move at the board and You don't need to output this last move.

Scoring

Base score for cleaned line of length m is m². The base score is multiplied by the number of lines cleaned in single cleaning up step and then multiplied by the cleaning up step number (see example for clarify).

The brick score is sum of scores received from cleaned lines after the brick falled down.

Total score is sum of brick scores.

Example

Explanation

In first example, for the first 10 bricks there is no line to clean. The last brick makes lines to clean in 4 cleaning up steps.

In 1st step there is only one line of length 3 to clean. The score is 3^2, multiplied by 1 (number of lines cleared in the step) and multiplied by 1 (number of step). 3²*1*1 = 9.

In 2nd step there are 3 lines (one of length 3, two of length 4). The score is 3²+4²+4², multiplied by 3 (number of lines cleared), multiplied by 2 (number of step). (3²+4²+4²)*3*2 = 41*6 = 246.

In 3rd step there are 2 lines (both of length 3). The score is (3²+3²)*2*3 = 18*6 = 108

In 4th step there are 2 lines of length 3. The score is (3²+3²)*2*4 = 18*8 = 144.

Total score is 9 + 246 + 108 + 144 = 507.

In second example player placed all bricks in 1st column. There is no cleaned line, so the 7th brick after falling down is located outside the board. The game finishes with score 0. Note, that there is only 7 lines in output.