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