在这个国家，所有来自国外的国际邮件首先被汇集到中央邮局，然后通过中转一些邮局分发到各个目的地邮局。邮局之间的投递路线由有向图 $G = (V, E)$ 描述，其中 $V$ 是邮局集合，$E$ 是可能的邮件转发步骤集合。由于操作效率低下，你不能指望邮件是沿着最短路径投递的。

邮局集合可以划分为若干个组。这里，组被定义为一组邮局，邮件可以从该组中的任何成员直接或间接地转发给任何其他成员。此类组中的邮局数量不超过 10 个。

邮局经常收到客户的投诉，称某些邮件尚未送达。这种问题通常是由于单个邮局的系统故障引起的，但确定是哪个邮局并不容易。因此，当收到此类投诉时，客户支持部门会派遣工作人员检查每个候选邮局的系统。这里，检查邮局 $u$ 系统的调查成本由 $c_u$ 给出，这取决于邮局的规模。

由于国内邮局众多，且此类投诉频繁，降低调查成本是一个重要问题。为了降低成本，邮政管理部门决定采用以下调度规则：当某一天收到关于未送达邮件的投诉（涉及邮局 $w_1, \dots, w_k$）时，第二天会派遣工作人员调查候选邮局中调查成本最低的一个邮局 $v$。这里，如果从中央邮局到邮局 $w_1, \dots, w_k$ 的所有邮件都必须经过 $v$，则称邮局 $v$ 为候选邮局。如果在邮局 $v$ 中没有发现问题，我们必须决定调查其他邮局的顺序，但这个问题留待以后的日子解决。

你的任务是编写一个程序，当给定某一天收到投诉的邮局列表 $w_1, \dots, w_k$ 作为查询时，找出成本最低的候选邮局的成本。

输入格式

输入包含单个测试用例，格式如下：

$n \ m$ $u_1 \ v_1$ $\vdots$ $u_m \ v_m$ $c_1$ $\vdots$ $c_n$ $q$ $k_1 \ w_{11} \ \dots \ w_{1k_1}$ $\vdots$ $k_q \ w_{q1} \ \dots \ w_{qk_q}$

$n$ 是邮局的数量（$2 \le n \le 50,000$），编号从 1 到 $n$。其中，邮局 1 对应中央邮局。$m$ 是邮局之间的转发对数量（$1 \le m \le 100,000$）。对 $(u_i, v_i)$ 表示在邮局 $u_i$ 收到的一些邮件被转发到邮局 $v_i$（$i = 1, \dots, m$）。$c_j$ 是邮局 $j$ 的调查成本（$j = 1, \dots, n$，$1 \le c_j \le 10^9$）。$q$（$q \ge 1$）是查询次数，每个查询由收到未送达邮件投诉的邮局列表指定。$k_i$（$k_i \ge 1$）是列表的长度，$w_{i1}, \dots, w_{ik_i}$ 是列表中的不同邮局。$\sum_{i=1}^q k_i \le 50,000$。

你可以假设从中央邮局到所有邮局至少存在一条投递路线。

输出格式

对于每个查询，输出一个整数，即故障邮局候选者中的最低调查成本。

样例

样例输入 1

8 8
1 2
1 3
2 4
2 5
2 8
3 5
3 6
4 7
1000
100
100
10
10
10
1
1
3
2 8 6
2 4 7
2 7 8

样例输出 1

1000
10
100

样例输入 2

10 12
1 2
2 3
3 4
4 2
4 5
5 6
6 7
7 5
7 8
8 9
9 10
10 8
10
9
8
7
6
5
4
3
2
1
3
2 3 4
3 6 7 8
3 9 6 3

样例输出 2

8
5
8