53. Пробежки по Манхэттену

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

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

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

Первая строка входного файла содержит числа t, d и n ($1 \le t \le 100$, $1 \le d \le 100$, $1 \le n \le 100$).

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

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

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