Задача J. Точки на планарном разбиении ≡

Условие

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

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

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

Формат входного файла

Во входном файле "input.txt" записано натуральное число n, за которым следует ровно n пар целых десятичных чисел (x_i, y_i), задающих координаты вершин планарного подразбиения.

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

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

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность из номеров ячеек, в которые попадают указанные точки.
При этом полагается, что нумерация ячеек начинается с нуля.

Для точек, лежащих за пределами каких либо ячеек, в качестве ответа необходимо вывести  − 1.

Ограничения

Гарантируется, что ни одна из искомых точек не попадает на границу ячейки.

Все входные значения являются целыми десятичными числами.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10³, 0 < k ≤ 3 ⋅ 10⁵

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

5
200 100
100 200
200 200
300 300
150 350

3
3 2 0 1
3 3 2 4
3 4 2 1

4
190 175
100 100
190 203
270 300

0
-1
2
1