Problem Description

The transportation system of Country H consists of $n$ cities and $m$ roads. Both cities and roads are numbered starting from $1$, and City $1$ is the capital of Country H. In Country H, each road directly connects two different cities, and there is at most one road between any two cities.

Country H is a nation that believes in magic. On day $j$, the magic value of City $i$ is $f_{i,j}$. The wizards of Country H have observed the magic values $f_{i,0}$ of all cities on day $0$. They also found that on each following day, the magic value of every city will become the XOR of the previous day's magic values of all cities directly connected to it, that is,

$$f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}$$

where $j\ge 1$, $v_1, v_2, \cdots, v_k$ are all cities directly connected to City $x$, and $\oplus$ denotes the XOR operation.

Now the king of Country H asks you $q$ questions. For the $i$-th question ($1\le i\le q$), you need to answer: what is the magic value of the capital on day $a_i$.

Input Format

The first line contains three integers $n, m, q$ separated by spaces, representing the number of cities, the number of roads, and the number of questions.

The second line contains $n$ integers separated by spaces, where the $i$-th integer represents $f_{i, 0}$.

The next $m$ lines each contain two positive integers $u, v$ separated by spaces, indicating a road connecting City $u$ and City $v$.

The next $q$ lines each contain one integer. The integer on the $i$-th line represents $a_i$.

Output Format

Output $q$ lines in order, each containing one integer, representing the answer to the corresponding question.

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

1

Hint

Constraints

• For $20\%$ of the testdata, $a_i \leq 100$.
• For $40\%$ of the testdata, $n \leq 20$.
• Another $30\%$ of the testdata satisfies $m=\frac{n(n-1)}{2}$.
• For $100\%$ of the testdata, $1 \leq n, q \leq 100$, $1 \leq m \leq \frac{n(n-1)}{2}$, $1\leq a_i < 2^{32}$, $0\leq f_{i,0} < 2^{32}$.

Notes

data provider: @一扶苏一. If there are issues with the data, please contact her. If it gets accepted by a naive fast exponentiation solution, please also contact her.

Translated by ChatGPT 5