[Solution] Restoring the Duration of Tasks Codeforces Solution

[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$n$ successive tasks.

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

It is known that the tasks were completed in the order in 

Solution Click Below:-  CLICK HERE

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 di$d_i$ (duration) of each task.

Input

The first line contains a single integer t$t$ (1≤t≤104$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$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$).

The second line of each test case contains exactly n$n$ integers s1<s2<⋯<sn$s_1<s_2<\cdots <s_n$ (0≤si≤109$0\le s_i\le {10}^9$).

Restoring the Duration of Tasks Codeforces Solution

The third line of each test case contains exactly n$n$ integers f1<f2<⋯<fn$f_1<f_2<\cdots <f_n$ (si<fi≤109$s_i<f_i\le {10}^9$).

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

Output

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