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

Сегодня Денис проводит в ЛКШ клуб анонимных геометров. Он заготовил для клуба $$$n$$$ выпуклых многоугольников, пронумерованных от $$$1$$$ до $$$n$$$. Он планирует предложить участникам клуба посчитать суммы Минковского этих многоугольников. А именно, он планирует дать $$$q$$$ заданий, в $$$i$$$-м из них нужно посчитать сумму Минковского многоугольников с номерами от $$$l_i$$$ до $$$r_i$$$ включительно.

Суммой Минковского двух множеств $$$A$$$ и $$$B$$$ называется множество $$$C = \{a + b : a \in A, b \in B\}$$$. Можно доказать, что если $$$A$$$ и $$$B$$$ являются выпуклыми многоугольниками, то $$$C$$$ тоже будет выпуклым многоугольником.

Сумма двух выпуклых многоугольников

Чтобы посчитать сумму Минковского $$$p$$$ многоугольников ($$$p > 2$$$), нужно посчитать сумму Минковского первых $$$p - 1$$$ многоугольников, а потом сумму Минковского результата и $$$p$$$-го многоугольника.

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

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

В первой строке дано одно целое число $$$n$$$ — количество выпуклых многоугольников, которые подготовил Денис ($$$1 \le n \le 100\,000$$$).

Далее дано описание $$$n$$$ выпуклых многоугольников. Описание $$$i$$$-го многоугольника начинается с целого числа $$$k_i$$$ — количество вершин в $$$i$$$-м многоугольнике ($$$3 \le k_i$$$). После чего в $$$k_i$$$ строках даны по два целых числа $$$x_{ij}$$$, $$$y_{ij}$$$ — координаты вершин $$$i$$$-го многоугольника в порядке обхода против часовой стрелки ($$$|x_{ij}|, |y_{ij}| \le 10 ^ 9$$$).

Гарантируется, что многоугольники не содержат трех последовательных вершин, лежащих на одной прямой. Суммарное количество вершин в многоугольниках не превышает $$$300\,000$$$.

В следующей строке одно целое число $$$q$$$ — количество заданий ($$$1 \le q \le 100\,000$$$). В следующих $$$q$$$ строках дано описание заданий. Описание $$$i$$$-го задания содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

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

Для каждого задания выведите одно целое число — количество вершин в сумме Минковского многоугольников с номерами от $$$l_i$$$ до $$$r_i$$$.

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

Пояснение к примеру:

Первый, второй и третий многоугольники из тестового примера
Суммы Минковского первого и второго, второго и третьего и всех трех многоугольников соответственно