Description
Write a program that uses four types of L-shaped trominoes to tile an L-shaped board completely. These L-shaped trominoes' size is 2 x 2 and labeled 1, 2, 3, 4, as shown in Figure 1.
The L-shaped board has even width and height.
The board’s full size is l × l, and the upper-right corner is removed with size m × m.
You must tile the entire L-shaped board by L-shaped trominoes without overlapping, and the trominoes must cover the board exactly. Please take a look at the example shown in Figure 2, where l = 8, m = 4.
Assume the origin (0, 0) is located at the lower-left corner.
Constraints: l and m are powers of 2, and 1 ≤ m < l ≤ 64.
Note that you have to consider the case that l is not equal to 2 x m.
Input
The input contains two numbers l and m.
Output
The output should list the types and positions of all L-shaped trominoes, respectively.
Since there are (l² − m²) / 3 trominoes, there should also be (l² − m²) / 3 lines in the output.
Each line represents one trominoe and contains three integers:
-
the tromino type (1–4),
-
the x-coordinate of the tromino’s center,
-
the y-coordinate of the tromino’s center.