Задача G. Geometric tomography ≡

Условие

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

Пусть имеется некоторый выпуклый многоугольник, вложенный в прямоугольник ABCD со сторонами параллельными осям координат (см. рисунок). Обозначим за P_AB, P_BC, P_CD и P_DA серию фотоснимков, представляющих собой множества вершин исходного многоугольника, которые могут быть спроецированы на соответствующие ребра прямоугольника. Помимо этого будем считать, что существует ровно одна промаркированная вершина, отмеченная на каждом из содержащих ее снимков.

Требуется по заданному набору снимков с отмеченной на них маркерной вершиной восстановить координаты вершин исходного многоугольника, где в качестве начала координат принимается точка A.

Формат входных данных

Во входных данных построчно хранятся множества P_AB, P_BC, P_CD и P_DA, записанные в следующем виде. Вначале идет число вершин N, попадающих в текущее множество. За ними следует ровно N целых чисел — проекции указанных вершин на соответствующее ребро. Далее следует индекс маркерной вершины, под которым она фигурирует в текущем множестве, или −1, если она в нем не содержится.

Вершины в пределах отдельно взятого снимка пронумерованы с нуля в порядке их обхода по часовой стрелке.

Формат выходных данных

Выходные данные должны содержать координаты вершин исходного многоугольника, расположенные в порядке их обхода по часовой стрелке, начиная от промаркированной вершины.

Ограничения

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

Число вершин многоугольника не превосходит 2 ⋅ 10⁵, а их координаты лежат в диапазоне от 0 до 10⁹.

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

3 54 146 267 -1
4 50 104 210 263 3
4 267 221 117 54 2
3 263 145 50 0

263 117
145 54
50 146
104 267
210 221

4 9 136 257 257 1
4 24 92 221 240 0
4 257 257 136 9 -1
3 240 175 24 2

24 136
92 257
221 257
240 136
175 9