[ZJOI2008]无序运动Movement

D 博士长期研究粒子运动的无序性。经过大量研究，他发现了许多频繁出现的轨迹片段，并将这些片段存入一个大型数据库。现在，他需要统计数据库中的每个轨迹片段在一条给定粒子运动轨迹中的出现次数。

定义粒子的运动轨迹为二维平面上的点列

$$P=(P_1,P_2,\ldots,P_N)。$$

点列 $P$ 的子列 $[i,j]$ 是其中一段连续的子序列

$$(P_i,P_{i+1},\ldots,P_j)。$$

设数据库中的一个轨迹片段为

$$Q=(Q_1,Q_2,\ldots,Q_{v-u+1})。$$

如果可以对 $Q$ 进行有限次平移、旋转、翻转或放缩，得到点列 $Q'$，并满足

$$Q'_k=P_{u+k-1}\qquad(k=1,2,\ldots,v-u+1)，$$

则称 $P$ 的子列 $[u,v]$ 是 $Q$ 在 $P$ 中的一次出现。

上述四种平面变换定义如下：

• 平移：设平移向量为 $(d_x,d_y)$，则点 $(x,y)$ 平移后变为 $(x+d_x,y+d_y)$。
• 旋转：设旋转角为 $t$，则点 $(x,y)$ 旋转后变为 $$(x\cos t-y\sin t,\ x\sin t+y\cos t)。$$
• 翻转：点 $(x,y)$ 翻转后变为 $(x,-y)$。
• 放缩：设放缩比例为 $p$，其中 $p\ne 0$，则点 $(x,y)$ 放缩后变为 $(px,py)$。

请分别计算数据库中的每个轨迹片段在给定运动轨迹中的出现次数。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示待处理运动轨迹的点数和数据库中的轨迹片段数。

接下来 $M$ 行，每行描述一个轨迹片段。每行首先包含一个正整数 $K$，表示该轨迹片段的点数；随后包含 $2K$ 个整数，依次表示这 $K$ 个点的横坐标和纵坐标。

最后一行包含 $2N$ 个整数，依次表示待处理运动轨迹中 $N$ 个点的横坐标和纵坐标。

输入中的每条轨迹内，任意相邻两点均不相同。

输出格式

输出 $M$ 行，第 $i$ 行表示数据库中第 $i$ 个轨迹片段在待处理运动轨迹中的出现次数。

样例输入

3 2
2 17 0 10 1
3 0 0 1 0 1 -1
0 0 1 0 1 1

样例输出

2
1

数据范围

• $N,K\le 2\times 10^5$；
• 所有轨迹片段的总长度不超过 $1.6\times 10^6$；
• 输入中所有点的横坐标和纵坐标的绝对值均不超过 $10^4$。

来源与许可

本题为 ZJOI 2008 试题「无序运动」，题面与测试数据整理自 BZOJ。