如果两个多重集最多只有一个元素不同，我们就称它们几乎确定相等（equal almost certainly）。也就是说，可以通过修改第一个多重集中的至多一个元素，使它们变得相等。例如，多重集 $\{1, 1, 2\}$ 和 $\{1, 2, 3\}$ 是几乎确定相等的，$\{1, 1, 1\}$ 和 $\{1, 1, 1\}$ 是几乎确定相等的，而 $\{1, 2, 3\}$ 和 $\{3, 4, 5\}$ 不是几乎确定相等的。

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

Vasya 有两个数组 $a$ 和 $b$，其中对于所有从 $1$ 到 $n$ 的 $i$，都有 $a_i \ge b_i$。Vasya 可以对数组 $a$ 进行任意次（可能为零次）如下操作：选择任意索引 $i$（$1 \le i \le n$）并将 $a_i$ 减去 $1$。与此同时，Vasya 不能改变数组 $b$。

Vasya 很快就明白了需要进行怎样的操作序列才能使数组 $a$ 和 $b$ 的元素组成的多重集几乎确定相等。因此，Vasya 把任务变得更复杂了——现在对于这些数组的每个前缀，他想知道使这些数组的前缀几乎确定相等所需的最小操作次数。

更正式地，对于每个从 $1$ 到 $n$ 的 $k$，Vasya 想要取出元素 $a_1, a_2, \dots, a_k$ 以及元素 $b_1, b_2, \dots, b_k$。Vasya 想知道使这些元素组成的多重集几乎确定相等所需的最小操作次数。注意，对于每个 $k$ 的任务是独立求解的。

输入格式

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

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 200\,000$）——数组 $a$ 和 $b$ 的大小。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的元素。

每组测试数据的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le a_i$）——数组 $b$ 的元素。

设 $N$ 为单个测试点中所有测试数据组的 $n$ 之和。保证 $N \le 200\,000$。

输出格式

对于每组测试数据，输出 $n$ 个整数，每个整数对应每个可能的前缀长度的答案。可以证明，答案总是存在的。

样例

输入样例 1

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

输出样例 1

0 1
0 0
0 4 2
0 10 30 48

输入样例 2

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

输出样例 2

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, 11]$，它们将几乎确定相等。

子任务

本题的测试点由六个子任务组成。只有当通过该子任务的所有测试点以及所有依赖子任务的测试点时，才能获得该子任务的分数。请注意，某些子任务不需要通过样例测试。离线评测（Offline-evaluation）意味着该子任务的评测结果仅在比赛结束后公布。

可以证明，第四组的所有测试点都满足第五组的限制。