A. Зарядка для кота
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хозяйка кота Бенедикта считает, что он мало двигается, и поэтому придумывает для кота разные подвижные игры. Одна из игр — погоня за светящейся точкой от лазерной указки.

Хозяйка включает лазерную указку и перемещает светящуюся точку по полу в течение $$$n$$$ единиц времени.

Будем считать, что на пол нанесена координатная сетка. За одну единицу времени светящаяся точка перемещается от одной точки с целыми координатами к другой точке с целыми координатами. Каждую единицу времени кот оценивает, будет ли он прыгать к светящейся точке или нет.

Кот выполняет оценку следующим образом. Пусть он находится в точке с координатами $$$(x_C, y_C)$$$, а светящаяся точка — в точке с координатами $$$(x_L, y_L)$$$.

  • Если $$$s \le (x_C - x_L)^2 + (y_C - y_L)^2 \le b$$$, то кот прыгнет в точку координатной сетки, где находится светящаяся точка.
  • Если $$$0 \le (x_C - x_L)^2 + (y_C - y_L)^2 \le p \lt s$$$, то кот поймает светящуюся точку лапой. Перемещаться при этом он не будет.
  • Во всех остальных случаях кот сочтёт расстояние либо слишком маленьким, либо слишком большим. В этом случае кот также не будет перемещаться (и будет выражать недовольство, постукивая хвостом).

По ходу игры кот подсчитывает, сколько он совершил прыжков и сколько раз поймал светящуюся точку лапой. Каждый раз, когда количество прыжков или количество пойманных светящихся точек меняется, кот вычисляет разность между этими величинами. Его интересует максимальное (по абсолютной величине) значение, которого достигала эта разность по ходу игры.

Изначально кот сидит в точке с координатами $$$(0, 0)$$$. Ваша задача — определить максимальную по абсолютной величине разность между количеством прыжков и количеством светящихся точек, пойманных лапой, которая наблюдалась по ходу игры. Также необходимо указать, в какой точке координатной сетки кот окажется по завершении игры.

Входные данные

В первой строке содержится целое число $$$s$$$ $$$(1 \le s \le 10^9)$$$ — нижняя граница оценки для прыжка кота.

Во второй строке содержится целое число $$$b$$$ $$$(s \le b \le 10^9)$$$ — верхняя граница оценки для прыжка кота.

В третьей строке содержится целое число $$$p$$$ $$$(0 \le p \lt s)$$$ — верхняя граница оценки для поимки светящейся точки лапой.

В четвёртой строке содержится целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество единиц времени, в течение которого хозяйка кота перемещала лазерную указку.

В каждой из следующих $$$n$$$ строк содержится по два целых числа $$$x_j$$$ и $$$y_j$$$ $$$(-10^4 \le x_j, \, y_j \le 10^4, \, j = 1, 2, \ldots, n)$$$.

Выходные данные

Выведите максимально возможную по абсолютной величине разность между количеством прыжков, которое совершит кот, и количеством светящихся точек, пойманных лапой, а также координаты точки, в которой кот окажется (сначала координату $$$x$$$, потом $$$y$$$).

Разделяйте выводимые числа пробелами или переводами строк.

Обратите внимание, что выводить следует именно разность, а не её абсолютное значение.

Система оценки

Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$p = 0, \, s = 1$$$нетполная
22 (до 10)$$$p = 0, \, s \ge 2$$$1полная
32 (до 20)$$$p = s-1 \ge 1$$$1полная
43 (до 60)любые возможные значения1, 2, 3полная

Примеры
Входные данные
1
50
0
9
2 3
1 7
2 8
-4 -3
-5 -1
0 -2
5 3
5 3
3 -5
Выходные данные
4
5
3
Входные данные
30
100
20
10
2 3
1 7
2 8
-4 -3
-5 -1
-4 -3
-7 3
-5 -1
-1 4
2 0
Выходные данные
-3
-1
4
Примечание

Поясним приведённые примеры.

Будем обозначать количество прыжков $$$jumps$$$ и количество пойманных светящихся точек $$$points$$$. В начале игры обе эти величины равны $$$0$$$.

В первом примере кот действует следующим образом.

  • Находясь в точке $$$(0, 0)$$$, он оценивает расстояние до точки $$$(2, 3)$$$: $$$1 \le (0-2)^2 + (0-3)^2 = 13 \le 50$$$ и принимает решение прыгнуть. Таким образом, $$$jumps = 1$$$, кот перемещается в $$$(2, 3)$$$. Поскольку $$$points = 0$$$, то разность $$$jumps - points = 1$$$, что совпадает с количеством прыжков.
  • Оценка для точки $$$(1, 7)$$$: $$$(2 - 1)^2 + (3 - 7)^2 = 17$$$, так что $$$jumps = 2$$$, кот перемещается в $$$(1, 7)$$$.
  • Оценка для точки $$$(2, 8)$$$: $$$(1 -2)^2 + (8 - 7)^2 = 2$$$, $$$jumps = 3$$$, кот перемещается в $$$(2, 8)$$$.
  • Оценка для точки $$$(-4, -3)$$$: $$$(2+4)^2 + (8+3)^2 = 157$$$, и это больше $$$b = 50$$$, так что кот прыгать не будет.
  • Оценка для точки $$$(-5, -1)$$$: $$$(2+5)^2 + (8+1)^2 = 130$$$, это также больше $$$50$$$, и кот остаётся на месте.
  • Оценка для точки $$$(0, -2)$$$: $$$(2 - 0)^2 + (8+2)^2 = 104$$$, кот опять остаётся на месте.
  • Оценка для точки $$$(5, 3)$$$: $$$(2 - 5)^2 + (8 - 3)^2 = 34$$$, $$$jumps = 4$$$, кот перемещается в точку $$$(5,3)$$$. Поскольку кот пока ещё ни разу не ловил светящуюся точку лапой, то и разность $$$jumps - points = 4$$$.
  • Оценка для точки $$$(5, 3)$$$: $$$(5 - 5)^2 + (3 - 3)^2 = 0$$$, кот остаётся в этой точке и ловит светящуюся точку лапой, по-прежнему $$$jumps = 4$$$, но впервые изменяется $$$points = 1$$$, так что $$$jumps - points = 3$$$.
  • Оценка для точки $$$(3, -5)$$$: $$$(5 - 3)^2 + (3 + 5)^2 = 68$$$, кот опять остаётся на месте.

Как можно видеть, максимально возможная разность между количеством прыжков и количеством пойманных точек будет равна $$$4$$$. В конце игры кот окажется в точке $$$(5, 3)$$$.

Во втором примере кот действует следующим образом.

  • Находясь в точке $$$(0, 0)$$$, он оценивает расстояние до точки $$$(2, 3)$$$: $$$(0-2)^2 + (0-3)^2 = 13$$$ и принимает решение поймать светящуюся точку лапой.. Таким образом, $$$points = 1$$$, кот остаётся в $$$(0, 0)$$$. Разность $$$jumps - points = -1$$$.
  • Оценка для точки $$$(1, 7)$$$: $$$(0 - 1)^2 + (0 - 7)^2 = 50$$$, кот будет прыгать. Так что $$$jumps = 1$$$, кот перемещается в $$$(1, 7)$$$, разность $$$jumps - points = 0$$$.
  • Оценка для точки $$$(2, 8)$$$: $$$(1 -2)^2 + (8 - 7)^2 = 2$$$, $$$points = 2$$$, кот остаётся в $$$(1, 7)$$$, разность $$$jumps - points = -1$$$.
  • Оценка для точки $$$(-4, -3)$$$: $$$(1+4)^2 + (7+3)^2 = 125$$$, и это больше $$$b = 100$$$, так что кот прыгать не будет, ловить точку лапой не будет тем более.
  • Оценка для точки $$$(-5, -1)$$$: $$$(1+5)^2 + (7+1)^2 = 100$$$, это как раз равно $$$100$$$, поэтому кот прыгнет в точку $$$(-5, -1)$$$, $$$jumps=2$$$, разность $$$jumps - points = 0$$$.
  • Оценка для точки $$$(-4, -3)$$$: $$$(-5 + 4)^2 + (-1+3)^2 = 5$$$, кот остаётся на месте и ловит лапой точку. Теперь $$$points = 3$$$, $$$jump - points = -1$$$.
  • Оценка для точки $$$(-7, 3)$$$: $$$(-5 +7)^2 + (-1 - 3)^2 = 20$$$, это верхняя граница для расстояния, на котором кот ещё ловит точку лапой. Поэтому $$$points = 4$$$, $$$jump - points = -2$$$, кот остаётся в точке $$$(-5,-1)$$$.
  • Оценка для точки $$$(-5, -1)$$$: $$$(-5 + 5)^2 + ( -1 + 1)^2 = 0$$$, кот останется в точке, в которой находился, и поймает точку лапой, $$$points = 5$$$, $$$jumps - points = -3$$$.
  • Оценка для точки $$$(-1, 4)$$$: $$$(-5 + 1)^2 + ( -1 - 4)^2 = 34$$$, кот прыгнет в эту точку, $$$jumps = 3$$$, $$$jumps - points = -2$$$.
  • Оценка для точки $$$(2, 0)$$$: $$$(-1 - 2)^2 + (4 - 0)^2 = 25$$$, кот не станет ни прыгать, ни дотягиваться лапой до точки.

Как можно видеть, в течение игры максимальная по абсолютной величине разность между количеством прыжков и количеством пойманных светящихся точек составляла $$$-3$$$ ($$$3$$$ по абсолютной величине).