CF1690C.Restoring the Duration of Tasks

Recently, Polycarp completed $n$ successive tasks.

For each completed task, the time $s_i$ is known when it was given, no two tasks were given at the same time. Also given is the time $f_i$ when the task was completed. For each task, there is an unknown value $d_i$ ($d_i \gt 0$) — duration of task execution.

It is known that the tasks were completed in the order in which they came. Polycarp performed the tasks as follows:

• As soon as the very first task came, Polycarp immediately began to carry it out.
• If a new task arrived before Polycarp finished the previous one, he put the new task at the end of the queue.
• When Polycarp finished executing the next task and the queue was not empty, he immediately took a new task from the head of the queue (if the queue is empty — he just waited for the next task).

Find $d_i$ (duration) of each task.

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

对于每个已完成的任务，已知其被分配的时间 $s_i$，且任意两个任务的分配时间均不相同。同时，还已知该任务完成的时间 $f_i$。对每个任务，存在一个未知值 $d_i$（$d_i \gt 0$）——即该任务的实际执行时长。

已知这些任务是按照它们被分配的顺序依次完成的。Polycarp 执行任务的方式如下：

• 一旦第一个任务被分配，Polycarp 立即开始执行它；
• 若在 Polycarp 完成上一个任务之前有新任务到达，则他将该新任务加入队列尾部；
• 当 Polycarp 完成当前任务后，若队列非空，则他立即从队列头部取出下一个任务开始执行（若队列为空，则他等待下一个任务到达）。

请计算每个任务的执行时长 $d_i$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The descriptions of the input data sets follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains exactly $n$ integers $s_1 \lt s_2 \lt \dots \lt s_n$ ($0 \le s_i \le 10^9$).

The third line of each test case contains exactly $n$ integers $f_1 \lt f_2 \lt \dots \lt f_n$ ($s_i \lt f_i \le 10^9$).

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

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

随后是各测试用例的输入数据描述。

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

每个测试用例的第二行包含恰好 $n$ 个整数 $s_1 \lt s_2 \lt \dots \lt s_n$（$0 \le s_i \le 10^9$）。

每个测试用例的第三行包含恰好 $n$ 个整数 $f_1 \lt f_2 \lt \dots \lt f_n$（$s_i \lt f_i \le 10^9$）。

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

For each of $t$ test cases print $n$ positive integers $d_1, d_2, \dots, d_n$ — the duration of each task.

对于每个测试用例，输出 $n$ 个正整数 $d_1, d_2, \dots, d_n$ —— 即每个任务的持续时间。

First test case:

The queue is empty at the beginning: $[ ]$. And that's where the first task comes in. At time $2$, Polycarp finishes doing the first task, so the duration of the first task is $2$. The queue is empty so Polycarp is just waiting.

At time $3$, the second task arrives. And at time $7$, the third task arrives, and now the queue looks like this: $[7]$.

At the time $10$, Polycarp finishes doing the second task, as a result, the duration of the second task is $7$.

And at time $10$, Polycarp immediately starts doing the third task and finishes at time $11$. As a result, the duration of the third task is $1$.

An example of the first test case.

第一个测试用例：

队列初始为空：$[ ]$。此时第一个任务到达。在时刻 $2$，Polycarp 完成第一个任务，因此第一个任务的持续时间为 $2$。此时队列为空，Polycarp 处于等待状态。

在时刻 $3$，第二个任务到达；在时刻 $7$，第三个任务到达，此时队列状态为：$[7]$。

在时刻 $10$，Polycarp 完成第二个任务，因此第二个任务的持续时间为 $7$。

在时刻 $10$，Polycarp 立即开始处理第三个任务，并于时刻 $11$ 完成。因此第三个任务的持续时间为 $1$。

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