Description

The mining area on the plane is divided into several development regions.

Simply put, you can regard the mining area as a connected planar graph. The plane is partitioned into several faces, and each face is a development region. The boundaries between faces consist of integer points (points whose coordinates are integers) and line segments connecting these integer points. The mineral amount of each development region depends on its area: specifically, for a development region with area $s$, its mineral amount is $s^2$.

There are $m$ mining plans. Each plan specifies a polygon consisting of several development regions. The priority of a plan is defined as the total mineral amount divided by the total area of the selected regions. For example, if a plan specifies two regions of areas $a$ and $b$, then its priority is $(a^2 + b^2)/(a + b)$. Since the planar graph is given by the points and edges that define the boundaries of development regions, each plan only specifies the boundary of its polygon, without explicitly listing which regions are included. However, once the polygon boundary is given, the included development regions are uniquely determined.

Your task is to compute the priority for each mining plan. To avoid precision issues, your answer must be output as a fraction in irreducible form, i.e., output the numerator and denominator as integers with their greatest common divisor removed. For example, if the total mineral amount is $1.5$ and the total area is $2$, then the numerator should be $3$ and the denominator should be $4$. As another example, if the total mineral amount is $2$ and the total area is $4$, then the numerator should be $1$ and the denominator should be $2$.

For certain reasons, you must process each mining plan sequentially (the next plan is encoded based on the previous plan’s answer). The specific encoding is given in the input format.

Input Format

The first line contains three positive integers $n, m, k$, representing the number of vertices in the planar graph, the number of edges, and the number of mining plans, respectively.

The next $n$ lines. In the $i$-th line ($i = 1, 2, \cdots, n$), there are two integers $x_i, y_i$, indicating that vertex $i$ has coordinates $(x_i, y_i)$.

The next $m$ lines. In the $i$-th line, there are two positive integers $a, b$, indicating that there is an edge between vertices $a$ and $b$.

The next line contains several integers describing all mining plans in order. For each plan, the first number $c$ determines the number of boundary vertices of the polygon formed by development regions as $d = (c + P) \bmod n \mathrel{+} 1$. Then $d$ integers follow, giving the boundary vertices in counterclockwise order: let the $i$-th number be $z_i$, then the index of the $i$-th vertex is $(z_i + P) \bmod n \mathrel{+} 1$. Here $P$ is the numerator of the answer for the previous mining plan; for the first plan, $P = 0$.

Output Format

For each mining plan, output one line with two positive integers, the numerator and the denominator, respectively.

9 14 5
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
1 2
2 3
5 6
7 8
8 9
1 4
4 7
5 8
3 6
6 9
4 8
1 5
2 6
6 8
3 3 0 4 7 1 3 4 6 4 8 0 4 3 6 2 3 8 0 4 6 2 5 0 4 5 7 6 3

1 1 
1 2 
1 1 
9 10 
3 4

Hint

Sample Explanation

The planar graph described by $9$ points and $14$ edges in the input is shown below:

For the first mining plan, the first value in the input is $3$, so the polygon of this plan has $(3 + 0) \bmod 8 + 1 = 4$ vertices. Substituting the next four numbers $3, 0, 4, 7$ into $(z_i + 0) \bmod n + 1$, the indices of the four vertices are $4, 1, 5, 8$. The numerator of the first plan is $1$, and the denominator is $1$.

Similarly, the remaining polygons’ vertex counts and indices are: for the second plan, it has $3$ vertices with indices $5, 6, 8$. For the third plan, it has $6$ vertices with indices $1, 2, 6, 5, 8, 4$. For the fourth plan, it has $5$ vertices with indices $1, 2, 6, 8, 4$. For the fifth plan, it has $6$ vertices with indices $1, 5, 6, 8, 7, 4$.

Constraints

For $100\%$ of the testdata, $n, k \leq 2 \times 10^5$, $m \leq 3n - 6$, and $|x_i|, |y_i| \leq 3 \times 10^4$.

The sum of $d$ over all mining plans does not exceed $2 \times 10^6$. It is guaranteed that each mining plan contains at least one development region, and these regions form a connected component.

It is guaranteed that the total mineral amount over all development regions does not exceed $2^{63} - 1$.

It is guaranteed that there are no redundant vertices or edges in the planar graph.

The input is guaranteed to be valid. Because the input size is large, fast I/O is recommended.

2025-06-03: Added a set of hack testdata This set of hack testdata had out-of-bounds values. It was removed and replaced on 2025.10.10.

Translated by ChatGPT 5