2 つの整数列 $A = (A_1, \dots, A_N)$, $B = (B_1, \dots, B_N)$ と、2 つの正整数列 $V = (V_1, \dots, V_N)$, $W = (W_1, \dots, W_N)$ が与えられます。4 つの数列の長さはすべて $N$ です。

添字の（空であってもよい）区間を 2 つ、すなわち $[L, R)$（$A$ に対応）と $[U, D)$（$B$ に対応）を選びます。ここで、$L, R, U, D$ は $1 \le L \le R \le N + 1$ および $1 \le U \le D \le N + 1$ を満たす整数です。

それぞれの区間に現れる値の集合を $X$, $Y$ とします：

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

選ぶ区間は $X \cap Y = \emptyset$ を満たさなければなりません。言い換えると、同じ値が両方の区間に現れてはなりません。

$L = R$ のとき、$A$ の区間は空であり $X = \emptyset$ です。同様に、$U = D$ のとき、$B$ の区間は空であり $Y = \emptyset$ です。

選んだ 2 つの区間のスコアは

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

条件を満たす選び方のうち、スコアの最大値を求めてください。

入力

入力は 1 つ以上のテストケースからなります。入力の 1 行目にはテストケースの個数を表す整数 $T$ ($1 \le T \le 10^4$) が与えられます。続いて $T$ 個のテストケースがそれぞれ以下の形式で与えられます。

$$ \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} $$

1 行目には、4 つの数列の共通の長さである単一の整数 $N$ ($1 \le N \le 2 \times 10^5$) が与えられます。

続く 4 行にはそれぞれ $N$ 個の整数が与えられ、順に数列 $A$, $B$, $V$, $W$ を表します。

整数 $A_i$, $B_i$ はすべての $i$ ($1 \le i \le N$) について $1 \le A_i, B_i \le N$ を満たします。

整数 $V_i$, $W_i$ はすべての $i$ ($1 \le i \le N$) について $1 \le V_i, W_i \le 10^9$ を満たします。

すべてのテストケースにおける $N$ の総和は $6 \times 10^5$ を超えません。

出力

$T$ 行出力してください。$i$ 行目には、$i$ 番目のテストケースにおけるスコアの最大値を出力してください。

入出力例

入力 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

出力 1

13
15
33
11

注記

1 番目のテストケースでは、区間 $[1, 3)$（$A$ の区間）と区間 $[1, 2)$（$B$ の区間）を選ぶことができます。より正確には、$L = 1$, $R = 3$, $U = 1$, $D = 2$ と設定できます。それぞれの値の集合は $\{1, 2\}$ と $\{3\}$ であり、互いに素です。スコアは

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

となり、これが可能な最大スコアです。

2 番目のテストケースでは、$A$ の空区間と、区間全体 $[1, 4)$（$B$ の区間）を選ぶことができます。より正確には、$L = 2$, $R = 2$, $U = 1$, $D = 4$ です。