Problem Description

Little S has an $n\times m$ chessboard. Initially, each cell has a stone. Each time, Little S may remove one stone such that the number of removed stones around it (4-neighborhood) is at most $1$. Find the maximum number of stones Little S can remove, and construct one valid removing plan.

Input Format

One line with two positive integers $n, m$, representing the board size.

Output Format

The first line contains one positive integer, the maximum number of stones that can be removed, $ans$.

Then output $n$ lines, each with $m$ integers between $-1$ and $ans$. The number in each cell indicates at which step the stone in this cell is removed. If the stone in that cell is not removed, output $-1$.

2 2

3
1 2
3 -1

3 5

12
2 3 4 5 6
1 -1 12 -1 7
8 9 -1 11 10

Hint

Sample Explanation

For Sample $1$, when removing $(1,1)$, there are $0$ removed cells around it. When removing $(1,2)$ and $(2,1)$, there is $1$ removed cell around each of them. Therefore, the construction satisfies the requirement.

It is easy to prove that there is no better answer.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $\bm{1\leq n\leq3}$, $1\leq m\leq10^5$.

If you get the first part (the maximum number of stones that can be removed) correct but fail to construct correctly, you will get $70\%$ of the score. For each subtask, your score is the minimum score among all test points in that subtask. Note that you still need to output $n\times m$ numbers as the construction plan in the required format. We recommend outputting all $-1$.

It is guaranteed that checker.cpp runs in no more than $0.5$ seconds with an output that meets the format requirements.

Translated by ChatGPT 5