Grigory has $n$ magic stones, conveniently numbered from $1$ to $n$. The charge of the $i$-th stone is equal to $c_i$.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index $i$, where $2 \le i \le n - 1$), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge $c_i$ changes to $c_i' = c_{i + 1} + c_{i - 1} - c_i$.

Andrew, Grigory's friend, also has $n$ stones with charges $t_i$. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory's stones into charges of corresponding Andrew's stones, that is, changes $c_i$ into $t_i$ for all $i$?


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of magic stones.

The second line contains integers $c_1, c_2, \ldots, c_n$ ($0 \le c_i \le 2 \cdot 10^9$) — the charges of Grigory's stones.

The second line contains integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 2 \cdot 10^9$) — the charges of Andrew's stones.


-----Output-----

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".


-----Examples-----
Input
4
7 2 4 12
7 15 10 12

Output
Yes

Input
3
4 4 4
1 2 3

Output
No



-----Note-----

In the first example, we can perform the following synchronizations ($1$-indexed):  First, synchronize the third stone $[7, 2, \mathbf{4}, 12] \rightarrow [7, 2, \mathbf{10}, 12]$.  Then synchronize the second stone: $[7, \mathbf{2}, 10, 12] \rightarrow [7, \mathbf{15}, 10, 12]$. 

In the second example, any operation with the second stone will not change its charge.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

def dif(x):
	c = []
	for i in range(n-1):
		c.append(x[i+1] - x[i])
	return c

if list(sorted(dif(a))) == list(sorted(dif(b))) and a[0] == b[0] and a[n-1] == b[n-1]:
	print('Yes')
else:
	print('No')

from sys import setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

n = read()
c = reads()
t = reads()

if c[0] != t[0] or c[-1] != t[-1]:
  print("No"); return

dc = [c[k+1] - c[k] for k in range(n-1)]
dt = [t[k+1] - t[k] for k in range(n-1)]

if sorted(dc) == sorted(dt):
  print("Yes")
else:
  print("No")

def __starting_point():    
    n = int(input())
    c = input().split()
    t = input().split()
    for i in range(n):
        c[i] = int(c[i])
        t[i] = int(t[i])
    
    d = [0 for i in range(n-1)]
    s = [0 for i in range(n-1)]
    for i in range(n-1):
        d[i] = c[i+1]-c[i]
        s[i] = t[i+1]-t[i]
    d.sort()
    s.sort()
    
    index = 0
    same = True
    while(same and index < n-1):
        if d[index] == s[index]:
            index += 1
        else:
            same = False
            
    if not c[0] == t[0]:
        same = False
    if not c[n-1] == t[n-1]:
        same = False
    
    if same:
        print("Yes")
    else:
        print("No")
    

__starting_point()

n = int(input())
C = [int(a) for a in input().split()]
T = [int(a) for a in input().split()]

CC = [C[i+1]-C[i] for i in range(n-1)]
TT = [T[i+1]-T[i] for i in range(n-1)]

if C[0] == T[0] and C[-1] == T[-1] and sorted(CC) == sorted(TT):
    print("Yes")
else:
    print("No")


n=int(input())
c=list(map(int,input().split()))
t=list(map(int,input().split()))
cdiffs=[c[i+1]-c[i] for i in range(n-1)]
tdiffs=[t[i+1]-t[i] for i in range(n-1)]
if sorted(cdiffs)==sorted(tdiffs) and t[0]==c[0]:
    print("Yes")
else:
    print("No")

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = []
y = []
for i in range(n-1):
    x.append(a[i+1]-a[i])
for i in range(n-1):
    y.append(b[i+1]-b[i])
x.sort()
y.sort()
# print(x,y)
if x == y and a[0] == b[0] and a[n-1] == b[n-1]:
    print("Yes")
else:
    print("No")


N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
S=[A[i]-A[i-1] for i in range(1,N)]
T=[B[i]-B[i-1] for i in range(1,N)]
S.sort()
T.sort()
if A[0]==B[0] and A[N-1]==B[N-1] and S==T:
    print('Yes')
else:
    print('No')

def get(l):
    res = {}
    for i in range(1, n):
        if l[i] - l[i - 1] in res:
            res[l[i] - l[i - 1]] += 1
        else:
            res[l[i] - l[i - 1]] = 1
    return res


n, a, b = int(input()), [int(_) for _ in input().split()], [int(_) for _ in input().split()]
ma, mb = get(a), get(b)
print("Yes" if ma == mb and a[0] == b[0] and a[-1] == b[-1] else "No")

(lambda N,c,t:print('Yes'if c[0]==t[0]and c[-1]==t[-1]and sorted(c[i]-c[i+1]for i in range(N-1))==sorted(t[i]-t[i+1]for i in range(N-1))else'No'))(int(input()),list(map(int,input().split())),list(map(int,input().split())))

def get(l):
    res = []
    for i in range(1, n):
        res.append(l[i] - l[i - 1])
    res.sort()
    return res


n, a, b = int(input()), [int(_) for _ in input().split()], [int(_) for _ in input().split()]
ma, mb = get(a), get(b)
print("Yes" if ma == mb and a[0] == b[0] and a[-1] == b[-1] else "No")

import sys
n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))

if c[0] != t[0] or c[n-1] != t[n-1]:
	print("No")
	return
if n == 2:
	print("Yes")
	return
g1 = [c[i+1] - c[i] for i in range(n-1)]
g2 = [t[i+1] - t[i] for i in range(n-1)]
if sorted(g1) == sorted(g2):
	print("Yes")
else:
	print("No")

n = int(input())

L = [int(x) for x in input().split()]

S = [int(x) for x in input().split()]

D1 = [0]
D2 = [0]

for i in range(n-1):
    D1.append(L[i+1]-L[i])
    D2.append(S[i+1]-S[i])

D1.sort()
D2.sort()
if (D1 == D2) and (L[0] == S[0]):
    print('Yes')
else:
    print('No')

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=[]
y=[]
for i in range(1,n):
    x.append(a[i]-a[i-1])
for i in range(1,n):
    y.append(b[i]-b[i-1])
x.sort()
y.sort()
if x==y and a[0]==b[0] and a[-1]==b[-1]:
    print("Yes")
else:
    print("No")

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

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

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


n=nn()

Gs=lm()

As=lm()

diffsG=[Gs[i]-Gs[i-1] for i in range(1,n)]

diffsA=[As[i]-As[i-1] for i in range(1,n)]


diffsG.sort()

diffsA.sort()

if Gs[0]==As[0] and diffsG==diffsA:
	print('Yes')
else:
	print('No')



n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
v = []
v1 = []
if c[0] != t[0] and c[n-1] != t[n-1]:
    print('No')
else:
    for _ in range(n-1):
        v.append(c[_+1]-c[_])
        v1.append(t[_+1]-t[_])
    v.sort()
    v1.sort()
    if v != v1:
        print('No')
    else:
        print('Yes')


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def deltas(a):
	r = [0]*(len(a)-1)
	for i in range(0,len(a)-1):
		r[i] = a[i+1]-a[i]
	r.sort()
	return r

n = mint()
a = list(mints())
b = list(mints())
print("Yes") if deltas(a) == deltas(b) and a[0] == b[0] else print("No")



# -*- coding: utf-8 -*-
# @Date    : 2019-02-08 08:18:25
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

from sys import stdin

max_val=int(10e12)
min_val=int(-10e12)

def read_int()     : return int(stdin.readline())
def read_ints()    : return [int(x) for x in stdin.readline().split()]
def read_str()     : return input()
def read_strs()    : return [x for x in stdin.readline().split()]

nb_elements = int(input())
first = [int(x) for x in input().split()]
secon = [int(x) for x in input().split()]
if first[-1] != secon[-1] or first[0] != secon[0]:
    print("No")
else:
    first_1 = [y - x for x, y in zip(first, first[1:])]
    secon_1 = [y - x for x, y in zip(secon, secon[1:])]
    #print(first_1, secon_1)
    print(["No", "Yes"][sorted(first_1) == sorted(secon_1)])


n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Diff1 = [A[i]-A[i-1] for i in range(1,n)]
Diff2 = [B[i]-B[i-1] for i in range(1,n)]
Diff1.sort()
Diff2.sort()
if A[0] == B[0] and B[-1] == A[-1] and Diff1 == Diff2:
    print("Yes")
else:
    print("No")
    



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

n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
d = lambda x: sorted(x[i + 1] - x[i] for i in range(n - 1))
print('Yes' if c[0] == t[0] and d(c) == d(t) else 'No')

import os
import sys
from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint
from bisect import *
if(os.getcwd() == 'C:\\Users\\User\\Desktop\\python\\Prog'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
# print(os.getcwd())


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


n = rI()[0]
c = rI()
t = rI()


def rec(c):
    for i in range(1, len(c)):
        print(c[i] - c[i - 1], end=' ')
    print()


rt = []
rc = []
for i in range(1, len(c)):
    rc.append(c[i] - c[i - 1])
    rt.append(t[i] - t[i - 1])


rt.sort()
rc.sort()

if(rt == rc and c[0] == t[0]):
    print('Yes')
else:
    print('No')


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))

c_diffs = [c[i] - c[i - 1] for i in range(1, n)]
t_diffs = [t[i] - t[i - 1] for i in range(1, n)]

print('Yes' if c[0] == t[0] and c[-1] == t[-1] and sorted(c_diffs) == sorted(t_diffs) else 'No')