21445번 - Пробежки по Манхэттену 스페셜 저지다국어

Дороги Нью-Манхэттена устроены следующим образом. С юга на север через каждые сто метров проходит авеню, с запада на восток через каждые сто метров проходит улица. Авеню и улицы нумеруются целыми числами. Меньшие номера соответствуют западным авеню и южным улицам. Таким образом, можно построить прямоугольную систему координат так, чтобы точка $(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\cdot 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\cdot i$ минут от начала пробежки.

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

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