Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef loves Tetris. He keeps on playing Tetris all the time. Today Chef's mother wanted to him play something else and brought an array for her son. That is why Chef now decided to play Tetris with arrays. Here are the rules of the game:

Chef has an array A consisting of N positive integers. This is a base array. 
Chef has an array B consisting of N positive integers. He placed this array directly above the array A. Imagine that array B is falling on array A, such that number B_{i} is directly above the number A_{i} initially.
If element B_{i} falls on A_{i}, A_{i} gets increased by B_{i}. 
Each element B_{i} can be dropped by Chef on either A_{i-1}, A_{i} or A_{i+1}.
Chef can't drop element out of array (for example he can't drop B_{0} on A_{-1}). 
Chef wants all the elements of array A to become equal, and looking for the biggest possible value he can get. 

Please help Chef in enjoying the game!!

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in both arrays. 
The second line contains N space-separated integers B_{1}, B_{2}, ..., B_{N} denoting the elements of the falling array. 
The third line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of the base array. 

------ Output ------ 

For each test case, output a single line containing a biggest integer Chef can get for all elements of array A or -1 if it is impossible. 

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{4}$
$1 ≤ A_{i} ≤ 10^{6}$
$1 ≤ B_{i} ≤ 10^{6}$

------ Subtasks ------ 

$Subtask N ≤ 15. Points: 30 $
$Subtask N ≤ 10^{4}. Points: 70 $

----- Sample Input 1 ------ 
3

1

10

20

4

15 7 10 10

6 14 21 1

3

1 100 3

1 2 3
----- Sample Output 1 ------ 
30

21

-1
----- explanation 1 ------ 
Example case 1.
The only option in first example is to make 10 fall on 20. As we have only one element condition of equality is satisfied. 

Example case 2.
Here Chef makes 15 fall on 6, 7 fall on 14, an then both elements with value 10 should fall on 1. Then all elements will become 21.

Example case 3.
There is no way for Chef to make all elements of a base array equal.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
def solve(a, b, n, avg):
	if a[0] + b[0] == avg:
		b[0] = 0
	elif a[0] + b[1] == avg:
		b[1] = 0
	elif a[0] + b[0] + b[1] == avg:
		(b[0], b[1]) = (0, 0)
	elif a[0] != avg:
		flag = 1
		return -1
	if a[n - 1] + b[n - 1] == avg:
		b[n - 1] = 0
	elif a[n - 1] + b[n - 2] == avg:
		b[n - 2] = 0
	elif a[n - 1] + b[n - 1] + b[n - 2] == avg:
		(b[n - 1], b[n - 2]) = (0, 0)
	elif a[n - 1] != avg:
		flag = 1
		return -1
	for i in range(1, n - 1):
		a[i] += b[i - 1]
		b[i - 1] = 0
		if a[i] + b[i] == avg:
			b[i] = 0
		elif a[i] + b[i + 1] == avg:
			b[i + 1] = 0
		elif a[i] + b[i] + b[i + 1] == avg:
			(b[i], b[i + 1]) = (0, 0)
		elif a[i] != avg:
			return -1
	return avg
for t in range(int(input())):
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	sun = sum(a) + sum(b)
	avg = sun // n
	if n <= 1:
		print(sun)
	elif n <= 15:
		print(solve(a, b, n, avg))
	else:
		print(solve(a, b, n, avg))
		print()


t = int(input())
for z in range(t):
	n = int(input())
	top = [int(i) for i in input().strip().split()]
	bottom = [int(i) for i in input().strip().split()]
	top.append(0)
	bottom.append(0)
	count = [0 for i in range(n)]
	count.append(1)
	su = sum(top) + sum(bottom)
	ans = 0
	if su % n != 0:
		print(-1)
	else:
		q = int(su / n)
		for i in range(n):
			if bottom[i] + top[i - 1] + top[i] + top[i + 1] == q and count[i - 1] == 0 and (count[i] == 0) and (count[i + 1] == 0):
				count[i - 1] = 0
				count[i] = 0
				count[i + 1] = 0
			elif bottom[i] + top[i - 1] + top[i] == q and count[i - 1] == 0 and (count[i] == 0):
				count[i] = 1
				count[i - 1] = 1
			elif bottom[i] + top[i - 1] + top[i + 1] == q and count[i - 1] == 0 and (count[i + 1] == 0):
				count[i - 1] = 1
				count[i + 1] = 1
			elif bottom[i] + top[i] + top[i + 1] == q and count[i] == 0 and (count[i + 1] == 0):
				count[i] = 1
				count[i + 1] = 1
			elif bottom[i] + top[i - 1] == q and count[i - 1] == 0:
				count[i - 1] = 1
			elif bottom[i] + top[i] == q and count[i] == 0:
				count[i] = 1
			elif bottom[i] + top[i + 1] == q and count[i + 1] == 0:
				count[i + 1] = 1
			elif bottom[i] == q:
				continue
			else:
				ans = -1
				break
		if ans == -1:
			print(ans)
		else:
			print(q)


__author__ = 'kamal'

def fun(A, B, N, a):
	flag = True
	for i in range(1, N):
		if B[i] == a:
			a = B[i]
		elif a == B[i] + A[i - 1]:
			A[i - 1] = 0
		elif a == B[i] + A[i - 1] + A[i]:
			A[i - 1] = 0
			A[i] = 0
		elif a == B[i] + A[i - 1] + A[i] + A[i + 1]:
			A[i - 1] = 0
			A[i] = 0
			A[i + 1] = 0
		elif a == B[i] + A[i - 1] + A[i + 1]:
			A[i - 1] = 0
			A[i + 1] = 0
		elif a == B[i] + A[i]:
			A[i] = 0
		elif a == B[i] + A[i] + A[i + 1]:
			A[i] = 0
			A[i + 1] = 0
		elif a == B[i] + A[i + 1]:
			A[i + 1] = 0
		else:
			flag = False
			break
	if flag and sum(A) == 0:
		return a
	else:
		return -1
T = int(input())
for t in range(T):
	N = int(input())
	K = list(map(int, input().strip().split()))
	B = list(map(int, input().strip().split()))
	K.append(0)
	K.append(0)
	A = [i for i in K]
	ans = -1
	if N == 1:
		ans = A[0] + B[0]
	else:
		a = fun(A, B, N, B[0])
		A = [i for i in K]
		b = fun([0] + A[1:], B, N, B[0] + A[0])
		A = [i for i in K]
		c = fun(A[:1] + [0] + A[2:], B, N, B[0] + A[1])
		A = [i for i in K]
		d = fun([0, 0] + A[2:], B, N, B[0] + A[0] + A[1])
		ans = max(a, b, c, d)
	print(ans)


t = int(input())
for ttt in range(t):
	n = int(input())
	x = input().split()
	y = input().split()
	a = []
	b = []
	ans = []
	for i in range(n):
		b.append(int(x[i]))
	for i in range(n):
		a.append(int(y[i]))
	if n == 1:
		print(a[0] + b[0])
		continue
	aa = []
	bb = []
	flag = 1
	for i in range(n):
		c = b[i]
		d = a[i]
		bb.append(c)
		aa.append(d)
	maximum = aa[0]
	for i in range(1, n - 1):
		aa[i] = aa[i] + bb[i - 1]
		if aa[i] == maximum:
			continue
		if aa[i] > maximum:
			flag = 0
			break
		if aa[i] + bb[i] == maximum:
			aa[i] = aa[i] + bb[i]
			bb[i] = 0
		elif aa[i] + bb[i + 1] == maximum:
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i + 1]
		elif aa[i] + bb[i] + bb[i + 1] == maximum:
			bb[i] = 0
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i] + bb[i + 1]
		else:
			flag = 0
			break
	if flag == 0:
		ans.append(-1)
	if flag == 1:
		aa[n - 1] = aa[n - 1] + bb[n - 1] + bb[n - 2]
		if aa[n - 1] == maximum:
			ans.append(maximum)
		else:
			ans.append(-1)
	aa = []
	bb = []
	flag = 1
	for i in range(n):
		c = b[i]
		d = a[i]
		bb.append(c)
		aa.append(d)
	maximum = aa[0] + bb[0]
	aa[0] = aa[0] + bb[0]
	bb[0] = 0
	for i in range(1, n - 1):
		aa[i] = aa[i] + bb[i - 1]
		if aa[i] == maximum:
			continue
		if aa[i] > maximum:
			flag = 0
			break
		if aa[i] + bb[i] == maximum:
			aa[i] = aa[i] + bb[i]
			bb[i] = 0
		elif aa[i] + bb[i + 1] == maximum:
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i + 1]
		elif aa[i] + bb[i] + bb[i + 1] == maximum:
			bb[i] = 0
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i] + bb[i + 1]
		else:
			flag = 0
			break
	if flag == 0:
		ans.append(-1)
	if flag == 1:
		aa[n - 1] = aa[n - 1] + bb[n - 1] + bb[n - 2]
		if aa[n - 1] == maximum:
			ans.append(maximum)
		else:
			ans.append(-1)
	aa = []
	bb = []
	flag = 1
	for i in range(n):
		c = b[i]
		d = a[i]
		bb.append(c)
		aa.append(d)
	maximum = aa[0] + bb[1]
	aa[0] = aa[0] + bb[1]
	bb[1] = 0
	for i in range(1, n - 1):
		aa[i] = aa[i] + bb[i - 1]
		if aa[i] == maximum:
			continue
		if aa[i] > maximum:
			flag = 0
			break
		if aa[i] + bb[i] == maximum:
			aa[i] = aa[i] + bb[i]
			bb[i] = 0
		elif aa[i] + bb[i + 1] == maximum:
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i + 1]
		elif aa[i] + bb[i] + bb[i + 1] == maximum:
			bb[i] = 0
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i] + bb[i + 1]
		else:
			flag = 0
			break
	if flag == 0:
		ans.append(-1)
	if flag == 1:
		aa[n - 1] = aa[n - 1] + bb[n - 1] + bb[n - 2]
		if aa[n - 1] == maximum:
			ans.append(maximum)
		else:
			ans.append(-1)
	aa = []
	bb = []
	flag = 1
	for i in range(n):
		c = b[i]
		d = a[i]
		bb.append(c)
		aa.append(d)
	maximum = aa[0] + bb[0] + bb[1]
	aa[0] = bb[0] + aa[0] + bb[1]
	bb[0] = 0
	bb[1] = 0
	for i in range(1, n - 1):
		aa[i] = aa[i] + bb[i - 1]
		if aa[i] == maximum:
			continue
		if aa[i] > maximum:
			flag = 0
			break
		if aa[i] + bb[i] == maximum:
			aa[i] = aa[i] + bb[i]
			bb[i] = 0
		elif aa[i] + bb[i + 1] == maximum:
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i + 1]
		elif aa[i] + bb[i] + bb[i + 1] == maximum:
			bb[i] = 0
			bb[i + 1] = 0
			aa[i] = aa[i] + bb[i] + bb[i + 1]
		else:
			flag = 0
			break
	if flag == 0:
		ans.append(-1)
	if flag == 1:
		aa[n - 1] = aa[n - 1] + bb[n - 1] + bb[n - 2]
		if aa[n - 1] == maximum:
			ans.append(maximum)
		else:
			ans.append(-1)
	print(max(ans))


T = int(input())
out = [0] * T
for t in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	A = list(map(int, input().split()))
	K = (sum(A) + sum(B)) / N
	if not K.is_integer():
		out[t] = -1
		continue
	C = []
	for i in range(N):
		C.append(K - A[i])
	usage = [False] * N
	if C[0] == 0:
		filler = 1
	elif B[0] == C[0]:
		usage[0] = True
	elif B[1] == C[0]:
		usage[1] = True
	elif B[0] + B[1] == C[0]:
		usage[0] = True
		usage[1] = True
	else:
		out[t] = -1
		continue
	C[0] = 0
	for i in range(1, N - 1):
		if usage[i - 1] == False:
			C[i] = C[i] - B[i - 1]
			usage[i - 1] = True
		if C[i] < 0:
			out[t] = -1
			break
		elif C[i] == 0:
			continue
		elif usage[i] == False and B[i] == C[i]:
			C[i] = 0
			usage[i] = True
		elif usage[i + 1] == False and B[i + 1] == C[i]:
			C[i] = 0
			usage[i + 1] = True
		elif not usage[i] and (not usage[i + 1]) and (B[i] + B[i + 1] == C[i]):
			C[i] = 0
			usage[i] = True
			usage[i + 1] = True
		else:
			out[t] = -1
			break
	if out[t] != -1:
		if usage[N - 2] == False:
			C[N - 1] = C[N - 1] - B[N - 2]
		if usage[N - 1] == False:
			C[N - 1] = C[N - 1] - B[N - 1]
		if C[N - 1] == 0:
			out[t] = K
for u in out:
	print(int(u))


for t in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	A = list(map(int, input().split()))
	if N == 1:
		print(B[0] + A[0])
		continue
	elif N == 2:
		ans = -1
		if B[0] + B[1] + A[1] == A[0]:
			ans = max(ans, A[0])
		if B[0] + B[1] + A[0] == A[1]:
			ans = max(ans, A[1])
		if B[0] + A[0] == A[1] + B[1]:
			ans = max(ans, A[0] + B[0])
		if B[0] + A[1] == A[0] + B[1]:
			ans = max(ans, A[1] + B[0])
		print(ans)
		continue
	l = set()
	ld = {A[0]: (), A[0] + B[0]: (0,), A[0] + B[1]: (1,), A[0] + B[0] + B[1]: (0, 1)}
	r = set()
	rd = {A[-1]: (), A[-1] + B[-1]: (N - 1,), A[-1] + B[-2]: (N - 2,), A[-1] + B[-1] + B[-2]: (N - 1, N - 2)}
	l.add(A[0])
	l.add(A[0] + B[0])
	l.add(A[0] + B[1])
	l.add(A[0] + B[0] + B[1])
	r.add(A[-1])
	r.add(A[-1] + B[-1])
	r.add(A[-1] + B[-2])
	r.add(A[-1] + B[-1] + B[-2])
	inter = sorted(list(l & r))
	inter.reverse()
	if not inter:
		print(-1)
		continue
	outer = False
	for i in inter:
		bflag = [True for _ in range(N)]
		for j in ld[i]:
			bflag[j] = False
		for j in rd[i]:
			bflag[j] = False
		f = False
		res = True
		for j in range(1, N - 1):
			if A[j] == i:
				f = True
			elif j - 1 >= 0 and bflag[j - 1] and (B[j - 1] + A[j] == i):
				f = True
				bflag[j - 1] = False
			elif j - 1 >= 0 and bflag[j - 1] and bflag[j] and (B[j - 1] + B[j] + A[j] == i):
				f = True
				bflag[j - 1] = False
				bflag[j] = False
			elif j - 1 >= 0 and j + 1 < N and bflag[j - 1] and bflag[j + 1] and (B[j - 1] + B[j + 1] + A[j] == i):
				f = True
				bflag[j - 1] = False
				bflag[j + 1] = False
			elif j - 1 >= 0 and j + 1 < N and bflag[j - 1] and bflag[j] and bflag[j + 1] and (B[j - 1] + B[j] + B[j + 1] + A[j] == i):
				f = True
				bflag[j - 1] = False
				bflag[j] = False
				bflag[j + 1] = False
			elif bflag[j] and B[j] + A[j] == i:
				f = True
				bflag[j] = False
			elif j + 1 < N and bflag[j + 1] and (B[j + 1] + A[j] == i):
				f = True
				bflag[j + 1] = False
			elif j + 1 < N and bflag[j + 1] and bflag[j] and (B[j + 1] + B[j] + A[j] == i):
				f = True
				bflag[j] = False
				bflag[j + 1] = False
			if not f:
				res = False
				break
			f = False
		if res:
			c = 0
			for x in bflag:
				if not x:
					c += 1
				if c == len(bflag):
					print(i)
					outer = True
					break
	if not outer:
		print(-1)


import sys
f = sys.stdin

def getInts(f):
	return list(map(int, f.readline().split()))

def solve(a, b):
	n = len(a)
	total = sum(a) + sum(b)
	if total % n != 0:
		return -1
	a0 = total // n
	for i in range(n):
		if a[i] + b[i] == a0:
			continue
		if i == n - 1:
			return -1
		if a[i] > a0:
			return -1
		if a[i] == a0:
			a[i + 1] += b[i]
			continue
		elif a[i] + b[i + 1] == a0:
			b[i + 1] = 0
			a[i + 1] += b[i]
			continue
		elif a[i] + b[i] + b[i + 1] == a0:
			b[i + 1] = 0
		else:
			return -1
	return a0
t = int(f.readline())
for i in range(t):
	f.readline()
	b = getInts(f)
	a = getInts(f)
	print(solve(a, b))


def ans(a, b, k):
	i = 0
	j = 0
	f = 1
	while i < len(a) - 1:
		if i == j:
			if a[i] == k:
				i += 1
				a[i] += b[j]
				j += 1
			elif a[i] + b[j] == k:
				i += 1
				j += 1
			elif a[i] + b[j + 1] == k:
				i += 1
				a[i] += b[j]
				j += 2
			elif a[i] + b[i] + b[i + 1] == k:
				i += 1
				j += 2
			else:
				print(-1)
				f = 0
				i = 10 ** 9
		elif a[i] == k:
			i += 1
		elif a[i] + b[j] == k:
			i += 1
			j += 1
		else:
			print(-1)
			i = len(a)
			f = 0
	if f == 1:
		if sum(a[i:]) + sum(b[j:]) == k:
			print(k)
		else:
			print(-1)
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = sum(a) + sum(b)
	if k % n == 0:
		k = k // n
		if max(a) <= k and max(b) < k:
			ans(a, b, k)
		else:
			print(-1)
	else:
		print(-1)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	B = list(map(int, sys.stdin.readline().split(' ')))
	A = list(map(int, sys.stdin.readline().split(' ')))
	C = []
	Sum = 0
	for j in range(N):
		Sum += A[j] + B[j]
		C.append(0)
	Average = 0
	Average += int(Sum / N)
	for j in range(N):
		win = True
		if A[j] == Average:
			continue
		elif j - 1 >= 0 and A[j] + B[j - 1] == Average and (C[j - 1] == 0):
			A[j] += B[j - 1]
			C[j - 1] = 1
		elif j - 1 >= 0 and A[j] + B[j - 1] + B[j] == Average and (C[j - 1] == 0) and (C[j] == 0):
			A[j] += B[j - 1] + B[j]
			C[j - 1] = 1
			C[j] = 1
		elif j - 1 >= 0 and j + 1 < N and (A[j] + B[j - 1] + B[j + 1] == Average) and (C[j - 1] == 0) and (C[j + 1] == 0):
			A[j] += B[j - 1] + B[j + 1]
			C[j - 1] = 1
			C[j + 1] = 1
		elif j - 1 >= 0 and j + 1 < N and (A[j] + B[j - 1] + B[j] + B[j + 1] == Average) and (C[j - 1] == 0) and (C[j] == 0) and (C[j + 1] == 0):
			A[j] += B[j - 1] + B[j] + B[j + 1]
			C[j - 1] = 1
			C[j] = 1
			C[j + 1] = 1
		elif A[j] + B[j] == Average and C[j] == 0:
			A[j] += B[j]
			C[j] = 1
		elif j + 1 < N and A[j] + B[j + 1] == Average and (C[j + 1] == 0):
			A[j] += B[j + 1]
			C[j + 1] = 1
		elif j + 1 < N and A[j] + B[j] + B[j + 1] == Average and (C[j] == 0) and (C[j + 1] == 0):
			A[j] += B[j] + B[j + 1]
			C[j] = 1
			C[j + 1] = 1
		if A[j] != Average:
			print(-1)
			win = False
			break
	if win:
		print(Average)


t = int(input())
for _ in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	c = list(map(int, input().split()))
	a = [i for i in c]
	b = [i for i in d]
	visited = [0] * n
	lst = []
	tar = a[0]
	f = 1
	for i in range(1, n):
		temp = 0
		if not visited[i - 1]:
			a[i] += b[i - 1]
			visited[i - 1] = 1
		if a[i] == tar:
			temp = 1
		if not visited[i] and a[i] + b[i] == tar:
			temp = 1
			a[i] += b[i]
			visited[i] = 1
		try:
			if not visited[i + 1] and a[i] + b[i + 1] == tar:
				temp = 1
				a[i] += b[i + 1]
				visited[i + 1] = 1
		except:
			pass
		try:
			if not visited[i + 1] and (not visited[i]) and (a[i] + b[i] + b[i + 1] == tar):
				a[i] += b[i] + b[i + 1]
				visited[i] = 1
				visited[i + 1] = 1
				temp = 1
		except:
			pass
		if not temp:
			f = 0
			break
	for i in visited:
		if not i:
			f = 0
	if f:
		lst += [tar]
	a = [i for i in c]
	b = [i for i in d]
	visited = [0] * n
	tar = a[0] + b[0]
	visited[0] = 1
	f = 1
	for i in range(1, n):
		temp = 0
		if not visited[i - 1]:
			a[i] += b[i - 1]
			visited[i - 1] = 1
		if a[i] == tar:
			temp = 1
		if not visited[i] and a[i] + b[i] == tar:
			temp = 1
			a[i] += b[i]
			visited[i] = 1
		try:
			if not visited[i + 1] and a[i] + b[i + 1] == tar:
				temp = 1
				a[i] += b[i + 1]
				visited[i + 1] = 1
		except:
			pass
		try:
			if not visited[i + 1] and (not visited[i]) and (a[i] + b[i] + b[i + 1] == tar):
				a[i] += b[i] + b[i + 1]
				visited[i] = 1
				visited[i + 1] = 1
				temp = 1
		except:
			pass
		if not temp:
			f = 0
			break
	for i in visited:
		if not i:
			f = 0
	if f:
		lst += [tar]
	if n > 1:
		a = [i for i in c]
		b = [i for i in d]
		visited = [0] * n
		tar = a[0] + b[0] + b[1]
		visited[0] = 1
		visited[1] = 1
		f = 1
		for i in range(1, n):
			temp = 0
			if not visited[i - 1]:
				a[i] += b[i - 1]
				visited[i - 1] = 1
			if a[i] == tar:
				temp = 1
			if not visited[i] and a[i] + b[i] == tar:
				temp = 1
				a[i] += b[i]
				visited[i] = 1
			try:
				if not visited[i + 1] and a[i] + b[i + 1] == tar:
					temp = 1
					a[i] += b[i + 1]
					visited[i + 1] = 1
			except:
				pass
			try:
				if not visited[i + 1] and (not visited[i]) and (a[i] + b[i] + b[i + 1] == tar):
					a[i] += b[i] + b[i + 1]
					visited[i] = 1
					visited[i + 1] = 1
					temp = 1
			except:
				pass
			if not temp:
				f = 0
				break
		for i in visited:
			if not i:
				f = 0
		if f:
			lst += [tar]
		a = [i for i in c]
		b = [i for i in d]
		visited = [0] * n
		tar = a[0] + b[1]
		visited[1] = 1
		f = 1
		for i in range(1, n):
			temp = 0
			if not visited[i - 1]:
				a[i] += b[i - 1]
				visited[i - 1] = 1
			if a[i] == tar:
				temp = 1
			if not visited[i] and a[i] + b[i] == tar:
				temp = 1
				a[i] += b[i]
				visited[i] = 1
			try:
				if not visited[i + 1] and a[i] + b[i + 1] == tar:
					temp = 1
					a[i] += b[i + 1]
					visited[i + 1] = 1
			except:
				pass
			try:
				if not visited[i + 1] and (not visited[i]) and (a[i] + b[i] + b[i + 1] == tar):
					a[i] += b[i] + b[i + 1]
					visited[i] = 1
					visited[i + 1] = 1
					temp = 1
			except:
				pass
			if not temp:
				f = 0
				break
		for i in visited:
			if not i:
				f = 0
		if f:
			lst += [tar]
	if len(lst) == 0:
		print(-1)
	else:
		print(max(lst))


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	flag = 0
	if n == 1:
		print(a[0] + b[0])
		continue
	s = sum(a) + sum(b)
	if s % n != 0:
		print('-1')
		continue
	s = int(s / n)
	if a[0] != s:
		r = s - a[0]
		if r == b[0]:
			a[0] += b[0]
			b[0] = 0
		elif r == b[1]:
			a[0] += b[1]
			b[1] = 0
		elif r == b[0] + b[1]:
			a[0] += b[0] + b[1]
			b[0] = 0
			b[1] = 0
		else:
			print('-1')
			continue
	for j in range(1, n):
		while a[j] != s:
			if b[j - 1] != 0:
				a[j] += b[j - 1]
				b[j - 1] = 0
			else:
				r = s - a[j]
				if r == b[j]:
					a[j] += b[j]
					b[j] = 0
				elif j + 1 < n and r == b[j + 1]:
					a[j] += b[j + 1]
					b[j + 1] = 0
				elif j + 1 < n and r == b[j] + b[j + 1]:
					a[j] += b[j] + b[j + 1]
					b[j] = 0
					b[j + 1] = 0
				else:
					flag = -1
					break
		if flag == -1:
			flag = 0
			break
		if j == n - 1:
			flag = 1
	if flag:
		print(s)
	else:
		print('-1')


T = int(input())
while T > 0:
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = (sum(a) + sum(b)) / n
	s = int(s)
	for i in range(n):
		if i > 0 and i < n - 1:
			if a[i] + b[i] == s or a[i] + b[i - 1] == s or a[i] + b[i + 1] == s or (a[i] + b[i] + b[i - 1] + b[i + 1] == s) or (a[i] == s) or (a[i] + b[i] + b[i + 1] == s) or (a[i] + b[i] + b[i - 1] == s) or (a[i] + b[i - 1] + b[i + 1] == s):
				f = 1
			else:
				f = 0
				break
		elif i == 0 and i + 1 < n - 1:
			if a[i] + b[i] == s or a[i] + b[i + 1] == s or a[i] + b[i] + b[i + 1] == s or (a[i] == s):
				f = 1
			else:
				f = 0
				break
		elif i == 0 and i + 1 > n - 1:
			if a[i] + b[i] == s or a[i] == s:
				f = 1
			else:
				f = 0
				break
		elif i == n - 1:
			if a[i] + b[i] == s or a[i] + b[i - 1] == s or a[i] + b[i - 1] + b[i] == s or (a[i] == s):
				f = 1
			else:
				f = 0
				break
	if f == 1:
		print(s)
	else:
		print('-1')
	T = T - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print(a[0] + b[0])
		continue
	if (sum(a) + sum(b)) % n:
		print(-1)
	else:
		flag = 1
		m = (sum(a) + sum(b)) // n
		hash = [1] * n
		if b[0] + a[0] == m and hash[0]:
			hash[0] = 0
		elif b[0] + a[1] == m and hash[1]:
			hash[1] = 0
		elif b[0] + a[0] + a[1] == m and hash[1] and hash[0]:
			(hash[0], hash[1]) = (0, 0)
		elif b[0] != m:
			print(-1)
			continue
		for i in range(1, n - 1):
			if b[i] == m:
				continue
			if b[i] + a[i - 1] == m and hash[i - 1]:
				hash[i - 1] = 0
				continue
			if b[i] + a[i - 1] + a[i] == m and hash[i - 1] and hash[i]:
				(hash[i - 1], hash[i]) = (0, 0)
				continue
			if b[i] + a[i - 1] + a[i] + a[i + 1] == m and hash[i] and hash[i - 1] and hash[i + 1]:
				(hash[i - 1], hash[i], hash[i + 1]) = (0, 0, 0)
				continue
			if b[i] + a[i - 1] + a[i + 1] == m and hash[i - 1] and hash[i + 1]:
				(hash[i - 1], hash[i + 1]) = (0, 0)
				continue
			if b[i] + a[i] == m and hash[i]:
				hash[i] = 0
				continue
			if b[i] + a[i] + a[i + 1] == m and hash[i] and hash[i + 1]:
				(hash[i], hash[i + 1]) = (0, 0)
				continue
			if b[i] + a[i + 1] == m and hash[i + 1]:
				hash[i + 1] = 0
				continue
			flag = 0
			print(-1)
			break
		if flag:
			if b[n - 1] + a[n - 1] == m and hash[n - 1]:
				print(m)
			elif b[n - 1] + a[n - 2] == m and hash[n - 2]:
				print(m)
			elif b[n - 1] + a[n - 2] + a[n - 1] == m and hash[n - 2] and hash[n - 1]:
				print(m)
			elif b[n - 1] == m:
				print(m)
			else:
				print(-1)


for _ in range(int(input())):
	n = int(input())
	B = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	sumi = sum(A) + sum(B)
	if n == 1:
		print(sumi)
		continue
	if sumi % n != 0:
		print(-1)
		continue
	else:
		sim = sumi // n
	i = 0
	while i < n:
		curr = A[i]
		if curr == sim:
			i += 1
			continue
		chk = 0
		if i != 0 and i != n - 1:
			if B[i - 1] + curr == sim:
				B[i - 1] = 0
				i += 1
				chk = 1
			elif B[i - 1] + B[i] + curr == sim:
				B[i - 1] = 0
				B[i] = 0
				i += 1
				chk = 1
			elif B[i - 1] + B[i + 1] + curr == sim:
				B[i - 1] = 0
				B[i + 1] = 0
				i += 1
				chk = 1
			elif B[i - 1] + B[i + 1] + B[i] + curr == sim:
				B[i - 1] = 0
				B[i] = 0
				B[i + 1] = 0
				i += 1
				chk = 1
		elif i == 0:
			if B[i] + curr == sim:
				B[i] = 0
				i += 1
				chk = 1
			elif B[i] + B[i + 1] + curr == sim:
				B[i] = 0
				B[i + 1] = 0
				i += 1
				chk = 1
			elif B[i + 1] + curr == sim:
				B[i + 1] = 0
				i += 1
				chk = 1
		elif i == n - 1:
			if B[i - 1] + curr == sim:
				B[i - 1] = 0
				i += 1
				chk = 1
			elif B[i - 1] + B[i] + curr == sim:
				B[i - 1] = 0
				B[i] = 0
				i += 1
				chk = 1
		if chk == 0:
			break
	if chk == 0:
		print(-1)
		continue
	else:
		print(sim)


def tetris():
	n = int(input())
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	allsum = sum(a) + sum(b)
	number = allsum / n
	if allsum % n != 0:
		return -1
	for i in range(n):
		if i > 0:
			a[i] += b[i - 1]
			b[i - 1] = 0
		if i == n - 1:
			a[i] += b[i]
			b[i] = 0
			if a[i] != number:
				return -1
			return number
		if a[i] > number:
			return -1
		if a[i] == number:
			continue
		if number - a[i] < b[i]:
			if number - a[i] != b[i + 1]:
				return -1
			a[i] += b[i + 1]
			b[i + 1] = 0
			continue
		if number - a[i] == b[i]:
			a[i] += b[i]
			b[i] = 0
			continue
		if number - a[i] > b[i]:
			if a[i] + b[i + 1] == number:
				a[i] += b[i + 1]
				b[i + 1] = 0
				continue
			a[i] += b[i]
			b[i] = 0
			if a[i] + b[i + 1] != number:
				return -1
			a[i] += b[i + 1]
			b[i + 1] = 0
t = int(input())
for cases in range(t):
	print(int(tetris()))


for t in range(int(input())):
	n = int(input())
	b = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	s = sum(a) + sum(b)
	if not s % n == 0:
		print(-1)
		continue
	x = s // n
	for i in range(n):
		if a[i] < x:
			if i > 0 and b[i - 1]:
				a[i] += b[i - 1]
				b[i - 1] = 0
		if a[i] < x:
			if a[i] + b[i] == x:
				a[i] = x
				b[i] = 0
			elif i < n - 1 and a[i] + b[i + 1] == x:
				a[i] = x
				b[i + 1] = 0
			elif i < n - 1 and a[i] + b[i] + b[i + 1] == x:
				a[i] = x
				b[i] = 0
				b[i + 1] = 0
		if not a[i] == x or (i > 0 and b[i - 1]):
			print(-1)
			break
	else:
		print(x)


T = int(input())
for t in range(T):
	N = int(input())
	B = [int(v) for v in input().split()]
	A = [int(v) for v in input().split()]
	s = sum(A) + sum(B)
	if s % N:
		print(-1)
		continue
	t = s // N
	flag = 0
	for i in range(N):
		v = t - A[i]
		if i > 0:
			v = v - B[i - 1]
		if v == 0:
			pass
		elif B[i] == v:
			B[i] = 0
		elif i < N - 1 and B[i + 1] == v:
			B[i + 1] = 0
		elif i < N - 1 and B[i] + B[i + 1] == v:
			B[i] = B[i + 1] = 0
		else:
			flag = 1
			break
	if flag:
		print(-1)
	else:
		print(t)


def get_options(i, n):
	if n == 1:
		return [[i]]
	if n == 2:
		return [[0], [1], [0, 1]]
	if n >= 3:
		if i == 0:
			return [[i], [i, i + 1], [i + 1]]
		elif i == n - 1:
			return [[i - 1], [i - 1, i], [i]]
		else:
			return [[i - 1], [i - 1, i], [i - 1, i + 1], [i - 1, i, i + 1], [i], [i, i + 1], [i + 1]]

def are_unused(indices, used):
	for each_val in indices:
		if used[each_val]:
			return False
	return True

def are_summable(indices, req, b):
	sum = 0
	for each_val in indices:
		sum += b[each_val]
	if sum == req:
		return True
	return False
t = int(input())
while t:
	n = int(input())
	b = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	total = sum(a) + sum(b)
	if total % n == 0:
		sahi = True
		each_val = int(total / n)
		used = [False] * n
		for i in range(n):
			req = each_val - a[i]
			if req > 0:
				options = get_options(i, n)
				for each_option in options:
					if are_unused(each_option, used) and are_summable(each_option, each_val - a[i], b):
						for each_index in each_option:
							used[each_index] = True
						break
		if False in used:
			sahi = False
		if not sahi:
			print(-1)
		else:
			print(int(each_val))
	else:
		print(-1)
	t -= 1


def maxequal(candidate, not_fall_on, cur_pos):
	print(cur_pos)
	if cur_pos >= N:
		if True in not_fall_on:
			return -1
		else:
			return candidate
	if candidate == A[cur_pos]:
		return maxequal(candidate, not_fall_on, cur_pos + 1)
	fall_on = [x for x in [cur_pos - 1, cur_pos, cur_pos + 1] if x >= 0 and x < N and not_fall_on[x]]
	tmp = -1
	if cur_pos == 0:
		tmp = max(tmp, maxequal(A[0], not_fall_on, cur_pos + 1))
	if len(fall_on) > 0:
		for i in fall_on:
			val = A[cur_pos] + B[i]
			if candidate == 0 or val == candidate:
				not_fall_on[i] = False
				tmp = max(tmp, maxequal(val, not_fall_on, cur_pos + 1))
				not_fall_on[i] = True
	if len(fall_on) > 1:
		for i in range(len(fall_on) - 1):
			for j in range(i + 1, len(fall_on)):
				val = A[cur_pos] + B[fall_on[i]] + B[fall_on[j]]
				if candidate == 0 or val == candidate:
					not_fall_on[fall_on[i]] = not_fall_on[fall_on[j]] = False
					tmp = max(tmp, maxequal(val, not_fall_on, cur_pos + 1))
					not_fall_on[fall_on[i]] = not_fall_on[fall_on[j]] = True
	if len(fall_on) > 2:
		val = A[cur_pos] + B[fall_on[0]] + B[fall_on[1]] + B[fall_on[2]]
		if candidate == 0 or val == candidate:
			not_fall_on[fall_on[0]] = not_fall_on[fall_on[1]] = not_fall_on[fall_on[2]] = False
			tmp = max(tmp, maxequal(val, not_fall_on, cur_pos + 1))
			not_fall_on[fall_on[0]] = not_fall_on[fall_on[1]] = not_fall_on[fall_on[2]] = True
	return tmp
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	B = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	avg = (sum(A) + sum(B)) / N
	if avg % 1 != 0:
		print(-1)
	else:
		avg = int(avg)
		not_fall_on = [True for x in range(N)]
		Flag = True
		for i in range(N):
			if Flag:
				yetnotfound = True
				if A[i] != avg:
					fall_on = [x for x in [i - 1, i, i + 1] if x >= 0 and x < N and not_fall_on[x]]
					L = len(fall_on)
					if L > 0 and yetnotfound:
						for j in range(L):
							if B[fall_on[j]] + A[i] == avg:
								yetnotfound = False
								not_fall_on[fall_on[j]] = False
								break
					if L > 1 and yetnotfound:
						for j in range(L - 1):
							for k in range(j + 1, L):
								if B[fall_on[j]] + B[fall_on[k]] + A[i] == avg:
									yetnotfound = False
									not_fall_on[fall_on[j]] = not_fall_on[fall_on[k]] = False
									break
					if L > 2 and yetnotfound:
						if B[fall_on[0]] + B[fall_on[1]] + B[fall_on[2]] + A[i] == avg:
							yetnotfound = False
							not_fall_on[fall_on[0]] = not_fall_on[fall_on[1]] = not_fall_on[fall_on[2]] = False
							break
					if yetnotfound:
						Flag = False
		if Flag:
			print(avg)
		else:
			print(-1)


def test(n, a, b):
	s = sum(a) + sum(b)
	if s % n > 0:
		return -1
	v = s // n
	for i in range(n - 1):
		if a[i] == v:
			a[i + 1] += b[i]
		elif a[i] + b[i] == v:
			pass
		elif a[i] + b[i + 1] == v:
			a[i + 1] += b[i]
			b[i + 1] = 0
		elif a[i] + b[i] + b[i + 1] == v:
			b[i + 1] = 0
		else:
			return -1
	return v
T = int(input())
for t in range(T):
	n = int(input())
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(test(n, a, b))