Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def resolve():
    S=input()
    T=input()
    for i in range(len(S)):
        s=S[i]
        S=S.replace(s,'A')
        S=S.replace(T[i],s)
        S=S.replace('A',T[i])
    if S==T:
        print('Yes')
    else:
        print('No')
resolve()

### FIXED CODE ###

def resolve():
    S=input()
    T=input()
    a,b={},{}
    for s,t in zip(S,T):
        if a.setdefault(s,t)!=t :
            print('No')
            return()
        if b.setdefault(t,s)!=s :
            print('No')
            return()
    print('Yes')
resolve()
### BUGGY CODE ###

S = str(input())

DP = list = [[0] * 13 for i in range(len(S))]

for i in reversed(range(len(S))):

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * (10 ** (len(S) - 1 - i))) % 13] = (DP[i][(j + int(S[i]) * (
                                10 ** (len(S) - 1 - i))) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * (10 ** (len(S) - 1 - i))) % 13] = (DP[i][
                                                                              (j + k * (10 ** (len(S) - 1 - i))) % 13] +
                                                                          DP[i + 1][j]) % 1000000007

print(DP[0][5])



### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

def construct_table(n, s):
    table = [-1] * (n + 1)
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = table[j]
        j += 1
        table[i + 1] = j
    return table


s = input()
t = input()
n = len(s)
m = len(t)
s2 = s * ((max(m, n) + m) // n + 1)
tb = construct_table(m, t)
l = [False] * n
i = 0
j = 0
while i < n:
    if t[j] != s2[i + j]:
        i += j - tb[j]
        if j > 0:
            j = tb[j]
    else:
        j += 1
        if j == m:
            l[i] = True
            i += j - tb[j]
            j = tb[j]
v = [0] * n
for i in range(n):
    tmp = i
    r = 0
    while l[i]:
        t = i
        i = (i - m) % n
        v[i] = v[t] + 1
        if i == tmp:
            print(-1)
            exit(0)
print(max(v))


### FIXED CODE ###

def construct_table(n, s):
    table = [-1] * (n + 1)
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = table[j]
        j += 1
        table[i + 1] = j
    return table


s = input()
t = input()
n = len(s)
m = len(t)
s2 = s * ((max(m, n) + m) // n + 1)
tb = construct_table(m, t)
l = [False] * n
i = 0
j = 0
while i < n:
    if t[j] != s2[i + j]:
        i += j - tb[j]
        if j > 0:
            j = tb[j]
    else:
        j += 1
        if j == m:
            l[i] = True
            i += j - tb[j]
            j = tb[j]
inv = [0] * n
for i in range(n):
    if l[i]:
        t = (i + m) % n
        i = t
        inv[t] += 1
ans = 0
v = [0] * n
for i in range(n):
    if inv[i] == 0:
        v[i] = 1
        r = 0
        while l[i]:
            r += 1
            t = (i + m) % n
            v[t] = 1
            i = t
        ans = max(ans, r)
if 0 in v:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
x=input()
xint=int(x, 2)
ones=0
for i in range(n):
  if x[i]=='1':
    ones+=1
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=xint+pow(2,n-1-i)
    temp1=ones+1
  else:
    temp=xint-pow(2,n-1-i)
    temp1=ones-1
  ans=0
  while temp!=0:
    temp=temp%temp1
    temp2=base10toN(temp,2)
    temp1=0
    for i in range(len(temp2)):
      if temp2[i]=='1':
        temp1+=1
    ans+=1
  print(ans)
    


### FIXED CODE ###

def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
pop=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  r=i%ans
  pop[i]=pop[r]+1
x=input()
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
dividemore=0
divideless=0
for i in range(n):
  if x[i]=='1':
    dividemore=(pow(2,n-1-i,ones+1)+dividemore)%(ones+1)
    if ones>=2:
      divideless=(pow(2,n-1-i,ones-1)+divideless)%(ones-1)
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=(dividemore+pow(2,n-1-i,ones+1))%(ones+1)
  else:
    if ones==1:
      ans1.append('0')
      continue
    else:
      temp=(divideless-pow(2,n-1-i,ones-1))%(ones-1)
  ans1.append(str(pop[temp]+1))
print(' '.join(ans1))
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
  query = input()
  if query == '1':
    s = s[::-1]
  else:
    t, f, c = query.split()
    if f == '1':
      s = c + s
    else:
      s = s + c
      
print(s)


### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().strip()
q = int(input())
query = [list(input().strip().split()) for _ in range(q)]

left = ''
right = ''
t = False
for ls in query:
    if len(ls) == 1:
        t = not t
    else:
        two, f, c = ls
        if f == '1':
            if t:
                right += c
            else:
                left += c
        else:
            if t:
                left += c
            else:
                right += c

if t:
    print(right[::-1] + s[::-1] + left)
else:
    print(left[::-1] + s + right)
### BUGGY CODE ###

fact = [0]*1010
for i in range(1, 1010): fact[i] = fact[i-1]+i

n, k, *a = map(int, open(0).read().split())
ans = 0
for i in range(n-k+1):
    tmp = 0
    for j in a[i:i+k]: tmp += fact[j]/j
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

fact = [0]*1010
for i in range(1, 1010): fact[i] = fact[i-1]+i

n, k, *a = map(int, open(0).read().split())
a = list(map(lambda x:fact[x]/x, a))
ans = tmp = sum(a[:k])
for i in range(n-k):
    tmp -= a[i]
    tmp += a[i+k]
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))  # 入力のときに N を使う必要はありません
ans = 1;
flg = True
A.sort()
for i in range(N):
    ans*=A[i]
    if(ans>1000000000000000000):
        flg = False
if(flg):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))  # 入力のときに N を使う必要はありません
ans = 1;
flg = True
A.sort()
for i in range(N):
    ans*=A[i]
    if(ans>1000000000000000000):
        flg = False
        break
if(flg):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

A, B = map(int, input().split())
#https://www.iandprogram.net/entry/2015/03/18/003511
def gcd(x, y):
        while y != 0:
            x, y = y, x%y
        return x
    
def factorize(n):
    factor = [1]
    for num in range(2, n*n+1):
        while n % num == 0:
            n //= num
            factor.append(num)
    return set(factor)
    
g = gcd(A, B)
f = factorize(g)
print(len(f))

### FIXED CODE ###

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())

ans = 0

for i in range(N + 1):
    t = math.floor(A * i / B) - A * math.floor(i / B)
    ans = max(ans, t)

print(ans)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))
### BUGGY CODE ###

N = int(input())
q = [sorted(list(map(int, input().split()))) for _ in range(N-1)]

ans = 0

for l in range(1, N+1):
    for r in range(l, N+1):
        points = (r - l + 1)
        edges = len([q[i] for i in range(N-1) if l <= q[i][0] and q[i][1] <= r])
        res = points - edges
        ans += res

print(ans)


### FIXED CODE ###

N = int(input())
q = [sorted(list(map(int, input().split()))) for _ in range(N-1)]

ans = 0

for i in range(1, N+1):
    ans += i * (N - i + 1)
for qi in q:
    u, v = qi[0], qi[1]
    ans -= u * (N - v + 1)

print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

def b_search(L,key,left,right):
    #L[i] < keyを満たす最大のi
    #L[i] < key <= L[i+1]
    if key <= L[0]:
        return 0
    elif key > L[len(L)-1]:
        return len(L)
    else:
        mid = (left+right)//2
        if L[mid] < key and key <= L[mid+1]:
            return mid+1
        elif L[mid] >= key:
            return b_search(L,key,left,mid)
        else:
            return b_search(L,key,mid,right)

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if j < N-1:
            ans += b_search(L[j+1:],L[i]+L[j],0,len(L[j+1:]))
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
c = 0

for i in range(n-1):
  for j in range(i+1,n):
    if sorted(s[i]) == sorted(s[j]):
      c += 1

print(c)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
d = {}
c = 0

for i in s:
  tmp = "".join(sorted(i))
  if tmp not in d:
    d[tmp] = 0
  else:
    d[tmp] += 1
  c += d[tmp]
  
print(c)
### BUGGY CODE ###

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[input() for _ in range(H)]

MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(warp)

cost1 = deque()

while 0 < len(cost0):
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				cost0.appendleft((h+i,w+j,Cost[h+i][w+j]))

	if len(cost0) == 0:

		while 0 < len(cost1):
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				# print(i,j)
				if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
					if S[h+i][w+j] == '.':
						if c + 1 < Cost[h+i][w+j]:
							Cost[h+i][w+j] = c + 1
							cost0.append((h+i,w+j,Cost[h+i][w+j]))


if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j,i-1)-bit2d.sum(i-1,j)+bit2d.sum(i-1,i-1)
  print(ans)

### FIXED CODE ###

class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j,i-1)-bit2d.sum(i-1,j)+bit2d.sum(i-1,i-1)
  print(ans)
### BUGGY CODE ###

a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

asmin=amax*n
for i in range(amin,amax+1):
    asf=asff(i,a,n)
    if asf<asmin:
        asmin=asf
            
print(asmin)


### FIXED CODE ###

import bisect

a=[]
s=[]
def asff(a,b,s,n):
    m=bisect.bisect(a,b)
    if m<=0:
        asf=-n*b+s[n-1]
    elif m<n:
        asf=(2*m-n)*b+s[n-1]-2*s[m-1]
    elif n<=m:
        asf=n*b-s[n-1]
    return asf

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

#n=5
#stra="2 2 3 5 5"
#ans=2

#n=9
#stra="1 2 3 4 5 6 7 8 9"
#ans=0

#n=6
#stra="6 5 4 3 2 1"
#ans=18

#n=7
#stra="1 1 1 1 2 3 4"
#ans=6

#a=list(map(int,stra.split()))

for i in range(n):
    a[i]=a[i]-i-1
#print(a)
a.sort()

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
bmin=min(a)-n
bmax=max(a)+n

b1=bmin
b5=bmax+1
b2=b1+int((b5-b1)/4)
b3=b1+int((b5-b1)/2)
b4=b1+int((b5-b1)/4*3)
#b2=b1+(b5-b1)//4
#b3=b1+(b5-b1)//4*2
#b4=b1+(b5-b1)//4*3
#print("b1",b1,"b5",b5)
    
asmin=bmax*n
#m0=0
m1=bisect.bisect(a,bmin)


while b1+1<b5:
    c=[]
    c.append([asff(a,b1,s,n),b1])
    c.append([asff(a,b2,s,n),b2])
    c.append([asff(a,b3,s,n),b3])
    c.append([asff(a,b4,s,n),b4])
    c.append([asff(a,b5,s,n),b5])
    c.sort()
    asf=c[0][0]
    d=[]
    d.append(c[0][1])
    d.append(c[1][1])
    d.append(c[2][1])
    d.sort()
    b1=d[0]
    b5=d[2]
    b2=b1+int((b5-b1)/4)
    b3=b1+int((b5-b1)/2)
    b4=b1+int((b5-b1)/4*3)
    
#    print("b1",b1,"b5",b5,"d0",d[0],"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)
### BUGGY CODE ###

N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [{} for _ in [0]*2]
for x,y,c in XYC:
    score[c][(y,x)] = score[c].get((y,x),0) + 1

for c in range(2):
    for x in range(K):
        for y in range(2*K):
            if (y,x) in score[c]:
                score[c][(y,x+2*K)] = score[c][(y,x)]
for c in range(2):
    for x in range(3*K):
        for y in range(K):
            if (y,x) in score[c]:
                score[c][(y+2*K,x)] = score[c][(y,x)]
    
S = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for c in range(2):
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] = S[c][i][j+1] + score[c].get((i,j),0)
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

ans = 0
for i in range(K):
    for j in range(2*K):
        tmp = 0
        tmp += get_sum(0,i,j,i+K-1,j+K-1)
        tmp += get_sum(1,i+K,j,i+2*K-1,j+K-1)
        j = (j+K)%(2*K)
        tmp += get_sum(1,i,j,i+K-1,j+K-1)
        tmp += get_sum(0,i+K,j,i+2*K-1,j+K-1)
        ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for x,y,c in XYC:
    x+=1
    y+=1
    score[c][y][x] += 1
    if x<K: score[c][y][x+2*K] += 1
    if y<K: score[c][y+2*K][x] += 1
    if x<K and y<K: score[c][y+2*K][x+2*K] += 1

S = score
for c in range(2):
    for j in range(3*K):
        for i in range(3*K):
            S[c][i+1][j+1] += S[c][i][j+1]
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

ans = 0
for i in range(K):
    for j in range(2*K):
        tmp = 0
        tmp += get_sum(0,i,j,i+K-1,j+K-1)
        tmp += get_sum(1,i+K,j,i+2*K-1,j+K-1)
        j = (j+K)%(2*K)
        tmp += get_sum(1,i,j,i+K-1,j+K-1)
        tmp += get_sum(0,i+K,j,i+2*K-1,j+K-1)
        ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
Ds = [b-(c+a) for b,c,a in zip(Bs,Cs,As)]
# Dが大きい順に操作していく？
# 初期値
for i,d in enumerate(Ds):
    if d < 0: continue
    heapq.heappush(q,(-d,i))

# print("init",Bs,Cs)
cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    # print(Bs,Cs,i,"before")
    cnt_ = (Bs[i%n]-As[i%n]) // Cs[i%n]
    Bs[i%n] -= cnt_*Cs[i%n]    
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # print("bef",Bs,Cs,i)
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    # print("pop",d,i,d_m,d_p)
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))        
    # print("debug",Bs,Cs)
    cnt += cnt_
if As == Bs:
    print(cnt)
else:
    print(-1)
    


### FIXED CODE ###

import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
# Dが大きい順に操作していく
for i, (b,c,a) in enumerate(zip(Bs,Cs,As)):
    d = b-(c+a) 
    if d < 0: continue
    heapq.heappush(q,(-d,i))

cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    cnt_ = (Bs[i%n]-As[i%n]) // Cs[i%n]
    Bs[i%n] -= cnt_*Cs[i%n]    
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))
    cnt += cnt_

if As == Bs:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

def solve(x,y):
	if x == a and y == b: return 1
	if x > a or y > b or [x,y] in block: return 0
	return solve(x+1,y) + solve(x,y+1)
	
while 1:
	a,b = map(int,raw_input().split())
	if a == 0: break
	block = [map(int,raw_input().split()) for i in range(input())]
	print solve(1,1)

### FIXED CODE ###

while 1:
	a,b = map(int,raw_input().split())
	if a == 0: break
	block = [map(int,raw_input().split()) for i in range(input())]
	road = [[0]*(a+1) for i in range(b+1)]
	road[1][1] = 1
	for bi in range(1,b+1):
		for ai in range(1,a+1):
			if [ai,bi] not in block:
				road[bi][ai] += road[bi-1][ai] + road[bi][ai-1]
	print road[b][a]
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
for q in a:
    if(v:=v+[min(2*(v[-1]-q),t:=t-q)])[-1]<0:print(-1);exit()
print(sum(v))

### FIXED CODE ###

from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        #print(b)
f()
### BUGGY CODE ###

# Mo's algorithm
# 言ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size + 1)]
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))

# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(n // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # print(nl, nr, l, r)
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        # print("a", num, "idx", idx, "LR", (l, r))
        # print("c", count)
        ans[idx] = num


print(*ans, sep="\n")



### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")