题目描述

最近，Polycarp 完成了 $n$ 个连续的任务。

对于每个已完成的任务，已知任务被分配的时间 $s_i$（没有两个任务在同一时刻被分配）。还给出了任务完成的时间 $f_i$。对于每个任务，有一个未知值 $d_i$（$d_i>0$），表示任务的执行时长。

已知任务按照它们到达的顺序被完成。Polycarp 执行任务的方式如下：

• 一旦第一个任务到来，Polycarp 立即开始执行它。
• 如果在 Polycarp 尚未完成前一个任务时有新任务到来，他会把新任务放到队列的末尾。
• 当 Polycarp 完成当前任务且队列不为空时，他会立即从队列头部取出下一个任务继续执行（如果队列为空，他就等待下一个任务到来）。

请你求出每个任务的 $d_i$（即每个任务的执行时长）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来是每个测试用例的数据描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个正整数 $s_1 < s_2 < \dots < s_n$（$0 \le s_i \le 10^9$），表示每个任务被分配的时间。

每个测试用例的第三行包含 $n$ 个正整数 $f_1 < f_2 < \dots < f_n$（$s_i < f_i \le 10^9$），表示每个任务完成的时间。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 $n$ 个正整数 $d_1, d_2, \dots, d_n$，表示每个任务的执行时长。

说明/提示

第一个测试用例：

一开始队列为空：$[\,]$。此时第一个任务到来。Polycarp 在时间 $2$ 完成第一个任务，因此第一个任务的执行时长为 $2$。队列为空，Polycarp 继续等待。

在时间 $3$，第二个任务到来。在时间 $7$，第三个任务到来，此时队列为 $[7]$。

在时间 $10$，Polycarp 完成第二个任务，因此第二个任务的执行时长为 $7$。

在时间 $10$，Polycarp 立即开始第三个任务，并在时间 $11$ 完成。因此第三个任务的执行时长为 $1$。

这是第一个测试用例的示意图。

由 ChatGPT 4.1 翻译

样例

4
3
0 3 7
2 10 11
2
10 15
11 16
9
12 16 90 195 1456 1569 3001 5237 19275
13 199 200 260 9100 10000 10914 91066 5735533
1
0
1000000000

2 7 1 
1 1 
1 183 1 60 7644 900 914 80152 5644467 
1000000000