题目描述

给出一棵 $n$ 个点 $m$ 条边的仙人掌 $G$，点 $i$ 有点权 $a_i$。（其中仙人掌定义为每条边至多出现在一个简单环中的简单无向连通图）。

$q$ 次询问，每次询问给出 $k$，表示查询在仙人掌上选择一个非空子树（也就是仙人掌的一个无环连通子图）和子树中的一个点 $r$，使得子树中所有点到 $r$ 在选出的子树上的距离之和 $\text{sum}$ 至少为 $k$ 的情况下，子树上所有点的点权的 $\text{gcd}$ 最大是多少。

输入格式

第一行 $4$ 个数 $C, n, m, q$，其中 $C$ 表示子任务编号（样例的 $C = 0$）。

接下来一行 $n$ 个正整数 $a_i$。

接下来 $m$ 行每行两个正整数 $u, v$ 表示 $u$ 和 $v$ 由一条双向边链接。

接下来 $q$ 行每行一个正整数 $k$。

以上字母未经特殊说明均与题目描述中含义一致。

输出格式

输出 $q$​ 行，每行一个数，依次表示对应询问的答案。特别地，如果不存在这样的选择子树方法，输出 -1。

样例 1

样例输入 1

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

样例输出 1

2

更多样例见下发文件

数据范围

对于所有数据 $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}$，保证输入是一棵仙人掌。