Blur

There is a "cloth" of 10 × 10 squares as shown in Fig. 1, and the squares are indicated by a pair of X-coordinate and Y-coordinate values ​​as shown in (1 and 2). The coordinate value is an integer starting from 0. For example, the coordinates of ◎ in Figure 1 are (1, 2). Dye is made by adding dye to this "cloth" little by little. There are three sizes of dripping dye drops, "Large", "Medium", and "Small", and the surroundings are colored as shown in Fig. 1 centering on the squares where the dye drops have fallen. In Fig. 1, ☆ is the center and ○ is the color bleeding range.

"Cloth" is initially "straight", that is, every square has a value of 0 that indicates the color depth. The value increases by 1 for each drop of dye. If "Small" falls to (1, 2) and "Medium" falls to (3, 2), the value of each square will be as shown on the left in Fig. 2. Since the dye is wasteful, it is not supposed to be removed so that the bleeding area on the right side of Fig. 2 sticks out of the cloth. Also, multiple dyes may be applied to the same place.

After repeating this process several times, a wonderful pattern emerged on the cloth, but unfortunately I inadvertently forgot to record the progress of the work. I can't remember at all, but I barely remembered the number of drops of dye I dropped. You have to reproduce the wonderful dyeing. Create a program that reads the data of wonderful dyes and outputs where and what kind of dye was applied. The number of drops of dye dropped should be 12 or less.

input

The input format is as follows:

The first line gives the number of drops of dye n dropped. The next to 10 lines are given the color strength of each coordinate, separated by blanks.

output

The output consists of n lines. "Large" of the dye drop is represented by 3, "Medium" is represented by 2, and "Small" is represented by 1, and the X coordinate, Y coordinate, and drop size of each dropped dye are output on one line separated by a blank. please.

The dyes can be applied in any order.

Example

Input

2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output

3 2 1 8 4 2

inputFormat

outputFormat

outputs where and what kind of dye was applied. The number of drops of dye dropped should be 12 or less.

input

The input format is as follows:

The first line gives the number of drops of dye n dropped. The next to 10 lines are given the color strength of each coordinate, separated by blanks.

output

The output consists of n lines. "Large" of the dye drop is represented by 3, "Medium" is represented by 2, and "Small" is represented by 1, and the X coordinate, Y coordinate, and drop size of each dropped dye are output on one line separated by a blank. please.

The dyes can be applied in any order.

Example

Input

2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output

3 2 1 8 4 2

样例

2
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

3 2 1
8 4 2

</p>