You are given two integer sequences $A = (A_1, \dots, A_N)$ and $B = (B_1, \dots, B_N)$, and two sequences of positive integers $V = (V_1, \dots, V_N)$ and $W = (W_1, \dots, W_N)$. All four sequences have length $N$.

Choose two (possibly empty) intervals of indices, $[L, R)$ for $A$ and $[U, D)$ for $B$. Here, $L, R, U, D$ are integers satisfying $1 \le L \le R \le N + 1$ and $1 \le U \le D \le N + 1$.

Let $X$ and $Y$ be the sets of values occurring in these intervals, respectively:

$$ \begin{aligned} X &= \{A_i \mid L \le i < R\}, \\ Y &= \{B_j \mid U \le j < D\}. \end{aligned} $$

The chosen intervals must satisfy $X \cap Y = \emptyset$. In other words, no value may occur in both intervals.

If $L = R$, the interval of $A$ is empty and $X = \emptyset$. Likewise, if $U = D$, the interval of $B$ is empty and $Y = \emptyset$.

The score of the two chosen intervals is

$$ \sum_{i=L}^{R-1} V_i + \sum_{j=U}^{D-1} W_j. $$

Find the maximum possible score among all valid choices.

Input

The input contains one or more test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$), which is the number of test cases. The descriptions of the $T$ test cases follow, each in the format below.

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \\ &V_1 \ V_2 \ \dots \ V_N \\ &W_1 \ W_2 \ \dots \ W_N \end{aligned} $$

The first line contains a single integer $N$, the common length of the four sequences ($1 \le N \le 2 \times 10^5$).

The following four lines contain $N$ integers each and describe the sequences $A$, $B$, $V$, and $W$, respectively.

The integers $A_i$ and $B_i$ satisfy $1 \le A_i, B_i \le N$ for every $i$ ($1 \le i \le N$).

The integers $V_i$ and $W_i$ satisfy $1 \le V_i, W_i \le 10^9$ for every $i$ ($1 \le i \le N$).

The sum of $N$ over all test cases does not exceed $6 \times 10^5$.

Output

Output $T$ lines. The $i$-th line should contain the maximum possible score for the $i$-th test case.

Example

Input 1

4
3
1 2 3
3 2 1
3 4 5
6 2 1
3
1 1 1
1 1 1
2 3 4
5 5 5
4
1 2 1 3
4 2 4 3
5 6 5 1
4 10 4 10
5
3 1 2 4 3
1 1 2 2 4
1 3 3 2 1
2 2 3 1 1

Output 1

13
15
33
11

Note

In the first test case, we can choose the interval $[1, 3)$ of $A$ and the interval $[1, 2)$ of $B$. More precisely, we can set $L = 1$, $R = 3$, $U = 1$, and $D = 2$. Their sets of values are $\{1, 2\}$ and $\{3\}$, respectively, and they are disjoint. The score is

$$ V_1 + V_2 + W_1 = 3 + 4 + 6 = 13, $$

which is the maximum possible score.

In the second test case, we can choose an empty interval of $A$ and the entire interval $[1, 4)$ of $B$. More precisely, $L = 2$, $R = 2$, $U = 1$, and $D = 4$.