Дивна плитка (складніша версія)

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

Різниця між задачами «Дивна плитка (простіша версія)» та «Дивна плитка (складніша версія)» лише в обмеженнях.

На рисунку зображено фігуру L-троміно в чотирьох різних положеннях. Назвемо ці фігури L-троміно зліва направо першого, другого, третього та четвертого типів.

На кожній фігурі центральну клітинку виділено зеленим кольором.

Марічці потрібно замостити прямокутну кімнату розміру \(n\) на \(m\) плиточками форми L-троміно і дівчина звернулася по допомогу до Зеника. Оскільки Зеник не вчився на будівельника, то він вважає, що достатньо розкласти плиточки так, аби кожна клітинка була покрита однаковою додатною кількістю плиточок.

Допоможіть Зенику — скажіть, чи можна так розкласти L-троміно, і якщо можна, то наведіть замощення.

Вхідні дані

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

Вихідні дані

Якщо кімнату замостити неможливо, у єдиному рядку виведіть No.

Інакше в першому рядку виведіть Yes.

Далі виведіть замощення кімнати плиточками.

Спочатку виведіть одну матрицю цілих чисел розміру \(n \times m\), що описує розміщення плиточок L-троміно першого типу. Число в кожній клітинці матриці означає кількість плиточок першого типу, для яких ця клітинка є центральною. Зауважте, що оскільки плиточки не можуть вилазити за межі кімнати, то перший рядок і перший стовпець матриці повинні бути нульовими.

Потім у такому ж форматі виведіть матриці, що описують замощення плиточками другого, третього та четвертого типів.

Матриці повинні бути розділені порожнім рядком.

Обмеження

\(7 \le n, m \le 100\).

Приклади

Вхідні дані (stdin) копіювати

Вихідні дані (stdout) копіювати

8 9

Yes 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Примітки

Зауважте, що плиточки не можуть виходити за межі кімнати.

Розташування плиточок в прикладі зображено нижче. У цьому прикладі кожна клітинка покрита одною плиточкою.