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

N, K = map(int,input().split())
edges = []

if K > (N-1)*(N-2)//2:
    print(-1)
else:
    edges.append((1,2))
    for i in range(3, N+1):
        edges.append((2, i))
    sa = (N-1)*(N-2)//2 - K
    for i in range(min(sa, N-2)):
        sa -= 1
        edges.append((1, i+3))
    if sa != 0:
        i = 3
        j = 4
        while sa > 0:
            while j < N and sa > 0:
                edges.append((i, j))
                j += 1
                sa -= 1
            i += 1
            j = i + 1
        print(len(edges))
        for i in range(len(edges)):
            print(edges[i][0], edges[i][1])
    else:
        print(len(edges))
        for i in range(len(edges)):
            print(edges[i][0], edges[i][1])
    

### FIXED CODE ###

N, K = map(int,input().split())
edges = []

if K > (N-1)*(N-2)//2:
    print(-1)
else:
    edges.append((1,2))
    for i in range(3, N+1):
        edges.append((2, i))
    sa = (N-1)*(N-2)//2 - K
    for i in range(min(sa, N-2)):
        sa -= 1
        edges.append((1, i+3))
    if sa != 0:
        i = 3
        j = 4
        while sa > 0:
            while j <= N and sa > 0:
                edges.append((i, j))
                j += 1
                sa -= 1
            i += 1
            j = i + 1
        print(len(edges))
        for i in range(len(edges)):
            print(edges[i][0], edges[i][1])
    else:
        print(len(edges))
        for i in range(len(edges)):
            print(edges[i][0], edges[i][1])
### BUGGY CODE ###

#

import sys
input=sys.stdin.readline
MOD=10**9+7

fac=[1]*(5*10**5+1)
for i in range(1,5*10**5+1):
    fac[i]=(fac[i-1]*i)%MOD
    
def inv(x):
    return pow(x,MOD-2,MOD)

def nPr(n,r):
    return (fac[n]*inv(fac[n-r]))%MOD
def nCr(n,r):
    return (fac[n]*inv(fac[n-r])*inv(fac[r]))%MOD

def main():
    N,M=map(int,input().split())
    hojo=0
    for i in range(1,N+1):
        hojo+=(-1)**(i)*nCr(N,i)*nPr(M,i)*nPr(M-i,N-i)**2
        hojo%=MOD
    print((nPr(M,N)**2+hojo)%MOD)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
input=sys.stdin.readline
MOD=10**9+7

fac=[1]*(5*10**5+1)
for i in range(1,5*10**5+1):
    fac[i]=(fac[i-1]*i)%MOD
    
def inv(x):
    return pow(x,MOD-2,MOD)

def nPr(n,r):
    return (fac[n]*inv(fac[n-r]))%MOD
def nCr(n,r):
    return (fac[n]*inv(fac[n-r])*inv(fac[r]))%MOD

def main():
    N,M=map(int,input().split())
    hojo=0
    for i in range(1,N+1):
        hojo+=(-1)**(i)*nCr(N,i)*nPr(M,i)*nPr(M-i,N-i)**2
        hojo%=MOD
    print((nPr(M,N)**2+hojo)%MOD)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a_check = [n] * n
c_check = [0] * n
for i,j in enumerate(sorted(b)):
    for k,l in enumerate(sorted(c)):
        if l > j:
            c_check[i] = n - k
            break
    for k,l in enumerate(sorted(a)):
        if l >= j:
            a_check[i] = k
            break
ans = 0
for i in range(n):
    ans += a_check[i] * c_check[i]
print(ans)

### FIXED CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

import bisect
count = 0
for i in b:
    a_count = bisect.bisect_left(a, i)
    c_count = n - bisect.bisect_right(c, i)
    count += a_count * c_count
    
print(count)
### BUGGY CODE ###

def num_divisors(n):
    num = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            num += 1
            if i != n // i:
                num += 1
    return num

N = int(input())

S = 0
for i in range(1,N+1):
    S += i * num_divisors(i)
print(S)

### FIXED CODE ###

# ABC172_D
N = int(input())
ans = 0

for i in range(1,N+1):
	ans += ((N//i)*(i+(N//i)*i))/2

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

def main():
    from itertools import accumulate, product

    def binary_search(a, x, lo, hi):
        while abs(hi - lo) > 0:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return hi

    n = int(input())
    *a, = map(int, input().split())
    acc = (0,) + tuple(accumulate(a))

    # [0,i), [i,j), [j,k), [k, n)

    ret = acc[-1]
    for j in range(2, n - 1):
        left = acc[j]
        right = acc[-1] - left

        i = binary_search(acc, left // 2, 2, j + 2)
        k = binary_search(acc, left + (right // 2), j + 2, n + 1)

        li = i - 1, i
        rk = k - 1, k

        for i, k in product(li, rk):
            if i <= 0 or k <= j:
                continue
            pqrs = acc[i], left - acc[i], acc[k] - left, acc[-1] - acc[k]
            ret = min(
                ret,
                max(pqrs) - min(pqrs)
            )

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate

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

cumsum = (0,) + tuple(accumulate(a))
# print(cumsum)

# PQ := [0, cut)
# RS = [cut, n)

ans = cumsum[-1]
for cut in range(2, n - 1):
    # cumsum[cut] : PQ区間和
    # cumsum[lc], cumsum[lc_1] : P区間和の候補
    # cumsum[n] - cumsum[cut] : RS区間和
    # cumsum[rc], cumsum[rc_1] : R区間和 + sPQの候補

    sPQ = cumsum[cut]
    sRS = cumsum[n] - cumsum[cut]

    lc = bisect_left(cumsum, sPQ // 2)
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    lc_1 = lc - 1
    # x未満で最大

    if abs((sPQ - cumsum[lc]) - cumsum[lc]) < abs((sPQ - cumsum[lc_1]) - cumsum[lc_1]):
        sP = cumsum[lc]
        # print('sP', sP, lc, cumsum)
    else:
        sP = cumsum[lc_1]
        # print('sP', sP, lc_1, cumsum)
    sQ = sPQ - sP
    # print('sQ', sQ)

    rc = bisect_left(cumsum, sPQ + (sRS // 2))
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    rc_1 = rc - 1
    # x未満で最大

    if abs((sRS - (cumsum[rc] - sPQ)) - (cumsum[rc] - sPQ)) < abs((sRS - (cumsum[rc_1] - sPQ)) - (cumsum[rc_1] - sPQ)):
        sR = cumsum[rc] - sPQ
        # print('sR', sR, rc, cumsum)
    else:
        sR = cumsum[rc_1] - sPQ
        # print('sR', sR, rc_1, cumsum)
    sS = sRS - sR
    # print('sS', sS)

    t = (sP, sQ, sR, sS)

    ans = min(ans, max(t) - min(t))
    # print(t)
print(ans)
### BUGGY CODE ###

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

def dp(n):
    if n == 0:
        return ["P"]
    k = dp(n-1)
    return ["B"]+k+["P"]+k+["B"]

burger = dp(n)
burger = "".join(burger)
ans = burger[:x].count("P")
print(ans)

### FIXED CODE ###

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

def dp(a, b):
    if a == 1:
        if 1 <= b <= 4:
            return b-1
        else:
            return 3
    elif b == 1:
        return 0
    elif 1 < b < 2**(a+1)-1:
        return dp(a-1, b-1)
    elif b == 2**(a+1)-1:
        return dp(a-1, 2**(a+1)-3) + 1
    elif 2**(a+1)-1 < b < 2**(a+2)-3:
        return dp(a-1, 2**(a+1)-3) + 1 + dp(a-1, b+1-2**(a+1))
    elif b == 2**(a+2)-3:
        return dp(a-1, 2**(a+1)-3) * 2 + 1
    
print(dp(n, x))
### BUGGY CODE ###

import math



N=int(input())

for i in range(1,N+1):
    ans=0
    if i<=5:
        print(0)
    else:
        ma=int(math.sqrt(i))
        for x in range(1,ma):
            for y in range(x,ma):
                for z in range(y,ma):
                    if x**2+y**2+z**2+x*y+y*z+z*x==i:
                        if x==y and y==z:
                            ans+=1
                        elif x==y or y==z or z==x:
                            ans+=3
                        else:
                            ans+=6
            
        print(ans)



### FIXED CODE ###

import math




N=int(input())

anslist=[0]*(N+1)
ma=int(math.sqrt(N))+1
for x in range(1,ma):
    for y in range(x,ma):
        for z in range(y,ma):
            n=x**2+y**2+z**2+x*y+y*z+z*x
            if n <=N:
                if x==y and y==z:
                    anslist[n]+=1
                elif x==y or y==z or z==x:
                    anslist[n]+=3
                else:
                    anslist[n]+=6

            
for i in range(1,N+1):
    print(anslist[i])
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
	for n in range(1,3501):
		A=N*h*n
		B=4*h*n-N*n-N*h
		if B<=0:
			continue
		if A%B==0:
			print(h,n,A//B)
			exit()


### FIXED CODE ###

N=int(input())
for h in range(1,3501):
	for n in range(1,3501):
		A=N*h*n
		B=4*h*n-N*n-N*h
		if B<=0:
			continue
		if A%B==0:
			print(h,n,A//B)
			exit()
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

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

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        a %= mod
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

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

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    for i in range(n):
        vec = dfs(friends, i)
        ans = len(vec)
        
        for f in friends[i]:
            if f in vec:
                ans -= 1
        
        for b in blocks[i]:
            if b in vec:
                ans -= 1
        
        ans -= 1
                
        print(ans, end=' ')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n 
        self.size = [1] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] = self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
                
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    friends[x].append(y)
    friends[y].append(x)

for i in range(k):
    x, y = map(lambda x: int(x) - 1, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

uf = UnionFind(n)
for i in range(n):
    for f in friends[i]:
        uf.union(i, f)

# 自分を除くUnionFind木の大きさ
ans = [uf.size[uf.find(i)] - 1 for i in range(n)]
# 直接的な友達を引く
for i in range(n):
    ans[i] -= len(friends[i])

for i in range(n):
    for b in blocks[i]:
        if uf.same(i, b):
            ans[i] -= 1

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

N=int(input())
A=list(map(int,input().split()))
     
number_of_items=0
A.sort()
for X in range(min(A)-1, max(A)+1):
    if number_of_items < A.count(X)+A.count(X-1)+A.count(X+1):
        number_of_items = A.count(X)+A.count(X-1)+A.count(X+1)
print(number_of_items)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
bucket=[0]*(max(A)+1)
answer=0
for number in A:
    bucket[number]+=1
if len(bucket)<3:
    answer=sum(bucket)
for i in range(1,max(A)):
    candidate=bucket[i-1]+bucket[i]+bucket[i+1]
    if candidate>answer:
        answer=candidate
print(answer)
### BUGGY CODE ###

N = int(input())

A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, key=lambda x: x[1], reverse = True)

dp = [[-10 ** 15] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for s in range(1, N+1):
  for l in range(s+1):
    r = s - l
    dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
ans = 0
for m in range(N):
  if(dp[m][N-m] > ans):
    ans = dp[m][N-m]
    
print(ans)



### FIXED CODE ###

def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * n
a[0] = 0
for i in range(1, n):
      hi = h[i]
      a[i] = min(a[j] + abs(hi - h[j]) for j in range(max(0, i - k), i))
print(a[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * n
a[0] = 0
for i in range(1, n):
      hi = h[i]
      a[i] = min(a[j] + abs(hi - h[j]) for j in range(max(0, i - k), i))
print(a[-1])
### BUGGY CODE ###

# ABC093 B - Small and Large Integers
a,b,k = map(int, input().split())

for i in range(a,b+1):
    if i <= a+k-1:
        print(i)
        continue
    elif i >= b-k+1:
        print(i)
        continue

### FIXED CODE ###

# ABC093 B - Small and Large Integers
a,b,k = map(int, input().split())

range_ab = set(range(a,a+k))|set(range(b-k+1,b+1))
l = list(range_ab)
l = [x for x in l if a<=x<=b]

l.sort()
print(*l,sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))
    bA = [[0]*N for _ in range(mLEN)]

    for i in range(N):
        a = format(A[i],'b').zfill(mLEN)
        for k in range(mLEN):
            bA[k][i] = a[k]

    answer = 0
    for keta in range(mLEN):
        zero = bA[keta].count('0')
        one = N-zero



        answer += (zero*one)*pow(2,mLEN-1-keta,MOD)
    print(answer%MOD)
    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))

    A = np.array(A)
    ans = 0
    d = 1
    while d < (1 << mLEN):
        cnt = np.count_nonzero(A & d)
        ans += (N - cnt) * cnt * d
        ans %= MOD
        d <<= 1
    print(ans)
    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)
### BUGGY CODE ###

import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='#' else float('inf') for i in list(input())] for _ in range(h)]
graph=np.array(graph)

def bfs():
    for x in range(h):
        for y in range(w):
            for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
                if 0<=x+dx<h and 0<=y+dy<w:
                    graph[x+dx][y+dy]=np.minimum(graph[x][y]+1,graph[x+dx][y+dy])
while np.max(graph)==float('inf'):
    bfs()
print(int(np.max(graph)))


### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='#' else float('inf') for i in list(input())] for _ in range(h)]
graph=np.array(graph)
for x in range(w-1):
    graph[:,x+1]=np.minimum(graph[:,x]+1,graph[:,x+1])
for x in range(w-1,0,-1):
    graph[:,x-1]=np.minimum(graph[:,x]+1,graph[:,x-1])
for y in range(h-1):
    graph[y+1,:]=np.minimum(graph[y,:]+1,graph[y+1,:])
for y in range(h-1,0,-1):
    graph[y-1,:]=np.minimum(graph[y,:]+1,graph[y-1,:])

print(int(np.max(graph)))
### BUGGY CODE ###

def MAP(): return map(int,input().split())

H,W = MAP()
lst = [list(input()) for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        #Left
        if lst[i][j]==".":
            L[i][j] = L[i][j-1]+1
        #Up
            U[i][j] = U[i-1][j]+1
        #Right
        if lst[i][-(j+1)]==".":
            R[i][-(j+1)] = R[i][-j]+1
        #Down
        if lst[-(i+1)][j]==".":
            D[-(i+1)][j] = D[-i][j]+1
ans=0
for i in range(H):
    for j in range(W):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)

### FIXED CODE ###

def MAP(): return map(int,input().split())

H,W = MAP()
lst = [list(input()) for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        #Left
        if lst[i][j]==".":
            L[i][j] = L[i][j-1]+1
        #Up
            U[i][j] = U[i-1][j]+1
        #Right
        if lst[i][-(j+1)]==".":
            R[i][-(j+1)] = R[i][-j]+1
        #Down
        if lst[-(i+1)][j]==".":
            D[-(i+1)][j] = D[-i][j]+1
ans=0
for i in range(H):
    for j in range(W):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
lst=[]
for i in range(n):
    if a[i]==b[i]:
        continue
    heappush(lst,[-b[i],i])
count=0
for _ in range(10**9):
    if not lst:
        print(count)
        break
    c=heappop(lst)
    num, j=c
    i,k=(j-1)%n,(j+1)%n
    num*=(-1)
    if (num-a[j])%(b[i]+b[k])==0:
        count+=(num-a[j])//(b[i]+b[k])
        b[j]=a[j]
        continue
    if num//(b[i]+b[k])==0:
        print(-1)
        break
    count+=num//(b[i]+b[k])
    num%=(b[i]+b[k])
    if num>a[j]:
        heappush(lst,[-num, j])
        b[j]=num
    elif num==a[j]:
        b[j]=num
        continue
    else:
        print(-1)
        break

### FIXED CODE ###

from heapq import heappush,heappop
import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
lst=[]
for i in range(N):
    heappush(lst,(-B[i],i))

count=0
while lst:
    h,i=heappop(lst)
    h=-h
    x,z=B[i-1],B[(i+1)%N]
    kkk=x+z
    if (h-A[i])%kkk==0:
        count+=(h-A[i])//kkk
        B[i]=A[i]
        continue
    elif kkk>=h:
        print(-1)
        sys.exit()
    else:
        count+=h//kkk
        h=h%kkk
        B[i]=h    
        if A[i]>h:
            print(-1)
            sys.exit()
        heappush(lst,(-h,i))

if A==B:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

#python3
#python3
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  ans+=x*(n-x)*2**k
print(ans%MOD)


### FIXED CODE ###

#python3
import numpy as np
N = int(input())
A = np.array([int(_) for _ in input().split()])
mod = 10**9 + 7
ans = 0
for b in range(60):
    B = (A >> b) & 1
    M = np.count_nonzero(B)
    ans += 2**b * M * (N - M)
    ans %= mod
print(ans)
### BUGGY CODE ###

from numba import njit

s = input()
t = input()


@njit
def f():
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

    for i, ei in enumerate(s, 1):
        for j, ej in enumerate(t, 1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

    return dp


dp = f()

i = len(s)
j = len(t)
ans = []
while i and j:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

ans = "".join(ans[::-1])
print(ans)


### FIXED CODE ###

s = input()
t = input()


dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

i = len(s)
j = len(t)
ans = []
while i and j:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

ans = "".join(ans[::-1])
print(ans)
### BUGGY CODE ###

import itertools
k=int(input())
def solve(a,b):
	if a<b:
		if b%a==0:
			return a
		else:
			return solve(a,b%a)
	if a%b==0:
		return b
	else:
		return solve(b,a%b)
arr=[i+1 for i in range(k)]

l = [p for p in itertools.product(arr, repeat=3)]
s=0
dic={}
for i in l:
	a,b,c=i
	s+=solve(c,solve(a,b))
print(s)

### FIXED CODE ###

import itertools
k=int(input())
def solve(a,b):
	if a<b:
		if b%a==0:
			return a
		else:
			return solve(a,b%a)
	if a%b==0:
		return b
	else:
		return solve(b,a%b)
arr=[i+1 for i in range(k)]
l=list(itertools.combinations_with_replacement(arr,3))
#l = [p for p in itertools.product(arr, repeat=3)]
s=0
dic={}

for i in l:
	a,b,c=i
	if a==b and a==c:
		s+=solve(c,solve(a,b))
	elif a==b or b==c or a==c:
		s+=3*(solve(c,solve(a,b)))
	else:
		s+=6*(solve(c,solve(a,b)))
print(s)