You are given an array $a_1, a_2, \dots, a_n$, which is sorted in non-descending order. You decided to perform the following steps to create array $b_1, b_2, \dots, b_n$:

Create an array $d$ consisting of $n$ arbitrary non-negative integers.

Set $b_i = a_i + d_i$ for each $b_i$.

Sort the array $b$ in non-descending order.

You are given the resulting array $b$. For each index $i$, calculate what is the minimum and maximum possible value of $d_i$ you can choose in order to get the given array $b$.

Note that the minimum (maximum) $d_i$-s are independent of each other, i. e. they can be obtained from different possible arrays $d$.


-----Input-----

The first line contains the single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of arrays $a$, $b$ and $d$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$; $a_i \le a_{i+1}$) — the array $a$ in non-descending order.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$; $b_i \le b_{i+1}$) — the array $b$ in non-descending order.

Additional constraints on the input:

there is at least one way to obtain the array $b$ from the $a$ by choosing an array $d$ consisting of non-negative integers;

the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print two lines. In the first line, print $n$ integers $d_1^{min}, d_2^{min}, \dots, d_n^{min}$, where $d_i^{min}$ is the minimum possible value you can add to $a_i$.

Secondly, print $n$ integers $d_1^{max}, d_2^{max}, \dots, d_n^{max}$, where $d_i^{max}$ is the maximum possible value you can add to $a_i$.

All $d_i^{min}$ and $d_i^{max}$ values are independent of each other. In other words, for each $i$, $d_i^{min}$ is just the minimum value among all possible values of $d_i$.


-----Examples-----

Input
4
3
2 3 5
7 11 13
1
1000
5000
4
1 2 3 4
1 2 3 4
4
10 20 30 40
22 33 33 55
Output
5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15


-----Note-----

In the first test case, in order to get $d_1^{min} = 5$, we can choose, for example, $d = [5, 10, 6]$. Then $b$ $=$ $[2+5,3+10,5+6]$ $=$ $[7,13,11]$ $=$ $[7,11,13]$.

For $d_2^{min} = 4$, we can choose $d$ $=$ $[9, 4, 8]$. Then $b$ $=$ $[2+9,3+4,5+8]$ $=$ $[11,7,13]$ $=$ $[7,11,13]$.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Greedy algorithms


Solutions:
import sys
import bisect

def solve():
	inp = sys.stdin.readline
	bs = bisect.bisect
	n = int(inp())
	a = list(map(int, inp().split()))
	b = list(map(int, inp().split()))
	c = [0]
	for i in range(1, n):
		if b[i - 1] < a[i]:
			c.append(i)
	c.append(n)
	print(' '.join((str(b[bs(b, a[i] - 1)] - a[i]) for i in range(n))))
	print(' '.join((str(b[c[bs(c, i)] - 1] - a[i]) for i in range(n))))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def solve_min(a, b):
	d_min = [0] * len(a)
	b_index = 0
	for d_index in range(len(a)):
		while a[d_index] > b[b_index]:
			b_index += 1
		d_min[d_index] = b[b_index] - a[d_index]
	return d_min

def solve_max(a, b):
	d_max = [0] * len(a)
	stack = []
	b_index = len(a) - 1
	for d_index in range(len(a) - 1, -1, -1):
		while b_index >= 0 and b[b_index] >= a[d_index]:
			stack.append(b[b_index])
			b_index -= 1
		d_max[d_index] = stack[0] - a[d_index]
		stack.pop()
	return d_max
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(comp) for comp in input().split(' ')]
	b = [int(comp) for comp in input().split(' ')]
	print(' '.join((str(k) for k in solve_min(a, b))))
	print(' '.join((str(k) for k in solve_max(a, b))))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	j = 0
	d = []
	g = [0] * n
	for i in range(n):
		while a[i] > b[j]:
			j += 1
		d.append(b[j] - a[i])
	g[n - 1] = b[n - 1] - a[n - 1]
	j = n - 1
	for i in range(n - 2, -1, -1):
		if a[i + 1] <= b[i]:
			g[i] = b[j] - a[i]
		else:
			g[i] = b[i] - a[i]
			j = i
	print(' '.join(list(map(str, d))))
	print(' '.join(list(map(str, g))))


t = int(input())
for _ in range(t):
	n = int(input())
	As = input().split()
	As = [int(i) for i in As]
	Bs = input().split()
	Bs = [int(i) for i in Bs]
	min_ds = []
	idx = 0
	for (i, a) in enumerate(As):
		while Bs[idx] < a:
			idx += 1
		min_ds.append(Bs[idx] - a)
	max_ds = []
	non_xies = [-1]
	for i in range(n - 1):
		if As[i + 1] > Bs[i]:
			non_xies.append(i)
	non_xies.append(n - 1)
	for i in range(1, len(non_xies)):
		for idx in range(non_xies[i - 1] + 1, non_xies[i] + 1):
			max_ds.append(Bs[non_xies[i]] - As[idx])
	print(' '.join([str(i) for i in min_ds]))
	print(' '.join([str(i) for i in max_ds]))


from collections import Counter

def main():
	t = int(input())
	for t in range(1, t + 1):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		dmin = [0] * n
		dmax = [0] * n
		j = 0
		for i in range(n):
			while b[j] < a[i]:
				j += 1
			dmin[i] = b[j] - a[i]
		j = 0
		for i in range(n):
			j = max(i, j)
			while j + 1 < n and a[j + 1] <= b[j]:
				j += 1
			dmax[i] = b[j] - a[i]
		print(' '.join(list(map(str, dmin))))
		print(' '.join(list(map(str, dmax))))
main()


import bisect

def solve(S, A, B):
	MIN = []
	MAX = []
	dp = []
	for x in A:
		i = bisect.bisect_left(B, x)
		MIN.append(B[i] - x)
	idx = 0
	dp.append([])
	P = [0] * S
	for i in range(S - 1):
		dp[idx].append(i)
		P[i] = idx
		if B[i] < A[i + 1]:
			dp.append([])
			idx += 1
	dp[idx].append(S - 1)
	P[S - 1] = idx
	M1 = []
	for items in dp:
		M1.append(max([B[i] for i in items]))
	for i in range(S):
		MAX.append(M1[P[i]] - A[i])
	return ' '.join([str(x) for x in MIN]) + '\n' + ' '.join([str(x) for x in MAX])
n = int(input())
for _ in range(n):
	S = int(input())
	A = [int(x) for x in input().split(' ')]
	B = [int(x) for x in input().split(' ')]
	res = solve(S, A, B)
	print(res)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d1 = [0] * n
	d2 = [0] * n
	j = n - 1
	res = []
	for i in range(n - 1, -1, -1):
		while j >= 0 and b[j] >= a[i]:
			res.append(b[j])
			j -= 1
		d1[i] = res[-1] - a[i]
		d2[i] = res[0] - a[i]
		c = n - i
		h = n - (j + 1)
		if c == h:
			res = []
	print(' '.join(map(str, d1)))
	print(' '.join(map(str, d2)))
	t -= 1


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(mi, ma) = ([], [])
	f = 0
	for i in range(n - 1):
		if A[i + 1] > B[i]:
			val = B[i]
			for j in range(f, i + 1):
				ma.append(val - A[j])
			f = i + 1
	for j in range(f, n):
		ma.append(B[-1] - A[j])
	j = 0
	for i in range(n):
		while j < n and B[j] < A[i]:
			j += 1
		mi.append(B[j] - A[i])
	print(*mi)
	print(*ma)
	return
for _ in range(int(input())):
	solve()


from bisect import bisect_left
import sys
input = sys.stdin.readline

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

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	a = inlt()
	b = inlt()
	mins = []
	maxs = []
	j = 0
	for i in range(n):
		while b[j] < a[i]:
			j += 1
		mins.append(b[j] - a[i])
	j = 0
	for i in range(n):
		j = max(i, j)
		while j + 1 < n and a[j + 1] <= b[j]:
			j += 1
		maxs.append(b[j] - a[i])
	print(*mins)
	print(*maxs)
for _ in range(inp()):
	solve()


def solve():
	num = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	ans1 = []
	ans2 = [0] * num
	pointer = 0
	for i in l1:
		while l2[pointer] < i:
			pointer += 1
		ans1.append(l2[pointer] - i)
	maxx = []
	for i in range(num - 1, -1, -1):
		x = l1[i]
		while len(l2) and l2[-1] >= x:
			maxx.append(l2.pop())
		ans2[i] = maxx[0] - x
		maxx.pop()
	print(*ans1)
	print(*ans2)
n = int(input())
for i in range(n):
	solve()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	Dmin = [0] * n
	Dmax = [0] * n
	bptr = n - 1
	(acount, bcount) = (0, 0)
	net = []
	for i in range(n - 1, -1, -1):
		while bptr >= 0 and B[bptr] >= A[i]:
			bcount += 1
			net.append(B[bptr])
			bptr -= 1
		Dmin[i] = net[-1] - A[i]
		Dmax[i] = net[0] - A[i]
		acount += 1
		if acount == bcount:
			net = []
	print(*Dmin)
	print(*Dmax)
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(dp1, dp2) = ([0] * n, [0] * n)
	j = 0
	for i in range(n):
		while b[j] < a[i]:
			j += 1
		dp1[i] = b[j] - a[i]
	j = n - 1
	for i in reversed(range(n)):
		dp2[i] = b[j] - a[i]
		if b[i - 1] < a[i]:
			j = i - 1
	print(*dp1)
	print(*dp2)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = 0
	(mn, mx) = ([], [])
	y = n - 1
	for u in range(n - 1, -1, -1):
		x = bisect_left(b, a[u])
		mn.append(b[x] - a[u])
		mx.append(b[y] - a[u])
		if x == u:
			y = x - 1
	print(*mn[::-1])
	print(*mx[::-1])


import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr1 = [0] * n
	arr2 = [0] * n
	mx = n - 1
	for i in range(n - 1, -1, -1):
		mn = bisect.bisect_left(b, a[i])
		arr1[i] = b[mn] - a[i]
		arr2[i] = b[mx] - a[i]
		if i == mn:
			mx = i - 1
	print(*arr1)
	print(*arr2)


t = int(input())
result = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = 0
	s = 0
	res1 = []
	res2 = []
	while f != n:
		if b[s] < a[f]:
			s += 1
			continue
		res1.append(b[s] - a[f])
		f += 1
	f = n - 1
	s = n - 1
	while f != -1:
		res2.append(b[s] - a[f])
		if b[f - 1] < a[f]:
			s = f - 1
		f -= 1
	result.append(res1)
	res2.reverse()
	result.append(res2)
for s in result:
	print(*s)


import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	di = [0] * n
	da = [0] * n
	ss = n
	for i in range(n - 1, -1, -1):
		t = bisect.bisect_left(b, a[i])
		di[i] = b[t] - a[i]
		da[i] = b[ss - 1] - a[i]
		if t == i:
			ss = i
	print(*di)
	print(*da)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	res = []
	ans = []
	for el in arr:
		idx = bisect_left(brr, el)
		res.append(brr[idx] - el)
	start = n - 1
	p = n - 1
	ans = [brr[-1] - arr[-1]]
	for i in range(len(arr) - 2, -1, -1):
		if arr[start] <= brr[i]:
			ans.append(brr[p] - arr[i])
			start -= 1
		else:
			ans.append(brr[i] - arr[i])
			start = i
			p = i
	print(*res)
	ans = ans[::-1]
	print(*ans)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if a == b:
		ans1 = [0] * n
		print(*ans1)
		print(*ans1)
		continue
	ans1 = []
	ans2 = []
	mx = n - 1
	for i in range(n - 1, -1, -1):
		mn = bisect.bisect_left(b, a[i])
		ans1.append(b[mn] - a[i])
		ans2.append(b[mx] - a[i])
		if i == mn:
			mx = i - 1
	print(*ans1[::-1])
	print(*ans2[::-1])


from bisect import bisect_left

def solve():
	n = int(input())
	arr = [-10] + list(map(int, input().split()))
	brr = [-10] + list(map(int, input().split()))
	for i in range(1, n + 1):
		print(brr[bisect_left(brr, arr[i])] - arr[i], end=' ')
	print()
	j = 2
	for i in range(1, n + 1):
		j = max(j, i + 1)
		while j <= n and arr[j] <= brr[j - 1]:
			j += 1
		print(brr[j - 1] - arr[i], end=' ')
	print()
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	i = 0
	first = 0
	last = n - 1
	dmin = []
	dmax = []
	while i < n:
		if a[i] <= b[first]:
			dmin.append(b[first] - a[i])
			i += 1
		else:
			first += 1
	j = n - 1
	while j >= 0:
		if j == n - 1:
			dmax.append(b[last] - a[j])
			j -= 1
		elif b[j] < a[j + 1]:
			last = j
			dmax.append(b[last] - a[j])
			j -= 1
		else:
			dmax.append(b[last] - a[j])
			j -= 1
	print(*dmin)
	print(*dmax[::-1])


def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		(d1, d2) = ([], [])
		j = 0
		for i in range(n):
			while b[j] < a[i]:
				j += 1
			print(b[j] - a[i], end=' ')
		print()
		j = 0
		for i in range(n):
			j = max(j, i)
			while j + 1 < n and a[j + 1] <= b[j]:
				j += 1
			print(b[j] - a[i], end=' ')
		print()
main()


for _ in range(int(input())):
	yun = int(input())
	yu = list(map(int, input().split()))
	hu = list(map(int, input().split()))
	hiup = lodow = yun - 1
	(low, high) = ([], [])
	for i in range(yun - 1, -1, -1):
		high.append(hu[hiup] - yu[i])
		while lodow > -1 and hu[lodow] >= yu[i]:
			lodow -= 1
		low.append(hu[lodow + 1] - yu[i])
		if lodow + 1 == i:
			hiup = lodow
	print(*low[::-1])
	print(*high[::-1])


import sys
from math import ceil
ls = []
for l in sys.stdin:
	lst = l.rstrip('\n')
	if len(lst) > 0:
		ls.append(lst)
for l in ls:
	sys.stderr.write(l + '\n')
sys.stderr.write('-- output --\n')

def at_least(L, x):
	for i in range(len(L)):
		if L[i] >= x:
			return i
	return len(L) - 1

def at_most(L, x):
	for i in range(len(L) - 1, -1, -1):
		if L[i] <= x:
			return i
	return 0

def solve(n, a, b):
	(dmin, dmax) = ([-1] * n, [-1] * n)
	(imin, imax) = (0, n - 1)
	for i in range(n):
		while b[imin] < a[i]:
			imin += 1
		dmin[i] = b[imin] - a[i]
		dmax[n - 1 - i] = b[imax] - a[n - 1 - i]
		if i < n - 1:
			if b[n - i - 2] < a[n - i - 1]:
				imax = n - i - 2
	return (dmin, dmax)
for i in range(1, len(ls) - 1, 3):
	n = int(ls[i])
	a = [int(x) for x in ls[i + 1].split(' ')]
	b = [int(x) for x in ls[i + 2].split(' ')]
	(dmin, dmax) = solve(n, a, b)
	print(*dmin)
	print(*dmax)


import bisect
for jj in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	di = [0] * n
	da = [0] * n
	ss = n
	for i in range(n - 1, -1, -1):
		t = bisect.bisect_left(b, a[i])
		di[i] = b[t] - a[i]
		da[i] = b[ss - 1] - a[i]
		if t == i:
			ss = i
	print(*di)
	print(*da)


from bisect import bisect_left as lb, bisect_right as ub
T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = [0] * n
	for i in range(n):
		pos = lb(b, a[i])
		d[i] = b[pos] - a[i]
	print(*d)
	d = [0] * n
	i = 0
	while i < n - 1:
		j = i
		while j < n - 1 and a[j + 1] <= b[j]:
			j += 1
		for k in range(i, j + 1):
			d[k] = b[j] - a[k]
		i = j + 1
	d[-1] = b[-1] - a[-1]
	print(*d)


from collections import defaultdict
tc = int(input())
for i in range(tc):
	n = int(input())
	ar = list(map(int, input().split()))
	br = list(map(int, input().split()))
	abr = sorted(br)
	dbr = sorted(br, reverse=True)
	dar = sorted(ar, reverse=True)
	c = []
	p = 0
	q = 0
	while p < n and q < n:
		if br[q] >= ar[p]:
			c.append(br[q] - ar[p])
			p += 1
		else:
			q += 1
	d = []
	p = 0
	q = 0
	d.append(dbr[q] - dar[p])
	q += 1
	chk = 0
	while p < n and q < n:
		if dbr[q] < dar[p]:
			chk = q
			p += 1
			d.append(dbr[chk] - dar[p])
			q += 1
		else:
			p += 1
			d.append(dbr[chk] - dar[p])
			q += 1
	print(*c)
	d.reverse()
	print(*d)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	ns = int(n)
	ans1 = [0] * ns
	ans = [0] * ns
	for i in range(n - 1, -1, -1):
		iter = bisect_left(b, a[i])
		ans1[i] = b[iter] - a[i]
		ans[i] = b[ns - 1] - a[i]
		if iter == i:
			ns = i
	print(*ans1)
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	j = n - 1
	l = []
	(dmin, dmax) = ([], [])
	for i in range(n - 1, -1, -1):
		while j >= 0 and b[j] >= a[i]:
			l.append(b[j])
			j -= 1
		dmin.append(l[-1] - a[i])
		dmax.append(l[0] - a[i])
		c1 = n - i
		c2 = n - (j + 1)
		if c1 == c2:
			l = []
	print(*dmin[::-1])
	print(*dmax[::-1])


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	dmin = []
	dmax = []
	check = []
	j = 0
	for i in range(n):
		while a[i] > b[j]:
			j += 1
		check.append(n - j)
		dmin.append(b[j] - a[i])
		dmax.append(0)
	x = 1
	m = b[-1]
	for i in range(n - 1, -1, -1):
		dmax[i] = m - a[i]
		if check[i] - x == 0:
			m = b[n - check[i] - 1]
		x += 1
	for i in dmin:
		print(i, end=' ')
	print()
	for i in dmax:
		print(i, end=' ')
	print()
	t -= 1


from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil, sqrt
from bisect import bisect_left as lb
from bisect import bisect_right as rb
flush = stdout.flush
p = int(1000000000.0 + 7)
tc = 1
tc = int(input())
for _ in range(1, tc + 1):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mn = []
	j = 0
	for i in range(n):
		while j < n and a[i] > b[j]:
			j += 1
		mn.append(b[min(j, n - 1)] - a[i])
	mx = [b[-1] - a[-1]]
	val = b[-1]
	for i in range(n - 2, -1, -1):
		if b[i] < a[i + 1]:
			val = b[i]
		mx.append(val - a[i])
	mx.reverse()
	print(*mn)
	print(*mx)


def get_min(a, b, n):
	mins = [0] * n
	i = n - 1
	min_ind = n - 1
	while i >= 0:
		while b[min_ind] >= a[i] and min_ind >= 0:
			min_ind -= 1
		min_ind += 1
		mins[i] = b[min_ind] - a[i]
		i -= 1
	return mins

def get_max(a, b, n):
	maxs = [0] * n
	high = n - 1
	maxs[high] = b[high] - a[high]
	i = n - 2
	while i >= 0:
		if b[i] < a[i + 1]:
			high = i
		maxs[i] = b[high] - a[i]
		i -= 1
	return maxs
test_cases = int(input())
for i in range(test_cases):
	arr_len = int(input())
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	mins = get_min(a, b, arr_len)
	maxs = get_max(a, b, arr_len)
	ans = ''
	for x in mins:
		ans += str(x) + ' '
	print(ans)
	ans = ''
	for x in maxs:
		ans += str(x) + ' '
	print(ans)


t = int(input())
for e in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dmn = [0] * n
	dmx = [0] * n
	ia = 0
	ib = 0
	while ia < n and ib < n:
		if a[ia] <= b[ib]:
			dmn[ia] = b[ib] - a[ia]
			ia += 1
		else:
			ib += 1
	ia = n - 1
	ib = n - 2
	tb = ib + 1
	ta = ia
	while ia >= 0 and ib >= 0:
		if ib == ia:
			ib -= 1
		while ib >= 0 and a[ia] <= b[ib]:
			ib -= 1
			ia -= 1
		while ta >= 0 and ta > ib:
			dmx[ta] = b[tb] - a[ta]
			ta -= 1
		tb = ib
		ia = ta
	if n == 1:
		dmx[0] = b[0] - a[0]
	print(*dmn)
	print(*dmx)


from bisect import bisect_left
from bisect import bisect_right
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	D1 = [0] * n
	D2 = [0] * n
	m1 = max(B)
	j = n - 1
	f = 1
	while j >= 0:
		if j >= 1:
			if A[j] > B[j - 1]:
				D2[j] = m1 - A[j]
				j -= 1
				m1 = B[j]
			else:
				D2[j] = m1 - A[j]
				j -= 1
		else:
			D2[j] = m1 - A[j]
			j -= 1
	for i in range(n):
		a = bisect_right(B, A[i])
		if a == n or B[a - 1] == A[i]:
			D1[i] = B[a - 1] - A[i]
		else:
			D1[i] = B[a] - A[i]
	print(*D1)
	print(*D2)


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
import math
import bisect
from collections import defaultdict

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	n = num()
	arr = vector()
	fin = vector()
	res1 = []
	res2 = [0 for i in range(n)]
	for i in range(0, n):
		x = bisect.bisect_left(fin, arr[i])
		res1.append(fin[x] - arr[i])
	l = n - 1
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			res2[i] = fin[i] - arr[i]
		elif fin[i] >= arr[i + 1]:
			res2[i] = fin[l] - arr[i]
		else:
			l = i
			res2[i] = fin[l] - arr[i]
	for i in res1:
		print(i, end=' ')
	print()
	for i in res2:
		print(i, end=' ')
	print()


from bisect import *
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = [*map(int, input().split())]
	l = []
	v = []
	j = n - 1
	r = []
	for i in range(n):
		o = bisect_left(b, a[i])
		l += [b[o] - a[i]]
	for i in range(n - 1, -1, -1):
		while j >= 0 and b[j] >= a[i]:
			v += [b[j]]
			j -= 1
		r += [v[0] - a[i]]
		v.pop()
	r = r[::-1]
	print(*l)
	print(*r)


def solve():
	n = int(input())
	a = list(map(int, input().split())) + [10 ** 10]
	b = list(map(int, input().split())) + [10 ** 10]
	min_ = n * [0]
	max_ = n * [0]
	r = -1
	for i in range(n):
		while r < n and a[i] > b[r + 1]:
			r += 1
		min_[i] = r + 1
	ind = 0
	cur = n
	for i in range(1, n + 1):
		max_[n - i] = max(cur - 1, 0)
		if min_[n - i] == n - i:
			cur = n - i
	for i in range(n):
		print(b[min_[i]] - a[i], end=' ')
	print()
	for i in range(n):
		print(b[max_[i]] - a[i], end=' ')
	print()
t = int(input())
for i in range(t):
	solve()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	j = n - 1
	l = []
	d_min = []
	d_max = []
	for i in range(n - 1, -1, -1):
		while b[j] >= a[i] and j >= 0:
			l.append(b[j])
			j -= 1
		a_count = n - i
		b_count = n - (j + 1)
		d_min.append(l[-1] - a[i])
		d_max.append(l[0] - a[i])
		if a_count == b_count:
			l = []
	for i in range(n - 1, -1, -1):
		print(d_min[i], end=' ')
	print()
	for i in range(n - 1, -1, -1):
		print(d_max[i], end=' ')
	print()


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	start = end = n - 1
	m = []
	M = []
	for i in range(n - 1, -1, -1):
		while b[start] >= a[i] and start >= 0:
			start -= 1
		start += 1
		m.append(b[start] - a[i])
		M.append(b[end] - a[i])
		if start == i:
			start -= 1
			end = start
	ans1 = ''
	ans2 = ''
	for i in range(n - 1, 0, -1):
		ans1 += str(m[i]) + ' '
		ans2 += str(M[i]) + ' '
	ans1 += str(m[0])
	ans2 += str(M[0])
	print(ans1)
	print(ans2)


import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxis = []
	minis = []
	for i in a:
		v = bisect.bisect_left(b, i)
		minis.append(max(0, b[v] - i))
	mx = [i for i in b]
	for i in range(n - 2, -1, -1):
		v = bisect.bisect_left(b, a[i + 1])
		if i + 1 != v:
			mx[i] = mx[i + 1]
		else:
			mx[i] = b[i]
	for i in range(n):
		maxis.append(mx[i] - a[i])
	print(*minis)
	print(*maxis)


import bisect

def resolve(list_a, list_b):
	min_list = []
	max_list = []
	for item in list_a:
		insert_index = bisect.bisect_left(list_b, item)
		min_list.append(list_b[insert_index] - item)
	interval = []
	for index in range(1, len(list_a)):
		if list_a[index] > list_b[index - 1]:
			interval.append(index)
	last = 0
	for item in interval:
		for index in range(last, item):
			max_list.append(list_b[item - 1] - list_a[index])
		last = item
	for index in range(last, len(list_a)):
		max_list.append(list_b[len(list_a) - 1] - list_a[index])
	return (min_list, max_list)

def read_input():
	lines_1 = input()
	lines_2 = input().split(' ')
	list_a = []
	list_b = []
	for item in lines_2:
		list_a.append(int(item))
	lines_3 = input().split(' ')
	for item in lines_3:
		list_b.append(int(item))
	return (list_a, list_b)
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		(list_a, list_b) = read_input()
		(res1, res2) = resolve(list_a, list_b)
		for item in res1:
			print(str(item) + ' ', end='')
		print()
		for item_2 in res2:
			print(str(item_2) + ' ', end='')
		print()


testcases = int(input())
for t in range(testcases):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	mini = []
	i = 0
	for x in a:
		while x > b[i]:
			i += 1
		mini.append(b[i] - x)
	maxi = []
	j = 0
	for k in range(n - 1):
		j = max(j, k)
		while j + 1 < n and a[j + 1] <= b[j]:
			j += 1
		maxi.append(b[j] - a[k])
	maxi.append(b[n - 1] - a[n - 1])
	for x in mini:
		print(x, end=' ')
	print()
	for x in maxi:
		print(x, end=' ')
	print()


standard_input = '4\n3\n2 3 5\n7 11 13\n1\n1000\n5000\n4\n1 2 3 4\n1 2 3 4\n4\n10 20 30 40\n22 33 33 55\n'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	greaterThan = [0 for _ in range(n)]
	k = n - 1
	for i in range(n - 1, -1, -1):
		while k > 0 and b[k - 1] >= a[i]:
			k -= 1
		greaterThan[i] = k
	print(*(b[greaterThan[i]] - a[i] for i in range(n)))
	bestSpot = [0 for _ in range(n)]
	highestSpot = n - 1
	maximum = [0 for _ in range(n)]
	for i in range(n - 1, -1, -1):
		while bestSpot[highestSpot]:
			highestSpot -= 1
		ans = b[highestSpot] - a[i]
		maximum[i] = ans
		k = greaterThan[i]
		while bestSpot[k]:
			k = bestSpot[k]
		bestSpot[k] = k + 1
		bestSpot[greaterThan[i]] = k + 1
	print(*maximum)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	bptr = n - 1
	aptr = n - 1
	store = []
	dmin = [0] * n
	dmax = [0] * n
	a_used = 0
	while aptr >= 0:
		while bptr >= 0 and b[bptr] >= a[aptr]:
			store.append(b[bptr])
			bptr -= 1
		dmin[aptr] = store[-1] - a[aptr]
		dmax[aptr] = store[0] - a[aptr]
		a_used += 1
		if a_used == len(store):
			store = []
			a_used = 0
		aptr -= 1
	for i in range(n):
		if i < n - 1:
			print(dmin[i], end=' ')
		else:
			print(dmin[i])
	for i in range(n):
		if i < n - 1:
			print(dmax[i], end=' ')
		else:
			print(dmax[i])
	t -= 1


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	q = deque()
	ans1 = [0] * n
	s = 0
	for i in range(n):
		while s < n:
			if a[i] <= b[s]:
				break
			s += 1
		ans1[i] = abs(a[i] - b[s])
	print(*ans1)
	for i in range(n - 1, -1, -1):
		if b[i] >= a[-1]:
			q.appendleft(b[i])
			b.pop()
		else:
			break
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		ans[i] = q[-1] - a[i]
		q.popleft()
		for j in range(len(b) - 1, -1, -1):
			if b[j] >= a[i - 1]:
				q.appendleft(b[j])
				b.pop()
			else:
				break
	print(*ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	min_list = [0] * n
	max_list = [0] * n
	k = 0
	for j in range(n):
		mi = 10000000000
		while True:
			if b[k] < a[j]:
				k += 1
			else:
				break
		while True:
			if k < n and b[k] - a[j] <= mi and (a[j] <= b[k]):
				mi = b[k] - a[j]
				k += 1
			else:
				k -= 1
				break
		min_list[j] = mi
	flag = 0
	end = n - 1
	for j in range(n - 1, 0, -1):
		max_list[j] = b[end] - a[j]
		if b[j - 1] - a[j] < 0:
			end = j - 1
	else:
		max_list[0] = b[0] - a[0]
		for j in range(1, end + 1):
			if b[j - 1] >= a[j]:
				max_list[0] = b[j] - a[0]
			else:
				break
	for j in min_list:
		print(j, end=' ')
	print()
	for j in max_list:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mini = [0] * n
	maxi = [0] * n
	up = 0
	down = 0
	while up < n and down < n:
		if b[down] < a[up]:
			down += 1
		else:
			maxi[up] = b[down] - a[up]
			if down + 1 < n and a[down + 1] <= b[down]:
				down += 1
			else:
				up += 1
	up = n - 1
	down = n - 1
	while up >= 0 and down >= 0:
		mini[up] = b[down] - a[up]
		if down - 1 >= 0 and b[down - 1] >= a[up]:
			down -= 1
		else:
			up -= 1
	print(*mini)
	print(*maxi)


def min_in_gr(arr, target):
	l = -1
	r = len(arr) - 1
	while l + 1 < r:
		mid = (l + r) // 2
		if arr[mid] >= target:
			r = mid
		else:
			l = mid
	return r

def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	d_min = [0] * n
	cnt = [0] * n
	for i in range(n):
		idx = min_in_gr(b, a[i])
		d_min[i] = b[idx] - a[i]
		cnt[idx] += 1
	d_max = [0] * n
	slotted = 0
	top = n - 1
	cur = n - 1
	while cur >= 0:
		d_max[cur] = b[top] - a[cur]
		if cnt[cur]:
			slotted += cnt[cur]
		if slotted == n - cur:
			top = cur - 1
		cur -= 1
	return (d_min, d_max)

def main():
	t = int(input())
	for i in range(t):
		(d_min, d_max) = solve()
		print(*d_min, sep=' ')
		print(*d_max, sep=' ')
main()


def binary(a, x):
	n = len(a)
	l = 0
	r = n - 1
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if x > a[mid]:
			l = mid + 1
		else:
			res = mid
			r = mid - 1
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	di = [0] * n
	da = [0] * n
	ss = n
	for i in range(n - 1, -1, -1):
		t = binary(b, a[i])
		di[i] = b[t] - a[i]
		da[i] = b[ss - 1] - a[i]
		if t == i:
			ss = i
	print(*di)
	print(*da)


import sys

def findleastgreater(lst, end, num):
	(l, r) = (1, end)
	if lst[0] >= num:
		return 0
	while l < r:
		mid = l + r >> 1
		if lst[mid] >= num and lst[mid - 1] < num:
			return mid
		elif lst[mid] >= num:
			r = mid - 1
		else:
			l = mid + 1
	return l
epoch = int(sys.stdin.readline())
for _ in range(epoch):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().strip().split()))
	d = list(map(int, sys.stdin.readline().strip().split()))
	(mi, ma) = ([], [])
	end = n - 1
	block = n
	for i in range(n - 1, -1, -1):
		num = a[i]
		idx = findleastgreater(d, end, num)
		end = idx
		ma.append(d[block - 1] - num)
		if i <= idx:
			block = idx
		mi.append(d[idx] - num)
	for i in mi[::-1]:
		print(i, end=' ')
	print('')
	for i in ma[::-1]:
		print(i, end=' ')
	print('')


def binary(a, x):
	n = len(a)
	l = 0
	r = n - 1
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] == x:
			return mid
		elif x > a[mid]:
			l = mid + 1
		else:
			res = mid
			r = mid - 1
	return res

def d_min(l, a):
	n = len(l)
	res = []
	for x in l:
		res.append(a[binary(a, x)] - x)
	return res

def d_max(a, b):
	x = 0
	n = len(a)
	d = [True for _ in range(n)]
	for i in range(n - 1, 0, -1):
		if a[i] <= b[i - 1]:
			d[i] = True
		else:
			d[i] = False
	dd = list(range(n))
	last = n
	for i in range(n - 1, -1, -1):
		dd[i] = last - 1
		if d[i] == False:
			last = i
	res = []
	for i in range(n):
		res.append(b[dd[i]] - a[i])
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	res1 = d_min(a, b)
	print(*res1)
	res2 = d_max(a, b)
	print(*res2)


def ss_min(l, a):
	n = len(l)

	def ceiling_of_element(x):
		start = 0
		end = n - 1
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if a[mid] == x:
				return a[mid]
			elif x > a[mid]:
				start = mid + 1
			else:
				res = mid
				end = mid - 1
		return a[res]
	ans = []
	for x in l:
		ans.append(ceiling_of_element(x) - x)
	return ans

def ss_max(a, b):
	n = len(a)
	t = [True for _ in range(n)]
	for i in range(n - 1, 0, -1):
		if a[i] <= b[i - 1]:
			t[i] = True
		else:
			t[i] = False
	t_t = [i for i in range(n)]
	last_f = n
	for i in range(n - 1, -1, -1):
		t_t[i] = last_f - 1
		if t[i] == False:
			last_f = i
	ans = []
	for i in range(n):
		ans.append(b[t_t[i]] - a[i])
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans_min = ss_min(a, b)
	ans_max = ss_max(a, b)
	print(*ans_min)
	print(*ans_max)