You are given a cactus graph $G$ with $n$ vertices and $m$ edges, where each vertex $i$ has a weight $a_i$. (A cactus graph is defined as a simple undirected connected graph where each edge belongs to at most one simple cycle.)

There are $q$ queries. Each query provides an integer $k$. You need to choose a non-empty subtree (a connected subgraph of the cactus that contains no cycles) and a vertex $r$ within that subtree, such that the sum of distances from all vertices in the subtree to $r$ within the chosen subtree is at least $k$. Among all such possible choices, find the maximum possible greatest common divisor (GCD) of the weights of all vertices in the chosen subtree.

Input

The first line contains four integers $C, n, m, q$, where $C$ is the subtask number ($C = 0$ for the sample).

The next line contains $n$ positive integers $a_i$.

The next $m$ lines each contain two positive integers $u, v$, representing an undirected edge between $u$ and $v$.

The next $q$ lines each contain a positive integer $k$.

All variables above have the same meanings as described in the problem statement.

Output

Output $q$ lines, each containing a single integer representing the answer to the corresponding query. Specifically, if no such subtree exists, output -1.

Examples

Input 1

0 5 6 1
2 4 6 8 9
1 2
1 3
2 3
2 4
2 5
4 5
5

Output 1

2

See the provided files for more examples.

Constraints

For all data, $3 \le n \le 2 \times 10^5$, $n - 1 \le m \le \min \{2n, 2 \times 10^5\}$, $1 \le a_i \le A \le 10^6$, $1 \le u, v \le n$, $1 \le q \le 2 \times 10^5$, $1 \le k \le 10^{10}$. It is guaranteed that the input is a cactus graph.