题目描述

小 M 有一个长度为 $n$ 的序列 $v_1,v_2,\ldots,v_n$，初始时，所有元素的值均为 $1$。

你有 $3$ 种作用在这个序列上的操作：

1. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_1,v_2,\ldots,v_i$ 的值全部设为 $0$，这种操作的代价是 $a_i$；
2. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $0$，这种操作的代价是 $b_i$；
3. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $1$，这种操作的代价是 $c_i$。

现在有 $q$ 次询问，每次询问中给定一个集合 $P$，你希望进行若干次操作（可能为 $0$），使得：序列 $v$ 中下标位于该集合的元素的值为 $1$，其余位置的值为 $0$。形式化地说，对于任意 $\bm{1\le i\le n}$，若 $\bm{i\in P}$，则 $\bm{v_i=1}$，否则 $\bm{v_i=0}$。 并且，你需要最小化这次询问中所有操作的总代价。

注意，询问是相互独立的，也就是说，每次询问结束后，序列 $v$ 将会回到初始状态，即所有元素的值全都变为 $1$。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示序列 $v$ 的长度。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示第一种操作的代价。

第三行包含 $n$ 个非负整数 $b_1,b_2,\ldots,b_n$，表示第二种操作的代价。

第四行包含 $n$ 个非负整数 $c_1,c_2,\ldots,c_n$，表示第三种操作的代价。

第五行包含一个正整数 $q$，表示询问次数。

接下来的 $q$ 行中，第 $i$ 行包含以下内容：

• 开头一个非负整数 $m$，表示第 $i$ 次询问中集合 $P$ 的大小；
• 接下来有 $m$ 个正整数 $p_1,p_2,\ldots,p_m$，依次表示集合 $P$ 中每个元素的值，保证对于任意 $1\le i<m$，都有 $p_i<p_{i+1}$。

输出格式

输出到标准输出。

输出共 $q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 次询问中操作总代价的最小值。

5
1 13 6 0 6
2 4 1 0 5
3 4 1 2 1
7
1 4
2 1 5
1 4
2 2 3
5 1 2 3 4 5
1 5
2 3 4

7
3
7
6
0
0
8

7
10 1 6 9 4 2 4 
0 5 2 3 0 1 4 
4 1 4 1 5 3 5 
6
3 1 3 6 
2 2 6 
4 3 4 5 7 
1 4 
2 3 7 
3 3 5 6

12
8
2
5
5
8

10
6 10 7 2 8 4 6 4 8 7
4 0 6 7 8 4 8 2 10 5
4 10 6 1 4 7 5 3 8 7
1
0

7

提示

【样例解释 #1】

对于第一次询问，可以按顺序执行如下操作：

• 在 $i=4$ 处执行操作 $1$，在这之后，序列 $v$ 变为 $[0,0,0,0,1]$，代价为 $0$；
• 在 $i=4$ 处执行操作 $3$，在这之后，序列 $v$ 变为 $[0,0,0,1,1]$，代价为 $2$；
• 在 $i=5$ 处执行操作 $2$，在这之后，序列 $v$ 变为 $[0,0,0,1,0]$，代价为 $5$。

所以总代价为 $0+2+5=7$，可以证明，不存在更小的总代价。

【样例解释 #3】

对于这个样例中的唯一一次询问，可以选择在 $i=10$ 处执行操作 $1$，总代价为 $a_{10}=7$。

【样例 #4】

见选手目录下的 reserve/reserve4.in 与 reserve/reserve4.ans。

【样例 #5】

见选手目录下的 reserve/reserve5.in 与 reserve/reserve5.ans。

这个样例满足测试点 $8\sim 11$ 的条件限制。

【样例 #6】

见选手目录下的 reserve/reserve6.in 与 reserve/reserve6.ans。

这个样例满足测试点 $14\sim 15$ 的条件限制。

【样例 #7】

见选手目录下的 reserve/reserve7.in 与 reserve/reserve7.ans。

这个样例满足测试点 $16$ 的条件限制。

【样例 #8】

见选手目录下的 reserve/reserve8.in 与 reserve/reserve8.ans。

这个样例满足测试点 $17\sim 20$ 的条件限制。

---

【数据范围】

记 $\sum m$ 为单测试点内所有询问 $m$ 的值之和。

对于所有数据保证：$1 \leq n \leq 5\times 10^5$，$0\le m \le n$，$0 \leq \sum m \leq 5 \times 10^5$，$1\le q\le \max(n,\sum m)$，$0 \le a_i, b_i, c_i \le 10^9$，$1\le p_i \le n$。

测试点编号	$n \le$	$m \le$	$\sum m \le$	是否有特殊性质
$1 \sim 2$	$5 \times 10^5$	$0$		否
$3 \sim 4$	$7$		$15$
$5 \sim 6$	$2 \times 10^3$	$1$	$2 \times 10^3$
$7$		$2 \times 10^3$		是
$8 \sim 11$		$2\times 10^3$		否
$12 \sim 13$	$5 \times 10^4$
$14 \sim 15$	$5 \times 10^5$	$1$	$5 \times 10^5$
$16$		$5 \times 10^5$		是
$17 \sim 20$				否

特殊性质：对于任意 $1\le i\le n$，保证 $c_i = 0$。

【提示】

本题输入输出量较大，请使用适当的 I/O 方式。