给定两个整数序列 $A = (A_1, \dots, A_N)$ 和 $B = (B_1, \dots, B_N)$，以及两个正整数序列 $V = (V_1, \dots, V_N)$ 和 $W = (W_1, \dots, W_N)$。这四个序列的长度均为 $N$。

请为下标选择两个（可能为空的）区间：$[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$。

所选两个区间的得分为

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

请在所有合法的选择方案中，求出可能的最大得分。

输入格式

输入包含一个或多个测试用例。输入的第一行包含一个整数 $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} $$

第一行包含一个整数 $N$，表示四个序列的共同长度（$1 \le N \le 2 \times 10^5$）。

接下来的四行每行包含 $N$ 个整数，分别描述序列 $A$、$B$、$V$ 和 $W$。

整数 $A_i$ 和 $B_i$ 满足 $1 \le A_i, B_i \le N$（对于每个 $i$，$1 \le i \le N$）。

整数 $V_i$ 和 $W_i$ 满足 $1 \le V_i, W_i \le 10^9$（对于每个 $i$，$1 \le i \le N$）。

所有测试用例中 $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, 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, $$

这是可能达到的最大得分。

在第二个测试用例中，我们可以为 $A$ 选择一个空区间，并为 $[1, 4)$（对应 $B$）选择整个序列区间。更确切地说，令 $L = 2$、$R = 2$、$U = 1$ 和 $D = 4$。