Problem Description

You are given an edge-biconnected graph with $n$ vertices and $m$ edges, along with the coordinates of each vertex, ensuring that no edges intersect except at their endpoints.

Given $k$ simple cycles $C_1, C_2, \dots, C_k$ on the graph, define $G_i$ as the subgraph consisting of the vertices and edges inside $C_i$.

For a subset $S \subseteq \{1, 2, \dots, k\}$, denoted as $S = \{s_1, s_2, \dots, s_t\}$, define $f(S)$ as the number of connected components in the intersection of all $G_{s_i}$.

There are $q$ queries, each providing a value $z$, and you need to output $\sum_{S \subseteq \{1, 2, \dots, k\}, |S| = z} f(S)$, modulo $998244353$.

Input Format

The first line contains three positive integers $n, m, k$.

The next $n$ lines, each containing two integers $(x_i, y_i)$, represent the coordinates of the $i$-th vertex. It is guaranteed that for all $1 \leq i < j \leq n$, $x_i \neq x_j$ and $y_i \neq y_j$.

The next $m$ lines, each containing two positive integers $u_i, v_i$, represent an undirected edge connecting $(u_i, v_i)$.

The next $k$ lines, each starting with a positive integer $l_i$ representing the size of the cycle, followed by $l_i$ positive integers $C_{i,1}, C_{i,2}, \dots, C_{i,l_i}$, describe a simple cycle on the original graph, ensuring that $C_{i,j}$ connected in order forms a cycle on the graph.

The next line contains a positive integer $q$.

The final $q$ lines, each containing a positive integer, represent the queries for $z_i$.

Output Format

Output $q$ lines, each containing an integer representing $\sum_{S \subseteq \{1, 2, \dots, k\}, |S| = z} f(S)$ modulo $998244353$.

Sample Input and Output

Input Sample #1

4 5 3
1 1
3 2
2 3
4 4
1 2
1 3
1 4
2 4
3 4
3 1 2 4
3 1 3 4
4 1 2 4 3
3
1
2
3

Output Sample #1

3
3
1

Input Sample #2

8 15 5
4 4
5 8
2 7
10 9
1 10
3 5
8 2
7 6
2 1
3 1
3 2
4 1
4 2
5 2
5 3
5 4
6 1
6 3
7 1
7 4
8 1
8 4
8 7
3 1 8 4 
3 1 6 3 
3 7 8 4 
4 8 1 7 4 
3 1 2 3 
5
1
2
3
4
5

Output Sample #2

5
8
5
1
0

Notes

[Sample Explanation #1]

The data for Sample 1 is illustrated in the following image:

[Data Range]

This problem uses subtask-based scoring.

For 100% of the data: $1 \leq n, \sum l_i \leq 10^5$, $1 \leq m \leq 3n - 6$, $3 \leq l_i$, $0 \leq |x_i|, |y_i| \leq 10^9$, $1 \leq q \leq 20$, $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq z_i \leq k$. It is guaranteed that for all $1 \leq i < j \leq n$, $x_i \neq x_j$ and $y_i \neq y_j$. It is guaranteed that no edges intersect except at their endpoints and that the graph is an edge-biconnected component.

见题面 Input 部分

见题面 Output 部分