题目描述

两个多重集被称为几乎必然相等，当且仅当修改其中一个多重集中至多一个元素后，两个多重集完全相等。

Vasya 有两个数组$a$和$b$，满足$b_i \leq a_i$（$1 \leq i \leq n$）。Vasya 可以对数组$a$执行任意次操作：选择下标$i$（$1 \leq i \leq n$），将$a_i$减$1$（$b$数组始终不变）。

对于每个前缀长度$k$（$1 \leq k \leq n$），需要求出将$a[1..k]$和$b[1..k]$的多重集变为几乎必然相等所需的最少操作次数（每个$k$的求解相互独立）。

输入格式

1. 第一行输入$t$（$1 \leq t \leq 100000$），表示测试用例数。
2. 每个测试用例：
   • 第一行输入$n$（$1 \leq n \leq 200000$），表示数组长度。
   • 第二行输入$n$个整数$a_1,a_2,...,a_n$（$1 \leq a_i \leq 10^9$）。
   • 第三行输入$n$个整数$b_1,b_2,...,b_n$（$1 \leq b_i \leq a_i$）。
3. 保证所有测试用例的$n$之和$N \leq 200000$。

输出格式

对于每个测试用例，输出$n$个整数，依次表示前缀长度$1$到$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 205

0 1
0 0
0 4 2
0 10 3048

3
4
2 4 512
1 3 410
4
3 5 820
1 2 67
4
4 4 44
1 2 34

0 1 13
0 1 36
0 2 33

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。