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

n,x,y=map(int,input().split())
#a<b
def dis(a,b):
    return min (b-a,abs(a-x)+1+abs(b-y))

for k in range(1,n):
  count=0
  #i<j
  for i in range(1,n):
    for j in range(i+1,n+1):
      if dis(i,j)==k:
        count+=1
  print(count)

### FIXED CODE ###

n,x,y=map(int,input().split())
#a<b
def dis(a,b):
    return min (b-a,abs(a-x)+1+abs(b-y))

# for k in range(1,n):
#   count=0
#   #i<j
#   for i in range(1,n):
#     for j in range(i+1,n+1):
#       if dis(i,j)==k:
#         count+=1
#   print(count)
ans=[0]*(n-1)
#i<j
for i in range(1,n):
  for j in range(i+1,n+1):
    ans[dis(i,j)-1]+=1
print(*ans,sep="\n")
### BUGGY CODE ###

import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [rl()[::-1] for _ in range(N)]
answer = 0
match = 0
while A:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][-1] - 1
        if op in used or i in used:
            continue
        if op > i and A[op][-1]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)


### FIXED CODE ###

import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

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

n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


print(answer)






### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)
### BUGGY CODE ###

N, K = map(int, input().split())
a_list = [int(i) for i in input().split()]
A = [0, a_list[0]]
for i in range(1, N):
    A.append(A[-1] + a_list[i])
A_combination = []
for i in range(N + 1):
    for j in range(i + 1, N + 1):
        A_combination.append(A[j] - A[i])
x = 0
for i in range(40, 0, - 1):
    cnt = 0
    t = pow(2, i - 1)
    for A_i in A_combination:
        if ((x + t) & (A_i)) == (x + t):
            cnt += 1
        if cnt >= K:
            x += t
            break
print(x)

### FIXED CODE ###

N, K = map(int, input().split())
a_list = [int(i) for i in input().split()]
A = [0, a_list[0]]
for i in range(1, N):
    A.append(A[-1] + a_list[i])
A_combination = []
for i in range(N + 1):
    for j in range(i + 1, N + 1):
        A_combination.append(A[j] - A[i])
x = 0
for i in range(40, 0, - 1):
    cnt = 0
    t = pow(2, i - 1)
    for A_i in A_combination:
        if ((x + t) & (A_i)) == (x + t):
            cnt += 1
        if cnt >= K:
            x += t
            break
print(x)
### BUGGY CODE ###

def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    Using Divide-and-Conquer method.
    """

    if m == 0:
        return True
    if i >= n:
        return False
    return solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)


n = int(input())

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

x = input()

M = list(map(int, input().split()))

for m in M:
    if solve(A, 0, m, n):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    R is the record of answer i, m.
    Using Divide-and-Conquer method.
    """

    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i >= n:
        R[i][m] = False
        return False
    else:
        ans = solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)
        R[i][m] = ans
        return ans


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)
R = [[None] * 2000 for i in range(n + 1)]

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')
### BUGGY CODE ###

s = int(input())
for i in range(-s, s):
    for j in range(-1, s):
        if i**5-j**5 == s:
            if i == abs(j)+1 or abs(j) == i+1:
                print(i, j)
                break

### FIXED CODE ###

x=int(input())
for i in range(-200,200):
  for j in range(-200,200):
    if (i**5)-(j**5)==x:
      print(i,j)
      exit()
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
cost = [None,2,5,5,4,5,6,3,7,6]

dp = [-1]*(N+20)
dp[0] = 0

min_cost = min([cost[a] for a in A])
max_cost = max([cost[a] for a in A])

l = 1
k = 1
while min_cost*l<=N:
    dp_new = [-1]*(N+20)
    for i in range(min_cost*l, min(max_cost*l, N)+1):
        for a in A:
            v = dp[i-cost[a]]
            if v>=0:
                dp_new[i] = v + a*k
                break
    dp = dp_new
    if dp[N]>0 : r=dp[N]
    l+=1
    k*=10

print(r)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cost = [None,2,5,5,4,5,6,3,7,6]

Aset = {}
for a in A:
    c = cost[a]
    Aset[c] = max(Aset[c], a) if c in Aset else a
A = sorted([v for k,v in Aset.items()])

dp = [None]*(N+1)
dp[0] = (0,[0]*len(A))

for ia, a in enumerate(A):
    c = cost[a]
    for i in range(c, N+1):
        t = dp[i-c]
        if t and (dp[i]==None or t[0]+1>=dp[i][0]):
            dp[i] = (t[0]+1, t[1].copy())
            dp[i][1][ia] += 1
      	
l=[]
for i in range(len(A)):
    l += [A[len(A)-1-i]]*dp[N][1][len(A)-1-i]

print(*l, sep='')
### BUGGY CODE ###

l, r = list(map(int, input().split()))

s = set()
for i in range(l, r+1):
    s.add(i % 2019)
s = list(s)

ans = 2018
for i, x in enumerate(s):
    for y in s[i+1:]:
        tmp = (x * y) % 2019
        if ans > tmp:
            ans = tmp
print(ans)

### FIXED CODE ###

l, r = list(map(int, input().split()))

if r - l > 2018:
    print(0)
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i+1, r+1):
            tmp = (i * j) % 2019
            if ans > tmp:
                ans = tmp
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
f = sorted(list(map(int, input().split())), reverse=True)


def test(x):
    cost = 0
    for i, j in zip(a, f):
        cost += max(0, i - x // j)
    return cost <= k


left = -1
right = a[-1]*f[0]
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = np.array(sorted(list(map(int, input().split()))))
f = np.array(sorted(list(map(int, input().split())), reverse=True))


def test(x):
    cost = np.maximum(0, a-x//f).sum()
    return cost <= k


left = -1
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

[N, A, B] = list(map(int, input().split()))
pair = A+B
count = 0
ans = 0

while N >= pair:
  N -= pair
  count += 1

if N <= A:
  ans = count*A + N
else:
  ans = count*A + A

print(ans)


### FIXED CODE ###

[N, A, B] = list(map(int, input().split()))
pair = A+B
ans = 0

num = int((N-(N%pair))/pair)

if N - num*pair <= A:
  ans = num*A + N - num*pair
else:
  ans = num*A + A

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
r = 1
pre = 0
for i, a in enumerate(A):
    i += 1
    if i > K:
        r = r // A[i-K-1]
    r *= a
    if i > K:
        print("Yes" if r > pre else "No")
    pre = r

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i, a in enumerate(A):
    if i+1 > K:
        print("Yes" if a > A[i-K] else "No")
### BUGGY CODE ###

N = input()
A = input().split()

for i in range(len(A)+1):
  print(A.count(str(i+1)))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0] * (n+1)

for a in A:
    B[a] += 1

print('\n'.join(map(str, B[1:])))
### BUGGY CODE ###

import itertools

n = int(input())
s = str(input())

R = []
G = []
B = []
for i in range(n):
  if s[i] == "R":
    R.append(i+1)
  elif s[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

kouho = list(itertools.product(R, G, B))
ans = 0
for i in range(len(kouho)):
  temp = [kouho[i][0], kouho[i][1], kouho[i][2]]
  temp.sort()
  if temp[1] - temp[0] != temp[2] - temp[1]:
    ans += 1

print(ans)      

### FIXED CODE ###

n = int(input())
s = str(input())

R = []
G = []
B = []
for i in range(n):
  if s[i] == "R":
    R.append(i+1)
  elif s[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

  
ans = 0

for i in range(len(R)):
  for j in range(len(G)):
    temp = 0
    if 2*R[i] - G[j] >0 and 2*R[i] - G[j] <= n:
      if s[2*R[i] - G[j] -1] == "B":
        temp += 1
    if 2*G[j] - R[i] >0 and 2*G[j] - R[i] <= n:
      if s[2*G[j] - R[i]-1] == "B":
        temp += 1
    if (R[i]+G[j])%2 == 0:
      if s[(R[i]+G[j])//2-1] == "B":
        temp += 1
    ans += len(B)- temp

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

from math import factorial


def combination(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


class UnionFind():
    def __init__(self, n):
        self.nodes = [-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root = root_x
                small_root = root_y
            else:
                small_root = root_x
                big_root = root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root] = big_root

    def solve_uncomfort(self, N):
        sum = 0
        for n in self.nodes:
            if n < 0:
                n = abs(n)
                sum += combination(abs(n), 2)
        return combination(N, 2)-sum


def main():
    N, M = map(int, input().split())
    A, B = [], []
    for i in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    uf = UnionFind(N+1)
    get_root, unite, nodes = uf.get_root, uf.unite, uf.nodes
    ans = []
    for i in reversed(range(M)):
        ans.append(uf.solve_uncomfort(N))
        unite(A[i], B[i])
    print('\n'.join(map(str, ans[::-1])))


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, M = map(int, input().split())
A = []
B = []
parent = [-1 for i in range(N)]
size = [1 for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)


def root(i):
    if parent[i] < 0:
        return i
    parent[i] = root(parent[i])
    return parent[i]


uncomfort = N * (N - 1) // 2
ans = [uncomfort]
for i in reversed(range(1, M)):
    # print(size)
    #print(parent, A[i], B[i])
    if root(A[i]) != root(B[i]):
        comfort = size[root(A[i])] * size[root(B[i])]
        uncomfort -= comfort
        #print(size[root(A[i])], size[root(B[i])])
        if size[root(A[i])] > size[root(B[i])]:
            size[root(A[i])] += size[root(B[i])]
            parent[root(B[i])] = root(A[i])
        else:
            size[root(B[i])] += size[root(A[i])]
            parent[root(A[i])] = root(B[i])
    # print(uncomfort)
    ans.append(uncomfort)
# print(ans[::-1])
for answer in reversed(ans):
    print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
a=[[] for i in range(n)]
p=[]*n
l=[0]*n
ans=[0]*n

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,input().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,input().split())
    l[t1-1]+=t2
dfs(-1,0,0)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

n,q = map(int,readline().split())
a=[[] for i in range(n)]
l=[0 for _ in range(n)]
ans=[0 for _ in range(n)]

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,readline().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,readline().split())
    l[t1-1]+=t2
dfs(-1,0,0)

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

n = int(input())
c = 1
for i in range(1,n):
    for j in range(2,n):
        if i**j <= n:
            c = max(c,i**j)
print(c)

### FIXED CODE ###

n = int(input())
c = 1
for i in range(1,n):
    for j in range(2,n):
        if i**j <= n:
            c = max(c,i**j)
        else:
            break
print(c)
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations


def p_e():
    N = int(input())
    S = input()

    S_idx = defaultdict(list)

    for i in range(N):
        S_idx[S[i]].append(i)

    max_ans = 0
    for c in S_idx.keys():
        if len(S_idx[c]) <= 1:
            continue

        comb_list = list(combinations(S_idx[c], 2))
        i = 1

        f = True
        while f:
            i += 1
            f = False
            for comb in comb_list:
                a = comb[0]
                b = comb[1]
                if a + i - 1 >= N or b + i - 1 >= N:
                    comb_list.remove(comb)
                    continue

                if a + i - 1 >= b:
                    comb_list.remove(comb)
                    continue

                if S[a + i - 1] == S[b + i - 1]:
                    f = True
                else:
                    comb_list.remove(comb)

        if max_ans < i - 1:
            max_ans = i - 1

    print(max_ans)


if __name__ == '__main__':
    p_e()


### FIXED CODE ###

def p_e():
    N = int(input())
    S = input()

    l, r, ans = 0, 0, 0

    while r < N:
        if S[l:r] in S[r:N]:
            ans = max(ans, r - l)
            r += 1
        else:
            l += 1

    print(ans)


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

s = input()

q = int(input())
r = 0
t = 0
for i in range(q):
    A = list(input().split())
    if A[0] == '1':
        r += 1
    else:
        if A[1] == '1':
            if r % 2 == 0:
                s = A[2] + s
            else:
                s = s + A[2]
        else:
            if r % 2 == 0:
                s = s + A[2]
            else:
                s = A[2] + s
if r % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

n,A,B = map(int,input().split())
s = list(str(input()))
p =[]
for i in range(0,n):
  if s[i] =="c":
    print("No")
  elif s[i]=="a":
    if A+B>len(p):
      p.append(s[i])
      print("Yes")
    else:
      print("No")
  elif s[i] =="b":
    if A+B>len(p) and p.count("b")<B:
      p.append(s[i])
      print("Yes")
    else:
      print("No")

### FIXED CODE ###

n,a,b = map(int,input().split(" "))
s = input()
accept = a+b
for i in range(len(s)):
  if s[i] == "c":
    print("No")
  elif accept <= 0:
    print("No")
  elif s[i] == "a":
    print("Yes")
    accept -= 1
  elif s[i] == "b" and b > 0:
    print("Yes")
    b -= 1
    accept -= 1
  else:
    print("No")
### BUGGY CODE ###

def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = float('inf')
	for i in range(1, n):
		left = sum(a[:i])
		right = sum(a[i:])
		ans = min(ans, abs(left - right))
	print(ans)
resolve()

### FIXED CODE ###

def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	m = sum(a)
	cnt = 0
	ans = float('inf')
	for i in range(len(a) - 1):
		cnt = cnt + a[i]
		ans = min(ans, abs(m - cnt*2))
	print(ans)
resolve()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque


def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = []
  for s,t,x in STX:
    l = bisect_left(Dn,s)
    while Dn[l] <= t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)    


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)
### BUGGY CODE ###

def p_c():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    l = [-1] * N
    idx = set(range(N))

    for i in range(N):
        l[i] = B[i - 1] + B[(i + 1) % N]

    ans = 0

    while 1:
        f = False
        for i in list(idx):
            if A[i] <= B[i] - l[i]:
                f = True
                ans += 1
                B[i] -= l[i]
                l[i - 1] -= l[i]
                l[(i + 1) % N] -= l[i]
                idx.add((N + i - 1) % N)
                idx.add((i + 1) % N)
            else:
                idx.remove(i)
        if not f:
            break

    if A != B:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    p_c()


### FIXED CODE ###

def p_c():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    l = [-1] * N

    for i in range(N):
        l[i] = B[i - 1] + B[(i + 1) % N]

    ans = 0

    while 1:
        f = False
        for i in range(N):
            if A[i] <= B[i] - l[i]:
                f = True
                n = (B[i] - A[i]) // l[i]
                ans += n
                B[i] -= n * l[i]
                l[i - 1] -= n * l[i]
                l[(i + 1) % N] -= n * l[i]
        if not f:
            break

    if A != B:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    p_c()