Weird Swaps - Repovive Premier Round 4 | Repovive

9C. Weird Swaps

1500 pts1s256 MB

You are given two arrays $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ .

In each operation you can choose two numbers $l$ and $r$ such that:

$1 \leq l < r \leq n$
$r - l + 1$ is even

Then for every $l \leq i \leq r$ , swap $a_i$ with $b_{l + r - i}$ .

Find the maximum sum of array $a$ after any number of operations (including zero).

Constraints

$1 \leq t \leq 10^4$
$1 \leq n \leq 2 \times 10^5$
$0 \leq a_i, b_i \leq 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3
1 1 1
2 2 2

Case 2

5
5 1 2 2 4
1 9 3 3 4

Case 3

4
3 9 9 0
2 0 4 2

Case 4

4
9 3 9 0
0 2 4 2

Explanation

Case 1

An operation on segment $[1, 2]$ will swap $a_1 \leftrightarrow b_2$ and $a_2 \leftrightarrow b_1$ , resulting in $a = [2, 2, 1]$ with sum equal to 5.

Case 2

An operation on segment $[2, 5]$ will swap $a_2 \leftrightarrow b_5, a_3 \leftrightarrow b_4, a_4 \leftrightarrow b_3$ and $a_5 \leftrightarrow b_2$ , resulting in $a = [5, 4, 3, 3, 9]$ with sum equal to 24.

Case 3

One operation on segment $[1, 4]$ will result in $a = [2, 4, 0, 2], b = [0, 9, 9, 3]$ . Another operation on segment $[2, 3]$ will result in $a = [2, 9, 9, 2]$ with sum equal to 22.

Case 4

No operation needed.

Output

Case 1

Case 2

Case 3

Case 4

You are given two arrays $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ .

In each operation you can choose two numbers $l$ and $r$ such that:

$1 \leq l < r \leq n$
$r - l + 1$ is even

Then for every $l \leq i \leq r$ , swap $a_i$ with $b_{l + r - i}$ .

Find the maximum sum of array $a$ after any number of operations (including zero).

$1 \leq t \leq 10^4$
$1 \leq n \leq 2 \times 10^5$
$0 \leq a_i, b_i \leq 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

An operation on segment $[1, 2]$ will swap $a_1 \leftrightarrow b_2$ and $a_2 \leftrightarrow b_1$ , resulting in $a = [2, 2, 1]$ with sum equal to 5.

One operation on segment $[1, 4]$ will result in $a = [2, 4, 0, 2], b = [0, 9, 9, 3]$ . Another operation on segment $[2, 3]$ will result in $a = [2, 9, 9, 2]$ with sum equal to 22.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9C. Weird Swaps

Constraints

Input

Output

Samples

9C. Weird Swaps

Constraints

Input

Output

Samples