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 < \dots < s_n$ ($0 \le s_i \le 10^9$).

The third line of each test case contains exactly $n$ integers $f_1 < f_2 < \dots < 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.


-----Examples-----

Input
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
Output
2 7 1 
1 1 
1 183 1 60 7644 900 914 80152 5644467 
1000000000


-----Note-----

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.

Source: codeforces | Difficulty: EASY
Tags: Data structures

Implementation

Greedy algorithms


Solutions:
def main():
	for _ in range(int(input())):
		problem()

def problem():
	n = int(input())
	starts = list(map(int, input().split()))
	ends = list(map(int, input().split()))
	durations = []
	time = 0
	for (start, end) in zip(starts, ends):
		if start > time:
			duration = end - start
		else:
			duration = end - time
		time = end
		durations.append(duration)
	print(' '.join(map(str, durations)))
import sys
input = sys.stdin.readline
exit(main())


def solve(n, ss, fs):
	(t, ds) = (0, [])
	for _ in range(n):
		(s, f) = (ss.popleft(), fs.popleft())
		d = f - s if s >= t else f - t
		t = f
		ds.append(d)
	print(' '.join(map(str, ds)))

def main():
	from sys import stdin
	from itertools import islice
	from collections import deque
	tkns = map(int, stdin.read().split())
	t = next(tkns)
	for _ in range(t):
		n = next(tkns)
		(s, f) = (deque(islice(tkns, n)), deque(islice(tkns, n)))
		solve(n, s, f)
main()


import sys

def main():
	input = sys.stdin.readline
	t = int(input())
	for i in range(t):
		n = int(input())
		s = list(map(int, input().split()))
		f = list(map(int, input().split()))
		d = []
		d.append(f[0] - s[0])
		for j in range(1, n):
			d.append(f[j] - max(f[j - 1], s[j]))
		print(' '.join(map(str, d)))
	return
main()


import sys
import collections
inp = lambda : sys.stdin.readline().rstrip()
LS = lambda : list(map(int, inp().split()))
for _ in range(int(inp())):
	n = int(inp())
	ls_s = [0] + LS()
	ls_f = [0] + LS()
	ans = []
	for i in range(1, len(ls_s)):
		if ls_s[i] < ls_f[i - 1]:
			ans.append(ls_f[i] - ls_f[i - 1])
		else:
			ans.append(ls_f[i] - ls_s[i])
	print(' '.join(list(map(str, ans))))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))
n = inp()
for _ in range(n):
	length = inp()
	array1 = inlt()
	array2 = inlt()
	answer = []
	time = array1[0]
	for i in range(length):
		if array1[i] > time:
			time = array1[i]
		timeTaken = array2[i] - time
		time += timeTaken
		answer.append(str(timeTaken))
	print(' '.join(answer))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	d = []
	for i in range(n):
		if i == 0:
			d.append(f[i] - s[i])
		else:
			d.append(f[i] - f[i - 1] if f[i - 1] > s[i] else f[i] - s[i])
	print(' '.join(map(str, d)))


import sys
import os
from collections import Counter, defaultdict, deque
from heapq import heapify, heappush, heappop
from functools import lru_cache
from math import floor, ceil, sqrt, gcd
from string import ascii_lowercase
from math import gcd
from bisect import bisect_left, bisect, bisect_right

def read():
	return input().strip()

def read_int():
	return int(read())

def read_str_list():
	return read().split()

def read_numeric_list():
	return list(map(int, read_str_list()))

def solve(N, start_arr, end_arr):
	curr_time = 0
	ans = []
	for i in range(N):
		(start_time, end_time) = (start_arr[i], end_arr[i])
		if curr_time < start_time:
			curr_time = start_time
		ans.append(end_time - curr_time)
		curr_time = end_time
	return ' '.join(map(str, ans))
T = read_int()
for t in range(T):
	N = read_int()
	start_arr = read_numeric_list()
	end_arr = read_numeric_list()
	print(solve(N, start_arr, end_arr))


from collections import deque
N = int(input())
for n in range(N):
	answer = ''
	s = int(input())
	if s > 1:
		arr1 = deque(list(map(int, input().split())))
		arr2 = deque(list(map(int, input().split())))
		c = arr1.popleft()
		d = arr2.popleft()
		answer = [d - c]
		end = d
		for i in range(1, s):
			a = arr1.popleft()
			b = arr2.popleft()
			if end <= a:
				answer.append(b - a)
			else:
				answer.append(b - end)
			end = b
		print(' '.join([str(a) for a in answer]))
	else:
		a = int(input())
		b = int(input())
		print(b - a)


from collections import Counter
from functools import lru_cache
import heapq
from itertools import combinations
import math
import sys
result = []
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	(timeEntered, timeEnded) = (list(map(int, input().split())), list(map(int, input().split())))

	def solve():
		tasks = []
		currentTime = float('inf')
		for (i, timeOne) in enumerate(timeEntered):
			tasks.append((timeOne, timeEnded[i], i))
			currentTime = min(currentTime, timeOne)
		tasks.sort()
		res = [0] * n
		currentTime = 0
		for (timeOne, timeTwo, idx) in tasks:
			if timeOne >= currentTime:
				res[idx] = str(timeTwo - timeOne)
				currentTime = timeTwo
			else:
				res[idx] = str(timeTwo - currentTime)
				currentTime = timeTwo
		return res
	ans = solve()
	print(' '.join(ans))


x = int(input())

def cal(n, a, b):
	ans = [0] * n
	t = 0
	for i in range(n):
		if a[i] < t:
			ans[i] = b[i] - t
		else:
			ans[i] = b[i] - a[i]
		t = b[i]
	res = [str(i) for i in ans]
	return ' '.join(res)
for jj in range(x):
	n = int(input())
	arr1 = [int(i) for i in input().split(' ')]
	arr2 = [int(i) for i in input().split(' ')]
	print(cal(n, arr1, arr2))


def solve():
	n = int(input())
	s = [int(i) for i in input().split()]
	e = [int(i) for i in input().split()]
	res = [e[0] - s[0]]
	for i in range(1, n):
		if s[i] < e[i - 1]:
			res.append(e[i] - e[i - 1])
		else:
			res.append(e[i] - s[i])
	print(' '.join([str(i) for i in res]))
	return

def main():
	for _ in range(int(input())):
		solve()
	return
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = []
	ans.append(b[0] - a[0])
	for i in range(1, n):
		ans.append(b[i] - max(b[i - 1], a[i]))
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split(' ')))
	f = list(map(int, input().split(' ')))
	b = 0
	ans = [None] * n
	for i in range(n):
		if s[i] > b:
			ans[i] = f[i] - s[i]
		else:
			ans[i] = f[i] - b
		b = f[i]
	print(' '.join(map(str, ans)))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = []
	for i in range(n):
		if i == 0:
			ans.append(b[i] - a[i])
		elif a[i] >= b[i - 1]:
			ans.append(b[i] - a[i])
		else:
			ans.append(b[i] - b[i - 1])
	print(' '.join(map(str, ans)))
t = int(input())
while t > 0:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	start = list(map(int, input().split()))
	end = list(map(int, input().split()))
	durations = []
	durations.append(str(end[0] - start[0]))
	for i in range(1, n):
		if start[i] >= end[i - 1]:
			durations.append(str(end[i] - start[i]))
		else:
			durations.append(str(end[i] - end[i - 1]))
	print(' '.join(durations))


def possible(s, f, n):
	result = ''
	for i in range(n):
		result += ' ' if result else ''
		if i > 0 and s[i] < f[i - 1]:
			result += str(f[i] - f[i - 1])
		else:
			result += str(f[i] - s[i])
	print(result)
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	possible(s, f, n)


def solve():
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	f.insert(0, 0)
	print(' '.join([str(f[i] - max(f[i - 1], s[i - 1])) for i in range(1, len(f))]))
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().rstrip().split()))
	list2 = list(map(int, input().rstrip().split()))
	list2.insert(0, 0)
	print(' '.join([str(list2[i] - max(list2[i - 1], list1[i - 1])) for i in range(1, n + 1)]))


def f():
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	d = [0] * n
	d[0] = f[0] - s[0]
	for i in range(1, n):
		d[i] = f[i] - max(f[i - 1], s[i])
	print(' '.join((str(x) for x in d)))
for _ in range(int(input())):
	f()


t = int(input())

def helper(n, s1, s2):
	end = -1
	ans = []
	for i in range(n):
		if end == -1:
			end = s2[i]
			ans.append(s2[i] - s1[i])
		elif end <= s1[i]:
			end = s2[i]
			ans.append(s2[i] - s1[i])
		elif end > s1[i]:
			ans.append(s2[i] - end)
			end = s2[i]
	return ans
for i in range(t):
	n = int(input())
	(s1, s2) = (list(map(int, input().split())), list(map(int, input().split())))
	res = helper(n, s1, s2)
	res = ' '.join(list(map(str, res)))
	print(res)


n = int(input())
for _ in range(n):
	leng = int(input())
	start = list(map(int, input().split()))
	end = list(map(int, input().split()))
	time = []
	prev = 0
	for i in range(leng):
		if start[i] < prev:
			time.append(end[i] - prev)
		elif start[i] >= prev:
			time.append(end[i] - start[i])
		prev = end[i]
	print(' '.join(map(str, time)))


def fn(start, finish):
	result = []
	result.append(finish[0] - start[0])
	flag = finish[0]
	for i in range(1, len(start)):
		if start[i] >= flag:
			result.append(finish[i] - start[i])
		else:
			result.append(finish[i] - flag)
		flag = finish[i]
	result = ' '.join((str(e) for e in result))
	return result
t = int(input())
for i in range(t):
	n = input()
	start = [int(j) for j in input().split()]
	finish = [int(k) for k in input().split()]
	output = fn(start, finish)
	print(output)


def solve():
	g = int(input())
	m = list(map(int, input().split()))
	l = list(map(int, input().split()))
	mx = m[0]
	out = []
	for i in range(g):
		if m[i] > mx:
			mx = m[i]
		out.append(str(l[i] - mx))
		mx = l[i]
	return ' '.join(out)
n = int(input())
for i in range(n):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	e = list(map(int, input().split()))
	res = []
	for i in range(n):
		if i >= 1 and s[i] < e[i - 1]:
			diff = e[i] - e[i - 1]
		else:
			diff = e[i] - s[i]
		res.append(diff)
	print(' '.join(map(str, res)))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	d = []
	d.append(f[0] - s[0])
	for i in range(1, n):
		if s[i] > f[i - 1]:
			d.append(f[i] - s[i])
		else:
			d.append(f[i] - f[i - 1])
	str_d = [str(x) for x in d]
	print(' '.join(str_d))


def sol(a, b):
	d = []
	d.append(str(b[0] - a[0]))
	for _ in range(1, len(a)):
		if a[_] >= b[_ - 1]:
			d.append(str(b[_] - a[_]))
		else:
			d.append(str(b[_] - b[_ - 1]))
	return ' '.join(d)
t = int(input())
for _ in range(t):
	n = input()
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	print(sol(a, b))


_ = int(input())
for __ in range(_):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	out = [arr2[0] - arr1[0]]
	for x in range(1, n):
		if arr1[x] < arr2[x - 1]:
			out.append(arr2[x] - arr2[x - 1])
		else:
			out.append(arr2[x] - arr1[x])
	print(' '.join([str(x) for x in out]))


from collections import deque

def solve(s, f):
	q = deque()
	startTime = s[0]
	lastDoneTime = f[0]
	ans = []
	ans.append(f[0] - s[0])
	for i in range(1, len(s)):
		startTime = max(lastDoneTime, s[i])
		ans.append(f[i] - startTime)
		lastDoneTime = f[i]
	return ans
t = int(input())
for i in range(t):
	input()
	s = list(map(int, input().split(' ')))
	f = list(map(int, input().split(' ')))
	ans = solve(s, f)
	print(' '.join(map(str, ans)))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	current = 0
	d = [0] * n
	for i in range(n):
		if s[i] >= current:
			current = s[i]
		d[i] = f[i] - current
		current = f[i]
	print(' '.join(map(str, d)))


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	f = [int(x) for x in input().split()]
	d = []
	cur_time = 0
	for i in range(len(s)):
		if s[i] > cur_time:
			cur_time = f[i]
			d.append(f[i] - s[i])
		else:
			d.append(-cur_time + f[i])
			cur_time = f[i]
	print(' '.join([str(x) for x in d]))


t = int(input())
ans = list()
for i in range(0, t):
	n = int(input())
	arrs = [int(x) for x in input().split()]
	arrf = [int(x) for x in input().split()]
	time = arrf[0] - arrs[0]
	s = f'{time}'
	for j in range(1, n):
		time = min(arrf[j] - arrs[j], arrf[j] - arrf[j - 1])
		s += f' {time}'
	ans.append(s)
for s in ans:
	print(s)


import os
import sys
import string
import math
n = int(input())

def solve(startTimes, endTimes, numTasks):
	workTimes = []
	counter = 0
	outStr = ''
	for s in range(numTasks):
		if startTimes[s] > counter:
			counter = startTimes[s]
		wTime = endTimes[s] - counter
		workTimes.append(wTime)
		counter = endTimes[s]
		outStr += f'{wTime} '
	print(outStr)
for i in range(n):
	numTasks = int(input())
	startTimes = input().split(' ')
	endTimes = input().split(' ')
	startTimes = list(map(lambda x: int(x), startTimes))
	endTimes = list(map(lambda x: int(x), endTimes))
	solve(startTimes, endTimes, numTasks)


for _ in range(int(input())):
	n = int(input())
	ts = [int(x) for x in input().split()]
	fs = [int(x) for x in input().split()]
	ds = []
	prevf = 0
	for (t, f) in zip(ts, fs):
		if prevf > t:
			d = f - prevf
		else:
			d = f - t
		prevf = f
		ds.append(str(d))
	print(' '.join(ds))


run = int(input())
for i in range(run):
	n = int(input())
	st = list(map(int, input().split()))
	fn = list(map(int, input().split()))
	f = 0
	out = []
	for i in range(n):
		if st[i] > f:
			out.append(fn[i] - st[i])
		else:
			out.append(fn[i] - f)
		f = fn[i]
	os = ''
	for i in out:
		os += str(i) + ' '
	print(os.rstrip())


for _ in range(int(input())):
	input()
	x = [int(a) for a in input().split()]
	y = [int(a) for a in input().split()]
	prev_f = -1
	d = []
	for i in range(len(x)):
		d.append(str(y[i] - max(x[i], prev_f)))
		prev_f = y[i]
	print(' '.join(d))


def solve():
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	d = [0] * n
	for i in range(n):
		if i == 0:
			d[i] = f[i] - s[i]
		else:
			d[i] = f[i] - max(s[i], f[i - 1])
	print(' '.join(map(str, d)))
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	F = list(map(int, input().split()))
	(d1, D) = (F[0] - S[0], [])
	D.append(d1)
	for i in range(1, n):
		if F[i - 1] > S[i]:
			D.append(F[i] - F[i - 1])
		else:
			D.append(F[i] - S[i])
	print(' '.join((str(x) for x in D)))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	k = [l2[0] - l1[0]]
	for i in range(1, n):
		if l1[i] > l2[i - 1]:
			k.append(l2[i] - l1[i])
		else:
			k.append(l2[i] - l2[i - 1])
	a = ' '.join((str(i) for i in k))
	print(a)


t = int(input())
for _ in range(t):
	d = []
	duration = 0
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	d.append(f[0] - s[0])
	duration += d[0]
	for i in range(1, n):
		if s[i] >= f[i - 1]:
			d.append(f[i] - s[i])
			duration += d[i]
		else:
			d.append(f[i] - f[i - 1])
			duration += d[i]
	print(' '.join(map(str, d)))


for _ in range(int(input())):
	n = int(input())
	s = [*map(int, input().split())]
	f = [*map(int, input().split())]
	ans = []
	for i in range(n):
		ans.append(f[i] - (f[i - 1] if i > 0 and f[i - 1] > s[i] else s[i]))
	print(' '.join((str(x) for x in ans)))


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	f = [int(x) for x in input().split()]
	time = []
	for i in range(n):
		if i == 0:
			time.append(str(f[i] - s[i]))
		else:
			time.append(str(f[i] - max(s[i], f[i - 1])))
	print(' '.join(time))


t = int(input())
for i in range(t):
	n = int(input())
	startTime = [int(j) for j in input().split()]
	finTime = [int(j) for j in input().split()]
	duration = []
	for j in range(0, n):
		if j == 0:
			duration.append(str(finTime[j] - startTime[j]))
		elif finTime[j - 1] > startTime[j]:
			duration.append(str(finTime[j] - finTime[j - 1]))
		else:
			duration.append(str(finTime[j] - startTime[j]))
	print(' '.join(duration))


t = int(input())
for i in range(t):
	n = int(input())
	s1 = [int(x) for x in input().split()]
	f1 = [int(x) for x in input().split()]
	res = f1[0] - s1[0]
	temp = [res]
	for i in range(1, len(s1)):
		if s1[i] >= f1[i - 1]:
			result = f1[i] - s1[i]
			temp.append(result)
		else:
			result = f1[i] - f1[i - 1]
			temp.append(result)
	new = ' '.join((str(x) for x in temp))
	print(new)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	r = []
	for (idx, (i, j)) in enumerate(zip(s, f)):
		if idx == 0:
			r.append(j - i)
			continue
		if i > f[idx - 1]:
			r.append(j - i)
		else:
			r.append(j - f[idx - 1])
	print(' '.join(map(str, r)))


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		s = [int(i) for i in input().split(' ')]
		f = [int(i) for i in input().split(' ')]
		print(str(Solution(n, s, f)))

def Solution(n, s, f):
	result = [str(f[0] - s[0])]
	for i in range(1, n):
		result.append(str(f[i] - max(s[i], f[i - 1])))
	return ' '.join(result)
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	o = []
	o += [f[0] - s[0]]
	for j in range(1, n):
		if s[j] < f[j - 1]:
			o += [f[j] - f[j - 1]]
		else:
			o += [f[j] - s[j]]
	print(' '.join(list(map(str, o))))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	ans = f'{f[0] - s[0]} '
	for i in range(1, n):
		ans += f'{f[i] - max(f[i - 1], s[i])} '
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	result = []
	j = 0
	while j < n - 1:
		if l2[j] > l1[j + 1]:
			l1[j + 1] = l2[j]
		result.append(l2[j] - l1[j])
		j = j + 1
	result.append(l2[n - 1] - l1[n - 1])
	print(' '.join(map(str, result)))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	res = [str(f[0] - s[0])]
	for i in range(1, n):
		res.append(str(f[i] - max(s[i], f[i - 1])))
	print(' '.join(res))


for _ in range(int(input())):
	n = int(input())
	s = [int(a) for a in input().split()]
	f = [int(b) for b in input().split()]
	res = []
	t = 0
	for (a, b) in zip(s, f):
		t = max(t, a)
		res.append(b - t)
		t = b
	print(' '.join(map(str, res)))


from posixpath import split
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = 0
	ans = ''
	for i in range(n):
		ans += str(b[i] - max(a[i], f)) + ' '
		f = b[i]
	print(ans)


N = int(input())
for x in range(N):
	l = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	final = []
	for i in range(l):
		if i == 0:
			final.append(f[i] - s[i])
		elif s[i] <= f[i - 1]:
			final.append(f[i] - f[i - 1])
		else:
			final.append(f[i] - s[i])
	print(' '.join(list(map(str, final))))


t = int(input())
for i in range(t):
	answer = []
	previous = 0
	n = int(input())
	s = [int(i) for i in input().split()]
	f = [int(i) for i in input().split()]
	for j in range(n):
		if s[j] >= previous:
			answer.append(str(f[j] - s[j]))
		else:
			answer.append(str(f[j] - f[j - 1]))
		previous = f[j]
	print(' '.join(answer))


t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(i) for i in input().split()]
	f = [int(i) for i in input().split()]
	times = [0] * n
	times[0] = f[0] - s[0]
	prev = f[0]
	for i in range(1, n):
		times[i] = f[i] - max(f[i - 1], s[i])
	print(' '.join(map(str, times)))


test = int(input())
for t in range(test):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	lst = []
	pend = 0
	for i in range(n):
		start = s[i]
		end = f[i]
		time = end - max(pend, start)
		pend = end
		lst.append(str(time))
	print(' '.join(lst))


t = int(input())
for i in range(0, t):
	alpha = ''
	n = int(input())
	x = list(map(int, input().split(' ')))
	y = list(map(int, input().split(' ')))
	alpha += str(y[0] - x[0])
	if n > 1:
		for j in range(1, n):
			if x[j] >= y[j - 1]:
				alpha += ' ' + str(y[j] - x[j])
			elif x[j] < y[j - 1]:
				alpha += ' ' + str(y[j] - y[j - 1])
	print(alpha)


m = int(input())
for i in range(m):
	n = int(input())
	s = [int(i) for i in input().split()]
	j = [int(i) for i in input().split()]
	d = [j[0] - s[0]] + [0] * (n - 1)
	for i in range(1, n):
		d[i] = j[i] - max(j[i - 1], s[i])
	print(' '.join([str(i) for i in d]))


from ast import For
import sys
ncases = int(input())

def solve():
	ntasks = int(input())
	begTimes = [int(x) for x in str(input()).split(' ')]
	endTimes = [int(x) for x in str(input()).split(' ')]
	times = [(begTimes[i], endTimes[i]) for i in range(ntasks)]
	i = 1
	r = [str(times[0][1] - times[0][0])]
	while i < ntasks:
		r.append(str(times[i][1] - max([begTimes[i], endTimes[i - 1]])))
		i += 1
	result.append(' '.join(r))
result = []
for x in range(ncases):
	solve()
[print(x) for x in result]


for _ in range(int(input())):
	n = input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	out = ''
	out += str(b[0] - a[0]) + ' '
	for i in range(1, len(b)):
		out += str(b[i] - max(b[i - 1], a[i])) + ' '
	print(out)


num_of_cases = int(input())
for case in range(0, num_of_cases):
	num_of_tasks = int(input())
	start_times = list(map(int, input().split(' ')))
	finish_times = list(map(int, input().split(' ')))
	total = []
	i = 0
	for (i, (s, f)) in enumerate(zip(start_times, finish_times)):
		if not i:
			total.append(f - s)
		elif s >= finish_times[i - 1]:
			total.append(f - s)
		else:
			total.append(f - finish_times[i - 1])
		i += 1
	print(' '.join([str(n) for n in total]))


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split(' ')))
	f = list(map(int, input().split(' ')))
	l = [f[0] - s[0]]
	for i in range(1, n):
		l.append(f[i] - max(f[i - 1], s[i]))
	print(' '.join((str(x) for x in l)))


for _ in range(int(input())):
	a = int(input())
	s1 = list(map(int, input().split()))
	s2 = list(map(int, input().split()))
	count = 0
	for z in range(1, a):
		if s1[z] < s2[z - 1]:
			s1[z] = s2[z - 1]
	ans = ''
	for p in range(a):
		ans += str(s2[p] - s1[p]) + ' '
	print(ans)


num = int(input())
for i in range(num):
	n = int(input())
	start = input()
	start = start.split(' ')
	start = [int(x) for x in start]
	finish = input()
	finish = finish.split(' ')
	finish = [int(x) for x in finish]
	res = [str(finish[0] - start[0])]
	for j in range(1, n):
		if start[j] <= finish[j - 1]:
			res.append(str(finish[j] - finish[j - 1]))
		else:
			res.append(str(finish[j] - start[j]))
	print(' '.join(res))


t = int(input())
for i in range(t):
	v = []
	n = int(input())
	x = input()
	s = x.split(' ')
	y = input()
	f = y.split(' ')
	v.append(str(int(f[0]) - int(s[0])))
	k = int(f[0])
	for i in range(len(s)):
		s[i] = int(s[i])
		f[i] = int(f[i])
		if i != 0:
			if s[i] > k:
				v.append(str(f[i] - s[i]))
			else:
				v.append(str(f[i] - k))
		k = f[i]
	print(' '.join(v))


tc = int(input())
while tc > 0:
	flag = 0
	n = int(input())
	A = [int(i) for i in input().split(' ')]
	B = [int(i) for i in input().split(' ')]
	x = '{} '.format(B[0] - A[0])
	for i in range(1, n):
		if A[i] > B[i - 1]:
			x = x + '{} '.format(B[i] - A[i])
		else:
			x = x + '{} '.format(B[i] - B[i - 1])
	print(x)
	tc = tc - 1


for _ in range(int(input())):
	size = int(input())
	d = [None] * size
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	start = 0
	for i in range(size):
		start = max(start, s[i])
		time_taken = f[i] - start
		d[i] = str(time_taken)
		start = f[i]
	print(' '.join(d))


for _ in range(0, int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	op = []
	op.append(f[0] - s[0])
	if n > 1:
		(i, j) = (1, 1)
		while i < n and j < n:
			if s[i] > f[j - 1]:
				op.append(f[j] - s[i])
			else:
				op.append(f[j] - f[j - 1])
			i += 1
			j += 1
	print(' '.join((str(x) for x in op)))


t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = []
	ans.append(b[0] - a[0])
	cnt = 1
	i = 1
	while cnt != n:
		if a[i] > b[i - 1]:
			ans.append(b[i] - a[i])
		else:
			ans.append(b[i] - b[i - 1])
		cnt += 1
		i += 1
	print(' '.join(map(str, ans)))


from sys import stdin, stdout, setrecursionlimit
import collections
import math
from collections import deque

def test():
	return

def solve():
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		s = list(map(int, input().split()))
		f = list(map(int, input().split()))
		res = [f[0] - s[0]]
		prev = f[0]
		for i in range(1, n):
			x = max(s[i], prev)
			res.append(f[i] - x)
			prev = f[i]
		print(*res)
	return
input = stdin.readline
main()


from math import ceil

def sol():
	n = int(input())
	(a, b, c) = (n // 3, n // 3, n // 3)
	if n % 3 == 0:
		b += 1
		c -= 1
	elif n % 3 == 1:
		b += 2
		c -= 1
	elif n % 3 == 2:
		a += 1
		b += 2
		c -= 1
	print(a, b, c)

def solv():
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	diff = max((a[i] - b[i] for i in range(n)))
	if diff < 0:
		return 'NO'
	for i in range(n):
		if a[i] - b[i] < 0:
			return 'NO'
		elif a[i] - b[i] < diff:
			if b[i] != 0:
				return 'NO'
	return 'YES'

def solve():
	n = int(input())
	s = list(map(int, input().strip().split()))
	f = list(map(int, input().strip().split()))
	d = [f[0] - s[0]]
	for i in range(1, n):
		d.append(min(f[i] - f[i - 1], f[i] - s[i]))
	print(' '.join((str(i) for i in d)))
for _ in range(int(input())):
	solve()


t = int(input())
for q in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	f = list(map(int, input().split()))
	p = 0
	D = []
	for i in range(n):
		d = f[i] - s[i]
		if p > s[i]:
			d = f[i] - p
		p = f[i]
		D.append(str(d))
	print(' '.join(D))


for _ in range(int(input())):
	input()
	(start_times, end_times) = (list(map(int, input().split())), list(map(int, input().split())))
	durations = [end_times[0] - start_times[0]]
	index = 1
	while len(durations) != len(start_times):
		duration = end_times[index] - max(start_times[index], end_times[index - 1])
		index += 1
		durations.append(duration)
	print(' '.join(map(str, durations)))


t = int(input())
for _ in range(t):
	n = int(input())
	given_times = [int(num) for num in input().split()]
	completed_times = [int(num) for num in input().split()]
	durations = [completed_times[0] - given_times[0]]
	last_task_completed = completed_times[0]
	for (task_given_time, task_completed_time) in zip(given_times[1:], completed_times[1:]):
		task_start_time = max(task_given_time, last_task_completed)
		duration = task_completed_time - task_start_time
		durations.append(duration)
		last_task_completed = task_completed_time
	durations = [str(d) for d in durations]
	print(' '.join(durations))


num_of_cases = int(input())
for _ in range(num_of_cases):
	N = int(input())
	start = [int(x) for x in input().split(' ')]
	end = [int(x) for x in input().split(' ')]
	res = []
	cur_time = 0
	for idx in range(N):
		cur_time = max(cur_time, start[idx])
		res.append(str(end[idx] - cur_time))
		cur_time = end[idx]
	print(' '.join(res))


for _ in range(int(input())):
	(n, sol) = (int(input()), [])
	s = list(map(int, input().split(' ')))
	f = list(map(int, input().split(' ')))
	for i in range(1, n):
		if s[i] < f[i - 1]:
			s[i] = f[i - 1]
	for (i, j) in zip(s, f):
		sol.append(str(j - i))
	print(' '.join(sol))


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	currStart = arr[0]
	lastEnd = brr[0]
	out = [brr[0] - arr[0]]
	for i in range(1, n):
		if arr[i] < lastEnd:
			currStart = lastEnd
		else:
			currStart = arr[i]
		out.append(brr[i] - currStart)
		lastEnd = brr[i]
	print(*out)


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	list2 = [int(num) for num in input().split()]
	d1 = list2[0] - list1[0]
	s = str(d1)
	i = 1
	for i in range(1, len(list2)):
		if list1[i] >= list2[i - 1]:
			s += ' ' + str(list2[i] - list1[i])
		else:
			s += ' ' + str(list2[i] - list2[i - 1])
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	start = [int(x) for x in input().split()]
	end = [0] + [int(x) for x in input().split()]
	duration = []
	for i in range(n):
		x = end[i + 1] - max(start[i], end[i])
		duration.append(str(x))
	print(' '.join(duration))


T = int(input(''))
for i in range(T):
	n = int(input(''))
	a = input('').split()
	a = [int(x) for x in a]
	b = input('').split()
	b = [int(x) for x in b]
	ans = []
	j = 0
	for j in range(n):
		if j == 0:
			ans.append(b[j] - a[j])
		elif a[j] > b[j - 1]:
			ans.append(b[j] - a[j])
		else:
			ans.append(b[j] - b[j - 1])
	finalans = ' '.join((str(y) for y in ans))
	print(finalans)


n = int(input())
list_for_tasks = []
for i in range(n):
	list_to_append = []
	a = [int(input())]
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	list_to_append = [a, b, c]
	list_for_tasks.append(list_to_append)
list_ = list_for_tasks
nn = n
times_final = []
for j in range(nn):
	times = []
	for i in range(list_[j][0][0]):
		if i == 0:
			time = '{}'.format(list_[j][2][i] - list_[j][1][i])
			times.append(time)
		elif list_[j][1][i] >= list_[j][2][i - 1]:
			time = '{}'.format(list_[j][2][i] - list_[j][1][i])
			times.append(time)
		else:
			time = '{}'.format(list_[j][2][i] - list_[j][2][i - 1])
			times.append(time)
	times_final.append(times)
for m in range(n):
	print(' '.join(times_final[m]))


n = int(input())
for i in range(n):
	x = input()
	s = list(map(int, input().split(' ')))
	f = list(map(int, input().split(' ')))
	out = str()
	for j in range(len(f)):
		if j == 0:
			out += str(f[0] - s[0])
		elif s[j] < f[j - 1]:
			out += str(f[j] - f[j - 1])
		else:
			out += str(f[j] - s[j])
		out += ' '
	print(out)


for t in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	s = ''
	for i in range(n):
		if i != 0 and arr1[i] >= arr2[i - 1] or i == 0:
			s += str(arr2[i] - arr1[i]) + ' '
		else:
			s += str(arr2[i] - arr2[i - 1]) + ' '
	print(s)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [0] * n
	now = -1
	for i in range(n):
		if a[i] >= now:
			c[i] = b[i] - a[i]
			now = b[i]
		else:
			c[i] = b[i] - now
			now = b[i]
	print(*c)
T = int(input())
for _ in range(T):
	solve()


x = lambda : map(int, input().split())
(t,) = x()
for _ in '+' * t:
	n = x()
	a = [*x()]
	b = [*x()]
	print(*(x - max(y, z) for (x, y, z) in zip(b, a, [0] + b)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().strip().split()))
	e = list(map(int, input().strip().split()))
	co = 0
	lans = []
	for i in range(n):
		if s[i] >= co:
			lans.append(e[i] - s[i])
			co = e[i]
		elif e[i] - co < 0:
			lans.append(0)
		else:
			lans.append(e[i] - co)
			co = e[i]
	print(*lans)


t = int(input())
for p in range(t):
	n = int(input())
	si = list(map(int, input().split()))
	fi = list(map(int, input().split()))
	pl = [fi[0] - si[0]]
	for i in range(1, n):
		if si[i] >= fi[i - 1]:
			pl.append(fi[i] - si[i])
		else:
			pl.append(fi[i] - fi[i - 1])
	ch = ''
	for i in range(n):
		ch += str(pl[i]) + ' '
	print(ch)


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	f = input().split()
	liss = []
	lisf = []
	lis = []
	for j in range(n):
		liss.append(int(s[j]))
		lisf.append(int(f[j]))
	lis.append(str(lisf[0] - liss[0]))
	for j in range(1, n):
		if liss[j] > lisf[j - 1]:
			lis.append(str(lisf[j] - liss[j]))
		else:
			lis.append(str(lisf[j] - lisf[j - 1]))
	print(' '.join(lis))


from sys import stdin, stdout
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def main():
	t = int(stdin.readline().strip())
	for tc in range(1, t + 1):
		n = int(stdin.readline().strip())
		s = [int(x) for x in stdin.readline().split()]
		f = [int(x) for x in stdin.readline().split()]
		duration = [0 for i in range(n)]
		duration[0] = f[0] - s[0]
		for i in range(1, n):
			duration[i] = f[i] - max(f[i - 1], s[i])
		print(*duration)
main()


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	R()
	a = R()
	(*b,) = R()
	print(*(x - max(y, z) for (x, y, z) in zip(b, [0] + b, a)))


def CF797C(starts, ends):
	curr = 0
	answer = []
	for (start, end) in zip(starts, ends):
		start = max(start, curr)
		answer.append(end - start)
		curr = end
	return answer
for _ in range(int(input())):
	input()
	print(*CF797C(list(map(int, input().split())), list(map(int, input().split()))))


from collections import defaultdict
import math as m
import sys
input = sys.stdin.readline

def get2int():
	p = input().split()
	return (int(p[0]), int(p[1]))

def get3int():
	p = input().split()
	return (int(p[0]), int(p[1]), int(p[2]))

def get4int():
	p = input().split()
	return (int(p[0]), int(p[1]), int(p[2]), int(p[3]))

def cinarr():
	return [int(i) for i in input().split()]

def solve():
	n = int(input())
	a = cinarr()
	b = cinarr()
	done = [0] * n
	done[0] = b[0] - a[0]
	for i in range(1, n):
		if a[i] >= b[i - 1]:
			done[i] = b[i] - a[i]
		else:
			done[i] = b[i] - b[i - 1]
	for i in range(n):
		print(done[i], end=' ')
	print()
for case in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	f = [int(x) for x in input().split()]
	d = [f[0] - max(s[0], 0)]
	for i in range(1, n):
		d.append(f[i] - max(s[i], f[i - 1]))
	print(*d)