В тридесятом государстве ради сбора мытных денег (таможенных пошлин) с торговых людей царь Салтан указал сделать зáсеки – заградительный полосы, которые тянутся с севера на юг или с запада на восток и преграждают путь всякому пешему и конному.
Тридесятое государство имеет форму прямоугольника, стороны которого тянутся с запада на восток и с севера на юг. Картограф изобразил карту государства в виде прямоугольника на системе координат с центром O, совпадающим с юго-западным углом страны и осями, параллельными осям координат. Засеки на карте изображены в виде отрезков различной длины, параллельных осям координат. При этом оказалось, что никакие два отрезка не пересекаются и не лежат на одной прямой.
Для удобства управления своей страной царь Салтан повелел разделить ее на непересекающиеся прямоугольные области с соблюдением следующих условий:
1) каждая засека входит полностью в границы областей
2) число областей должно быть наименьшим, дабы уменьшить расходы на приказный люд.
Напишите программу, помогающую картографическому приказу построить искомое разбиение.
Входные данные
В первой строке находятся координаты северо-восточного угла страны, Во второй строке указано количество засек N (N≤1000). Каждая из следующих N строк содержит описание одной из засек в виде четверки числе x1, y1, x2, y2, что соответствует отрезку с концевыми точками (x1, y1) и (x2, y2). Все координаты являются неотрицательными целыми и не превосходят 10000.
Выходные данные
В первую строку выведите количество областей M в найденном разбиении. В последующих M строках должны находиться целочисленные координаты юго-западного и северо-восточного углов для каждой из областей разбиения. Числа внутри строки разделять пробелами.