두 정수 수열 $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$는 모든 $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, 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$입니다.