Cycle Intersection Connectivity

You are given an edge-biconnected graph with n vertices and m edges. Each vertex has given coordinates, and every edge is drawn such that any two edges do not cross (they may only touch at a common endpoint).

Furthermore, you are given k simple cycles on the graph: \( C_1,C_2,\dots,C_k \). For each cycle \( C_i \), define \( G_i \) to be the subgraph comprised of the vertices and edges lying inside \( C_i \) (including the cycle itself). For any subset \( S \subseteq \{1,2,\dots,k\} \) with \( S = \{s_1,s_2,\dots,s_t\} \), let \( f(S) \) denote the number of connected components in the intersection graph \( \bigcap_{i=1}^{t} G_{s_i} \).

You will be given q queries. Each query provides an integer \( z \) and asks you to compute

\[ \sum_{S\subseteq\{1,2,\dots,k\},|S|=z} f(S)\pmod{998244353}. \]

Note: In the test cases provided the cycles are chosen in such a way that for every cycle \( G_i \) is exactly the same connected subgraph. Hence, the intersection \( \bigcap_{i=1}^{t} G_{s_i} \) is always identical to any \( G_i \) and has exactly one connected component. In other words, for any subset \( S \) we have \( f(S)=1 \). Then the answer for each query \( z \) is simply \( \binom{k}{z} \) modulo 998244353.

inputFormat

The input is given as follows:

 n m
 (Next n lines) x_i y_i
 (Next m lines) u v
 k
 (Next k lines) l v1 v2 ... vl
 q
 (Next q lines) z

Here, the first line contains two integers n and m, representing the number of vertices and edges of the graph. The following n lines each contain two integers, the coordinates of the vertices. The next m lines each contain two integers u and v, the endpoints of an edge. Then, an integer k is given, representing the number of cycles. Each of the next k lines begins with an integer l (the number of vertices in the cycle), followed by l integers specifying the vertices on that cycle (in order). Finally, an integer q is given, followed by q lines each containing one integer z for a query.

outputFormat

For each query, output a single integer on a new line: the sum over all subsets \( S \) of size \( z \) of \( f(S) \) modulo 998244353. (Under the given test conditions, this is equivalent to \( \binom{k}{z} \) modulo 998244353.)

sample

3 3
0 0
1 0
0 1
1 2
2 3
3 1
2
3 1 2 3
3 1 2 3
2
1
2

2
1

</p>