Dr. D has conducted in-depth research in physics, with theorems named after him in classical physics, astrophysics, and quantum physics. Recently, Dr. D has been obsessed with the irregularity of particle motion. A firm believer in the Bible, he trusts that everything created by God must be orderly and rational, rather than irregular or chaotic.
After long-term research, Dr. D has found many frequently occurring trajectory fragments, which he stores in a large database. He needs your help to write a program that counts the number of occurrences of each trajectory fragment in a given particle motion trajectory.
For clarity, we define a particle's trajectory as a sequence of points on a two-dimensional plane $(P_1, P_2, \dots, P_N)$. A sub-sequence $[i, j]$ of point sequence $P$ is defined as a contiguous subsequence $(P_i, P_{i+1}, \dots, P_j)$ in $P$. A sub-sequence $[u, v]$ of $P$ is said to be an occurrence of the point sequence $Q = (Q_1, Q_2, \dots, Q_{v-u+1})$ in $P$ if and only if $Q$ can be transformed into $Q'$ through a finite number of translations, rotations, reflections, and scalings such that $Q'_k = P_{u+k-1}$ for $k = 1, \dots, v-u+1$.
| Operation | Explanation for the X-Y Plane |
|---|---|
| Translation | Given a translation vector $(dx, dy)$, the result for any point $(x, y)$ is $(x+dx, y+dy)$ |
| Rotation | Given a rotation angle $t$, the result for any point $(x, y)$ is $(x \cos t - y \sin t, x \sin t + y \cos t)$ |
| Reflection | The result for any point $(x, y)$ is $(x, -y)$ |
| Scaling | Given a scaling factor $p$ ($p \neq 0$), the result for any point $(x, y)$ is $(px, py)$ |
Input
The first line contains two integers $N$ and $M$, representing the size of the particle motion trajectory to be processed and the number of trajectory fragments in the database, respectively.
The next $M$ lines describe each trajectory fragment. Each line starts with a positive integer $K$, representing the length of the trajectory fragment point sequence. This is followed by $2K$ integers, describing the $x$ and $y$ coordinates of the $K$ points in the sequence.
The next line contains $2N$ integers, describing the $x$ and $y$ coordinates of the $N$ points in the particle motion trajectory to be processed.
Note: No two adjacent points in any trajectory in the input are identical.
Output
The output should contain $M$ lines, each giving the number of occurrences of the corresponding fragment in the trajectory being processed.
Examples
Input 1
3 2 2 1 7 0 10 1 3 0 0 1 0 1 -1 0 0 1 0 1 1
Output 1
2 1
Constraints
For 30% of the test data, $N, M, K \le 100$, total length of fragments $\le 500$; For 50% of the test data, $N, M, K \le 1\,000$, total length of fragments $\le 5\,000$; For 100% of the test data, $N, K \le 200\,000$, total length of fragments $\le 200\,000$. The absolute values of all coordinates given in the input are no greater than $10\,000$.