Задача №112768. Площадь Пажитнова
В прошлом году всемирно известной игре Тетрис исполнилось 30 лет. В Берляндии очень любят Тетрис, и поэтому решили назвать одну из городских площадей в столице в честь изобретателя игры, Алексея Леонидовича Пажитнова. Дизайн площади, разумеется, должен напоминать всем о Тетрисе. Поэтому она будет замощена плитками в виде фигурок игры.
Как известно, фигурки Тетриса состоят из четырех «клеток». Берляндский завод тротуарной плитки может выпускать плитку в виде любых фигурок Тетриса. Размер каждой «клетки» такой плитки составляет \(1 \times 1\) метр. Все возможные фигурки Тетриса представлены на рисунке ниже.
Например, площадь длиной 3 и шириной 4 метра можно покрыть тремя плитками, как показано на рисунке ниже.
В первой и единственной строке записаны два натуральных числа \(N\) и \(M\) (\(1 \le N, M \le 100\)), разделенные пробелом — длина и ширина площади соответственно.
В первой строке выведите число \(K\) — минимальное количество плиток, нужное для того, чтобы замостить площадь. Если площадь замостить невозможно, то выведите одно число -1.
Если замощение существует, то выведите его, начиная со второй строки. А именно, считайте, что плитки, используемые в замощении, занумерованы натуральными числами от 1 до \(K\). Выведите \(N\) строк по \(M\) чисел, разделенных пробелами, в каждой. Эти числа должны соответствовать номерам плиток, покрывающим соответствующие «клетки» площади.
Если существует несколько замощений с минимальным количеством плиток, то выведите любое из них.
Первый пример соответствует картинке из условия.
3 4
3 1 1 1 1 2 2 2 2 3 3 3 3
3 3
-1