Национальный лес Квадрляндии был разделен на одинаковые квадратные участки размером \(1 \times 1\), выровненные по направлениям с севера на юг и с востока на запад. Каждый участок может быть однозначно задан целочисленными Декартовыми координатами \((x, y)\) своего юго-западного угла.
Три друга, Алиса, Боб и Чарли собираются купить три отдельных участка земли \(A, B, C\) в лесу. Изначально все участки в лесу (включая участки \(A, B, C\)) покрыты деревьями. Друзья хотят навещать друг друга, поэтому они хотят очистить некоторые участки от деревьев. После очистки, можно будет добраться до любого из участков \(A, B, C\) от любого другого, перемещаясь по соседним очищенным участкам. Два земельных участка являются соседними, если они имеют общую сторону.
Например, \(A=(0,0)\), \(B=(1,1)\), \(C=(2,2)\). Необходимо очистить как минимум \(5\) участков, чтобы соединить друзей. Эти участки выделены серым цветом. Конечно, друзья не хотят слишком напрягаться. Помогите им найти наименьшее количество участков, которые они должны очистить от деревьев.
Выходные данные
В первой строке выведите одно целое число \(k\) — наименьшее количество участков, которые необходимо очистить от деревьев. Следующие \(k\) строк должны содержать координаты всех участков, которые необходимо очистить. Все \(k\) участков должны быть различны. Участки можно вывести в любом порядке.
Если решений несколько, выведите любое из них.
Примечание
Первый пример показан на картинке в условии задачи.
Второй пример изображен на этой картинке:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 0
1 1
2 2
|
5
0 0
1 0
1 1
1 2
2 2
|
|
2
|
0 0
2 0
1 1
|
4
0 0
1 0
1 1
2 0
|