Задача G. Пробежки по Манхэттену ≡

Условие

Дороги Нью-Манхэттена устроены следующим образом. С юга на север через каждые сто метров проходит авеню, с запада на восток через каждые сто метров проходит улица. Авеню и улицы нумеруются целыми числами. Меньшие номера соответствуют западным авеню и южным улицам. Таким образом, можно построить прямоугольную систему координат так, чтобы точка (x, y) лежала на пересечении x-ой авеню и y-ой улицы. Легко заметить, что для того, чтобы в Нью-Манхэттене дойти от точки (x₁, y₁) до точки (x₂, y₂) нужно пройти |x₂ − x₁| + |y₂ − y₁| кварталов. Эта величина называется манхэттенским расстоянием между точками (x₁, y₁) и (x₂, y₂).

Миша живет в Нью-Манхэттене и каждое утро делает пробежку по городу. Он выбегает из своего дома, который находится в точке (0, 0) и бежит по случайному маршруту. Каждую минуту Миша либо остается на том же перекрестке, что и минуту назад, или перемещается на один квартал в любом направлении. Чтобы не заблудиться Миша берет с собой навигатор, который каждые t минут говорит Мише, в какой точке он находится. К сожалению, навигатор показывает не точное положение Миши, он может показать любую из точек, манхэттенское расстояние от которых до Миши не превышает d.

Через t⋅ n минут от начала пробежки, получив n-е сообщение от навигатора, Миша решил, что пора бежать домой. Для этого он хочет понять, в каких точках он может находиться. Помогите Мише сделать это.

Формат входного файла

Первая строка входного файла содержит числа t, d и n.

Далее n строк описывают данные, полученные от навигатора. Строка номер i содержит числа x_i и y_i — данные, полученные от навигатора через t ⋅ i минут от начала пробежки.

Формат выходного файла

В первой строке выходного файла выведите число m — число точек, в которых может находиться Миша. Далее выведите m пар чисел — координаты точек. Точки можно вывести в произвольном порядке.

Гарантируется, что навигатор исправен и что существует по крайней мере одна точка, в которой может находиться Миша.

Ограничения

1≤ t≤ 100;

1≤ d≤ 100;

1≤ n≤ 100;

Примеры тестов

2 1 5
0 1
-2 1
-2 3
0 3
2 5

2
1 5
2 4