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

from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start]:
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]]:
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)

### FIXED CODE ###

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

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))
### BUGGY CODE ###

N=int(input())
#A,B,C>0 C=N-A*B
count=(N-1)*2-1
for A in range(2,N):
    for B in range(2,N):
        if N-(A*B)<0:
            break
        elif N-(A*B)>0:
            count+=1
            # print(A,B,N-A*B)
print(count)

### FIXED CODE ###

N=int(input())
count=0
for A in range(1,N):
    count+=int((N-1)/A)
print(count)
### BUGGY CODE ###

H, W = map(int, input().split())

List = list(range(H) for i in range(W))
count = 0

for i in range(W):
  for j in range(H):
    if List[i][j]%2 == 0 and i%2 ==0:
      count +=1
    elif List[i][j]%2 != 0 and i%2 !=0:
      count +=1

print(count)


### FIXED CODE ###

H, W = map(int, input().split())

if H==1 or W==1:
  Answer =1

elif W%2 ==0:
  Answer = W/2*H
  
else:
  count = (W-1)/2 +1
  if H%2 ==0:
    Answer = count*H - H/2
  else:
    Answer = count*H - (H-1)/2

print(int(Answer))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [[]]
for i in range(N):
    A.append(LIST()[::-1])

def check(li):
    global cnt
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    nxtli = set()
    for i in li:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をセットに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    return nxtli

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    nxtli = check(nxtli)
    day += 1
print(day)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=[]
b=[]
c=[]
d=[]
for j in range(0,n):
    t1,t2,t3,t4 = (int(i) for i in input().split())  
    a.append(t1)
    b.append(t2)
    c.append(t3)
    d.append(t4)
    
for i in range(0,n):
    if a[i] < b[i]:
        print("No")
    elif d[i] < b[i]:
        print("No")
    else:
        flag=1
        for j in range(0,b[i]):
            p= (a[i]+j*d[i]) % b[i]
            if p==0:
                break
            elif p > c[i]:
                flag=0
                break
        if flag == 1:
            print("Yes")
        else:
            print("No")
    



### FIXED CODE ###

#
import sys

n = int(input())
a=[]
b=[]
c=[]
d=[]
for j in range(0,n):
    t1,t2,t3,t4 = (int(i) for i in input().split())  
    a.append(t1)
    b.append(t2)
    c.append(t3)
    d.append(t4)
    
for i in range(0,n):
    if a[i] < b[i]:
        print("No")
    elif d[i] < b[i]:
        print("No")
    else:
        p= b[i]
        q= d[i]
        while p%q :
            r=q
            q=p%q
            p=r
        if (b[i]-q)+a[i]%q > c[i]:
            print("No")
        else:
            print("Yes")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter

MOD = 1000000007  # type: int

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = {i:0 for i in range(1, n+1) if is_prime[i-1]}
    # return is_prime, table
    return table

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def solve(N: int, A: "List[int]"):
    table = dict()

    for i in range(N):
        decom = Counter(prime_decomposition(A[i]))

        for d,number in decom.items():
            if table.get(d) == None:
                table[d] = number
                continue

            if table[d] < number:
                table[d] = number
    LCM = 1
    for key,value in table.items():
        LCM *= key**value

    print(sum([LCM//a for a in A])%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 fractions
from functools import reduce
import random

MOD = 1000000007  # type: int

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def solve(N: int, A: "List[int]"):

    LCM = reduce(lcm,A)
    answer = 0
    for i in range(N):
        answer += LCM//A[i]
    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()
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
points = list(map(lambda x: x-q, [k for i in range(n)]))
for i in set(a):
    points[i-1] += a.count(i)
for i in points:
  if i <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[k-q]*n
for i in range(q):
    point=int(input())
    a[point-1] += 1
for i in range(len(a)):
    if a[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N, K = LI()
    Aarray = LI()

    start = 1
    for i in range(K):
        start *= Aarray[i]

    for i in range(K, N):
        now = start*Aarray[i]/Aarray[i-K]
        if now > start:
            print("Yes")
        else:
            print("No")
        start = now


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）

import sys


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N, K = LI()
    Aarray = LI()

    # start = 1
    # for i in range(K):
    #     start *= Aarray[i]

    # for i in range(K, N):
    #     now = start/Aarray[i-K]*Aarray[i]
    #     if now > start:
    #         print("Yes")
    #     else:
    #         print("No")
    #     start = now

    for i in range(K, N):
        now = Aarray[i-K]
        now2 = Aarray[i]
        if now2 > now:
            print("Yes")
        else:
            print("No")


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

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                I=str(i)
                if j=="?":
                    for r in map(str,range(10)):
                        dp[int(I+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(I+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[(10*i+r)%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


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

c = Counter(a)

ans = n
for e in a:
    c[e] -= 1
    for fct in fact(e):
        if c[fct]:
            ans -= 1
            break

    c[e] += 1

print(ans)


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


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

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
    l = []
    for i in range(len(S)):
      for j in range(i+1, len(G)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!='#':
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                if nexty == G[j][0] and nextx == G[j][1]:
                  break
                que.append([nexty,nextx])
        l.append(maze1[G[j][0]][G[j][1]])
    print(max(l))
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1 for i in range(Q)]

dist = [10000000000000 for i in range(Q)]

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]



for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])


### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<18
NG=0

while OK-NG>10**(-6):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<31
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)
### BUGGY CODE ###

ABC = 'ABC'
S = input()

dp = [0, 0, 0, 0]
dp[3] = 1

for i in range(len(S))[::-1]:
    c = S[i]
    if c == '?':
        dp[0] = 3 * dp[0] + dp[1]
        dp[1] = 3 * dp[1] + dp[2]
        dp[2] = 3 * dp[2] + dp[3]
        dp[3] = 3 * dp[3]
    elif c == 'A':
        dp[0] = 1 * dp[0] + dp[1]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'B':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1] + dp[2]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'C':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2] + dp[3]
        dp[3] = 1 * dp[3]

print(dp[0] % 1000000007)


### FIXED CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)
### BUGGY CODE ###

N = int(input())

num_list = list(map(int, input().split()))
     
num = 1
     
for i in num_list:
    num *= i
    
    if num == 0:
        break

if num > 1000000000000000000:
    num = -1

print(num)

### FIXED CODE ###

def product(list):
    num = 1

    if any([i == 0 for i in num_list]):
        print(0)
        return
     
    for i in num_list:
        num *= i
        if num > 1000000000000000000:
            num = -1
            break

    print(num)


N = int(input())

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

product(num_list)
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
#print(cum)
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    for i in range(4):
        s[0] = cum[ll - (i&1)]
        s[1] = cum[mid] - cum[ll - (i&1)]
        s[2] = cum[rl - ((i&2) >> 1)] - cum[mid]
        s[3] = cum[n] - cum[rl - ((i&2) >> 1)]
#        print(ll - (i&1), mid, rl - ((i&2) >> 1), s)
        mincost = min(mincost, max(s) - min(s))
print(mincost)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    lrsum += new
    l[mid] = l[mid-1]
    unk = a[l[mid]]
    while(abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk)):
        llsum += unk
        lrsum -= unk
        l[mid] += 1
        unk = a[l[mid]]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    rlsum += new
    r[mid] = r[mid+1]
    unk = a[r[mid] - 1]
    while(abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk)):
        rrsum += unk
        rlsum -= unk
        r[mid] -= 1
        unk = a[r[mid] - 1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)
### BUGGY CODE ###

#!/usr/bin/env python
import math

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

def lcm(a, b): 
    return a*b//math.gcd(a, b)

l = a[0]
for i in range(n):
    l = lcm(l, a[i])

ans = 0 
for i in range(n):
    ans += (l//a[i])%mod

print(ans%mod)


### FIXED CODE ###

#!/usr/bin/env python
import math
n = int(input()) 
a = list(map(int, input().split()))

mod = 10**9+7

def lcm(a, b): 
    return a*b//math.gcd(a, b)

l = a[0]
for i in range(n):
    l = lcm(l, a[i])
l %= mod 

ans = 0 
for i in range(n):
    inv = pow(a[i], mod-2, mod)
    ans += (l*inv)%mod

print(ans%mod)