eolymp
bolt
Try our new interface for solving problems
Problems

Прямоугольник

Прямоугольник

Time limit 1 second
Memory limit 64 MiB

Напишите программу, которая определит, как в последовательности прямоугольников образовать последний из остальных прямоугольников склеиванием их вдоль сторон без разрезаний и без перекрытий внутренними частями.

Input data

Содержит натуральное число n (n < 15), а далее - последовательность из (n + 1)-ой пары натуральных чисел, которые являются длинами и высотами соответствующих прямоугольников. Площади всех прямоугольников не превосходят 1234567890.

Output data

Расположим (n + 1)-ый прямоугольник таким образом, чтобы начало координат было вершиной прямоугольника, одна сторона - высота принадлежала оси ординат, а все внутренние точки лежали в первой четверти декартовой плоскости. Каждая выводимая строка должна содержать n четверок неотрицательных целых чисел, которые взаимно однозначно описывают соответствующую склейку.

Первые два числа такой четверки - это координаты нижней левой вершины прямоугольника, третье число - его номер, последнее число 1 или 0 в соответствии с тем, повернут ли на 90° этот прямоугольник или нет.

Строки следует записать в лексикографическом порядке, а в каждой строке четверки чисел также следует расположить в лексикографическом порядке.

Если склейка невозможна, то вывести два слова: "No solution".

Examples

Input example #1
2 3 2 5 3 7 3
Output example #1
0 0 1 1 2 0 2 0
0 0 2 0 5 0 1 1