Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Геолокация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы работаете на компанию Гриззл в Пауни, штат Индиана.

Недавно возле Пауни открылся новый национальный парк и перед вами была поставлена задача разработать систему геопозиционирования, чтобы люди в нём не заблудились. Концепция, которую вы разработали, инновационна и минималистична. В парке будет установлено $$$n$$$ антенн. Когда кто-то захочет узнать своё местонахождение, их гриззлфон свяжется с антеннами и узнает расстояния от текущей позиции пользователя до всех антенн.

Зная эти расстояния и местонахождение антенн, восстановить местонахождение пользователя должно быть просто... Ведь так? Ну, почти. Единственная проблема заключается в том, что вы не знаете, какой антенне соответствует каждое из расстояний. Ваша задача – определить местонахождение пользователя, зная только местонахождение всех антенн и мультимножество расстояний до них.

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

Первая строка ввода содержит единственное целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$), количество антенн.

Следующие $$$n$$$ строк содержат координаты антенн, $$$i$$$-я строка содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \leq x_i,y_i \leq 10^8$$$). Гарантируется, что все местонахождения антенны различны.

Следующая строка содержит единственное целое число $$$m$$$ ($$$1 \leq n \cdot m \leq 10^5$$$), количество запросов на определение местонахождения пользователя.

Следующие $$$m$$$ строк содержат $$$n$$$ целых чисел $$$0 \leq d_1 \leq d_2 \leq \dots \leq d_n \leq 2 \cdot 10^{16}$$$ каждая. Эти числа образуют мультимножество квадратов расстояний от местонахождения пользователя $$$(x;y)$$$ до всех антенн.

Для всех тестов, кроме примеров, гарантируется, что во всех запросах местонахождения пользователя $$$(x;y)$$$ были выбраны равномерно и независимо друг от друга среди всех возможных целочисленных точек, таких что $$$0 \leq x, y \leq 10^8$$$.

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

Для каждого запроса выведите сначала число $$$k$$$ – количество возможных местонахождений пользователя, а затем список из этих точек в лексикографическом порядке.

Гарантируется, что сумма $$$k$$$ по всем запросам не превосходит $$$10^6$$$.

Примеры
Входные данные
3
0 0
0 1
1 0
1
1 1 2
Выходные данные
1 1 1
Входные данные
4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8
Выходные данные
4 0 0 0 1 1 0 1 1 
4 -1 -1 -1 2 2 -1 2 2
Примечание

Как можно видеть во втором примере — хотя местонахождение пользователя и выбирается так, чтобы иметь неотрицательные координаты, вам необходимо вывести все возможные целочисленные координаты.