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

Автор:Жюри ВКОШП-2009   Ограничение времени:2 сек
Входной файл:mantan.in   Ограничение памяти:256 Мб
Выходной файл:mantan.out  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1≤ t≤ 100;

1≤ d≤ 100;

1≤ n≤ 100;

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

Входной файл (mantan.in) Выходной файл (mantan.out)
1
2 1 5
0 1
-2 1
-2 3
0 3
2 5
2
1 5
2 4

0.040s 0.010s 15