Даны две последовательности целых чисел $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$.