2334: Restoring the Duration of Tasks
Description
Recently, Polycarp completed nn successive tasks.
For each completed task, the time sisi is known when it was given, no two tasks were given at the same time. Also given is the time fifi when the task was completed. For each task, there is an unknown value didi (di>0di>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 didi (duration) of each task.
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The desc
The first line of each test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105).
The second line of each test case contains exactly nn integers s1<s2<⋯<sns1<s2<⋯<sn (0≤si≤1090≤si≤109).
The third line of each test case contains exactly nn integers f1<f2<⋯<fnf1<f2<⋯<fn (si<fi≤109si<fi≤109).
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
For each of tt test cases print nn positive integers d1,d2,…,dnd1,d2,…,dn — the duration of each task.
Sample Input Copy
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
Sample Output Copy
2 7 1
1 1
1 183 1 60 7644 900 914 80152 5644467
1000000000
HINT
First test case:
The queue is empty at the beginning: [][]. And that's where the first task comes in. At time 22, Polycarp finishes doing the first task, so the duration of the first task is 22. The queue is empty so Polycarp is just waiting.
At time 33, the second task arrives. And at time 77, the third task arrives, and now the queue looks like this: [7][7].
At the time 1010, Polycarp finishes doing the second task, as a result, the duration of the second task is 77.
And at time 1010, Polycarp immediately starts doing the third task and finishes at time 1111. As a result, the duration of the third task is 11.
