Problem Description

Xiao M has a sequence of length $n$, $v_1, v_2, \ldots, v_n$, where initially all elements are $1$.

You have three operations that can be applied to this sequence:

1. Choose an index $i$ ($1 \le i \le n$) and set $v_1, v_2, \ldots, v_i$ to $0$. The cost of this operation is $a_i$.
2. Choose an index $i$ ($1 \le i \le n$) and set $v_i$ to $0$. The cost of this operation is $b_i$.
3. Choose an index $i$ ($1 \le i \le n$) and set $v_i$ to $1$. The cost of this operation is $c_i$.

There are $q$ queries. Each query specifies a set $P$, and you want to perform a number of operations (possibly $0$) such that: the elements of sequence $v$ with indices in $P$ are $1$, and all other elements are $0$. Formally, for any $1 \le i \le n$, if $i \in P$, then $v_i = 1$, otherwise $v_i = 0$. You need to minimize the total cost of operations for each query.

Note that queries are independent, meaning that after each query, the sequence $v$ returns to its initial state, where all elements are $1$.

Input Format

Input is read from standard input.

The first line contains a positive integer $n$, the length of the sequence $v$.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, the costs of the first operation.

The third line contains $n$ non-negative integers $b_1, b_2, \ldots, b_n$, the costs of the second operation.

The fourth line contains $n$ non-negative integers $c_1, c_2, \ldots, c_n$, the costs of the third operation.

The fifth line contains a positive integer $q$, the number of queries.

The next $q$ lines, each contains:

• A non-negative integer $m$, the size of the set $P$ for the $i$-th query;
• Followed by $m$ positive integers $p_1, p_2, \ldots, p_m$, the elements of set $P$ in ascending order.

Output Format

Output is written to standard output.

Output $q$ lines, each containing a non-negative integer, the minimum total cost of operations for the $i$-th query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

7
3
7
6
0
0
8

Input Sample #2

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

Output Sample #2

12
8
2
5
5
8

Input Sample #3

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

Output Sample #3

7

Notes/Hints

[Sample Explanation #1]

For the first query, the following operations can be performed in order:

• Perform operation 1 at $i=4$, making the sequence $v$ become $[0,0,0,0,1]$, with a cost of $0$;
• Perform operation 3 at $i=4$, making the sequence $v$ become $[0,0,0,1,1]$, with a cost of $2$;
• Perform operation 2 at $i=5$, making the sequence $v$ become $[0,0,0,1,0]$, with a cost of $5$.

Thus, the total cost is $0 + 2 + 5 = 7$. It can be proven that no smaller total cost exists.

[Sample Explanation #3]

For this sample's only query, you can choose to perform operation 1 at $i=10$, with a total cost of $a_{10} = 7$.

[Data Range]

Let $\sum m$ be the sum of all $m$ values in a single test point.

For all data, it is guaranteed that: $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$.

Special Properties: For any $1 \le i \le n$, $c_i = 0$ is guaranteed.

[Hint]

The input and output for this problem are large, please use appropriate I/O methods.

见题面 Input 部分

见题面 Output 部分