Mirror IIOT 2022-2023, International Round | tetris

Tommaso is one of the best Tetris players in the world. Today he became bored of playing the game and decided to create a different version. He wants to fill a $N \times M$ grid with the standard Tetris pieces.

The pieces can be rotated, but they cannot overlap or go outside the grid. Help Tommaso by writing a program that, given the size of the grid, finds a way to completely fill it with tetris pieces.

Input data

The first line contains the integers $N$ and $M$.

Output data

If it is not possible to fill the grid, you need to write a single line with the number $-1$. Otherwise on the first line you need to write the number $K$ of pieces used to fill the grid.

Then, you need to write $N$ lines with $M$ numbers each, where the $j$-th number of the $i$-th line is the number of the piece used to fill the cell $(i,j)$. The different pieces must be numbered from $0$ to $K-1$.

Constraints and Clarifications

• $1 \le N \le 500$.
• $1 \le M \le 500$.
• If there are multiple solutions, you can print any of them.
• Tommaso has an infinite amount of pieces of each type.

Example 1

stdin

2 3

stdout

-1

Explanation

In the first sample case there is no way to completely fill a $2 \times 3$ grid.

Example 2

stdin

4 3

stdout

3
0 0 0
1 2 0 
1 2 2 
1 1 2 

Explanation

In the second sample case a possible way to fill the grid is shown in the image below: