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

X = int(input())
def bfs(position=[0],depth=1):
    queue = []
    for p in position:
        for dx in [-depth,0,depth]:
            nextp = p + dx
            if nextp == X:
                return depth
            queue.append(nextp)
    position = queue[:]
    if depth == 10**5:
        return depth
    return bfs(position,depth+1)
print(bfs())

### FIXED CODE ###

X = int(input())
for t in range(1,X+1):
    if t*(t+1)//2 >= X:
        print(t)
        break
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10**9
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for k in range(1, K+1):
            if i + k < N:
                dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
            else:
                break
    print(dp[N-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])
### BUGGY CODE ###

K, S = map(int, input().split())
n = 0
for x in range(K+1):
  for y in range(K+1):
    if x+y > S:
      break
    for z in range(K+1):
      if x+y+z == S:
        n += 1
      elif x+y+z > S:
        break
print(n)

### FIXED CODE ###

K, S = map(int, input().split())
n = 0
for x in range(K+1):
  for y in range(K+1):
    z = S-x-y
    if z>=0 and z<=K:
      n +=1
print(n)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="#":
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
while que:
    y,x=map(int,que.popleft())
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

ans=0
for i in range(H):
    ans=max(ans,max(dist[i]))

print(ans)

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="#":
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
ans=0
while que:
    y,x=map(int,que.popleft())
    ans=dist[y][x]
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

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

n=int(input())
x=list(int(input()) for _ in range(n))

from copy import deepcopy

for i in range(n):
	y=deepcopy(x)
	del y[i]
	print(max(y))

### FIXED CODE ###

n=int(input())
x=list(int(input()) for _ in range(n))

import numpy as np

mi=np.argmax(x)

y=np.array(x)

for i in range(n):
	if i!=mi:
		print(x[mi])
	else:
		z=np.ones(n)
		z[i]=0
		print(int(max(y*z)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
upd = []
for i in range(m):
    s, l = map(int, input().split())
    temp = [l]*s
    upd.extend(temp)
upd.sort(reverse=True)

# output
f = len(a)
o = 0
c = len(upd)
ch = c
if f > c:
    for i in range(c):
        if upd[c-1-i] > a[c-1-i]:
            break
        else:
            ch = c-i-1
else:
    for i in range(f):
        if upd[f-1-i] > a[f-1-i]:
            break
        else:
            ch = f-i-1
print(sum(upd[:ch])+sum(a[ch:]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
from operator import itemgetter
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
upd = []
for i in range(m):
    upd.append(list(map(int, input().split())))
upd.sort(key=itemgetter(1), reverse=True)
# print(upd)
# output
f = len(a)
p = 0
for t in upd:
    for i in range(p, p+t[0]):
        if p < f:
            if a[p] < t[1]:
                a[p] = t[1]
            else:
                break
        else:
            break
        p += 1
print(sum(a))
### BUGGY CODE ###

def check(A):
	c = 0
	for i in range(H):
		for j in range(W):
			if A[i][j] == ".":
				return 1
	return 0

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([s for s in input()])

c = 0
while check(A) != 0:
	for i in range(H):
		for j in range(W):
			if A[i][j] != "." and A[i][j] != c:
				if i != 0:
					if A[i-1][j] == ".":
						A[i-1][j] = c
				if i != H-1:
					if A[i+1][j] == ".":
						A[i+1][j] = c
				if j != 0:
					if A[i][j-1] == ".":
						A[i][j-1] = c
				if j != W-1:
					if A[i][j+1] == ".":
						A[i][j+1] = c
	c += 1
print(c)

### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([0 if s == "#" else H+W for s in input()])

A = np.array(A)
for x in range(W - 1):
	A[:,x+1] = np.minimum(A[:, x]+1,A[:, x+1])
for x in range(W - 1, 0 , -1):
	A[:,x-1] = np.minimum(A[:, x-1],A[:, x]+1)
for y in range(H -1):
	A[y+1,:] = np.minimum(A[y, :]+1,A[y+1, :])
for y in range(H -1, 0, -1):
	A[y-1,:] = np.minimum(A[y-1, :],A[y, :]+1)

print(np.max(A))
### BUGGY CODE ###

A, B, C = map(int, input().split())
K = int(input())

while K > 0:
    if A > B:
        B *= 2
        K -= 1
    else:
        if B > C:
            C *= 2
            K -= 1

if A < B and B < C:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A, B, C = map(int, input().split())
K = int(input())
n = 0

while A >= B:
    B *= 2
    n += 1

while B >= C:
    C *= 2
    n += 1

if n <= K:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
n = 1
while n <= N:
    n *= 2

data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0

dp = [[A[0]]] + [0] * (N - 1)
update(H[0], A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(1, H[i]) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i], dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

import math

import sys
k = sys.stdin.readline()
k = int(k)
sum = 0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            sum = sum +math.gcd(math.gcd(x, y), math.gcd(y, z))

print(sum)

### FIXED CODE ###

import math

import sys
k = sys.stdin.readline()
k = int(k)
sum = 0
for x in range(1,k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if len(set([x,y,z])) is 1:
                sum = sum +math.gcd(math.gcd(x, y), math.gcd(y, z))
            elif len(set([x,y,z])) is 2:
                sum = sum + 3 * math.gcd(math.gcd(x, y), math.gcd(y, z))
            elif len(set([x,y,z])) is 3:
                sum = sum + 6* math.gcd(math.gcd(x, y), math.gcd(y, z))
print(sum)
### BUGGY CODE ###

import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
@lru_cache(None)
def F(k):#ｆ１＋ｆ２＋．。。ｆｋ
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    return res
  res=F(k-1)
  #print(res)
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
      if res[i]>=mod:
        res[i]-=mod
  if a[k]<s+1:
      res[a[k]]+=1
  res[0]+=1
  return res
ans=0
for i in range(1,n+1):
  ls=F(i)
  ans+=ls[-1]
  if ans>=mod:
        ans-=mod
print(ans)

### FIXED CODE ###

import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
f=[[] for i in range(n+1)]
for k in range(1,n+1):
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    f[1]=res
    continue
  res=f[k-1][:]
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
      res[i]%=mod
  if a[k]<s+1:
      res[a[k]]+=1
  res[0]+=1
  f[k+1]=res
ans=0
#print(f)
for i in range(1,n+1):
  ans+=f[i][-1]
ans%=mod
print(ans)
### BUGGY CODE ###

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

# 以下カンニング
for _ in range( min( k, 41 ) ):
    b = [ 0 ] * 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

print( " ".join( list( map( str, a ) ) ) )

### FIXED CODE ###

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

# 以下カンニング
for _ in range( min( k, 41 ) ): # 41 ~ log( 2 * 10 ** 5 )
    b = [ 0 ] * 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

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

def binarySearchLeft(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = low + high >> 1
        if target == nums[mid]:
            if mid == 0 or target != nums[mid - 1]:
                return mid
            else:
                high = mid - 1
        elif target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return low

def solve(N, A, B, C):
     A.sort()
     B.sort()
     C.sort()
     ret = 0
     for a in A:
         b_idx = binarySearchLeft(B, a + 1)
         if not (0 <= b_idx < N):
             continue
         for j in range(b_idx, N):
             c_idx = binarySearchLeft(C, B[j] + 1)
             ret += N - c_idx if 0 <= c_idx < N else 0
     print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    solve(N, A, B, C)


### FIXED CODE ###

def binarySearchLeft(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = low + high >> 1
        if target == nums[mid]:
            if mid == 0 or target != nums[mid - 1]:
                return mid
            else:
                high = mid - 1
        elif target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return low

def binarySearchRight(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = low + high >> 1
        if target == nums[mid]:
            if mid == len(nums) - 1 or target != nums[mid + 1]:
                return mid
            else:
                low = mid + 1
        elif target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return high

def solve(N, A, B, C):
     A.sort()
     B.sort()
     C.sort()
     ret = 0
     for j in range(N):
         i = binarySearchRight(A, B[j] - 1)
         k = binarySearchLeft(C, B[j] + 1)
         ret += (i + 1) * (N - k) if 0 <= i < N and 0 <= k < N else 0
     print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    solve(N, A, B, C)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [[j == "#" for j in input()] for _ in range(h)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# スタート地点をqueueに追加
que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0
add = 0
while True:
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        y, x = que.popleft()
        add -= 1
        for j in range(4):
            ny = y + dy[j]
            nx = x + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                que.append((ny, nx))
                add += 1
    if not que:
        break

print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)
### BUGGY CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
dp = [0] * (M+1)
for i in range(1, M+1):
    tmp = 0
    idx = -1
    for idxab, ab in enumerate(AB):
        if ab[0] <= i:
            if tmp < ab[1]:
                idx = idxab
                tmp = ab[1]
        else:
            break
    if idx >= 0:
        AB[idx][1] = 0
    dp[i] = dp[i-1] + tmp

print(dp[len(dp)-1])

### FIXED CODE ###

from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    # pop
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
 
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q.popleft()
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

ps = [ list(input().split()) for _ in range(m) ]

ac_list = []
wa_count_list = [0]*n
wa_count = 0
# ac_count = 0
for i in range(m):
    q = int(ps[i][0])
    if q in ac_list:
        pass
    else:
        if ps[i][1] == "AC":
            # ac_count += 1
            ac_list.append(int(ps[i][0]))
            wa_count += wa_count_list[q-1]
        else:
            wa_count_list[q-1] += 1

print(len(ac_list),wa_count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

ps = [ list(input().split()) for _ in range(m) ]

ac_count_list = [0]*n
wa_count_list = [0]*n
wa_count = 0

for i in range(m):
    q = int(ps[i][0])
    if ps[i][1] == "AC":
        if ac_count_list[q-1] == 0:
            ac_count_list[q-1] = 1
            wa_count += wa_count_list[q-1]
        else:
            pass
    else:
        if ac_count_list[q-1]==0:
            wa_count_list[q-1] += 1

print(sum(ac_count_list),wa_count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

def maxValue(z:int, w:int, a:"List[int]", player:str) -> int:
    if not a:
        return abs(z-w)

    if player == "X": ## playerXが操作する。価値がmaxになるように
        value = 0
        for i in range(len(a)):
            value = max(maxValue(a[i],w,a[i+1:],"Y"),value)
    else: ## yが操作,価値がminになるように
        value = 10**9
        for i in range(len(a)):
            value = min(maxValue(z,a[i],a[i+1:],"X"),value)
    return value        

def solve(N: int, Z: int, W: int, a: "List[int]"):
    print(maxValue(Z,W,a,"X"))
    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
    Z = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, Z, W, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, Z: int, W: int, a: "List[int]"):
    print(max(abs(a[N-1]-a[N-2]),abs(a[N-1]-W)))
    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
    Z = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, Z, W, a)

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

from heapq import heappop, heappush
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
q = []
for i,b in enumerate(B):
    heappush(q,(-b,i))
answer = 0
while len(q)>0:
    b,i = heappop(q)
    b = -b
    if b < A[i]:
        answer = -1
        break
    sub = B[(i-1)%N] + B[(i+1)%N]
    t = ( b - A[i]) // sub
    if t == 0:
        if b == A[i]:
            continue
        answer = -1
        break
    B[i] -= sub * t
    answer += t
    heappush(q,(-B[i],i))
print(answer)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
q = []
for i,b in enumerate(B):
    heappush(q,(-b,i))
answer = 0
while len(q)>0:
    b,i = heappop(q)
    b = -b
    if b < A[i]:
        answer = -1
        break
    sub = B[(i-1)%N] + B[(i+1)%N]
    t = ( b - A[i]) // sub
    if t == 0:
        if b == A[i]:
            continue
        answer = -1
        break
    B[i] -= sub * t
    answer += t
    heappush(q,(-B[i],i))
print(answer)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0

for i in range(0, 1000):
    count = 0
    val = list(str(i).zfill(3))
    for j in s:
        if j == val[count]:
            count += 1
            if count == 3:
                ans += 1
                break
print(ans)



### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

for i in range(0, 1000):
    count = 0
    val = list(str(i).zfill(3))
    k = val[count]
    for j in s:
        if j == k:
            count += 1
            if count <= 2:
                k = val[count]
            elif count == 3:
                ans += 1
                break
print(ans)