CF2173B.Niko's Tactical Cards

Niko is playing a game. Her score is denoted by an integer $k$ which is $0$ initially.

The game has $n$ turns. On the $i$-th turn, Niko is given a red card with an integer $a_i$ on it, as well as a blue card with an integer $b_i$ on it. She must choose exactly one of the cards and update her score according to her choice:

• If she chooses the red card, her score becomes $k - a_i$, where $k$ is her score before the turn.
• If she chooses the blue card, her score becomes $b_i - k$, where $k$ is her score before the turn.

After this, the game proceeds to the next turn, or ends if it is the $n$-th turn.

Your task is to find the maximum possible score Niko can obtain at the end of the game.

尼可正在玩一个游戏。她的得分用一个整数 $k$ 表示，初始值为 $0$。

游戏共进行 $n$ 轮。在第 $i$ 轮中，尼可会收到一张红色卡片，上面印有一个整数 $a_i$；同时还会收到一张蓝色卡片，上面印有一个整数 $b_i$。她必须恰好选择其中一张卡片，并根据所选卡片更新自己的得分：

• 若她选择红色卡片，则她的得分变为 $k - a_i$，其中 $k$ 是本轮开始前的得分；
• 若她选择蓝色卡片，则她的得分变为 $b_i - k$，其中 $k$ 是本轮开始前的得分。

随后游戏进入下一轮，若当前已是第 $n$ 轮，则游戏结束。

你的任务是求出尼可在游戏结束时所能获得的最高可能得分。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of turns.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示回合数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \le b_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single integer — the maximum possible score Niko can obtain at the end of the game.

对于每个测试用例，输出一个整数——Niko 在游戏结束时所能获得的最高分数。

In the first test case, one optimal strategy is as follows:

Turn

0

1

2

3

Card Chosen

—

Blue

Red

Red

Score

$0$

$-3 - 0 = -3$

$-3 - (-8) = 5$

$5 - (-1) = 6$

In the second test case, one optimal strategy is as follows:

Turn

0

1

2

3

4

5

Card Chosen

—

Blue

Blue

Blue

Blue

Red

Score

$0$

$-5$

$8$

$-9$

$13$

$12$

在第一个测试用例中，一种最优策略如下所示：

轮次

0

1

2

3

所选卡片

—

蓝色

红色

红色

得分

$0$

$-3 - 0 = -3$

$-3 - (-8) = 5$

$5 - (-1) = 6$

在第二个测试用例中，一种最优策略如下所示：

轮次

0

1

2

3

4

5

所选卡片

—

蓝色

蓝色

蓝色

蓝色

红色

得分

$0$

$-5$

$8$

$-9$

$13$

$12$