eolymp
bolt
Try our new interface for solving problems
Problems

Triomino

Triomino

Time limit 1 second
Memory limit 64 MiB
prb2150

Tile the rectangular grid m × n with triomino figures which are shown at the picture. The figures can be rotated through angles which are multiples of 90º, but it’s prohibited to overlay figures at the same place. Of course, not all m × n rectangles can be tiled completely, but it’s possible to minimize number of non-tiled cells.

Write a program that finds any allowed tiling of m × n rectangle with triomino figures, which have minimal possible number of non-tiled cells.

Input data

Two integers m and n (1m100, 1n100) — number of rows and columns in rectangle.

Output data

Print m rows with n numbers in each row. Each number indicates the number of the triomino figure that covers this cell. If current cell is not covered by any figure, 0 number should be printed. Figures should be denoted with different numbers 1, 2, 3, ..., k (where k is total number of used figures).

Usually, there are many different correct answers for the same input data. Your program should write any one of them.

prb2150-1

Examples

Input example #1
4 11
Output example #1
1 1 1 2 2 2 3 3 3 4 4
8 7 7 7 6 6 6 5 5 5 4
8 8 9 9 9 10 10 10 11 11 11
0 0 14 14 14 13 13 13 12 12 12
Source International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011