Задача P. Спичечные блоки ≡

Условие

Пусть имеется n спичек равной длины. Из указанных спичек необходимо собрать набор прямоугольных блоков, каждый из которых представляет собой двумерную матрицу квадратных ячеек (см. рисунок). При этом каждое ребро в таком блоке соответствует ровно одной спичке. Таким образом, полученный блок однозначно определяется своей конфигурацией [A × B], где A и B — размеры его сторон. Блоки, совпадающие с точностью до поворота, считаются одинаковыми, т.е. [A × B] = [B × A].

Требуется вывести все уникальные комбинации прямоугольных блоков, которые можно составить из заданного числа спичек. При этом каждая такая комбинация должна включать в себя все имеющиеся спички. Комбинации, различающиеся только лишь порядком следования составляющих их блоков, полагаются тождественными и не должны встречаться более одного раза.

Формат входного файла

Входной файл "input.txt" содержит исходное число спичек n.

Формат выходного файла

Выходной файл "output.txt" должен содержать все найденные комбинации, представленные в следующем формате: вначале указывается число блоков в текущей комбинации k; далее следует ровно k пар натуральных чисел, определяющих конфигурации имеющихся блоков.

В случае, если подходящие комбинации не были найдены,
выходной файл следует оставить пустым.

Ограничения

0 < n ≤ 128

Примеры тестов

23

5 1 1 1 1 1 1 1 1 1 2
3 1 1 1 2 2 2
2 1 1 1 6
2 1 2 1 5
2 1 3 1 4

3