B2. Восстановление многоугольника (средняя)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теперь, когда Хайди убедилась, что её тестер уровня загрязнения зомби работает, пора наносить удар! В этот раз, убежище зомби представляет собой строго выпуклый многоугольник на решётке. Каждая вершина многоугольника находится в каком-то узле решётки. Для каждой клетки решётки Хайди знает уровень загрязнения зомби — количество углов клетки, которые находятся внутри или на границе решётки.

По данной информации Хайди хочет определить точную форму убежища, чтобы обрушить на зомби справедливое возмездие, помогите ей в этом!

Входные данные

Входные данные содержат несколько тестов.

В первой строке каждого теста записано целое число n — размер решётчатого поля (5 ≤ n ≤ 500). В каждой из последующих n строк записаны n символов, описывающих уровень загрязнения зомби в каждой из клеток поля. Каждый символ каждой строки является цифрой от 0 до 4.

Клетки даны в том же порядке, что и на картинке выше: строки нумеруются в порядке уменьшения y координаты, и в каждом ряду клетки даны в порядке увеличения x координаты. Это означает, что первый ряд соответствует клеткам с координатами (1, n), ..., (n, n), а последний ряд соответствует клеткам с координатами (1, 1), ..., (n, 1).

В последней строке файла записан ноль. Эта строка служит сигналом конца ввода и не должна обрабатываться как отдельный тест. Сумма значений n по всем тестам в файле не превзойдёт 5000.

Выходные данные

Для каждого теста выведите ответ в следующем виде:

в первой строке выведите целое число v — количество вершин в многоугольнике, являющемся секретным убежищем. В следующих v строках выведите по два целых числа, определяющих вершины многоугольника в порядке обхода по часовой стрелке, начиная с лексикографически минимальной вершины.

Примеры
Входные данные
8
00000000
00000110
00012210
01234200
02444200
01223200
00001100
00000000
5
00000
01210
02420
01210
00000
7
0000000
0122100
0134200
0013200
0002200
0001100
0000000
0
Выходные данные
4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2
3
2 5
4 5
4 2
Примечание

Гарантируется, что решение всегда существует и единственно. Гарантируется, что в корректном решении вершины многоугольника имеют координаты между 2 и n - 2. Вершины (x1, y1) лексикографически меньше вершины (x2, y2) если x1 < x2 или .