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

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

2 seconds
512 megabytes
Very hard

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

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

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

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

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

Input

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

1 \le n, m,

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

Output

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

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

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі шукана відстань дорівнює \sqrt{2}.

У другому прикладі шукана відстань дорівнює \sqrt{5}.

У третьому прикладі шукана відстань дорівнює .