Максимізуйте мінімальну відстань

Обмеження: 2 сек., 512 МіБ

Ця задача відрізняється від задачі «Мінімізуйте максимальну відстань».

На двовимірній площині розташовано \(n \cdot m\) точок, організованих у \(n\) рядків та \(m\) стовпців.

Відстані між сусідніми рядками та сусідніми стовпцями всі дорівнюють \(1\).

Вам потрібно розфарбувати всі точки у деякі кольори. Усі кольори, які можна використовувати, позначаються цілими числами \(1, 2, \dots, 10^5\). Кожен використаний колір має відповідати рівно двом або трьом точкам.

Ваша мета — максимізувати мінімальну евклідову відстань між точками одного кольору. Потрібно не лише знайти значення шуканої відстані, а й побудувати відповідне розфарбування точок.

Вхідні дані

У єдиному рядку задано два цілі числа \(n\) та \(m\) — кількість рядків і стовпців відповідно.

Вихідні дані

У першому рядку виведіть одне ціле число — квадрат максимально можливої мінімальної відстані між точками одного кольору.

У наступних \(n\) рядках виведіть по \(m\) цілих чисел \(c_{ij}\), що позначають кольори точок. Ці числа мають задовольняти умову \(1 \le c_{ij} \le 10^5\). Кожне з цих чисел повинно зустрічатися рівно два або три рази.

Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Обмеження

\(1 \le n, m\),

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 3	2 4 7 4 7 4 7

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3	5 1 2 3 3 4 5 6 1 2 4 5 6

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 5	4 4 7 4 7 4

Примітки