Paving Blocks

Yeona and Yeonjae often play on a paved area shaped like the figures below. An M×N pavement has M rows and N columns and consists of 2MN tiles. Every tile is a rectangle of the same size whose short side and long side have length ratio 1:2, and each tile is either white or gray.

Figure 1(a). A 2×3 pavement

Figure 1(b). A 4×4 pavement

Rows are numbered from 1 to M from top to bottom, and columns are numbered from 1 to N from left to right. In row i and column j, two tiles of different colors form one square. Their arrangement is determined by the parity of i+j.

1. If i+j is even, the two tiles are stacked vertically, and the upper tile is white.
2. If i+j is odd, the two tiles are placed side by side, and the left tile is white.

The white tile in row i and column j is denoted by (i, j, 0), and the gray tile is denoted by (i, j, 1).

The game is played as follows. First choose the size of the pavement. Then choose any tile as the starting tile. Move through as many distinct tiles as possible while satisfying the conditions below, and finally return to the starting tile.

1. Any tile may be chosen as the starting tile.
2. Every tile except the starting tile may be stepped on at most once. The starting tile is stepped on once at the beginning and once at the end.
3. Each move must go to a tile that shares an edge with the current tile. Therefore, a tile can have at most 5 possible next tiles. In Figure 1(a), from the white tile in row 1, column 2, one can move to the gray tile on its right, the white tile below it, or the white or gray tile on its left.

On the 2×3 pavement in Figure 1(a), all 12 tiles can be visited in the following order.

(1,1,1) → (1,1,0) → (1,2,0) → (1,2,1) → (1,3,0) → (1,3,1) → (2,3,1) → (2,3,0) → (2,2,0) → (2,2,1) → (2,1,1) → (2,1,0) → (1,1,1)

Given M and N, write a program that outputs the maximum number of tiles that can be visited and one tile-visiting order that achieves that maximum.

The first line contains two integers M and N, the number of rows and columns of the pavement. (2 ≤ M, N ≤ 100)

Print the maximum number K of tiles that can be visited on the first line. Then print K lines, one tile per line, in the order visited starting from the starting tile. Do not print the starting tile again at the end. Each tile is printed as three integers i, j, c separated by spaces. Here i is the row number, j is the column number, and c is the color, either 0 or 1.