题目描述

$xy$ 平面上に $N$ 個の多角形があります。
これらの多角形は、全ての辺が $x$ 軸または $y$ 軸に平行で、全ての角が $90$ 度または $270$ 度で、かつ単純です。
$i$ 個目の多角形は $M_i$ 個の頂点からなり、$j$ 番目の頂点は $(x_{i,\ j},\ y_{i,\ j})$ です。
多角形の辺は $j$ 番目の頂点と $j+1$ 番目の頂点を結んでできる線分です(ただし $M_i+1$ 番目の頂点は $1$ 番目の頂点とします)。

多角形が単純とは 連続しないどの $2$ 辺も共通部分を持たない(すなわち交差も接触もしない)とき、その多角形を単純といいます。

$Q$ 個のクエリが与えられます。 $i\ =\ 1,\ 2,\ \dots,\ Q$ について、$i$ 個目のクエリは以下の通りです。

• $N$ 個の多角形のうち、点 $(X_i\ +\ 0.5,\ Y_i\ +\ 0.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$ 個目のクエリに対する答えを出力せよ。

题目大意

题目大意

给出平面的 $N$ 个简单多边形，对于每个多边形，其每一条边都平行于 $X$ 轴或 $Y$ 轴，每一个角都为 $90$ 度或 $270$ 度，如图所示。

现在有 $Q$ 次询问，每次给出一个有序整数对 $(X,Y)$ ，求点 $(X+0.5,Y+0.5)$ 被多少个多边形覆盖。

数据范围

• $1\le N \le 10^5$

• $4\le M_i \le 10^5$

• $\forall M_i,i\isin [1,N],M_i$ 为偶数

• $\sum M_i\le 4\times 10^5$

• $0\le x_{i,j},X_i,y_{i,j},Y_i \le 10^5$

• $1\le Q \le 10^5$

• 对于 $j=1,3,5... M_i-1$ ，都有 $x_{i,j}=x_{i,j+1}$

• 对于 $j=2,4,6... M_i$ ，都有 $y_{i,j}=y_{i,j+1}$ （特殊的, $y_{i,M_i}=y_{1,1}$ ）

• 对于任意一个给出多边形，没有重合的顶点。即若 $k \not= j$ ，则 $(x_{i,j},y_{i,j}) \not= (x_{i,k},y_{i,k})$

• 输入的所有数据均为整数。

输入格式

第一行输入一个整数 $N$ 。

后面 $1$ 至 $N+1$ 行，第 $i$ 行先输入一个整数 $M_i$ ，再输入 $2\times M_i$ 个整数：$x_{i,1},y_{i,1},x_{i,2},y_{i,2},...,x_{i,M_i},y_{i,M_i}$ 。其相邻两点所连成的线段即为多边形的边。

接下来读入一个数 $Q$ 。表示询问 $Q$ 次。

后面 $Q$ 行每行有两个数 $X_i,Y_i$ ，表示询问点 $(X_i+0.5,Y_i+0.5)$ 被多少个多边形覆盖。

输出格式

共 $Q$ 行，每一行有一个整数表示答案。

样例解释

1.如上图

2.如下图

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

0
2
1

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

0
2
1
1

提示

制約

• $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$
• 入力は全て整数

Sample Explanation 1

 異なる多角形同士は、交差したり接触したりする可能性があることに注意してください。

Sample Explanation 2

 多角形は単純ですが、凸多角形とは限りません。