Ни один день победы в Берляндии не обходился без парада военной техники. Этот год не является исключением. В связи с этим подготовка уже идёт полным ходом. Танки уже строятся в одну колонну, артиллерийские установки готовы стрелять, солдаты маршируют на главной площади... А у генерала военно-воздушных сил Генералова опять неприятности. За последний год в Берляндии полным ходом шло строительство небоскрёбов, поэтому самолётам теперь не так просто летать по городу. Было решено, что все самолёты будут лететь строго с юга на север, при этом на всём пути самолёта не должно встретиться ни одного небоскрёба, иначе праздник закончится трагически. В министерстве строительства были получены данные об n небоскрёбах (остальные здания достаточно маленькие и самолётам не помешают). Если смотреть на город с юга на север как на плоскость, то i-ое здание представляет собой прямоугольник высоты hi. Его самая западная точка имеет абсциссу li, а самая восточная точка — ri. Рельеф местности в городе плоский, поэтому основания всех зданий находятся на одном уровне. Ваша задача, как главного программиста министерства обороны, по данным о небоскрёбах найти огибающую ломаную, то есть такую что:
- Если смотреть на город с юга на север как на плоскость, то любая часть любого здания будет находиться внутри или на границе области, ограниченной ломаной вместе с поверхностью земли.
- Ломаная начинается и заканчивается на уровне поверхности земли, т.е. на высоте 0.
- Звенья ломаной параллельны осям координат, т.е. могут быть только вертикальными или горизонтальными.
- Вершины ломаной должны иметь целочисленные координаты.
- На виде города с юга на север ломаная (вместе с поверхностью земли) ограничивает минимально возможную площадь.
- Ломаная должна иметь наименьшую длину среди всех ломаных, ограничивающих вместе с поверхностью земли наименьшую площадь.
- Последовательные звенья ломаной должны быть перпендикулярны.
Рисунок ко второму примеру (в правой части отмечена искомая огибающая ломаная). Выходные данные
В первой строке выведите целое число m — количество вершин огибающей ломаной. Следующие m строк должны содержать по 2 целых числа — позицию и высоту вершины ломаной. Вершины ломаной выдавайте в порядке обхода ломаной с запада на восток. Помните, что первая и последняя вершины ломаной должны располагаться на высоте 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 0 2
4 1 3
|
6
0 0
0 3
1 3
1 4
3 4
3 0
|
|
2
|
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
|
14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0
|