Вы работаете на компанию Гриззл в Пауни, штат Индиана.
Недавно возле Пауни открылся новый национальный парк и перед вами была поставлена задача разработать систему геопозиционирования, чтобы люди в нём не заблудились. Концепция, которую вы разработали, инновационна и минималистична. В парке будет установлено \(n\) антенн. Когда кто-то захочет узнать своё местонахождение, их гриззлфон свяжется с антеннами и узнает расстояния от текущей позиции пользователя до всех антенн.
Зная эти расстояния и местонахождение антенн, восстановить местонахождение пользователя должно быть просто... Ведь так? Ну, почти. Единственная проблема заключается в том, что вы не знаете, какой антенне соответствует каждое из расстояний. Ваша задача – определить местонахождение пользователя, зная только местонахождение всех антенн и мультимножество расстояний до них.
Выходные данные
Для каждого запроса выведите сначала число \(k\) – количество возможных местонахождений пользователя, а затем список из этих точек в лексикографическом порядке.
Гарантируется, что сумма \(k\) по всем запросам не превосходит \(10^6\).
Примечание
Как можно видеть во втором примере — хотя местонахождение пользователя и выбирается так, чтобы иметь неотрицательные координаты, вам необходимо вывести все возможные целочисленные координаты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0
0 1
1 0
1
1 1 2
|
1 1 1
|
|
2
|
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
|