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

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
if 5<n<13:
    t=n//5
elif n<3000:
    t=n//9
else:
    t=n//17
while G[0]<t:
    G.insert(0,G[0]*3+1)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])

### FIXED CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//5
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
#Gt=[4, 9, 20, 46, 103, 233, 525, 1182,2660, 5985, 13467]
f=1.0
while f<t:
    f*=2.2
    f=int(f)
    G.insert(0,f)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])
### BUGGY CODE ###

w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [10000000000000 for i in range(w+1)]

for j in range(w+1):
    for i in range(h):
        if j <= ab[i][0]:
            dp[j] = min(dp[j], ab[i][1])
        else:
            dp[j] = min(dp[j], dp[j-ab[i][0]]+ab[i][1])

print(dp[w])

### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
 
max_a=max(a for a,_ in ab)
dp = [0] * (h+max_a)
 
for i in range(0,h+max_a):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[h])
### BUGGY CODE ###

n = int(input())

max_sum = 0
for i in range(0,n+1):
    this_sum = sum([int(n_part) for n_part in str(i)])
    if max_sum < this_sum:
        max_sum = this_sum

print(max_sum)

### FIXED CODE ###

n = int(input())

def digit_sum_simple(n):
    
    max_sum = -1

    for i in range(10**(len(str(n))-1)-1, n+1):
        
        i_parts = []
        for i_part in str(i):
            i_parts.append(int(i_part))

        this_sum = sum(i_parts)
        
        if max_sum < this_sum:
            max_sum = this_sum
            max_sum_i = i

    return max_sum, max_sum_i

def digit_sum_temp(n):
    max_sum_i = int(str(int(str(n+1)[0])-1) + "9"*(len(str(n+1))-1))
    max_sum = sum([int(j) for j in str(max_sum_i)])

    return max_sum

print(digit_sum_temp(n))
### BUGGY CODE ###

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

for i in range(m):
    max = 0
    for j in range(n):
        if max < a[j]:
            max = a[j]
            max_i = j
    a[max_i] = math.floor(a[max_i] / 2)
###    a[a.index(max(a))] = math.floor(a[a.index(max(a))] / 2)

print(sum(a))

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
a = [-int(x) for x in input().split()]

heapq.heapify(a)

for i in range(m):
    t = -heapq.heappop(a)
    heapq.heappush(a, (t // 2) * (-1))

print(-sum(a))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
r = ""
for i in range(N):
  r+= str(A.index(i+1)+1)
  r+= " "
print(r)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(range(1,N+1,1))
C = zip(A,B)
D = sorted(C)
a, b = zip(*D)
print(" ".join(str(x) for x in b))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited = [0] * n
vmap = dict()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = []
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vmap:
            return 0 
        else:
            vmap[(prev, n)] = 1
    else:
        if (n, prev) in vmap:
            return 0 
        else:
            vmap[(n, prev)] = 1
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n, v])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n, prev])
        return 0

dfs(-1, 0)
for f, t in ans:
    print(f+1, t+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

import math

def gcd (a,b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

def gcd_list(arr):

    ans = arr[0]
    for c in arr[1::]:
        ans = gcd(ans , c)
    return ans

N = int(input())

A = list(map(int, input().split()))

g = gcd_list(A)

for i in range(N):
    tmp = A.pop(0)
    if g < gcd_list(A):
        g = gcd_list(A)
    A.append(tmp)

print(g)


### FIXED CODE ###

'''
import math

def gcd (a,b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

def gcd_list(arr):

    ans = arr[0]
    for c in arr[1::]:
        ans = gcd(ans , c)
    return ans
'''
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())

A = list(map(int, input().split()))
A.sort()

af = A[0]
ag = A[1]

F = make_divisors(af)
G = make_divisors(ag)
F.sort(reverse=True)
G.sort(reverse=True)
del F[-1]
del G[-1]

'''
print(F)
print(G)
'''

ansf = 1
ansg = 1

for i in F:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansf = i
        break
    if count == 0:
        ansf = i
        break

for i in G:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansg = i
        break

print(max(ansf,ansg))
'''
g = gcd_list(A)
print(g)

for i in range(N):
    tmp = A.pop(0)
    if g < gcd_list(A):
        g = gcd_list(A)
    A.append(tmp)

print(g)
'''
### BUGGY CODE ###

#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]


for i in range(N):
    for sum_w in range(1,W+1):
        if sum_w-w[i+1]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

print(dp[N][W])

### FIXED CODE ###

#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加
def main():
  for _ in range(N):
      wi,vi=map(int,input().split())
      w.append(wi)
      v.append(vi)

  dp=[[0 for _ in range(W+1)] for _ in range(N+1)]


  for i in range(N):
      for sum_w in range(1,W+1):
          if sum_w-w[i+1]>=0:
              dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
          else:
              dp[i+1][sum_w]=dp[i][sum_w]

  print(dp[N][W])
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
def dfs(n, p, s):
  res[n] = s
  for nei in adj[n]:
    if nei != p:
      dfs(nei, n, s+scores[nei])

dfs(0,-1,scores[0])

print(" ".join(map(str, res)))

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
visited = [False] * N
q = deque([(scores[0], 0)])
while q:
  s,n = q.popleft()
  res[n] = s
  visited[n] = True

  for nei in adj[n]:
    if not visited[nei]:
      q.append((s+scores[nei], nei))

print(" ".join(map(str, res)))
### BUGGY CODE ###

q = int(input())

l = []
x = ""
y = ""

for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = 0
            elif k == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j - 1][k]
            elif j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j][k - 1]
            elif x[k] == y[j]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
 
    print(l[yLen- 1][xLen - 1])



### FIXED CODE ###

q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    for i in range(1, N + 1):
        if Ks[i]:
            continue
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] += 1
            Cs[b] += 1
            # tab.remove((a, b))
            wa.append(a)
            wa.append(b)
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d += 1
    if c == 0:
        print(-1)
        break

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline


s = input().rstrip()
q = int(input())

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        s = ''.join(list(reversed(s)))
    elif query[1] == '1':
        s = query[2] + s
    elif query[1] == '2':
        s = s + query[2]
        
print(s)
        


### FIXED CODE ###

from sys import stdin
input = stdin.readline

s = input().rstrip()
q = int(input())

isRev = False

head = ''

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        isRev = not isRev
    else:
        if isRev and query[1] == '1':
            s = s + query[2]
        elif query[1] == '1':
            head = head + query[2]
        elif isRev and query[1] == '2':
            head = head + query[2]
        elif query[1] == '2':
            s = s + query[2]
            
if isRev:
    s = s[::-1] + head
else:
    s = head[::-1] + s
        
print(s)
### BUGGY CODE ###

#C - 755 解2
Set753 = {7, 5, 3}

num = int(input())
count = 0
for i in range(357, num+1):
    nSet = set([])
    n = i
    while n>0:
        d = n%10
        if d in Set753:
            nSet.add(d)
            n //= 10
        else: 
            nSet = set([])
            break
    if nSet=={}: continue 
    elif nSet==Set753: 
        #print(i,end=', ') #
        count += 1
print(count) 

### FIXED CODE ###

#C - 755 解3
Set753 = {7, 5, 3}
List753 = [7, 5, 3]

N = int(input())

def getDigitList(n):
    list = []
    while n>0:
        list.append(n%10)
        n //= 10
    list.reverse()
    if list==[]: list = [0]
    return list

def gen(n):
    if n>N: return []
    else:
        d = getDigitList(n)
        #print(d) #
        if set(d)==Set753: 
            result = [n]
        else:
            result = []
        for a in List753:  result += gen(n*10+a)
        return result
                
result = gen(0)
#print(result) #
print(len(result))
### BUGGY CODE ###

def make_divisors(n):
  divisors = []
  for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)
  return divisors

S = int(input())

x1, y2 = 0, 0
y1, x2, x3, y3 = 0, 0, 0, 0

flag = False
div = make_divisors(S)
for d in div:
  x2 = d
  y3 = S // x2
  if x2 <= 1000000000 and y3 <= 1000000000:
    flag = True
    break

if flag == False:
  for i in range(1, int(S ** 0.5) + 1):
    x2 = i
    if S / x2 > 1000000000:
      continue
    Y = S / x2
    y3 = int(Y) + 2
    x3 = x2 // 2
    if x3 == 0:
      y1 = 2
    else:
      y1 = (Y - y3) * x2 / x3
    if y1 == int(y1):
      break

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))

### FIXED CODE ###

S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

n=int(input())
s=input()
ans=n+1
for i in range(n+1):
  a=s[:i].count("#")+s[i:].count(".")
  ans=min(ans,a)
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
a=s.count(".")
ans=a
for i in range(n):
  if s[i]==".":
    a-=1
  else:
    a+=1
  ans=min(ans,a)
print(ans)
### BUGGY CODE ###

import collections

n = int(input())
s = [None]*n
ans = 0
for i in range(n):
    c = collections.Counter(s)
    tmp = str(sorted(input()))
    ans += c[tmp]
    s[i] = tmp
print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = str(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(K):
    B = [0 for _ in range(N)]
    if all(b == N for b in B):
        break
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    # 累積和
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()
   
for b in B:
    print(b, end=" ")

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(min(K, 50)):
    B = [0 for k in range(N)]
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    # 累積和
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()
   
for b in B:
    print(b, end=" ")
### BUGGY CODE ###

def lb_str(a, K):
    n = len(a)
    if n == 0:
        return -1
    elif K <= a[0]:
        return -1
    low = 0
    high = n - 1
    while low < high:
        mid = (low + high + 1) // 2
        if a[mid] < K:
            low = mid
        else:
            high = mid - 1

    return low

N, M = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])

data = []
for i in range(M):
    B, C = [int(x) for x in input().split()]
    data.append([C, B])
data = sorted(data)

for i in range(M):
    C, B = data[i][0], data[i][1]
    j = lb_str(A, C)
    if j + 1 <= B:
        A = [C]*(j + 1) + A[j + 1:]
    else:
        A = A[B:j + 1] + [C]*B + A[j + 1:]
ans = sum(A)
print(ans)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])

data = []
for i in range(M):
    B, C = [int(x) for x in input().split()]
    data.append([C, B])
data = sorted(data, reverse=True)

D = []
i, tot = 0, 0
while tot < N and i < M:
    C, B = data[i][0], data[i][1]
    for _ in range(B):
        D.append(C)
        tot += 1
        if tot >= N:
            break
    i += 1

i = 0
while i < min(N, len(D)) and A[i] < D[i]:
    i += 1

ans = sum(D[:i] + A[i:])
print(ans)
### BUGGY CODE ###

def main():
    import numpy as np
    def bfs(S,s,g,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v==g:
                return dist[v[0]][v[1]]
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return -1

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    for i in range(h):
        for j in range(w):
            s = [i,j]
            if S[i][j]=='#':
                continue
            for k in range(h):
                for l in range(w):
                    g = [k,l]
                    if S[k][l]=='#':
                        continue
                    if m<bfs(S,s,g,h,w):
                        m = bfs(S,s,g,h,w)
    print(int(m))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import numpy as np
    def bfs(S,s,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return np.max(dist)

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)):
        s = spot[i]
        if S[s[0]][s[1]]=='#':
            continue
        d = bfs(S,s,h,w)
        if m<d:
            m = d
    print(int(m))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from heapq import heappop, heappush

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    hq = []
    for i, _b in enumerate(b):
        heappush(hq, (-_b, i))

    ans = 0
    while len(hq) != 0:
        q = heappop(hq)
        if -q[0] == a[q[1]]:
            # 同じなら何もする必要はない
            continue
        elif -q[0] < a[q[1]]:
            # 増やすことは出来ないので、小さいなら構築不可
            ans = -1
            break

        ac = b[(q[1] - 1) % n] + b[(q[1] + 1) % n]
        if (b[q[1]] - a[q[1]]) // ac == 0:
            # 一致しておらず、さらに減らせないので構築不可
            ans = -1
            break
        else:
            # できる限り減らす
            tmp = (b[q[1]] - a[q[1]]) // ac
            b[q[1]] -= ac * tmp
            ans += tmp
            heappush(hq, (-b[q[1]], q[1]))
    
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from heapq import heappop, heappush

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    hq = []
    for i, _b in enumerate(b):
        heappush(hq, (-_b, i))

    ans = 0
    while len(hq) != 0:
        q = heappop(hq)
        if -q[0] == a[q[1]]:
            # 同じなら何もする必要はない
            continue
        elif -q[0] < a[q[1]]:
            # 増やすことは出来ないので、小さいなら構築不可
            ans = -1
            break

        ac = b[(q[1] - 1) % n] + b[(q[1] + 1) % n]
        if (b[q[1]] - a[q[1]]) // ac == 0:
            # 一致しておらず、さらに減らせないので構築不可
            ans = -1
            break
        else:
            # できる限り減らす
            tmp = (b[q[1]] - a[q[1]]) // ac
            b[q[1]] -= ac * tmp
            ans += tmp
            heappush(hq, (-b[q[1]], q[1]))
    
    print(ans)

if __name__ == '__main__':
    main()