Прямоугольник
Напишите программу, которая определит, как в последовательности прямоугольников образовать последний из остальных прямоугольников склеиванием их вдоль сторон без разрезаний и без перекрытий внутренними частями.
Входные данные
Содержит натуральное число n (n < 15), а далее - последовательность из (n + 1)-ой пары натуральных чисел, которые являются длинами и высотами соответствующих прямоугольников. Площади всех прямоугольников не превосходят 1234567890.
Выходные данные
Расположим (n + 1)-ый прямоугольник таким образом, чтобы начало координат было вершиной прямоугольника, одна сторона - высота принадлежала оси ординат, а все внутренние точки лежали в первой четверти декартовой плоскости. Каждая выводимая строка должна содержать n четверок неотрицательных целых чисел, которые взаимно однозначно описывают соответствующую склейку.
Первые два числа такой четверки - это координаты нижней левой вершины прямоугольника, третье число - его номер, последнее число 1 или 0 в соответствии с тем, повернут ли на 90° этот прямоугольник или нет.
Строки следует записать в лексикографическом порядке, а в каждой строке четверки чисел также следует расположить в лексикографическом порядке.
Если склейка невозможна, то вывести два слова: "No solution".