Arya and Aryan live in a country called Nadaca. Nadaca consists of $N$ cities numbered $1$ through $N$, which are connected by some bidirectional roads. Each road has a positive (not necessarily integer) length. Arya lives in city $1$ and Aryan lives in city $N$.
Arya claims that for each city $v$, the shortest path from city $1$ to city $v$ has length $a_v$. Aryan does not disagree, but claims that for each city $v$, the shortest path from city $N$ to city $v$ has length $b_v$. You are the wisest person they know, so they asked you to tell them if it is possible for their claims to be true, i.e. if a road network which fully satisfies their claims exists. Help them!

-----Input-----
- The first line of the input contains a single 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$.
- The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.
- The third line contains $N$ space-separated integers $b_1, b_2, \ldots, b_N$.

-----Output-----
For each test case, print a single line containing the string "Yes" if Arya's and Aryan's claims can be true or "No" otherwise.

-----Constraints-----
- $1 \le T \le 10^3$
- $2 \le N \le 10^6$
- $0 \le a_i, b_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $10^3$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
3
0 1 1
1 1 0
3
0 1 5
5 1 0

-----Example Output-----
Yes
No

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
for _ in range(int(input())):
 n=int(input())
 a=list(map(int, input().split()))
 b=list(map(int, input().split()))

 if a[0]!=0 or b[-1]!=0 or a[-1]!=b[0]:
  print('No')
  
 else:
  ab=b[0]
  flag=0
  for i in range(1, n-1):
   if a[i]==0 or b[i]==0:
    print('No')
    flag=1 
    break
   
   elif a[i]+b[i]<ab:
    print('No')
    flag=1 
    break
   
   elif a[i]>ab+b[i] or b[i]>ab+a[i]:
    print('No')
    flag=1 
    break
   
  if flag==0:
   print('Yes')

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 a=list(map(int, input().split()))
 b=list(map(int, input().split()))

 if a[0]!=0 or b[-1]!=0 or a[-1]!=b[0]:
  print('No')
  
 else:
  ab=b[0]
  flag=0
  for i in range(1, n-1):
   if a[i]==0 or b[i]==0:
    print('No')
    flag=1 
    break
   
   elif a[i]+b[i]<ab:
    print('No')
    flag=1 
    break
   
   elif a[i]>ab+b[i] or b[i]>ab+a[i]:
    print('No')
    flag=1 
    break
   
  if flag==0:
   print('Yes')

for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split(" ")))
 B=list(map(int,input().split(" ")))
 ans="Yes"

 a_1=A[0]
 a_n=A[n-1]
 b_1=B[0]
 b_n=B[n-1]

 if a_1!=0 or b_n!=0 or a_n!=b_1 :
  ans="No"
 else:
  for i in range(1,n-1):
   if A[i]==0 or B[i]==0 :
    ans="No"
    break
   elif b_1+A[i]<B[i]:
    ans="No"
    break
   elif A[i]+B[i]<b_1:
    ans="No"
    break
   elif B[i]+b_1<A[i]:
    ans="No"
    break
   else:
    pass

 print(ans)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split(" ")))
 B=list(map(int,input().split(" ")))
 ans="Yes"

 a_1=A[0]
 a_n=A[n-1]
 b_1=B[0]
 b_n=B[n-1]

 if a_1!=0 or b_n!=0 or a_n!=b_1 :
  ans="No"
 else:
  for i in range(1,n-1):
   if A[i]==0 or B[i]==0 :
    ans="No"
    break
   elif b_1+A[i]<B[i]:
    ans="No"
    break
   elif A[i]+B[i]<b_1:
    ans="No"
    break
   elif B[i]+b_1<A[i]:
    ans="No"
    break
   else:
    pass

 print(ans)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split(" ")))
 B=list(map(int,input().split(" ")))
 ans="Yes"

 a_1=A[0]
 a_n=A[n-1]
 b_1=B[0]
 b_n=B[n-1]

 if a_1!=0 or b_n!=0 or a_n!=b_1 :
  ans="No"
 else:
  for i in range(1,n-1):
   if A[i]==0 or B[i]==0 :
    ans="No"
    break
   elif b_1+A[i]<B[i]:
    ans="No"
    break
   elif A[i]+B[i]<b_1:
    ans="No"
    break
   elif B[i]+b_1<A[i]:
    ans="No"
    break
   else:
    pass

 print(ans)

# cook your dish here
for _ in range(int(input())):
 N=int(input())
 A=list(map(int, input().split()))
 B=list(map(int, input().split()))

 if A[0]!=0 or B[N-1]!=0 or A[N-1]!=B[0]:
  print('No')
  continue

 ans='Yes'
 for i in range(N):
  if i!= 0 and A[i]==0:
   ans='No'
   break
  if i!=N-1 and B[i]==0:
   ans='No'
   break
  if A[i]+B[i]<B[0] or A[i]+B[0]<B[i] or B[i]+B[0]<A[i]:
   ans='No'
   break
 print(ans)



def calculate_min_path(A,B):
 if A[0] != 0 or B[n-1] != 0:
  return False
 
 if A[n-1] != B[0]:
  return False
  
 for i in range(1,n-1):
  a, b, c = A[i], A[n-1], B[i]
  if a+b < c or a+c < b or b+c < a or a*b*c == 0:
   return False
 return True
 
t=int(input())
for i in range(t):
 n=int(input())
 A = list(map(int, input().split()))
 B = list(map(int, input().split()))
 
 if calculate_min_path(A,B):
  print("Yes")
 else:
  print("No")


def calculate_min_path(A,B):
 flag = 1
 if A[0] != 0 or B[n-1] != 0:
  print("No")
  return
 
 if A[n-1] != B[0]:
  print("No")
  return
  
 for i in range(1,n-1):
  a = A[i]
  b = A[n-1]
  c = B[i]
  
  if a > 0 and b > 0 and c > 0:
   if a+b < c or a+c < b or b+c < a:
    flag = 0
    break
  else:
   flag = 0
   break
 
  
 if flag == 1:
  print("Yes")
 else:
  print("No")
t=int(input())
for i in range(t):
 n=int(input())
 A = list(map(int, input().split()))
 B = list(map(int, input().split()))
 

 calculate_min_path(A,B)

def check_claim(A, B, n):
 if A[0] or B[-1]:
  return False
 if A[-1] != B[0]:
  return False
 if n == 2:
  return True
 for i in range(1, n-1):
  l1, l2, l3 = B[0], A[i], B[i]
  if l1 > l2+l3 or l2 > l1+l3 or l3 > l1+l2 or l1*l2*l3 == 0:
   return False
 return True

t = int(input())
for test in range(t):
 n = int(input())
 A = [int(x) for x in input().split()]
 B = [int(x) for x in input().split()]
 if check_claim(A, B, n):
  print("Yes")
 else:
  print("No")

# cook your dish here
for i in range(int(input())):
 n=int(input())
 x=0
 l1=list(map(float,input().split()))
 l2=list(map(float,input().split()))
 if l1[0]==0 and l2[n-1]==0 and l1[n-1]==l2[0]:
  for j in range(1,n-1):
   if(l1[j]==0 or l2[j]==0):
    x=1
    break
   if l2[0]>(l1[j]+l2[j]):
    x=1 
    break
   if l1[j]>(l2[j]+l2[0]):
    x=1
    break
   if l2[j]>(l1[j]+l2[0]):
    x=1
    break
 else:
  x=1
 if x==0:
  print("Yes")
 else:
  print("No")

for _ in range(int(input())):
 n = int(input())
 a= list(map(int,input().split()))
 b = list(map(int,input().split()))
 fl =1
 if(a[0]!=0 or b[n-1]!=0 or a[n-1]!=b[0]):
  fl=0
 s =b[0]
 if(fl):
  for i in range(n):
   if(i!=0 and i!= n-1):
    if(a[i]==0 or b[i]==0):
     fl=0
     break


   if(a[i]+b[i] < s):
    fl=0
    break
   if(s+b[i] < a[i]):
    fl =0
    break
   if(s+a[i] <b[i]):
    fl=0
    break
 if(fl):
  print("Yes")
 else:
  print("No")

t=int(input())
for _ in range(t):
 n=int(input())
 aa=list(map(int,input().split()))
 bb=list(map(int,input().split()))
 if aa[0]!=0 or bb[-1]!=0:
  print("No")
  continue
 if aa[-1]!=bb[0]:
  print("No")
  continue
 if 0 in aa[1:] or 0 in bb[:n-1]:
  print("No")
  continue
 
 ma=aa[-1]
 ans="Yes"
 for i in range(1,n-1):
  if aa[i]+bb[i]<ma:
   ans="No"
  if aa[-1]+bb[i]<aa[i]:
   ans="No"
  if aa[i]+bb[0]<bb[i]:
   ans="No"
 print(ans)


t = int(input())
for _ in range(t):
 n = int(input())
 a1 = input()
 b1 = input()
 a = list(map(int, a1.split()))
 b = list(map(int, b1.split()))
 c1 = a.count(0)
 c2 = b.count(0)
 flag = False
 if c1 == 1 and c2 == 1 and a[n-1] == b[0]:
  k = a[n-1]
  for i in range(1, n-1):
   m = a[i]
   n = b[i]
   if k <= m + n and m<=k+n and n<=k+m:
    flag = False
   else:
    flag = True
    break
  if flag:
   print("No")
  else:
   print("Yes")
 else:
  print("No")

def istriangle(a, b, c):
 if a <= 0 or b <= 0 or c <= 0:
  return False
 if (a + b < c) or (a + c < b) or (b + c < a):
  return False
 else:
  return True


def valid(a, b, n):
 if a[0] != 0 or b[-1] != 0 or a[-1] != b[0]:
  return False
 for i in range(1, n - 1):
  if not istriangle(a[-1], a[i], b[i]):
   return False
 return True


for i in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 b = list(map(int, input().split()))
 if valid(a, b, n):
  print('Yes')
 else:
  print('No')

for _ in range(int(input())):
 n = int(input())
 a = [int(x) for x in input().split()]
 b = [int(x) for x in input().split()]
 flag = 1
 if a[0]!=0 or b[n-1]!=0:
  flag = 0
 if a[n-1]!=b[0]:
  flag = 0
 for i in range(1, n-1):
  if a[i]==0 or b[i]==0:
   flag = 0
  if a[i]+b[i]<b[0]:
   flag = 0
  if b[0]+a[i]<b[i]:
   flag = 0
  if b[i]+b[0]<a[i]:
   flag = 0
 if flag==1:
  print('Yes')
 else:
  print('No')


t = int(input())
for _ in range(t):
 n = int(input())
 a = list(map(int, input().split()))
 b = list(map(int, input().split()))
 if a[0]!=0 or b[n-1]!=0 or a[n-1]!=b[0] or b[0]==0:
  print("No")
 else:
  flag=0
  for i in range(n):
   if (a[i]+b[i]<b[0] or a[i]+b[0]<b[i] or b[i]+b[0]<a[i]):
    flag=1
    break
  if flag==1:
   print("No")
  else:
   print("Yes")
  


# cook your dish here
try:
 t = int(input())
 for case in range(t):
  n = int(input())
  a = [int(i) for i in input().split()]
  b = [int(i) for i in input().split()]
  yes = True
  if a[0] != 0 or b[n - 1] != 0:
   print("No")
   yes = False
  elif a[n - 1] != b[0]:
   print("No")
   yes = False
  else:
   for edge in range(1, n - 1):
    if a[edge] == 0 or b[edge] == 0:
     print("No")
     yes = False
     break
    elif a[edge] + b[edge] < b[0]:
     print("No")
     yes = False
     break
    elif a[edge] + b[0] < b[edge]:
     print("No")
     yes = False
     break
    elif a[n - 1] + b[edge] < a[edge]:
     print("No")
     yes = False
     break
  if yes:
   print("Yes")
except EOFError:
 pass

def check(n, a, b):
 for i in range(1, n): 
  if a[i] == 0: return False
 for i in range(n-1): 
  if b[i] == 0: return False
 if a[-1] != b[0] or a[0] != 0 or b[-1] != 0: return False
 else:
  d = b[0]
  for i in range(1, n-1):
   if d > a[i] + b[i]: return False
  for i in range(1, n-1):
   if a[i] > d + b[i]: return False
   if b[i] > d + a[i]: return False
 return True

for _ in range(int(input())):
 n = int(input())
 a = [int(i) for i in input().split()]
 b = [int(i) for i in input().split()]

 if check(n, a, b): print('Yes')
 else: print('No')



t = int(input())

for m in range(t):

 n = int(input())
 l1 = list(map(int,input().split()))
 l2 = list(map(int,input().split()))
 flag = 0
 if l1[0]!=0 or l1[-1] == 0 or l2[0] == 0 or l2[-1]!=0 or l1[-1]!=l2[0]:
  flag = 1

 if flag!=1:
  for i in range(1,n-1):
   if l1[i]+l2[i]<l1[-1]:
    flag = 1
    break
   if l1[-1]+l2[i]<l1[i]:
    flag = 1
    break
   if l1[-1]+l1[i]<l2[i]:
    flag = 1
    break
 if flag == 0:
  print('Yes')
 else:
  print('No')