Magic Value Evolution in H Country

H country's transportation network consists of n cities and m roads, with both cities and roads numbered from 1, where city 1 is the capital. Each road directly connects two different cities, and any two cities have at most one road between them.

This country believes in magic. On day \( j \) the magic value of city \( i \) is \( f_{i,j} \). The magicians have observed the magic values \( f_{i,0} \) on day 0 for all cities, and they discovered that for every day \( j \ge 1 \) the magic value of each city becomes the XOR of the previous day magic values of all cities directly connected to it. In other words,

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

where \( v_1, v_2, \dots, v_k \) are all the cities directly connected to city \( x \), and \( \oplus \) denotes the bitwise XOR operation.

You are given \( q \) queries. For the \( i\)-th query, answer what is the magic value of the capital (city 1) on day \( a_i \).

inputFormat

The first line contains two integers \( n \) and \( m \) denoting the number of cities and roads respectively.

The next \( m \) lines each contain two integers \( u \) and \( v \) indicating a road between cities \( u \) and \( v \).

The following line contains \( n \) integers \( f_{1,0}, f_{2,0}, \dots, f_{n,0} \) representing the initial magic values on day 0 for each city.

The next line contains an integer \( q \), the number of queries.

Each of the following \( q \) lines contains a single non-negative integer \( a_i \) representing the day for the respective query.

outputFormat

For each query, output a line containing a single integer: the magic value of the capital (city 1) on day \( a_i \).

sample

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

1
2
2