Problem G
Geometry is Fun

Geometry is Fun! Won’t you agree? From the Greeks to the Chinese, and to you, we all love geometry! It so happens that The Great Lord Pooty loves geometry as well! So here is a geometry question for you.

You have been hit by a truck and reincarnated as a point in a 2-dimensional world (which is good, since you hated the 3-dimensional world anyways). However, you are sent inside a bounding box that has a height of $2 \cdot h$ and a width of $2 \cdot 10^{100}$. The bottom-left corner of the box is on coordinate $(-10^{100}, -h)$, and the top-right corner of the box is on coordinate $(10^{100}, h)$. You cannot touch or pass through the walls of the bounding box.

You want to escape the box by getting from the left side of the box at coordinate $(-10^{99}, 0)$ to the exit at the right side of the box at coordinate $(10^{99}, 0)$. While you can travel at the speed of light and could find the exit in an instant, there is a single problem. The box consists of patches of pain and despair. Having been granted a new life in a new world, you don’t want to become depressed like you were in your old world. As such, you must avoid these patches at all costs while moving to the exit.

However, this may not be possible. But fear not! Lord Pooty, the benevolent god that sent you here, decide to give you a deal. He can remove the patches in exchange for your coins (which you will repay in the future). First, let us define the shape of these patches.

A patch $i$ is defined by its origin ${O_ i}$, a set of $k_ i$ vectors $V_ i = \{ \vec{v_{i,1}}, \dots \vec{v_{i,k_ i}}\} $, and a real-valued factor $F$. The factor $F$ is shared among all patches. Then, the set of points $S_ i$ for a patch $i$ is defined as:

Notice that the set of points $S_ i$ will give you a convex polygon, which is the area covered by the patch $i$. Intuitively, you can imagine the parameter $F$ as a modifier of the size of the patch and the set of vectors $V_ i$ defines the shape of the patch.

A patch $i$ costs $c_ i$ per unit area to remove. Thus, the cost to remove patch $i$ is $c_ i A_ i$, where $A_ i$ is the area of the patch $S_ i$. Note that you cannot partially remove a patch — you can only remove either the entire patch or none of it.

At the start, all patches have $F = 0$. In other words, the patches are just a point. However, over the next $m$ seconds, they will grow. After the $i$-th second, $F$ will increase by $q_ i$. Note that all of the patches will grow by the same $q_ i$, and the changes are persistent.

You have not decided when to start your journey. Therefore, supposing you start your journey just after the $i$-th second, you want to find out the minimum cost you must pay to Lord Pooty so he can remove zero or more patches such that you can reach the exit without touching any patch.

Note that some points may be covered by multiple patches, and you must pay the cost of all patches if you wish to travel through that point. Additionally, the boundary of each patch is also considered to be part of the patch.

Since the output may not fit in a 64-bit integer, simply output the answer modulo $10^{10} + 3233 = 10\, 000\, 003\, 233$.

There is one other important constraint: the $x$ and $y$ components of all vectors $\vec{v_{i,j}}$ are generated uniformly and independently at random from the interval $[-10^4, 10^4]$ and the $x$ and $y$ components of all origins ${O_ i}$ are generated uniformly and independently at random from the interval $[-10^9, 10^9]$ .

Input

The input starts with a line containing two integers $h$ and $n$, denoting half the height of the bounding box and the number of patches ($1 \leq h \leq 10^9$; $1 \leq n \leq 100$).

The input is then followed by the description of $n$ patches. Each patch is described as follows:

• The first line contains two integers $k_ i$, and $c_ i$, denoting the number of vectors describing the patch and the cost per unit area to remove the patch ($1 \leq k_ i \leq 500\, 000$; $1 \leq c_ i \leq 10^4$). The sum of $k_ i$ over all patches is at most $500\, 000$. Furthermore, it is guaranteed $c_ i$ is even.

• The second line contains two integers $O_{i,x}$ and $O_{i,y}$, denoting the $x$ and $y$ coordinates of the origin of the patch $O_ i$ ($|O_{i,x}|, |O_{i,y}| \leq 10^9$). It is guaranteed that $O_{i,x}$ and $O_{i,y}$ are generated uniformly and independently at random from the interval $[-10^9, 10^9]$.

• The third line contains $2 \cdot k_ i$ integers, $v_{i,1,x}, v_{i,1,y}, v_{i,2,x}, v_{i,2,y}, \dots v_{i,k_ i,x}, v_{i,k_ i,y}$, denoting the $x$ and $y$ components of the vectors $\vec{v_{i,j}}$ describing the patch ($|v_{i,j,x}|, |v_{i,j,y}| \leq 10^4$). It is guaranteed that $v_{i,j,x}$ and $v_{i,j,y}$ are generated uniformly and independently at random from the interval $[-10^4, 10^4]$.

The next line of input contains an integer $m$ denoting the number of seconds ($1 \leq m \leq 1\, 000\, 000$).

The next line contains $m$ integers $q_1, q_2, \dots q_ m$, denoting the amount by which the factor $F$ (the size of the patches) will increase after each second ($1 \leq q_ i \leq 10^9$). Furthermore, it is guaranteed that $\sum _{i = 1}^ m q_ i \leq 10^9$.

Output

Output $m$ lines, each containing a single integer. The $i$-th line should contain the minimum cost to remove zero or more patches such that you can reach the exit without touching any patch just after the $i$-th second. Since the output may not fit in a 64-bit integer, you should output the answer modulo $10\, 000\, 003\, 233$.

10 1
4 10
0 0
0 1 0 -1 1 0 -1 0
7
1 3 4 10 9 10000000 10

0
0
0
6480
14580
153411347
4153424147

10 3
4 10
0 -5
0 1 0 -1 1 0 -1 0
4 10
0 5
0 1 0 -1 1 0 -1 0
2 3230
0 0
0 -3233 0 3233
10
1 1 1 1 1 1 1 10 1000000 100000000

0
0
0
0
500
720
980
11560
1347079560
5440679560