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

k, q = map(int, input().split())
d = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = [elem % m for elem in d]
    rem_d_mod = d_mod[: (n - 1) % k]
    print(n - 1 - (x % m + ((n - 1) // k) * sum(d_mod) + sum(rem_d_mod)) // m
          - ((n - 1) // k) * d_mod.count(0) - rem_d_mod.count(0))


### FIXED CODE ###

import numpy as np


k, q = map(int, input().split())
d = np.array(list(map(int, input().split())), dtype=np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    rem_d_mod = d_mod[: (n - 1) % k]
    print(n - 1 - (x % m + ((n - 1) // k) * np.sum(d_mod) + np.sum(rem_d_mod)) // m
          - ((n - 1) // k) * np.count_nonzero(d_mod == 0) - np.count_nonzero(rem_d_mod == 0))
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
Q = int(input())
for _ in range(Q):
    B,C = map(int,input().split())
    A = [C if i == B else i for i in A]
    print (sum(A))


### FIXED CODE ###

n = int(input())
A = {}
a = list(map(int,input().split()))
for i in a:
    if not i in A:
        A[i] = 1
    else:
        A[i] += 1

s = 0
for k,v in A.items():
    s += k*v

Q = int(input())
for _ in range(Q):
    b,c = map(int,input().split())
    if b in A:
        s = s-(b-c)*A[b]
        if not c in A:
            A[c] = A[b]
        else:
            A[c] += A[b]
        A[b] = 0

    print (s)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
a.append(a[n-1]+1)
l=[0]
for i in range(n):
    l.sort()
    if a[i]>=a[i+1]:
        if l[0]<a[i]:
            l[0]=a[i]
        else:
            l.append(a[i])
    else:
        continue
if l[0]==0:
    print(len(l))
else:
    print(len(l)+1)

### FIXED CODE ###


from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<a[i]:
        l[-1]=a[i]
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))
### BUGGY CODE ###

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

### FIXED CODE ###

from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*a[i]
ans=0
lcm%=mod
for i in range(n):
  ans=(ans+lcm*inv[a[i]])%mod
print(ans%mod)
### BUGGY CODE ###

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

a = len(A)
for _ in range(M):
    B,C = input().split()
    A += [int(C)]*int(B)

A.sort(reverse=True)
print(sum(A[:a]))

### FIXED CODE ###

N, M = map(int,input().split())
A = [[1,int(a)] for a in input().split()]
BC = A + [list(map(int,input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

i = 0
ans = 0
for B,C in BC:
    if i + B <= N:
        ans += B*C
        i += B
    else:
        ans += (N - i) * C
        break

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

N = int(input())
As = sorted(list(map(int, input().split())))
As_set = set(As)

i = 0
while i < N - 1:  
  j = i + 1
  while j < N:
    if As[j] % As[i] == 0:
      if As[j] in As_set:
        As_set.remove(As[j])
      As.pop(j)
      N -= 1
    else:
      j += 1
  i += 1
  
print(len(As_set))

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
As = list(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd
from functools import reduce
l = As[0]
for a in As:
    l = l * a // gcd(l, a)

i = 2
while l & (i - 1) == 0:
    i <<= 1
i = (i >> 1) - 1

fg = False
if i > 0:
    for a in As:
        if a & i > 0:
            fg = True
            break

if fg:
    print(0)
else:
    print(M // l - M // (l * 2))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd

l = As[0]
for a in As:
    l = l * a // gcd(l, a)
    if l > M:
        break

if l <= M:
    i = 2
    while l & (i - 1) == 0:
        i <<= 1
    i = (i >> 1) - 1

    fg = False
    if i > 0:
        for a in As:
            if a & i > 0:
                fg = True
                break

    if fg:
        print(0)
    else:
        print(M // l - M // (l * 2))
else:
    print(0)
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)


@lru_cache(None)
def dp(i, prev):
    if i == N:
        return 0
    else:
        if prev is None or abs(A[i] - prev) <= K:
            return max(dp(i + 1, prev), dp(i + 1, A[i]) + 1)
        else:
            return dp(i + 1, prev)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print(dp(0, None))


### FIXED CODE ###

def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    S = list(input())

    streak = [[S[0], 1]]
    for i in range(1,N):
        if S[i] != S[i-1]:
            streak.append([S[i],1])
        else:
            streak[-1][1] += 1

    # print(streak)
    idx = streak.index(max(streak, key=lambda x:x[1]))

    for _ in range(K):
        if len(streak) == 1:
            break

        if len(streak) >= 3:
            if idx == 0 or idx == len(streak) - 1:
                idx = streak.index(max(streak[1:-1], key=lambda x:x[1]))

        new_direct = 'L' if streak[idx][0] == 'R' else 'R'
        max_streak = streak[idx][1]
        max_streak += streak[idx-1][1] if idx > 0 else 0
        max_streak += streak[idx+1][1] if idx + 1 < len(streak) else 0

        new_streak = []
        new_idx = 0

        if idx - 1 > 0:
            new_streak.extend(streak[:idx - 1])

        new_streak.append([new_direct,max_streak])
        new_idx = len(new_streak) -1

        if idx + 2 < len(streak):
            new_streak.extend(streak[idx + 2:])

        streak = new_streak
        idx = new_idx
        # print(streak, idx)

    ans = sum(map(lambda x: x[1] - 1, streak))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    S = list(input())

    rev = False
    rev_count = 0
    for i in range(1,N):
        if S[i] == S[i-1]:
            rev = False
        else:
            if not rev and rev_count < K:
                rev_count += 1
                rev = True

            if rev:
                S[i] = 'L' if S[i] == 'R' else 'R'


    ans = 0
    for i in range(1,N):
        if S[i] == S[i-1]:
            ans += 1

    print(ans)


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

from queue import Queue

n, q = map(int, input().split())
adj = [[] for _ in range(n + 1)]
lazy = [0] * (n + 1)

for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for _ in range(q):
    p, x = map(int, input().split())
    lazy[p] += x

qu = Queue()
qu.put((1, 0))
while not qu.empty():
    pair = qu.get()
    u = pair[0]
    for v in adj[u]:
        if v == pair[1]: continue
        lazy[v] += lazy[u]
        qu.put((v, u))

for i in range(1, n + 1):
    print(str(lazy[i]), end=' ')
 

### FIXED CODE ###

from queue import Queue
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

n, q = map(int, input().split())
adj = [[] for _ in range(n + 1)]
lazy = [0] * (n + 1)

for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for _ in range(q):
    p, x = map(int, input().split())
    lazy[p] += x

qu = Queue()
qu.put((1, 0))
while not qu.empty():
    pair = qu.get()
    u = pair[0]
    for v in adj[u]:
        if v == pair[1]: continue
        lazy[v] += lazy[u]
        qu.put((v, u))

for i in range(1, n + 1):
    print(str(lazy[i]) + ' ')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
C - Linear Approximation
https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

"""
import sys
from sys import stdin
input = stdin.readline


def solve(arr):
    ub = max(arr)
    lb = -max(arr)

    while True:
        mid1 = (lb*2 + ub) // 3
        mid2 = (lb + ub*2) // 3
        mid1_score = sum([abs(a-(mid1+i)) for i, a in enumerate(arr, start=1)])
        mid2_score = sum([abs(a-(mid2+i)) for i, a in enumerate(arr, start=1)])

        if mid2_score > mid1_score:
            ub = mid2
        else:
            lb = mid1
        if abs(ub - lb) <= 4:
            break

    ans = float('inf')
    for b in range(lb, ub+1):
        t = sum([abs(a-(b+i)) for i, a in enumerate(arr, start=1)])
        ans = min(ans, t)
    return ans



def main(args):
    N = int(input())
    arr = [int(a) for a in input().split()]
    ans = solve(arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
C - Linear Approximation
https://beta.atcoder.jp/contests/abc102/tasks/arc100_a
TLE
"""
import sys
from sys import stdin
input = stdin.readline

from functools import lru_cache
def _solve(arr):
    @lru_cache(maxsize=None)
    def calc_score(n):
        return sum([abs(a-(n+i)) for i, a in enumerate(arr, start=1)])

    ub = max(arr)
    lb = -max(arr)

    while True:
        mid1 = (lb*2 + ub) // 3
        mid2 = (lb + ub*2) // 3
        mid1_score = calc_score(mid1)
        mid2_score = calc_score(mid2)

        if mid2_score > mid1_score:
            ub = mid2
        else:
            lb = mid1
        if abs(ub - lb) <= 4:
            break

    ans = float('inf')
    for b in range(lb, ub+1):
        t = calc_score(b)
        ans = min(ans, t)
    return ans


from statistics import median

def solve(arr):
    def calc_score(n):
        return sum([abs(a-(n+i)) for i, a in enumerate(arr, start=1)])

    array_b = [a-i for i, a in enumerate(arr, start=1)]
    m = median(array_b)
    ans = float('inf')
    for i in range(int(m)-1, int(m)+2):
        ans = min(ans, calc_score(i))
    return ans



def main(args):
    N = int(input())
    arr = [int(a) for a in input().split()]
    ans = solve(arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

N =int(input())
ans = 0
for j in range(2,N):
  for i in range(N//(j),N//(j-1)):
    if (N//i) == N%i:
        ans += i
print(ans)

### FIXED CODE ###

import math
def prime_divisor(n):
    ls = []
    i = 2
    while i <= math.floor(n**0.5):
        if n%i == 0:
            ls.append(i)
            ls.append(n//i)
            i += 1
        else:
            i += 1
    if n > 1:
        ls.append(n)
    return ls
N = int(input())
ls1 = prime_divisor(N)
ls2 = [x-1 for x in list(set(ls1)) if x >= 2]
ls2.sort()
ls2.reverse()
ans = 0
for i in range(len(ls2)):
    if N // ls2[i] == N % ls2[i]:
        ans += ls2[i]
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
money=0
l=[]
for i in range(N):
    l.append(ab[i][0])
while True:
    min_id=l.index(min(l))
    for i in range(ab[min_id][1]):
        money+=l[min_id]
        ct+=1
        if ct==M:
            break
    ab[min_id][0]=-1
    l[min_id]=100000
    if ct==M:
        break
print(money)

### FIXED CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
ct1=0
ct2=0
money=0
l=[]
id=[]
for i in range(N):
    l.append(ab[i][0])
id=sorted(range(len(l)),key=lambda k: l[k])
l.sort()
while ct<M:
    while ct2<ab[id[ct1]][1]:##
        money+=l[ct1] #l[ct1]
        #print(money,l[ct1])
        ct+=1
        ct2+=1
        if ct==M:
            break
    ct1+=1
    ct2=0
print(money)
### BUGGY CODE ###

N = int(input())
X = [0]*N
L = [0]*N

for i in range(N):
    X[i], L[i] = map(int, input().split())

start = -1000000000
seen = [False]*N

while True:
    min = 2000000000
    minin = None
    for i in range(N):
        if X[i]-L[i]< start or seen[i]==True:continue
        if X[i]+L[i]<min:
            min = X[i]+L[i]
            minin = i

    if minin == None:
        break
    seen[minin] = True
    start = min

print(seen.count(True))


### FIXED CODE ###

from collections import deque
N = int(input())
X = [0]*N
L = [0]*N
lis = deque()
for i in range(N):
    X[i], L[i] = map(int, input().split())
    lis.append([i,X[i]-L[i], X[i]+L[i]])

lis = sorted(lis, key=lambda x:x[2])
lis = deque(lis)

end = lis[0][2]
start = lis[0][1]
lis.popleft()
cnt = 1
while lis:
    x, y, z = lis.popleft()
    if y < end:
        continue
    elif y >= end:
        start = y
        end = z
        cnt += 1

print(cnt)
### BUGGY CODE ###

from collections import Counter
N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res=[]
for letter,count in counted.most_common() :
    if count < counted.most_common()[0][1]:
        break
    else:
        res.append(letter)

[print(i) for i in sorted(res)]

### FIXED CODE ###

from collections import Counter


N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res_max= counted.most_common()[0][1]
ans = []
for k, v in counted.items():
    if v == res_max:
        ans.append(k)

ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = []
for i, j in combinations(range(1, N+1), 2):
    if j<=X:
        result.append(j-i)
    else:
        jy = abs(Y-j)
        ix = abs(X-i)
        if (j-i)<=(jy+ix+1):
            result.append(j-i)
        else:
            result.append(jy+ix+1)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

### FIXED CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = [0]*N
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result[mins] += 1
    
for i in range(1, N):
    print(result[i])
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

L=input()
a=0
x=10**9+7
c=len(L)
y=0
for i in range(c):
 if L[i]=="1":
  a+=(3**(c-1-i)*2**y)%x
  a%=x
  y+=1
print((a+2**y)%x)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

L=input()
a=0
x=10**9+7
def bp(a,n):
        r=1
        while(n):
           if n%2:
              r=r*a%x
           a=a*a%x
           n>>=1
        return r
c=len(L)
y=0
for i in range(c):
 if L[i]=="1":
  a+=(bp(3,c-1-i)*bp(2,y))%x
  a%=x
  y+=1
print((a+2**y)%x)
### BUGGY CODE ###

def examA():
    S = SI(); N = len(S)
    prev = S[0]; cur = ""
    k = 0; ans = 1
    while(k<N-1):
        k +=1
        cur += S[k]
        if cur==prev:
            continue
        prev = cur
        cur = ""
        ans +=1
    print(ans)
    return

def examB():
    N = I()
    S = SI()
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    K = 0
    ans = -1
    que = []
    for i in range(N):
        que.append((-B[i],i))
    heapify(que)
    flag = True
    while(que):
#        print(que)
        b,i = heappop(que)
        b *=(-1)
        if b<=A[i]:
            if b!=A[i]:
                flag = False
                break
            else:
                continue
        ac = B[i-1]+B[i+1-N]
        while(b>A[i] and b>=ac):
            b -=ac
            K +=1
        B[i] = b
        heappush(que,(-b,i))
#    print(que)
#    print(K)
    if flag:
        ans = K
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18

if __name__ == '__main__':
    examC()


### FIXED CODE ###

def examA():
    S = SI(); N = len(S)
    prev = S[0]; cur = ""
    k = 0; ans = 1
    while(k<N-1):
        k +=1
        cur += S[k]
        if cur==prev:
            continue
        prev = cur
        cur = ""
        ans +=1
    print(ans)
    return

def examB():
    N = I()
    S = SI()
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    ans = 0
    que = []
    for i in range(N):
        heappush(que,(-B[i],i))
    flag = True
    while(que):
        b,i = heappop(que)
        b *=(-1)
        if b == A[i]:
            continue
        a, c = B[(i - 1) % N], B[(i + 1) % N]
        if b - A[i] < a + c:
            flag = False
            break
        r = (b - A[i]) // (a + c)
        b -= (a + c) * r
        B[i] = b
        ans += r
        if b != A[i]:
            heapq.heappush(que, (-b, i))
#    print(que)
#    print(K)
    if flag:
        print(ans)
    else:
        print(-1)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18

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

N, M = map(int, input().split())
A = [ int(a) for a in input().split() ]
A.sort(reverse=True)

for m in range(M):
    A[0] = A[0] // 2
    A.sort(reverse=True)

print(sum(A))


### FIXED CODE ###

import heapq
import math

N, M = map(int, input().split())
A = [ -int(a) for a in input().split() ]
heapq.heapify(A)
for m in range(M):
    heapq.heappush(A, math.ceil(heapq.heappop(A) / 2.0))

print(-sum(A))
### BUGGY CODE ###

# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


def f(X):
    result = 1
    for _, c in prime_factorize(X):
        result *= c + 1
    return result


N = int(input())

prime_table = make_prime_table(N)
result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)


### FIXED CODE ###

# エラトステネスの篩
N = int(input())

sieve = [0] * (N + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, N + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, N + 1, i):
        if sieve[j] == 0:
            sieve[j] = i


def f(K):
    t = []
    a = K
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    result = 1
    for _, n in t:
        result *= (n + 1)
    return result


result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)
### BUGGY CODE ###

h, w, *s = open(0).read().split()
h = int(h)
w = int(w)

q = []
used = [False] * (h * w)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#' and not used[i * w + j]:
            bcnt = 0
            cnt = 0

            q.append((i, j))
            used[i * w + j] = True
            cnt += 1
            bcnt += 1

            for y, x in q:
                for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= nx < w and 0 <= ny < h and s[y][x] != s[ny][nx] and not used[ny * w + nx]:
                        q.append((ny, nx))
                        used[ny * w + nx] = True
                        cnt += 1
                        if s[ny][nx] == '#':
                            bcnt += 1
            ans += bcnt * (cnt - bcnt)
print(ans)


### FIXED CODE ###

from collections import deque
h, w, *s = open(0).read().split()
h = int(h)
w = int(w)

q = deque()
used = [False] * (h * w)

ans = 0
for i in range(h):
    for j in range(w):
        if not used[i * w + j]:
            bcnt = 0
            cnt = 0

            q.append((i, j))
            used[i * w + j] = True
            cnt += 1
            bcnt += s[i][j] == '#'

            while len(q):
                y, x = q.popleft()
                for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= nx < w and 0 <= ny < h and s[y][x] != s[ny][nx] and not used[ny * w + nx]:
                        q.append((ny, nx))
                        used[ny * w + nx] = True
                        cnt += 1
                        bcnt += s[ny][nx] == '#'
            ans += bcnt * (cnt - bcnt)
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())

for i in range(Q):
    B, C = map(int, input().split())
    A = np.where(A==B, C, A)              
    print(np.sum(A))

### FIXED CODE ###

from collections import Counter as cnt
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = sum(A)
D = cnt(A)

for i in range(Q):
    B, C = map(int, input().split())
    S = S+(C-B)*D[B]
    print(S)
    D[C] += D[B]
    D[B] = 0
### BUGGY CODE ###

n=int(input())
x=3500
for k in range(1,x):
    for j in range(1,x):
        if (4*j*k - n*k - n*j)!=0:
            i = n*j*k / (4*j*k - n*k - n*j)
            if i==int(i) and i>0:
                print(int(i),j,k)
                break
    else:
        continue
    break

### FIXED CODE ###

n=int(input())
for k in range(1,3501):
    for j in range(1,k+2):
        a=(4*j*k - n*k- n*j)
        if a<=0 : continue
        i = n*j*k / a
        i2= n*j*k // a
        if i==i2 :
            print(i2,j,k)
            break
    else:
        continue
    break