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

from collections import Counter
import queue


def bfs(d, s, N):
    dist = [-1]*N
    q = queue.Queue()
    q.put(s)
    dist[i] = 0
    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == -1:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    return dist


N, X, Y = map(int, input().split())
d = [[] for _ in range(N+1)]
d[X].append(Y)
d[Y].append(X)
for i in range(1, N):
    d[i].append(i+1)
    d[i+1].append(i)

ans = [0]*(N+1)

for i in range(N):
    s = i+1
    c = Counter(bfs(d, i+1, N))
    for i, m in c.items():
        ans[i] += m

for i in range(1, N):
    print(ans[i]//2)



### FIXED CODE ###

from collections import Counter, deque


def bfs(d, s, N):
    dist = [-1]*N
    q = deque()
    q.append(s)
    dist[i] = 0
    while len(q) != 0:
        From = q.popleft()
        for To in d[From]:
            if dist[To-1] == -1:
                q.append(To)
                dist[To-1] = dist[From-1]+1
    return dist


N, X, Y = map(int, input().split())
d = [[] for _ in range(N+1)]
d[X].append(Y)
d[Y].append(X)
for i in range(1, N):
    d[i].append(i+1)
    d[i+1].append(i)

ans = [0]*(N+1)

for i in range(N):
    s = i+1
    c = Counter(bfs(d, i+1, N))
    for i, m in c.items():
        ans[i] += m

for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

import sys

values = [int(input()) for i in range(int(input()))]

maxv = - sys.maxsize - 1

for c, i in enumerate(values):
    for j in values[c + 1:]:
        val = j - i
        if maxv < val:
            maxv = val

print(maxv)


### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int, input().split()))
a = 0
for i in list(itertools.combinations(L,3)):
  if (i[0]<i[1]+i[2]) and (i[1]<i[0]+i[2]) and (i[2]<i[1]+i[0]):
    a += 1
print(a)

### FIXED CODE ###

from bisect import bisect_left
 
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
cnt = 0
 
# 2番目に長い棒bを固定
for b in range(N):
    # bより短い棒aを一つずつ探索
    for a in range(b):
        ab = L[a] + L[b]
        # 二分探索でa+bより短い棒（c<a+bが成り立つc）の範囲を求める
        r = bisect_left(L, ab)
        # cの範囲のうちbの範囲を除外して、cの本数を求める
        cnt += r - (b + 1)
 
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N, K = list(map(int, input().split()))
ab = [None]*(N-1)
for i in range(N-1):
    ab[i] = list(map(int, input().split()))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][0] - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num

def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)

    for edge in ki[i]["eda"]:
        if edge[0] != base:
            num *= saiki(edge[0], i, ki)

    num = num % 1000000007
    return num

total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[0], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, h: "List[int]"):
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for j in range(K):
            if i + j + 1 < N:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i] + abs(h[i + j + 1] - h[i]))
    print(dp[N - 1])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)
 
 
def solve(N: int, K: int, h: "List[int]"):
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for j in range(K):
            if i + j + 1 < N:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i] + abs(h[i + j + 1] - h[i]))
    print(dp[N - 1])
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
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()
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)

dq = deque()
dq.append([-1, 0])
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
            print(n+1, v+1)
    if child_num % 2 == 0:
        return 1
    else:
        print(n+1, prev+1)
        return 0

dfs(-1, 0)

### 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 sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

N = int(input())
vws = np.array([tuple(map(int, input().split())) for _ in range(N)], np.int32)

n = min(2**1, N)

@njit("i4[:, :](i4[:, :], )", cache = True)
def precompute(vws):
    dp = np.zeros((n, 10**5+1), np.int32)
    dp[0, vws[0, 1]:] = vws[0, 0]
    for i in range(1, n):
        v, w = vws[i]
        dp[i] = dp[(i-1)//2]
        dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])
    return dp

@njit("i4(i4[:], i4[:], i4, i4[:])", cache = True)
def func(vs, ws, L, dp_):
    bits = np.arange(1 << len(vs))
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vs)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vs[i]
        weights[indices] += ws[i]

    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

dp = precompute(vws)

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws[Vs, 0]
        ws = vws[Vs, 1]
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

from math import gcd
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")


### FIXED CODE ###

from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)
def d(y):
    t=[]
    while y>=2:
        p=x[y]
        t.append(p)
        y=y//p
    t=list(set(t))
    for i in range(len(t)):
        z[t[i]]+=1
    return
g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        d(a[i])
    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")
### BUGGY CODE ###

n = int(input())
gift = []
cnt =0
for i in  range(n):
    get = input()
    if get not in gift:
        gift.append(get)
        cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
dic = {}
cnt =0
for i in  range(n):
    get = input()

    if get not in dic:
        dic[get] = 1

print(len(dic))
### BUGGY CODE ###

n, a, b = [int(i) for i in input().split()]

p = 10 ** 9 + 7
N = 10 ** 9
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N+1):
    fact.append((fact[-1]*i)%p)
    inv.append((-inv[p%i] * (p//i)) % p) 
    factinv.append(factinv[-1] * inv[-1] % p)
    
def comb(n, r, p):
    if r < 0 or n < r:
        return 0
    
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p
  
print(pow(2, n, p) -1 -comb(n, a, p) - comb(n, b, p))

### FIXED CODE ###

n, a, b = [int(i) for i in input().split()]
mod = 10**9+7

def func_156d(n, r):
    r =min(r, n-r)
    numerator = 1
    denominator = 1
    
    for i in range(n-r+1, n+1):
        numerator = numerator * i % mod
        
    for i in range(1, r+1):
        denominator = denominator * i % mod
        
    return numerator * pow(denominator, mod-2, mod) %mod

print((pow(2, n, mod) -1 - func_156d(n,a) - func_156d(n,b) + 2*mod) %mod )
### BUGGY CODE ###

n, k = map(int,input().split())
r, s, p = map(int,input().split())
t = input()

def point(aite):
    if aite == "r":
        return p
    elif aite == "s":
        return r
    else:
        return s

ten = 0
lose = []
for i in range(n):
    if i < k:
        ten += point(t[i])
    else:
        if t[i-k] == t[i] and not i-k in lose:
            lose.append(i)
        else:
            ten += point(t[i])

print(ten)


### FIXED CODE ###

n, k = map(int,input().split())
r, s, p = map(int,input().split())
t = input()

def point(aite):
    if aite == "r":
        return p
    elif aite == "s":
        return r
    else:
        return s

ten = 0
kako = ["o"]*k
for i in range(n):
    if kako[i%k] == t[i]:
        kako[i%k] = "o"
    else:
        kako[i%k] = t[i]
        ten += point(t[i])

print(ten)
### BUGGY CODE ###

n=input()
m=0
MOD = 10**9 + 7
from itertools import combinations
for i,j in combinations(map(int,input().split()),2):
    k=i*j
    m+=k
v=m%MOD
if m<=MOD:
    print(m)
else:
    print(v)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
MOD = 10 ** 9 + 7

cumsum = [A[0]]
for i in range(1, N):
    cumsum.append(A[i] + cumsum[i - 1])

ans = 0
for i in range(N):
    ans += (A[i] * (cumsum[-1] - cumsum[i])) % MOD
    ans %= MOD

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

def doubling(n,k,a):
    logk = 1
    beki = 2
    while beki < k:
        logk += 1
        beki = beki << 1
    dp = [[0 for _ in range(n)] for _ in range(logk)]
    for i in range(n):
        dp[0][i] = a[i]
    for i in range(logk-1):
        for j in range(n):
            dp[i+1][j] = dp[i][dp[i][j]]
    now = 0
    index = 0
    while k > 0:
        if k&1:
            now = dp[index][now]
        k = k >> 1
        index += 1
    return now+1


def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    for i in range(n):
        a[i] -= 1
    print(doubling(n,k,a))    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k = inpm()
    a = inpl()
    past = [0 for _ in range(n)]
    past[0] = 1
    root = [0]
    pre = 0
    while True:
        Next = a[pre]-1
        if past[Next]:
            break
        root.append(Next)
        pre = Next
        past[Next] = 1
    rev = []
    i = 0
    while root[len(root)-1-i] != Next:
        rev.append(root[len(root)-1-i])
        i += 1
    rev.reverse()
    rever = [Next]
    for i in range(len(rev)):
        rever.append(rev[i])
    n1 = len(root)
    n2 = len(rever)
    if n1-1 >= k:
        print(root[k]+1)
        return
    if rever[0] != 0:
        k -= n1-n2
    print(rever[(k)%n2]+1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

A_len, B_len, K = map(int, input().split(' '))
#print("Aは{0}冊. Bは{1}冊. 上限{2}分".format(A_len, B_len, K))

A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
#print(A, B)

# A,Bの累積和の配列を出して、A_acc,B_accの要素番地が最大となるような組み合わせを出す

A_acc = []
for idx_A in range(A_len): 
  if(idx_A == 0):
    A_acc.append(A[0])
  else:
    A_acc.append(A_acc[idx_A - 1] + A[idx_A])
A_acc.insert(0, 0)
    
B_acc = []
for idx_B in range(B_len):
  if(idx_B == 0):
    B_acc.append(B[0])
  else:
    B_acc.append(B_acc[idx_B - 1] + B[idx_B])
B_acc.insert(0, 0)

#print(A_acc, B_acc)

max_num = 0
left_time = K
for a_num in range(A_len + 1):
  b_num = 0
  left_time = K - A_acc[a_num]
  #print("Aから{0}冊読んだ場合はそもそも残り{1}分".format(a_num, left_time))
  if(left_time < 0):
    break
  
  while(True):
    #print("Bから{0}冊読んでる場合,残り時間{1}".format(b_num, left_time - B_acc[b_num]))
    
    if(b_num + 1 > B_len):
      break
    
    if(left_time - B_acc[b_num + 1] < 0):
      break
    
    b_num += 1
    
  #print("結果,A棚から{0}冊、B棚から{1}冊で合計{2}冊で経過時間{3}"
        #.format(a_num, b_num, a_num + b_num, A_acc[a_num] + B_acc[b_num]))
  max_num = max(max_num, (a_num + b_num))
  #print("現在max{0}".format(max_num))
  
print(max_num)
    


### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
    
  while b[j] > K - a[i]:
    j -= 1
    
  ans = max(ans, i + j)

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

from sys import stdin
from collections import defaultdict
trim = lambda s: s[:-1] if s[-1] == "\n" else s
s = trim(stdin.readline())
t = trim(stdin.readline())

dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 0
for minS in range(0, len(s)):
    for minT in range(0, len(t)):
        dp[minS+1][minT] = max(dp[minS+1][minT], dp[minS][minT])
        dp[minS][minT+1] = max(dp[minS][minT+1], dp[minS][minT])
        if s[minS] == t[minT]:
            dp[minS+1][minT+1] = max(dp[minS+1][minT+1], dp[minS][minT]+1)
            
edgesS = list(dp[len(s)].values())
edgesT = [dp[i][len(t)] for i in range(0, len(s)+1)]
ind = (-1, -1)
ans = ''
if max(edgesS) >= max(edgesT):
    for i in range(0, len(t)+1):
        if dp[len(s)][i] == max(edgesS):
            ind = (len(s), i)
            break
    while (ind[0] != 0) and (ind[1] != 0):
        cur = max(dp[ind[0]-1][ind[1]-1], dp[ind[0]-1][ind[1]], dp[ind[0]][ind[1]-1])
        if (cur == dp[ind[0]-1][ind[1]-1]) and (s[ind[0]-1] == t[ind[1]-1]):
            ind = (ind[0]-1, ind[1]-1)
            ans += s[ind[0]]
        elif cur == dp[ind[0]-1][ind[1]]:
            ind = (ind[0]-1, ind[1])
        else:
            ind = (ind[0], ind[1]-1)
else:
    for i in range(0, len(s)+1):
        if dp[i][len(t)] == max(edgesT):
            ind = (i, len(t))
            break
    while (ind[0] != 0) and (ind[1] != 0):
        cur = max(dp[ind[0]-1][ind[1]-1], dp[ind[0]-1][ind[1]], dp[ind[0]][ind[1]-1])
        if cur == dp[ind[0]-1][ind[1]-1]:
            ind = (ind[0]-1, ind[1]-1)
            ans += s[ind[0]]
        elif cur == dp[ind[0]-1][ind[1]]:
            ind = (ind[0]-1, ind[1])
        else:
            ind = (ind[0], ind[1]-1)
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

m = len(s)
n = len(t)

dp = [[None] * (n+1) for i in range(m+1)]

for i in range(m+1):
    for j in range(n+1):

        if i == 0 or j == 0:
            dp[i][j] = 0

        elif s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])



final = dp[m][n]

lcs = [""] * (final + 1)
lcs[final] = ""

i = m
j = n

while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        lcs[final-1] = s[i-1]
        i -= 1
        j -= 1
        final -= 1

    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1


print("".join(lcs))
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ma=max(A)
import heapq
BB=[]
for i in range(n):
  BB.append([-B[i],i])
heapq.heapify(BB)
b,ind=heapq.heappop(BB)
ans=0
while b<-ma:
  if ind==0:
    d=B[-1]+B[1]
  elif ind==n-1:
    d=B[-2]+B[0]
  else:
    d=B[ind-1]+B[ind+1]
  b_next,ind_next=heapq.heappop(BB)
  ans+=(-b+b_next-1)//d+1
  b+=d*((-b+b_next-1)//d+1)
  heapq.heappush(BB,[b,ind])
  heapq.heappush(BB,[b_next,ind_next])
  B[ind]=-b
  b,ind=heapq.heappop(BB)
  ans+=((-b+b_next-1)//d+1)
print(ans if A==B else -1)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

from scipy.spatial.distance import cityblock
B = []
Distance = []

H,W = map(int,input().split())
minD = 0
for row in range(H):
    Inputs = list(input())
    for column in [i for i, x in enumerate(Inputs) if x == '#']:
        B.append((column,row))

for column in range(W):
    for row in range(H):
        Distance = []
        a = (column,row)
        for b in B:
            Manhattan = cityblock(a,b)
            if Manhattan > minD:
                Distance.append(Manhattan)
            else:
                break
        if len(Distance) == len(B):
            if min(Distance) > minD:
                minD = min(Distance)
print(minD)

### FIXED CODE ###

# -*- coding: utf-8 -*-
h, w = map(int, input().split())
a = []
a = [[True] * (w + 2)]
for i in range(h):
    a.append([True] + [x == '#' for x in input()] + [True])
a.append([True] * (w + 2))
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)