Задача №112138. Разрезания
Петя очень любит различные задачи на разрезания. Но почти все задачи из интернета он уже перерешал. Поэтому он самостоятельно придумал новую задачу.
У Пети имеется листок клетчатой бумаги n на m клеток. Он хочет посчитать количество различных способов разрезать этот лист по линиям сетки так, чтобы никакие два из получившихся кусочков не совпадали при наложении (при наложении можно поворачивать листочки). Два способа называются различными, если существует кусочек такой формы, что он получается в первом способе и не получается во втором. Резать можно только по линиям сетки и только прямым разрезом (то есть один разрез должен соединять две точки на противоположных сторонах прямоугольника). Отсутствие разрезаний также является одним из способов.
Петя уже решил эту задачу. А сможете ли Вы?
Даны два натуральных числа n и m . Произведение этих чисел не превышает 40.
Выведите k строк, где k — количество различных способов. В каждой строке выведите описание способов: описания n кусочков через пробел. Для каждого кусочка выведите два числа через пробел — длину и ширину, в любом порядке. Кусочки внутри способа выводите в любом порядке. Способы, также, выводите в любом порядке.
Пояснение к третьему способу разреза: мы сначала он листа 3х3 отрезаем кусок 2х3, потом режем другой кусок (1х3) на два куска 1х2 и 1х1.
3 3
3 3 1 3 2 3 1 1 1 2 2 3 1 2 1 3 2 2