Problem Description

Little M has a sequence $v_1, v_2, \ldots, v_n$ of length $n$. Initially, all elements are $1$.

You have $3$ types of operations on this sequence:

1. Choose an index $i$ ($1 \le i \le n$), and set $v_1, v_2, \ldots, v_i$ all 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$.

Now there are $q$ queries. In each query, you are given a set $P$. You want to perform some operations (possibly $0$ operations) so that: the elements whose indices belong to this set have value $1$, and all other positions have value $0$. Formally, for any $\bm{1 \le i \le n}$, if $\bm{i \in P}$ then $\bm{v_i = 1}$, otherwise $\bm{v_i = 0}$. You also need to minimize the total cost of all operations in this query.

Note that the queries are independent. That is, after each query ends, the sequence $v$ returns to the initial state, where all elements become $1$ again.

Input Format

Read input from standard input.

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

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

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

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

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

In the following $q$ lines, the $i$-th line contains:

• A leading non-negative integer $m$, denoting the size of set $P$ in the $i$-th query.
• Then $m$ positive integers $p_1, p_2, \ldots, p_m$, in order, denoting each element in set $P$. It is guaranteed that for any $1 \le i < m$, $p_i < p_{i+1}$.

Output Format

Write to standard output.

Output $q$ lines. The $i$-th line contains a non-negative integer, denoting the minimum total cost of operations in the $i$-th query.

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

Hint

[Sample Explanation #1]

For the first query, you can perform the following operations in order:

• Perform operation $1$ at $i = 4$. After that, the sequence $v$ becomes $[0, 0, 0, 0, 1]$, with cost $0$.
• Perform operation $3$ at $i = 4$. After that, the sequence $v$ becomes $[0, 0, 0, 1, 1]$, with cost $2$.
• Perform operation $2$ at $i = 5$. After that, the sequence $v$ becomes $[0, 0, 0, 1, 0]$, with cost $5$.

So the total cost is $0 + 2 + 5 = 7$. It can be proven that there is no smaller total cost.

[Sample Explanation #3]

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

[Sample #4]

See reserve/reserve4.in and reserve/reserve4.ans under the contestant directory.

[Sample #5]

See reserve/reserve5.in and reserve/reserve5.ans under the contestant directory.

This sample satisfies the constraints of test points $8 \sim 11$.

[Sample #6]

See reserve/reserve6.in and reserve/reserve6.ans under the contestant directory.

This sample satisfies the constraints of test points $14 \sim 15$.

[Sample #7]

See reserve/reserve7.in and reserve/reserve7.ans under the contestant directory.

This sample satisfies the constraints of test point $16$.

[Sample #8]

See reserve/reserve8.in and reserve/reserve8.ans under the contestant directory.

This sample satisfies the constraints of test points $17 \sim 20$.

[Constraints]

Let $\sum m$ be the sum of all $m$ over all queries within one test case.

It is guaranteed for all data 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 property: for any $1 \le i \le n$, it is guaranteed that $c_i = 0$.

[Hint]

The input and output sizes of this problem are large, so please use an appropriate I/O method.

Translated by ChatGPT 5