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

def cul(lists):
    culist = []
    lene = len(lists)
    culist = [sum(lists[0:x:1]) for x in range(0, lene + 1)]
    return culist[1:]


n, m, k = map(int, input().split())
li = list(map(int, input().split()))[:n]
li2 = list(map(int, input().split()))[:m]
all = 0
all2 = 0
g = 0
z = 0
a = cul(li)
b = cul(li2)
for i in range(n):
    if a[i] <= k:
        g += 1
    else:
        break

all += a[i-1]

for i in range(m):
    if all + b[i] <= k:
        g += 1
    else:
        break

for i in range(m):
    if b[i] <= k:
        z += 1
    else:
        break

all2 += b[i-1]
for i in range(n):
    if all2 + a[i] <= k:
        z += 1
    else:
        break

print(max(g, z))


### FIXED CODE ###

def main():
    line1 = input()
    line2 = input()
    line3 = input()
    n, m, k = list(map(int, line1.split()))
    a = [0] + list(map(int, line2.split()))
    b = [0] + list(map(int, line3.split()))
    mark1, mark2 = 0, 0
    for i in range(1, len(a)):
        a[i] += a[i-1]
        if a[i] > k:
            mark1 = i
            break
    for i in range(1, len(b)):
        b[i] += b[i-1]
        if b[i] > k:
            mark2 = i
            break
    if mark1:
        a = a[:mark1]
    if mark2:
        b = b[:mark2]
    ans = 0
    for i in range(len(a)):
        target = k - a[i]
        tmp = 0
        low, high = 0, len(b)
        while low < high:
            mid = (low + high) // 2
            if b[mid] <= target:
                tmp = mid
                low = mid + 1
            else:
                high = mid - 1
        ans = max(ans, i + tmp)
    print(ans)
    return

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

n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow(Ya,10**9+5,10**9+7))%(10**9+7)
comb_b = (X*pow(Y,10**9+5,10**9+7))%(10**9+7)

result = pow(2,n)-1-comb_a-comb_b
print(result if result>=0 else result+10**9+7)

### FIXED CODE ###

def pow_self(x,n):
    ans = 1
    while n>0:
        if n&1 == 1:
            ans = (ans*x)%(10**9+7)
            
        x = (x*x)%(10**9+7)
        n >>= 1
    return ans

  
n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow_self(Ya,10**9+5))%(10**9+7)
comb_b = (X*pow_self(Y,10**9+5))%(10**9+7)

result = pow_self(2,n)-1-comb_a-comb_b
while result <0:
    result += 10**9+7
print(result)
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
a = 0
for i in range(N//R+1):
    for j in range(((N-(i*R))//G)+1):
        if N -i*R-j*G ==0:
            a += 1
            
        
        elif(N -i*R-j*G)%B == 0 and (N -i*R-j*G) > 0:
            a += 1
          
        
            
           

print(a)

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
a = 0
for i in range(N//R+1):
    for j in range(((N-(i*R))//G)+1):
        if (N -i*R-j*G)%B == 0:
            a += 1
                       
           

print(a)
### BUGGY CODE ###

N = input()
AN = list(map(int, input().split()))
X = 1
for i in range(len(AN)):
    X = X*AN[i]

if X <= 10**18:
    print(X)
else:
    print(-1)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
    exit()
    
for i in range(N):
    ans *= A[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
L = np.array(sorted(list(map(int, input().split()))))
# print('L', L)


def f(v):
    left = 0
    right = N
    while left + 1 < right:
        x = (left + right) // 2
        if v > L[x]:
            left = x
        else:
            right = x
    return right


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = f(a + b)
        # print('a, b, idx', a, b, idx)
        # idx = np.searchsorted(L, a + b, sorter=None)
        ans += idx - 1 - j
print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

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

import bisect
N,M = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
for i in range(M):
    b,c = map(int,input().split())
    if l_a[b-1] <= c:
        l_a[:b] = [c]*b
        l_a.sort()
    else:
        ins = bisect.bisect_right(l_a,c)
        l_a[:ins] = [c]*ins
print(sum(l_a))

### FIXED CODE ###

from operator import itemgetter
N,M = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
#O(NlogN)
l_bc = [list(map(int,input().split())) for i in range(M)]
l_bc.sort(key = itemgetter(1), reverse = True)
#O(MlogM)
for b,c in l_bc:
    l_a.extend([c]*b)
    if len(l_a) > N*2:
        break
l_a.sort(reverse = True)
print(sum(l_a[:N]))
### BUGGY CODE ###

N = int(input())
S = input()
memo = {"R":0,"G":0,"B":0}
ans = 0
if len(set(S))==3:
  for i,s in enumerate(S):
    a = 1
    for k,v in memo.items():
      a *= 1 if k==s else v
    for j in range(i//2):
      if len(set(s+S[:i+1][::-(j+1)][:3]))==3: a-=1
    ans += a
    memo[s] += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
memo = {"R":0,"G":0,"B":0}
ans = 0
if len(set(S))==3:
  for i,s in enumerate(S):
    a = 1
    for k,v in memo.items(): a *= 1 if k==s else v
    b = sum([len(set(s+S[:i+1][::-(j+1)][:3]))//3 for j in range(i//2)])
    ans += a-b
    memo[s] += 1
print(ans)
### BUGGY CODE ###

N = int(input())

result = 0
for i in range(N):
    result += i
print(result)


### FIXED CODE ###

N = int(input())

print(N * (N-1) // 2)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import queue
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[a] = True
            
print(' '.join(list(map(str, v))))

### FIXED CODE ###

# coding: utf-8
# Your code here!

import queue
import sys
input = sys.stdin.readline
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[c] = True
            
print(' '.join(list(map(str, v))))
### BUGGY CODE ###

from bisect import bisect_left

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

s = sum(A)
for i in range(1, N) :
    A[i] += A[i-1]


def check(d) :
    ifr = bisect_left(A, (s - 3 * d) // 4)
    ito = bisect_left(A, (s + 3 * d) // 4)
    for i in range(ifr, min(N, ito + 1)) :
        jfr = bisect_left(A, A[i] + (s - A[i] - 2 * d) // 3)
        jto = bisect_left(A, A[i] + (s - A[i] + 2 * d) // 3)
        for j in range(max(i + 1, jfr), min(N, jto + 1)) :
            kfr = bisect_left(A, A[j] + (s - A[j] - d) // 2)
            kto = bisect_left(A, A[j] + (s - A[j] + d) // 2)
            for k in range(max(j + 1, kfr), min(N - 1, kto + 1)) :
                cut = [A[i], A[j] - A[i], A[k] - A[j], s - A[k]]
                if max(cut) - min(cut) <= d :
                    return True
    return False

ng, ok = 0, s
while ok - ng > 1 :
    mid = (ng + ok) // 2
    
    if check(mid) :
        ok = mid
    else :
        ng = mid

print(ok)

### FIXED CODE ###

from bisect import bisect_left

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

s = sum(A)
for i in range(1, N) :
    A[i] += A[i-1]

ret = float('inf')
for b in range(1, N - 1) :
    a = bisect_left(A, A[b] / 2)
    c = bisect_left(A, A[b] + (s - A[b]) / 2)
    for i in [a - 1, a] :
        for j in [c - 1, c] :
            if not 0 <= i < b < j < N - 1 :
                continue
            cut = [A[i], A[b] - A[i], A[j] - A[b], s - A[j]]
            ret = min(ret, max(cut) - min(cut))
            
print(ret)
### BUGGY CODE ###

S = input()
MOD = 10**9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

for digit in range(1, len(S) + 1) :
    digitMask = 10**(digit - 1)
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD

ans = (dp[len(S)][5]) % MOD
print(ans)



### FIXED CODE ###

S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10
    digitMask %= 13

ans = (dp[len(S)][5]) % MOD
print(ans)
### BUGGY CODE ###

# Problem D - Pairs

# input
N, K = map(int, input().split())
a_nums = list(map(int, input().split()))

# initialization
a_nums = sorted(a_nums)
left = -10**18
right = 10**18

# binary search
while right-left>1:
    x = (right + left) // 2
    S = 0
    T = 0
    # 判定部分
    for a in a_nums:
        if a>0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    l2 = mid
                else:
                    r2 = mid
            S += r2
        elif a<0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    r2 = mid
                else:
                    l2 = mid
            S += N - r2
        elif x>=0: # a==0の時
            S += N
        # 重複を数える
        if a*a<=x:
            T += 1
    # 判定部分（大元）
    check_nums = (S - T) // 2
    if check_nums>=K:
        right = x
    else:
        left = x

# output
print(right)


### FIXED CODE ###

#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {-1:[], 0:[], 1:[]}
    for a in A:
        if a == 0:
            B[0].append(0)
        else:
            B[a//abs(a)].append(a)
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


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

import numpy as np

n,k = map(int, input().split())
d = np.array(list(map(int, input().split())))
l = np.arange(n)
ans = np.array([0]*n)
cnt = 0

def func(x_left, x_right):
  for x_l,x_r in zip(x_left,x_right):
      ans[x_l:x_r] += 1

while True:
  if np.all(d==n):
    ans = d
    break

  if cnt == k:
    break

  ans *= 0
  x_left = l-d
  x_left[x_left < 0] = 0
  x_right = l+d+1
  x_right[x_left > n] = n
  func(x_left, x_right)
  cnt += 1
  if np.all(d+n==ans):
    ans+=(k-cnt)*n
    break
  else:
    d = ans.copy()
    continue

  
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K,C=mi()
    S=list(input())
    ok,ng = "o","x"

    OK = []
    for i in range(N):
        if S[i] == ok:
            OK.append(i+1) # 1-index
    
    greeds = [OK[0]]
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)

    inv_greeds = [OK[-1]]
    for i in range(1,len(OK)):
        x = OK[::-1][i]
        if -x + inv_greeds[-1] > C:
            inv_greeds.append(x)
    
    if len(greeds) < K or len(inv_greeds) < K:
        exit()

    greeds = greeds[:K]
    inv_greeds = inv_greeds[:K][::-1]

    # print(greeds,inv_greeds)
    for i in range(len(greeds)):
        if greeds[i] == inv_greeds[i]:
            print(greeds[i])



    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K,C=mi()
    S=list(input())
    ok,ng = "o","x"

    OK = []
    for i in range(N):
        if S[i] == ok:
            OK.append(i+1) # 1-index
    
    greeds = [OK[0]]
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)
            if len(greeds) > K:
                break

    inv_greeds = [OK[-1]]
    inv_OK = OK[::-1]
    for i in range(1,len(OK)):
        x = inv_OK[i]
        if -x + inv_greeds[-1] > C:
            inv_greeds.append(x)
            if len(inv_greeds) > K:
                break
    
    if len(greeds) < K or len(inv_greeds) < K:
        exit()

    greeds = greeds[:K]
    inv_greeds = inv_greeds[:K][::-1]

    # print(greeds,inv_greeds)
    for i in range(len(greeds)):
        if greeds[i] == inv_greeds[i]:
            print(greeds[i])



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

import math
a, b, n = map(int, input().split())
arr = [math.floor(a * 1 / b) - a * math.floor(1 / b)]
ans = 0
for i in range(n):
  x = i + 1
  if math.floor(a * x / b) - a * math.floor(x / b) < arr[-1]:
    ans = arr[-1]
    break
  else:
    arr.append(math.floor(a * x / b) - a * math.floor(x / b))
    ans = arr[-1]
ans = max(arr)
print(ans)

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b - 1, n)
ans = math.floor(a * x / b) - a * math.floor(x / b)
print(ans)
### BUGGY CODE ###

# -*- coding utf-8 -*-
import math


def calc_C(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % (10**9 + 7)


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M % (10**9 + 7)

# col
for i in range(M):
    ans += i * (M - i) * N * N % (10**9 + 7)

ans = ans % (10**9 + 7)
ans = ans * calc_C(N * M - 2, K - 2) % (10**9 + 7)
print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-
import math


def calc_C(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % (10**9 + 7)


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M % (10**9 + 7)

# col
for i in range(M):
    ans += i * (M - i) * N * N % (10**9 + 7)

ans = ans % (10**9 + 7)
ans = ans * calc_C(N * M - 2, K - 2) % (10**9 + 7)
print(ans)
### BUGGY CODE ###

n,x=map(int,input().split())
A=[int(i) for i in input().split()]
B=[float("inf")]*n
ans=float("inf")
for i in range(n):
  ans_i=i*x
  for j in range(n):
    B[j]=min(B[j],A[j-i])
    ans_i+=B[j]
  ans=min(ans,ans_i)
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
A=[int(i) for i in input().split()]
B=[float("inf")]*n
ans=float("inf")
for i in range(n):
  ans_i=i*x
  for j in range(n):
    B[j]=min(B[j],A[j-i])
    ans_i+=B[j]
  ans=min(ans,ans_i)
print(ans)
### BUGGY CODE ###

from collections import Counter

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

a = list(set(A))
cc = Counter(A)
dup = [x for x in a if cc[x] > 1]
m = len(a)
l = len(A) 
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)

for k in A:
    if k not in dup:
        print(int(al))
    else :
        print(int(al-cc[k]+1))

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
a = list(set(A))
cc = Counter(A)
dup = set([x for x in a if cc[x] > 1])
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)

# for k in A:
#     if k in dup:
#         print(int(al-cc[k]+1))
#     else :
#         print(int(al))
[print(int(al-cc[k]+1)) if k in dup else print(int(al)) for k in A]
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N, M, Q = map(int, input().split())

Xi = np.zeros((N+1,N+1),dtype=np.int32)
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# pqi = []
ans = []
for i in range(Q):
    tmp = 0
    p, q = map(int, input().split())
    # pqi.append((p,q))
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]
    ans.append(tmp)

for a in ans:
    print(a)
#
# for (p, q) in pqi:
#     tmp = 0
#     for l in range(p,q+1):
#         tmp += Ci[l][q] - Ci[l][p-1]
#
#     print(tmp)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# import numpy as np

N, M, Q = map(int, input().split())

# Xi = np.zeros((N+1,N+1),dtype=np.int32)
Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

# Ci = np.zeros((N+1,N+1),dtype=np.int32)
Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq as hp


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    q = []
    for i, b in enumerate(B):
        hp.heappush(q, (-b, i))

    c = 0
    while q:
        #print(q)
        _, ind = hp.heappop(q)
        b = B[ind]
        if ind == N-1:
            s = B[ind-1]+B[0]
        else:
            s = B[ind-1]+B[ind+1]
        #print(b, s)
        if (b-A[ind])%s == 0:
            B[ind] = A[ind]
            c += (b-A[ind])//s
        elif b%s <= A[ind] or b < s:
            c = -1
            break
        else:
            c += b//s
            B[ind] = b%s
            hp.heappush(q, (-B[ind], ind))

    print(c)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq as hp


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    q = []
    for i, b in enumerate(B):
        hp.heappush(q, (-b, i))

    c = 0
    while q:
        #print(q)
        _, ind = hp.heappop(q)
        b = B[ind]
        if ind == N-1:
            s = B[ind-1]+B[0]
        else:
            s = B[ind-1]+B[ind+1]
        #print(b, s)
        if (b-A[ind])%s == 0:
            B[ind] = A[ind]
            c += (b-A[ind])//s
        elif b%s <= A[ind] or b < s:
            c = -1
            break
        else:
            c += b//s
            B[ind] = b%s
            hp.heappush(q, (-B[ind], ind))

    print(c)

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

#input
S = str(input())

#output
import numpy as np
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = np.zeros(N+1, int)

for i in range(1, N+1):
    dp[i] = int(S[-i::]) % 2019

T = Counter(dp[1:])

answer = 0
answer += T[0]

for t in T.values():
    if t >= 2:
        answer += t*(t-1)//2

print(answer)

### FIXED CODE ###

#input
S = str(input())[::-1]

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)
### BUGGY CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)


### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

s = input()
q = int(input())
flip = 1
right_edge = s
left_edge = ''
for i in range(q):
    query = input()
    if query[0] == '1':
        flip *= -1
    else:
        if query[2] == '1':
            if flip == 1:
                left_edge = query[-1] + left_edge
            else:
                right_edge += query[-1]
        else:
            if flip == 1:
                right_edge += query[-1]
            else:
                left_edge = query[-1] + left_edge
if flip == 1:
    print(left_edge + right_edge)
else:
    print(right_edge[::-1] + left_edge[::-1])
        



### FIXED CODE ###

s = input()
q = int(input())
flip = 1
right_edge = list(s)
left_edge = []
for i in range(q):
    query = input()
    if query[0] == '1':
        flip *= -1
    else:
        if query[2] == '1':
            if flip == 1:
                left_edge.append(query[-1])
            else:
                right_edge.append(query[-1])
        else:
            if flip == 1:
                right_edge.append(query[-1])
            else:
                left_edge.append(query[-1])
left_edge = left_edge[::-1]
if flip == 1:
    print(''.join(left_edge + right_edge))
else:
    print(''.join(right_edge[::-1] + left_edge[::-1]))