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