题目描述

我们称两个多重集几乎等价，如果它们至多有一个元素不同。也就是说，可以通过将第一个多重集中的至多一个元素修改为其他值，使得两个多重集完全相同。例如，多重集 $\{1, 1, 2\}$ 与 $\{1, 2, 3\}$ 是几乎等价的，$\{1, 1, 1\}$ 与 $\{1, 1, 1\}$ 也是几乎等价的，而 $\{1, 2, 3\}$ 与 $\{3, 4, 5\}$ 则不是几乎等价的。

有一个叫 Vasya 的男孩非常喜欢这个定义，并立刻想出了相关的问题。

Vasya 有两个数组 $a$ 和 $b$，且对于所有 $i$，都有 $a_i \geq b_i$。Vasya 可以对数组 $a$ 进行如下操作若干次（可以为零次）：选择任意一个下标 $i$（$1 \leq i \leq n$），并将 $a_i$ 减 $1$。数组 $b$ 不发生任何变化。

Vasya 很快就明白了如何通过一系列操作，使得数组 $a$ 和 $b$ 的值组成的多重集几乎等价。于是他将问题升级——现在，他想知道对于这两个数组的每一个前缀，最少需要多少次操作，才能使这两个前缀的多重集几乎等价。

更具体地说，对于每个 $k$，$1 \leq k \leq n$，Vasya 需要考虑 $a_1, a_2, \ldots, a_k$ 以及 $b_1, b_2, \ldots, b_k$ 这两个前缀，并求出最少需要多少次操作，才能使这两个前缀的多重集几乎等价。注意，每个 $k$ 的问题是独立解决的。

输入格式

每组测试包含一个或多个数据集。第一行是一个整数 $t$（$1 \leq t \leq 100\,000$），表示数据集数量。接下来是每组数据集的描述。

每组数据集的第一行是一个整数 $n$（$1 \leq n \leq 200\,000$），表示数组 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq a_i$），表示数组 $b$ 的元素。

设 $N$ 为所有数据集中 $n$ 的总和，保证 $N \leq 200\,000$。

输出格式

对于每组数据集，输出 $n$ 个整数，分别表示每个前缀的答案。可以证明答案总是存在。

4
2
3 4
1 2
2
3 4
1 3
3
11 17 14
1 13 10
4
100 11 50 42
30 1 20 5

0 1
0 0
0 4 2
0 10 30 48

3
4
2 4 5 12
1 3 4 10
4
3 5 8 20
1 2 6 7
4
4 4 4 4
1 2 3 4

0 1 1 3
0 1 3 6
0 2 3 3

提示

说明

以第一个输入样例的第一组数据为例：

• 对于长度为 $1$ 的前缀，无需任何操作。
• 对于长度为 $2$ 的前缀，需要将 $a_1 = 3$ 减 $1$，此时 $a = [2, 4]$，$b = [1, 2]$，两者几乎等价。

再看第一个输入样例的第三组数据：

• 长度为 $1$ 的前缀，无需任何操作。
• 长度为 $2$ 的前缀，需要将 $a_2 = 17$ 减 $4$，此时 $a = [11, 13]$，$b = [1, 13]$，两者几乎等价。
• 长度为 $3$ 的前缀，需要将 $a_1 = 11$ 减 $1$，$a_3 = 14$ 减 $1$，此时 $a = [10, 17, 13]$，$b = [1, 13, 10]$，两者几乎等价。

计分方式

本题共六组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。Offline-evaluation 表示该组结果仅在赛后可见。

翻译由 ChatGPT-4.1 完成。