#919 Grid Problem

Statement

Statement language

There is an $N \times M$ grid. Initially, every cell is intact.

Break exactly $X$ cells. Then write each integer $0,1,\cdots,NM-X-1$ exactly once in the remaining $NM-X$ cells.

Let integers $L,R$ satisfy $0 \le L<R<NM-X$ . Keep only the cells whose written values $i$ satisfy . The interval is called a if these cells form one connected component. Two cells are adjacent only when they share a side.

Your goal is to make every interval $(L,R)$ not good. Find the minimum possible number $X$ of broken cells and construct one grid attaining that minimum.

If at most one cell remains intact, there is no interval satisfying $L<R$ , so the condition is satisfied automatically.

Input

The input is given in the following format.

$N\ M$

Output

On the first line, print the minimum possible number $X$ of broken cells.

On the next $N$ lines, print $M$ integers $B_{i,1},B_{i,2},\cdots,B_{i,M}$ to describe the grid.

Constraints

$1 \le N,M \le 2000$ .

Samples

Sample 1

Input

1 1

Output

0
0

Sample 2

Input

1 2

Output

1
0 -1

Sample 3

Input

2 2

Output

2
1 -1
-1 0