Зомби узнали о тестере уровня загрязнения зомби и умудрились его повредить! Теперь определение формы их логова стало по-настоящему сложной задачей для Хайди. Как и прежде, убежище представляет собой строго выпуклый многоугольник на решётке. Каждая вершина многоугольника расположена в каком-то узле решётки. Однако, повреждённый тестер уровня загрязнения зомби может только определять, находится ли уровень загрязнения данной клетке в множестве {1, 2, 3}. Другими словами, Хайди знает все клетки поля, для которых уровень загрязнения зомби не равен 0 и не равен 4.
По данной информации Хайди всё ещё хочет определить точную форму убежища зомби, чтобы всё-таки обрушить на их головы справедливое возмездие. Помогите ей!
Входные данные содержат несколько тестов.
В первой строке каждого теста записаны два целых числа n и m, где n определяет размер решётки (5 ≤ n ≤ 100 000), а m означает количество клеток решётки, для которых уровень загрязнения зомби равняется 1, 2 или 3 (8 ≤ m ≤ 200 000).
Во второй строке записаны m пар целых чисел x1, y1, ..., xm, ym — координаты клеток, уровень загрязнения зомби которых не равен 0 или 4. Гарантируется, что 1 ≤ xi, yi ≤ n. Все пары xi, yi попарно различны.
Клетки нумеруются по координатам их правых верхних углов. Это означает, что самая нижняя левая клетка, которая касается начала координат, имеет координаты (1, 1), а самая верхняя левая клетка имеет координаты (1, n).
В последней строке входных данных записаны два нуля. Эта строка служит сигналом конца ввода и не должна обрабатываться как отдельный тест. Сумма значений m по всем входным данным не превосходит 200 000.
Для каждого теста выведите ответ в следующем виде:
в первой строке выведите целое число v — количество вершин в многоугольнике, являющемся секретным убежищем. В следующих v строках выведите по два целых числа, определяющих вершины многоугольника в порядке обхода по часовой стрелке, начиная с лексикографически минимальной вершины.
8 19
2 3 2 4 2 5 3 3 3 5 4 3 4 5 4 6 5 2 5 3 5 6 6 2 6 3 6 4 6 5 6 6 6 7 7 6 7 7
5 8
2 2 2 3 2 4 3 2 3 4 4 2 4 3 4 4
0 0
4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2
Гарантируется, что решение всегда существует и единственно. Гарантируется, что в корректном решении вершины многоугольника имеют координаты между 2 и n - 2. Вершины (x1, y1) лексикографически меньше вершины (x2, y2) если x1 < x2 или 
.
