## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Restoring the Duration of Tasks Codeforces Solution

C. Restoring the Duration of Tasks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}>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.

Input

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}<{s}_{2}<\cdots <{s}_{n}$ ($0\le {s}_{i}\le {10}^{9}$).

The third line of each test case contains exactly $n$ integers ${f}_{1}<{f}_{2}<\cdots <{f}_{n}$ (${s}_{i}<{f}_{i}\le {10}^{9}$).

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

Output

For each of $t$ test cases print $n$ positive integers ${d}_{1},{d}_{2},\dots ,{d}_{n}$ — the duration of each task.