问题描述

我们在 $xy$ 平面上有 $N$ 个多边形。
这些多边形的每条边都与 $x$ 轴或 $y$ 轴平行，并且每个内角为 $90$ 度或 $270$ 度。所有这些多边形都是简单多边形。
第 $i$ 个多边形有 $M_i$ 个角，第 $j$ 个角的坐标为 $(x_{i, j}, y_{i, j})$。
该多边形的边是连接第 $j$ 个角和 $(j+1)$ 个角的线段。（假设 $(M_i+1)$ 个角是第一个角。）

当...

对于它的任意两条不相邻的边，它们不相交（不交叉也不触碰）。

你会得到 $Q$ 个查询。对于每个 $i = 1, 2, \dots, Q$，第 $i$ 个查询如下：

• 在 $N$ 个多边形中，有多少个多边形包含点 $(X_i + 0.5, Y_i + 0.5)$？

约束条件

• $1 \leq N \leq 10^5$
• $4 \leq M_i \leq 10^5$
• 每个 $M_i$ 都是偶数。
• $\sum_i M_i \leq 4 \times 10^5$
• $0 \leq x_{i, j}, y_{i, j} \leq 10^5$
• 若 $j \neq k$，则 $(x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k})$。
• 对于 $j = 1, 3, \dots, M_i-1$，有 $x_{i, j} = x_{i, j+1}$。
• 对于 $j = 2, 4, \dots, M_i$，有 $y_{i, j} = y_{i, j+1}$。（假设 $y_{i, M_i +1} = y_{i, 1}$。）
• 给定的多边形都是简单多边形。
• $1 \leq Q \leq 10^5$
• $0 \leq X_i, Y_i \lt 10^5$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $M_1$ $x_{1, 1}$ $y_{1, 1}$ $x_{1, 2}$ $y_{1, 2}$ $\dots$ $x_{1, M_1}$ $y_{1, M_1}$ $M_2$ $x_{2, 1}$ $y_{2, 1}$ $x_{2, 2}$ $y_{2, 2}$ $\dots$ $x_{2, M_2}$ $y_{2, M_2}$ $\vdots$ $M_N$ $x_{N, 1}$ $y_{N, 1}$ $x_{N, 2}$ $y_{N, 2}$ $\dots$ $x_{N, M_N}$ $y_{N, M_N}$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_Q$ $Y_Q$

输出

输出 $Q$ 行。
第 $i$ 行应包含第 $i$ 个查询的答案。

示例输入1

3
4
1 2 1 4 3 4 3 2
4
2 5 2 3 5 3 5 5
4
5 6 5 5 3 5 3 6
3
1 4
2 3
4 5

示例输出1

0
2
1

请注意，不同的多边形可能会相交或接触。

示例输入2

2
4
12 3 12 5 0 5 0 3
12
1 1 1 9 10 9 10 0 4 0 4 6 6 6 6 2 8 2 8 7 2 7 2 1
4
2 6
4 4
6 3
1 8

示例输出2

0
2
1
1

虽然多边形是简单的，但它们可能不是凸多边形。