410234: GYM103987 J Gift

Walk Alone has just met a cute girl, Salix Leaf. Her birthday is coming, so Walk Alone decides to buy a bipartite graph with $$$n+m$$$ nodes. $$$m$$$ nodes for her, and the rest $$$n$$$ for himself. On each node there is a number, and there are $$$e$$$ edges connecting the two sides.

Walk Alone is curious about the graph, and he wants to find out some features of the graph so that he can tease Salix when meeting her the next time.

Specifically, Walk Alone will ask her $$$q$$$ questions. In each question, Walk Alone will give her a number $$$x$$$, and ask her to tell him the number of ways to choose a subset of nodes from the graph such that

• The xor sum of nodes she chooses is $$$x$$$.
• It is possible to choose some edges from the graph, so that each node in the graph is covered by at most one edge, and each node in the subset is be covered by exactly one edge.

Since the answer is very large, Walk Alone only requires the answer modulo $$$998\,244\,353$$$.

It is too hard for Salix to solve the questions herself. As her best friend, can you help her with the questions?

The first line contains three integers, $$$n\ (1\le n\le 20)$$$, $$$m\ (1\le m\le 20)$$$, and $$$e\ (1\le e\le n\cdot m)$$$.

The second line contains $$$n$$$ integers, the $$$i$$$-th number $$$a_i\ (0\le a_i<2^{18})$$$ represents the number on the $$$i$$$-th node of Walk Alone's.

The third line contains $$$m$$$ integers, the $$$i$$$-th number $$$b_i\ (0\le b_i<2^{18})$$$ represents the number on the $$$i$$$-th node of Salix's.

The next $$$e$$$ lines describe the edges in the graph. Each line contains two integers $$$u\ (1\le u\le n)$$$ and $$$v\ (1\le v\le m)$$$, indicating an edge between the $$$u$$$-th node of Walk Alone's and the $$$v$$$-th node of Salix's. It is guaranteed that there are no multiple edges.

The next line contains an integer $$$q\ (1\le q\le 10^5)$$$, and each of the next $$$q$$$ lines contains an integer $$$x\ (0\le x<2^{18})$$$ indicating a question.

For each query, output a number in a line representing the answer.

3 2 4
1 2 3
4 5
1 1
1 2
2 1
3 2
3
0
1
7

3
3
4

The graph in the example is shown in the picture below (we label the nodes owned by Walk Alone and Salix as $$$A_1,A_2,A_3$$$ and $$$B_1,B_2$$$ respectively).

In the first query, the sets with xor sum equal to $$$0$$$ are $$$\varnothing,\{A_1,B_1,B_2\},\{A_2,A_3,B_1,B_2\}$$$. All these sets are valid. For the second set, we can choose $$$2$$$ edges, $$$(A_1,B_1)$$$ and $$$(A_3,B_2)$$$. For the last set, we can choose $$$(A_2,B_1)$$$ and $$$(A_3,B_2)$$$.

In the second query, the sets with xor sum equal to $$$1$$$ are $$$\{A_1\},\{A_2,A_3\},\{B_1,B_2\},\{A_1,A_2,A_3,B_1,B_2\}$$$. For the last set, it can be proved that choosing a valid set that can cover all nodes exactly once is impossible, so there are only $$$3$$$ valid sets in total.