eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Триміно

Триміно

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
prb2150

Прямоугольную решетку размером m × n необходимо выложить фигурками тримино как показано на рисунке. Фигурки можно вращать на углы, кратные 90º, но не разрешается их накладывать друг на друга. Не все прямоугольники m × n можно выложить полностью, однако при этом можно минимизировать количество невыложенных ячеек.

Напишите программу, которая найдет одну их возможных укладок прямоугольника m × n фигурками тримино, при этом минимизировав количество невыложенных ячеек.

Вхідні дані

Два целых числа — количество строк m и колонок n (1m100, 1n100) прямоугольника.

Вихідні дані

Вывести m строк, каждая из которых содержит n чисел. Каждое число указывает на номер фигуры тримино, покрывающей текущую ячейку. Если ячейка не покрыта ни одним тримино, то на ее месте следует вывести 0. Фигуры обозначаются разными числами 1, 2, 3, ..., k (через k обозначено количество использованных фигур).

В этой задаче может быть несколько правильных ответов. Вам следует вывести один из них.

prb2150-1

Приклад

Вхідні дані #1
4 11
Вихідні дані #1
1 1 1 2 2 2 3 3 3 4 4
8 7 7 7 6 6 6 5 5 5 4
8 8 9 9 9 10 10 10 11 11 11
0 0 14 14 14 13 13 13 12 12 12
Джерело International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011