Description

"Clone! Technique!" — Xiao P.

On a plane, there are $n$ clones of Xiao P. Define the region occupied by a set of clones as the smallest convex polygon that covers this set of clones (i.e., the convex hull). Xiao P's ability is limited: at each time step, several clones will disappear. However, before the next time step, Xiao P will use the Clone Technique to make these disappeared clones reappear at their original positions.

Xiao P wants to know the area of the region occupied by the remaining clones after the disappearances at each time step.

Constraints

• $|x_i|, |y_i| \le 10^8$.
• No two clones share exactly the same coordinates.
• $k \le 100$.
• The sum of $k$ over all time steps does not exceed $2 \times 10^6$.
• $0 \le c_i \le 2^{31} - 1$.
• Initially, the area occupied by all $n$ clones is greater than $0$.
• Define the vertex set of the region occupied by all $n$ clones as $S$, with $|S| \ge 3$. At any time step, there exist at least two clones from $S$ that have not disappeared.

Input Format

The first line contains two positive integers $n, m$, denoting the initial number of clones and the total number of time steps.

The next $n$ lines each contain two integers $x_i, y_i$, describing the position of the $i$-th clone.

The next $m$ lines: on each line, the first integer $k$ indicates that $k$ clones disappear at this time step. Then there are $k$ non-negative integers $c_1, c_2, \ldots, c_k$, used to generate the indices of the disappearing clones.

Generation method:

Let $S$ be twice the area of the region occupied by the clones at the previous time step. Then the indices of the clones that disappear at this time step, $p_1, p_2, \ldots , p_k$, are: $p_i = [(S + c_i) \bmod n] + 1$.

In particular, at the first time step we assume $S = -1$, i.e., the indices of the clones that disappear at the first time step, $p_1, p_2, \ldots , p_k$, are: $p_i = [(−1 + c_i) \bmod n] + 1$.

Output Format

Output $m$ lines in the order of the time steps. Each line contains one integer: twice the area of the region occupied by the remaining clones at that time step.

6 2
-1 0
-1 -1
0 -1
1 0
0 1
0 0
3 1 3 6
2 0 1

3
2

Hint

Sample explanation:

As shown in the figure: the left figure shows the positions of the $6$ clones and the region they occupy; the middle figure shows the situation at the first time step, where the indices of the disappearing clones are $1, 3, 6$. The remaining $3$ points occupy the region inside the solid lines in the figure, and twice the area is $3$. The right figure shows the situation at the second time step, where the indices of the disappearing clones are

$[(0 + 3)\bmod 6] + 1 = 4$

$[(1 + 3)\bmod 6] + 1 = 5$

The remaining $4$ points occupy the region inside the solid lines in the figure.

Translated by ChatGPT 5