Stop Cheating!

Interview

Time limit2sMemory limit1024 MB

Summary

Assign one of the fewest paper kinds to each cell of an N by M grid so that no two cells touching by side or corner share a kind.

Level: Easy3 of 10
Topics: Implementation, Math
Solved: No attempts yet

Problem

Professor Kim Chaewan is preparing the final exam for the course "Programming and Volunteering". The exam room is a rectangle with $M$ columns and $N$ rows, and each cell has exactly one student seated. To prevent cheating, Professor Kim wants to prepare several kinds of exam papers so that every student receives a different paper from each adjacent student. Two students are adjacent if their cells share a side or a corner.

Professor Kim did not have time to prepare many kinds of exam papers, so he wants to minimize the number of kinds. Write a program that distributes the papers so the condition is met, using as few kinds of papers as possible.

Input

The first line contains integers $N$ and $M$ separated by a space. $(1 \leq N, M \leq 1\,000)$

Output

The first line prints $K$ , the number of kinds of exam papers used. From the second line, print $N$ lines, each with $M$ integers from $1$ to $K$ separated by spaces. Each integer is the number of the paper given to that cell. That is, the $x$ -th integer on line $y+1$ is the number of the paper given to the cell in row $y$ from the top and column $x$ from the left.

Hint

The input and output are large, so use the fast I/O described in the language guide on pages 2-4 of the problem booklet.

Examples2

Example 1
Input
```
3 4
```
Expected output
```
4
3 2 4 2
4 1 3 1
3 2 4 2
```
Example 2
Input
```
1 1
```
Expected output
```
1
1
```