Maximize the Minimum Distance | Archive

  1. Archive
  2. 2197

Maximize the Minimum Distance

Limits: 2 sec., 512 MiB

This problem is different from the problem "Minimize the Maximum Distance".

There are \(n \cdot m\) points on a two-dimensional plane located in \(n\) rows and \(m\) columns.

Distances between adjacent rows and columns are all equal to \(1\).

You want to paint all the points in some colors. We denote all colors you can use with integers \(1, 2, \dots, 10^5\). The number of points for each color you use must be two or three.

Your goal is to maximize the minimum Euclidean distance between points of the same color. You need not only to find the value of the sought distance but also to find the actual colors of the points.

Input

The single line contains two integers \(n\) and \(m\) – the number of rows and columns, respectively.

Output

In the first line, print an integer number – the square of the maximum possible minimum distance between points of the same color.

In the following \(n\) lines, print \(m\) integers \(c_{i j}\) that denote the colors of the points. These numbers must satisfy \(1 \le c_{i j} \le 10^5\). Each of these numbers must occur exactly two or three times.

If there are multiple answers, any of them will be accepted.

Constraints

\(1 \le n, m\),

\(2 \le n \cdot m \le 10^5\).

Samples

Input (stdin) Output (stdout)
2 3 2 4 7 4 7 4 7
Input (stdin) Output (stdout)
4 3 5 1 2 3 3 4 5 6 1 2 4 5 6
Input (stdin) Output (stdout)
1 5 4 4 7 4 7 4

Notes

In the first example, the sought distance is \(\sqrt{2}\).
In the second example, the sought distance is \(\sqrt{5}\).
In the third example, the sought distance is \(2\).

Source: Ukrainian National Programming Contest 2024 - Stage 2

Submit a solution

Element TypeCreatedWhoProblemCompilerResultTime (sec.)Memory (MiB)#Actions
Element TypeCreatedWhoProblemCompilerResultTime (sec.)Memory (MiB)#Actions