Rotating Square Tiles

Sixteen tiles numbered from 1 to 16 are placed once each on a 4×4 board. The goal is to transform the board into the ordered state below.

Figure 1

One move is one of the following operations.

• Rotate one row cyclically to the right by 1, 2, or 3 cells.
• Rotate one column cyclically downward by 1, 2, or 3 cells.

Figure 2 shows the result of moving the 2nd row of Figure 1 two cells to the right. Tiles 7 and 8 pass the right edge and reappear at the left end of the row.

Figure 2

Figure 3 shows the result of moving the 3rd column of Figure 2 one cell downward. Tile 15, which was at the bottom of that column, reappears at the top.

Figure 3

From the state in Figure 3, moving the 3rd column downward by 3 cells and then moving the 2nd row right by 2 cells produces the state in Figure 1. Thus 2 moves are enough.

Given an initial arrangement of the tiles, output a sequence of moves that transforms it into Figure 1. The number of moves must be minimum.

The board is given as 4 lines, each containing the tile numbers in one row. The tile numbers are integers from 1 to 16, and each number appears exactly once.

Each line contains the 4 tiles of that row from left to right, separated by spaces.

Print the minimum number of moves on the first line. Then print one move per line in the order they are performed.

If you move row i to the right by k cells, print 1 i k. If you move column i downward by k cells, print 2 i k. Here i is between 1 and 4, and k is between 1 and 3.

A cyclic shift of one row or one column counts as one move, regardless of how many cells it is shifted.

Every given input can be transformed into the state in Figure 1 using at least 1 move and at most 7 moves.