Dane są dwa ciągi liczb całkowitych $A = (A_1, \dots, A_N)$ i $B = (B_1, \dots, B_N)$ oraz dwa ciągi dodatnich liczb całkowitych $V = (V_1, \dots, V_N)$ i $W = (W_1, \dots, W_N)$. Wszystkie cztery ciągi mają długość $N$.

Wybierz dwa (być może puste) przedziały indeksów: $[L, R)$ dla ciągu $A$ oraz $[U, D)$ dla ciągu $B$. Tutaj $L, R, U, D$ są liczbami całkowitymi spełniającymi $1 \le L \le R \le N + 1$ oraz $1 \le U \le D \le N + 1$.

Niech $X$ oraz $Y$ oznaczają zbiory wartości występujących odpowiednio w tych przedziałach:

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

Wybrane przedziały muszą spełniać warunek $X \cap Y = \emptyset$. Innymi słowy, żadna wartość nie może wystąpić w obu przedziałach jednocześnie.

Jeśli $L = R$, przedział dla $A$ jest pusty i $X = \emptyset$. Podobnie, jeśli $U = D$, przedział dla $B$ jest pusty i $Y = \emptyset$.

Wynik dwóch wybranych przedziałów wynosi

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

Znajdź maksymalny możliwy wynik spośród wszystkich poprawnych wyborów.

Wejście

Wejście zawiera jeden lub więcej przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Następnie podane są opisy $T$ przypadków testowych, każdy w poniższym formacie.

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

Pierwszy wiersz zawiera jedną liczbę całkowitą $N$ — wspólną długość czterech ciągów ($1 \le N \le 2 \times 10^5$).

Kolejne cztery wiersze zawierają po $N$ liczb całkowitych i opisują odpowiednio ciągi $A$, $B$, $V$ oraz $W$.

Liczby całkowite $A_i$ i $B_i$ spełniają $1 \le A_i, B_i \le N$ dla każdego $i$ ($1 \le i \le N$).

Liczby całkowite $V_i$ i $W_i$ spełniają $1 \le V_i, W_i \le 10^9$ dla każdego $i$ ($1 \le i \le N$).

Suma wartości $N$ po wszystkich przypadkach testowych nie przekracza $6 \times 10^5$.

Wyjście

Wypisz $T$ wierszy. W $i$-tym wierszu powinien znaleźć się maksymalny możliwy wynik dla $i$-tego przypadku testowego.

Przykład

Wejście 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

Wyjście 1

13
15
33
11

Uwagi

W pierwszym przypadku testowym możemy wybrać przedział $[1, 3)$ ciągu $A$ oraz przedział $[1, 2)$ ciągu $B$. Dokładniej, możemy przyjąć $L = 1$, $R = 3$, $U = 1$ oraz $D = 2$. Ich zbiory wartości to odpowiednio $\{1, 2\}$ oraz $\{3\}$ i są one rozłączne. Wynik wynosi

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

co jest maksymalnym możliwym wynikiem.

W drugim przypadku testowym możemy wybrać pusty przedział ciągu $A$ oraz cały przedział $[1, 4)$ ciągu $B$. Dokładniej: $L = 2$, $R = 2$, $U = 1$ oraz $D = 4$.