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

My submissions

Announcements

9C. Weird Swaps

Constraints

Input

Output

Samples

9C. Weird Swaps

Constraints

Input

Output

Samples