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

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)

N, K = [int(x) for x in stdin.readline().rstrip().split()]
D = [int(x) for x in stdin.readline().rstrip().split()]

L = [x for x in range(10) if x not in D]
ans = 10 ** 7


def dfs(n):
    if len(n) >= len(str(N)):
        if int(n) >= N and n[0] != '0':
            return int(n)
    output = 10 ** 7
    for l in L:
        output = min(dfs(n + str(l)), output)
    return output


print(dfs(''))


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)

N, K = [int(x) for x in stdin.readline().rstrip().split()]
D = [int(x) for x in stdin.readline().rstrip().split()]

L = [x for x in range(10) if x not in D]
ans = 10 ** 7


def dfs(n):
    global ans
    if n != '' and n[0] == '0':
        return
    if n != '' and int(n) >= ans:
        return
    if len(n) >= len(str(N)):
        if int(n) >= N:
            ans = int(n)
    for l in L:
        dfs(n + str(l))


dfs('')
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int,input().split())
if M == 0:
    print("Yes")
    exit(0)

INF = float("inf")
G = [[] for k in range(N)]
D = [INF for k in range(N)]
def dfs(x):
    if len(G[x]) == 0:
        D[x] = x
    else:
        for e in G[x]:
            if D[e[0]] == INF:
                D[e[0]] = D[x] + e[1]
                dfs(e[0])
            else:
                if D[e[0]] != D[x] + e[1]:
                    print("No")
                    exit(0)

for k in range(M):
    L, R, S = map(int,input().split())
    G[L-1].append([R-1,S])
    G[R-1].append([L-1,-S])

for k in range(N):
    if D[k] == INF:
        D[k] = k
        dfs(k)
print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int,input().split())
if M == 0:
    print("Yes")
    exit(0)

INF = float("inf")
G = [[] for k in range(N)]
D = [INF for k in range(N)]
def dfs(x):
    if len(G[x]) == 0:
        D[x] = x
    else:
        for e in G[x]:
            if D[e[0]] == INF:
                D[e[0]] = D[x] + e[1]
                dfs(e[0])
            else:
                if D[e[0]] != D[x] + e[1]:
                    print("No")
                    exit(0)

for k in range(M):
    L, R, S = map(int,input().split())
    G[L-1].append([R-1,S])
    G[R-1].append([L-1,-S])

for k in range(N):
    if D[k] == INF:
        D[k] = k
        dfs(k)
print("Yes")
### BUGGY CODE ###

S = input()
S = S[::-1]
candidacies = ["dream", "dreamer", "erase", "eraser"]
candidacies = [c[::-1] for c in candidacies]

fi_flg = False
while fi_flg is False:
  if S[:6] in candidacies:
    S = S[6:]
  elif S[:5] in candidacies:
    S = S[5:]
  elif S[:7] in candidacies:
    S = S[:7]
  else:
    fi_flg = True

if len(S) == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S = input()
S = S[::-1]
candidacies = ["dream", "dreamer", "erase", "eraser"]
candidacies = [c[::-1] for c in candidacies]

fi_flg = False
while fi_flg is False:
  if S[:7] in candidacies:
    S = S[7:]
  elif S[:6] in candidacies:
    S = S[6:]
  elif S[:5] in candidacies:
    S = S[5:]
  else:
    fi_flg = True

if len(S) == 0:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    q = deque()
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        q.append((a, b))

    ans = 0
    cnt = 1
    while cnt <= M:
        q_ = deque()
        max_a, max_b = 0, 0
        while q:
            a, b = q.pop()
            if a > cnt:
                q_.append((a, b))
                continue
            elif b > max_b:
                q_.append((max_a, max_b))
                max_a, max_b = a, b
            else:
                q_.append((a, b))

        ans += max_b
        cnt += 1
        q = q_


    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from collections import defaultdict
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        d[a].append(-b)

    ans = 0
    heap = []
    for i in range(1, M+1):
        for b in d[i]:
            heappush(heap, b)
        if heap:
            ans -= heappop(heap)

    return ans


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

N=int(input())
numbers = map(int,input().split())

result=1
for n in numbers:
  result *= n
  
if result > 10**18:
  result = -1
  
print(result)



### FIXED CODE ###

N=int(input())
numbers = list(map(int,input().split()))

if 0 in numbers:
  print("0")
else:
 result=1
 for n in numbers:
    result *= n
    if result > 10**18:
      result = -1
      break
 print(result)
### BUGGY CODE ###

import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics


# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

data1 = getInputListInt()
n = data1[0]
q = data1[1]

data2 = getSomeInputListInt(n-1)

data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]

treeList = [[] for _ in range(n)]

for i in range(len(data2)):
    treeList[data2[i][0]-1].append(data2[i][1]-1)
    treeList[data2[i][1]-1].append(data2[i][0]-1)

def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

N, M = map(int, input().split())
passages = [[] for i in range(N-1)]
for i in range(M):
    s, t = map(int, input().split())
    passages[s-1].append(t-1)

# no blocking
E = [0] * N
for n, dest in list(enumerate(passages))[::-1]:
    E[n] = sum(E[d] for d in dest) / len(dest) + 1

min_E = E[0]

# with blocking
for n, dest in enumerate(passages):
    if len(dest) == 1:
        continue
    max_E = max(E[d] for d in dest)
    E[n] = ((E[n] - 1) * len(dest) - max_E) / (len(dest) - 1) + 1
    if n > 0:
        for n2, dest2 in list(enumerate(passages))[n-1::-1]:
            E[n2] = sum(E[d2] for d2 in dest2) / len(dest2) + 1
    min_E = min(min_E, E[0])

print(min_E)


### FIXED CODE ###

N, M = map(int, input().split())
passages = [[] for i in range(N-1)]
for i in range(M):
    s, t = map(int, input().split())
    passages[s-1].append(t-1)

prob = [0] * N
prob[0] = 1
for n, dest in enumerate(passages):
    for d in dest:
        prob[d] += prob[n] / len(dest)

# no blocking
E = [0] * N
for n, dest in list(enumerate(passages))[::-1]:
    E[n] = sum(E[d] for d in dest) / len(dest) + 1

min_E = E[0]

# with blocking
for n, dest in enumerate(passages):
    if len(dest) == 1:
        continue
    new_E = ((E[n] - 1) * len(dest) - max(E[d] for d in dest)) / (len(dest) - 1) + 1
    min_E = min(min_E, E[0] - (E[n] - new_E) * prob[n])

print(min_E)
### BUGGY CODE ###

n=int(input())
a=[int(z) for z in input().split()]
x=1
for i in a:
    x*=i
if x<=10**18:
    print(x)
else:
    print("-1")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
mul=1
if 0 in A:print("0")
else:
    for i in range(N):
        mul*=A[i]
        if mul>pow(10,18):
            print("-1")
            break
        elif i==N-1:print(mul)
### BUGGY CODE ###

mod = 10**9 + 7
n, a, b = map(int, input().split())

ans = pow(2, n, mod)

def C(n, k):
    x, y = 1, 1
    for i in range(k):
        x *= n - i
        y *= i+1

    return (x * pow(y, mod-2, mod)) % mod

print((ans - C(n, a) - C(n, b) - 1) % mod)



### FIXED CODE ###

mod = 10**9 + 7
n, a, b = map(int, input().split())

ans = pow(2, n, mod)

def C(n, k):
    x, y = 1, 1
    for i in range(k):
        x = x *(n - i) % mod
        y = y *(i+1) % mod

    return (x * pow(y, mod-2, mod)) % mod

print((ans - C(n, a) - C(n, b) - 1) % mod)
### BUGGY CODE ###

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

result = 1
for an in a:
    result *= an

max = 10 ** 18
if result > max:
    result = -1

print(result)


### FIXED CODE ###

def calc(a, n):
    for x in range(n):
        if a[x] == 0:
            return 0

    result = 1
    max = 10 ** 18
    for x in range(n):
        result *= a[x]
        if result > max:
            return -1

    return result

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

print(calc(a, n))
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [N*10**4]*N
dp[0] = 0
for i in range(N):
        x = min(i+K+1, N)
        for j in range(i+1, x):
                dp[j] = min(dp[j], dp[i] + abs(H[i]-H[j]))
print(dp[N-1])

### FIXED CODE ###

inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]
 
dp = [inf] * n
dp[0] = 0
 
for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])
### BUGGY CODE ###

import itertools
import collections
S = str(input())

l = []
for i,j in itertools.combinations(range(len(S)), 2):
  l.append((int(S[i:j+1]))%2019)
      
print(l.count(0))

### FIXED CODE ###

S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

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

inf=10**9+1

n=int(input())
array_a=sorted([a for a in map(int, input().split())])+[inf]
array_b=sorted([a for a in map(int, input().split())])+[inf]
array_c=sorted([a for a in map(int, input().split())])

nums_b=[0 for _ in range(n)]
cur=0
for (idx,b) in enumerate(array_b[:-1]):
    while(array_a[cur]<b):
        cur+=1
    nums_b[idx]=cur


nums_c=[0 for _ in range(n)]
cur=0
for (idx,c) in enumerate(array_c):
    while(array_b[cur]<c):
        cur+=1
    nums_c[idx]=sum(nums_b[:cur])
print(sum(nums_c))

### FIXED CODE ###

inf=10**9+1

n=int(input())
array_a=sorted([a for a in map(int, input().split())])+[inf]
array_b=sorted([a for a in map(int, input().split())])+[inf]
array_c=sorted([a for a in map(int, input().split())])

nums_b=[0 for _ in range(n)]
cur=0
for (idx,b) in enumerate(array_b[:-1]):
    while(array_a[cur]<b):
        cur+=1
    nums_b[idx]=cur


cur=0
res=0
for (idx,c) in enumerate(array_c):
    while(array_b[cur]<c):
        res+=nums_b[cur]*(n-idx)
        cur+=1
print(res)
### BUGGY CODE ###

import collections
import math
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(N):
  li = A[:i] + A[i+1:]
  c = collections.Counter(li)
  l = [math.factorial(i[1]) // (math.factorial(i[1]-2) * 2) for i in c.items() if i[1] > 1]
  print(sum(l))
  ans = 0

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    ans = 0
    for i in range(N-K+1):
        s = sum(p[i:i+K])
        if ans < s : ans = s
    print(  (ans+K)*0.5  )
    return

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    if N>K:
        esum = [0]*N
        psum = [0]*(N-K)
        esum[0] = p[1]
        for i in range(1,K):
            esum[i] = esum[i-1]+p[i]
        for i in range(K,N):
            esum[i] = esum[i-1]+p[i]
            psum[i-K] = esum[i]-esum[i-K]
        ans = (max(psum)+K)*0.5
    else:
        ans = (sum(p)+K)*0.5

    print(ans)
    return

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

import sys
from math import gcd


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    c = A[0]
    b = []

    m = A[0]

    for i in range(n - 1):
        m *= A[i + 1]

    for i in range(n - 1):
        c = gcd(c, A[i + 1])

    for i in range(n):
        b.append(gcd(A[i], m // A[i]))

    if c == 1 and all([bb == 1 for bb in b]):
        print('pairwise coprime')
    elif c == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import gcd


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    c = A[0]
    b = []

    cnt = [0] * (10 ** 6 + 1)

    for a in A:
        c = gcd(c, a)
        cnt[a] += 1

    max_num = 0
    for i in range(2, 10 ** 6 + 1):
        max_num = max(max_num, sum(cnt[i::i]))

    if c == 1 and max_num <= 1:
        print('pairwise coprime')
    elif c == 1:
        print('setwise coprime')
    else:
        print('not coprime')


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

n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))
  


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]
  

for j in range(n):
  print(10**15-min(ans[j:]))
  
  
  
  
  
      
    
    
    
    
  
  


  

### FIXED CODE ###

n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq
#n:頂点数、m:辺の数　s:始点　es:辺のリスト
def dijkstra(n,m,s,es):
  #used:訪問済みかどうかを確認する　false 使ってない
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])
### BUGGY CODE ###


def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    return n, alist

def get_sign(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    return 0

def submit():
    n, alist = read_input()

    s = alist[0]
    sign = get_sign(s)
    edit = 0
    for a in alist[1:]:
        temp = s + a
        temp_sign = get_sign(temp)

        while temp_sign == sign or temp == 0:
            edit += 1
            temp -= sign
            temp_sign = get_sign(temp)

        s = temp
        sign = temp_sign

    print(edit)





if __name__ == '__main__':
    submit()


### FIXED CODE ###


def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    return n, alist

def get_sign(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    return 0

def submit():
    n, alist = read_input()

    # pattern 1
    s = 0
    sign = 1
    edit = 0

    for a in alist:
        temp = s + a
        temp_sign = get_sign(temp)

        if sign == temp_sign:
            edit += temp_sign * temp
            temp -= temp

        if temp == 0:
            edit += 1
            temp -= sign

        s = temp
        sign = get_sign(s)

    edit1 = edit

    # pattern 2
    s = 0
    sign = -1
    edit = 0

    for a in alist:
        temp = s + a
        temp_sign = get_sign(temp)

        if sign == temp_sign:
            edit += temp_sign * temp
            temp -= temp

        if temp == 0:
            edit += 1
            temp -= sign

        s = temp
        sign = get_sign(s)

    edit2 = edit

    print(min(edit1, edit2))


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

N = int(input())
s = [input().split() for i in range(N)]
for i in range(N):
    s[i] = list(s[i][0])
    s[i].sort()
s.sort()
count = 0
for i in range(N):
    for j in range(i+1, N):
        Flag = True
        for k in range(10):
            if s[i][k] != s[j][k]:
                Flag = False
                break
        if Flag:
            count += 1
        else:
            break
print(count)
            

### FIXED CODE ###

N = int(input())
s = [input().split() for i in range(N)]
for i in range(N):
    s[i] = list(s[i][0])
    s[i].sort()
    s[i] = ''.join(map(str, s[i]))
s.sort()
count = 0
ren = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        count += 1+ren
        ren += 1
    else:
        ren = 0
print(count)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
for i, b in enumerate(B):
    q.append([-b, i])
heapq.heapify(q)
ans = 0
while len(q)>0:
    b, idx = heapq.heappop(q)
    b = -b
    if b==A[idx]:
        continue
    d = B[(idx+1)%N] + B[idx-1]

    p_ = (b-A[idx]) // d
    p = min(p_, (b-B[idx-1])//d+1, (b-B[(idx+1)%N])//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    #print(B, idx, ans, p_)
    if b > A[idx]:
        heapq.heappush(q, [-b, idx])
        if q[0][1] ==idx:
            print(-1)
            exit()
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
q = [(-b, i) for i, b in enumerate(B)]
heapq.heapify(q)
ans = 0
N_m1 = N-1
while len(q)>0:
    b, idx = q[0]
    b = -b
    b_p1, b_m1 = B[idx+1 if idx<N_m1 else 0], B[idx-1]
    d = b_p1 + b_m1

    a = A[idx]
    p = min((b-a)//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    if b > a:
        heapq.heapreplace(q, (-b, idx))
        if q[0][1] == idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
x=n%(a+b)
y=n//(a+b)
c=list(i for i in range(1,a+1))
if x in c:
    print(a*y+x)
elif x==0:
    print(a*y)
else:
    print(a*(y+1))

### FIXED CODE ###

n,a,b=map(int,input().split())
x=int(n/(a+b))
y=n%(a+b)
if a==0:
    print(0)
elif y==0:
    print(a*x)
elif 0<y<a+1:
    print(a*x+y)
else:
    print(a*(x+1))
### BUGGY CODE ###

N = int(input())
AAA = [int(i) for i in input().split()]
BBB = [0]
for a in AAA:
    BBB.append(a+BBB[-1])
ans=0
for i in range(N+1):
    for j in range(i+1,N+1):
        if BBB[i]==BBB[j]:
            ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
AAA = [int(i) for i in input().split()]
BBB = [0]
for a in AAA:
    BBB.append(a+BBB[-1])
ans=[]
#print(BBB)
BBB=sorted(BBB)
#print(BBB)
prev = float("inf")
buff=BBB[0]
ans=[]
for i,b in enumerate(BBB):
    #print(b,prev,buff)
    if b==prev:
        buff+=1
    else:
        if buff>=2:
            #print("append!")
            ans.append(buff)
        buff=1
        prev=b
if buff!=1:
    ans.append(buff)
#print(ans)
print(sum([(i-1)*i//2 for i in ans]))
### BUGGY CODE ###

n=int(input())
h= list(map(int,input().split()))
res=[0]*n
for i in range(n-1):
  j=i+1
  while j<=n-1:
    if h[i]>=h[j]:
      res[i]+=1
      i+=1
      j+=1
    else:
      break
print(max(res))

### FIXED CODE ###

n=int(input())
h= list(map(int,input().split()))
res=[0]*n
for i in range(1,n):
  if h[-i]<=h[-i-1]:
    res[i]=res[i-1]+1
  else:
    res[i]=0
print(max(res))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    for i in range(len(tmp)):
        if len(tmp[i]) == 1:
            s = s[::-1]
        else:
            f = int(tmp[i][1])
            c = tmp[i][2]
            if f == 1:
                s = c + s
            else:
                s = s + c
                
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and flag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans)[::-1])

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

n = int(input())
ans = 1 + n

for i in range (1, n+1):
    if n % i == 0 and i + n / i < ans:
        ans = i + n /i

print(int(ans - 2))


### FIXED CODE ###

import math
n = int(input())
ans = 1 + n

max = math.ceil(n**0.5)

for i in range (2, max+1):
    if n % i == 0 and i + n / i < ans:
        ans = i + n / i

print(int(ans - 2))