أُعطيت متتاليتين من الأعداد الصحيحة $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$.