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

def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

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

n, k = map(int, input().split())
dp = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

#A**n
def pow(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B

ans_matrix = pow(dp, k, MOD)
ans = 0
for i in range(n):
    ans += sum(ans_matrix[i])
    ans %= MOD
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
dp = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

#A**n
def pow(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B

ans_matrix = pow(dp, k, MOD)
ans = 0
for i in range(n):
    ans += sum(ans_matrix[i])
    ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import deque
 
S = input()
 
ss = []
flag = True
ans = 0
for i in range(len(S)): ss.append(S[i])
 
while flag:
    length = len(ss)
    tmp_flag = False
    for i in range(length-1):
        if ss[i] != ss[i+1]:
            rm = i
            ans += 2
            tmp_flag = True
            break
    if tmp_flag:
        ss.pop(rm)
        ss.pop(rm)
    else:
        flag = False
    
print(ans)


### FIXED CODE ###

S = input()

ss = []
ans = 0
for i in range(len(S)): ss.append(S[i])

zeros = 0
ones = 0

for i in range(len(ss)):
    if ss[i] == "0":
        zeros += 1
    elif ss[i] == "1":
        ones += 1

ans = 2*min(zeros, ones)
print(ans)
### BUGGY CODE ###

#n = int(input())
n,k = map(int,input().split())
p_L = list(map(int,input().split()))

mydata = []

for i in p_L:
    kitai = sum(list(range(1,i+1)))/i
    mydata.append(kitai)

res = [0] * (n+1)

res[0] = mydata[0]
for i in range(len(mydata)-1):
    res[i+1] = res[i] + mydata[i+1]

# print(mydata)
# print(res)
# print("----")
ans = 0
for i in range(n-k+1):
    ans = max(ans,sum(mydata[i:i+k]))
    #print(mydata[i:i+k])
print(ans)

### FIXED CODE ###

#n = int(input())
n,k = map(int,input().split())
p_L = list(map(int,input().split()))

mydata = []

kazu = list(range(1,1001))
for i in p_L:

    kitai = sum(kazu[0:i])/i
    mydata.append(kitai)

res = [0] * (n+1)

res[0] = mydata[0]
for i in range(len(mydata)-1):
    res[i+1] = res[i] + mydata[i+1]

# print(mydata)
# print(res)
# print("----")
ans = 0
for i in range(n):
    tmp = res[i] - res[i-k]
    ans = max(ans,tmp)
    #print(mydata[i:i+k])
print(ans)
### BUGGY CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input())*10**9)
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

T = input()
# T ="PD?D??P"

for i in range(len(T)):
    if T[i] == "?":
        if i == 0:
            T = "D" + T[1:len(T)]
        if i == len(T) - 1:
            T = T[:len(T)-1] + "D"
        else:
            T = T[0:i] + "D" + T[i+1:len(T)]
print(T)


#
# P = 0
# D = 0
# Q = 0
# for i in range(len(T)):
#     if T[i] == "P":
#         P += 1
#     elif T[i] == "D":
#         D += 1
#     else:
#         Q += 1
# while Q >= 1:
#     if P >= D:
#         D += 1
#         Q -= 1
#     else:
#         P += 1
#         Q -= 1
#
# if P == D:
#     while P >= 1:
#         print("PD", end='')
#         P -= 1
#         D -= 1
#     print("")
# elif P > D:
#     while D >= 1:
#         print("PD", end="")
#         P -= 1
#         D -= 1
#     while P >= 1:
#         print("P", end="")
#         P -= 1
#     print("")
# elif P < D:
#     while P >= 1:
#         print("PD", end="")
#         P -= 1
#         D -= 1
#     while D >= 1:
#         print("D", end="")
#         D -= 1
#     print("")
#
#
# # print(P)
# # print(D)
# # print(Q)


### FIXED CODE ###

T = input()
# T ="PD?D??P"
L = len(T)
ans = ""

for i in range(L):
    if T[i] == "?" or T[i] == "D":
        ans += "D"
    else:
        ans += "P"

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

import math
num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    j = 0
    k = 0
    l = 0
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j == k and k == l:
                        xyz_count += 1
                    elif j == k and k > l or j > k and k == l:
                        xyz_count += 3
                    else:
                        xyz_count += 6
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,l = inpl()
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a,b,c = inpl()
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
e = [[INF]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            e[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            e[i][j] = min(e[i][j], e[i][k]+e[k][j])
q = inp()
for _ in range(q):
    a,b = inpl()
    ans = e[a-1][b-1]
    print(-1 if ans == INF else ans-1)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,l = inpl()
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a,b,c = inpl()
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
e = [[INF]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            e[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            e[i][j] = min(e[i][j], e[i][k]+e[k][j])
q = inp()
for _ in range(q):
    a,b = inpl()
    ans = e[a-1][b-1]
    print(-1 if ans == INF else ans-1)
### BUGGY CODE ###

S = input()
T = input()

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [['']*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j]+S[i]
            elif len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
    ans = dp[-1][-1]
    return ans
print(solve(S,T))

### FIXED CODE ###

S = input()
T = input()

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [[0]*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    ans = ''
    i,j = s,t
    while i>0 and j>0:
        if dp[i][j]==dp[i-1][j]:
            i -= 1
        elif dp[i][j]==dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1]+ans
            i-=1
            j-=1
    return ans
print(solve(S,T))
### BUGGY CODE ###


def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = max(
                                        array[i-1][j],
                                        array[i][j-1],
                                        array[i-1][j-1]+c)
        print(array[na-1][nb-1])
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###


def solve():
  s = input()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])
    for j in range(2):
      if j==0:
        dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
        if number != 9:
          dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
      else:
        dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
        dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  #print(dp)
  print(min(dp[n][0],dp[n][1]+1))
solve()

### FIXED CODE ###


def solve():
  s = input()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])
    for j in range(2):
      if j==0:
        dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
        if number != 9:
          dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
      else:
        dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
        dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  #print(dp)
  print(min(dp[n][0],dp[n][1]+1))
solve()
### BUGGY CODE ###

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

for i in range(1,n+1):
    ch = [[] for _ in range(n+1)]
    pa = [0]*(n+1)
    dp = [[1,1] for _ in range(n+1)]
    checked = []
    stack = [i]
    stack2 = []
    while stack:
        a = stack.pop()
        checked.append(a)
        if a != i and len(graph[a]) == 1:
            stack2.append(a)
        else:
            for j in graph[a]:
                if j in checked:
                    continue
                else:
                    checked.append(j)
                    stack.append(j)
                    pa[j] = a
                    ch[a].append(j)
    checked = []
    while stack2:
        a = stack2.pop()
        if a == i:
            print(dp[i][0])
            break
        else:
            p = pa[a]
            dp[p][0] *= dp[a][0]*factorial_inv[dp[a][1]]
            dp[p][0] %= mod
            dp[p][1] += dp[a][1]
            ch[p].remove(a)
            if len(ch[p]) == 0:
                dp[p][0] *= factorial[dp[p][1]-1]
                dp[p][0] %= mod
                stack2.append(p)
            checked.append(a)

### FIXED CODE ###

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i%mod
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

pa = [0]*(n+1)
dp = [1]*(n+1)
size = [1]*(n+1)
checked = []
stack = [i]
while stack:
    a = stack.pop()
    checked.append(a)
    for j in graph[a]:
        if pa[a] == j:   
            continue
        else:
            stack.append(j)
            pa[j] = a

for i in checked[::-1]:
    p = pa[i]
    s = size[i]
    dp[i] *= factorial[s-1]
    dp[i] %= mod
    dp[p] *= dp[i]*factorial_inv[s]
    dp[p] %= mod
    size[p] += s

size_ = [n-i+1 for i in size]
dp_ = [1]*(n+1)
for i in checked[1:]:
    p = pa[i]
    dp_[i] *= dp[p]
    dp_[i] *= factorial_inv[size[p]-1]
    dp_[i] *= pow(dp[i],mod-2,mod)
    dp_[i] *= factorial[size[i]]
    dp_[i] *= dp_[p]
    dp_[i] *= factorial_inv[size_[p]-1]
    dp_[i] *= factorial[size_[i]-2]
    dp_[i] %= mod
    
for i in range(1,n+1):
    ans = factorial[n-1]*dp[i]*dp_[i]*factorial_inv[size[i]-1]*factorial_inv[size_[i]-1]
    ans %= mod
    print(ans)
### BUGGY CODE ###

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

D_list = [[int(i) for i in input().split()] for _ in range(c)]
c_list = [[int(i) for i in input().split()] for _ in range(n)]


ans = 10 ** 10
for i in range(1,c**3):
    x=i%c
    y=(i%c**2)//c
    z=i//c**2
    if x==y or y==z or z==x:
        continue
    else:
        color=[x,y,z]
        count = 0
        for a in range(n):
            for b in range(n):
                if color[(a+b+2)%3] != c_list[b][a]-1:
                    count+=D_list[c_list[b][a]-1][color[(a+b+2)%3]]
        if count < ans:
            ans = count

print(ans)


### FIXED CODE ###

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

D_list = [[int(i) for i in input().split()] for _ in range(c)]
c_list = [[int(i) for i in input().split()] for _ in range(n)]

c_num=[[0 for _ in range(3)] for __ in range(c)]

for a in range(n):
    for b in range(n):
        c_num[c_list[b][a]-1][(a+b+2)%3] += 1


ans = 10 ** 10
for i in range(1,c**3):
    x=i%c
    y=(i%c**2)//c
    z=i//c**2
    if x==y or y==z or z==x:
        continue
    else:
        color=[x,y,z]
        count = 0
        for s in range(3):
            for t in range(c):
                count += c_num[t][s] *D_list[t][color[s]]

        if count < ans:
            ans = count

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

import itertools
N,M=map(int,input().split())
kslist=[]
for i in range(M):
    kslist.append(list(map(int,input().split()))) 
plist=list(map(int,input().split()))
seq=[0]*N+[1]*N
ls=list(set(list(itertools.permutations(seq,N))))
n=0
for tup in ls:
    ln=[]
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        ln.append(sum1%2)
    if ln==plist:
        n+=1
        
print(n)            
    


### FIXED CODE ###

import itertools
N,M=map(int,input().split())
kslist=[(list(map(int,input().split()))) for i in range(M)]
plist=list(map(int,input().split()))
ls=list((itertools.product(range(2),repeat=N)))
n=0
for tup in ls:
    n+=1
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        if sum1%2!=plist[j]:
            n=n-1
            break
print(n)
### BUGGY CODE ###

import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
dis_dict = dict()
parent = [i for i in range(n)]

def calc_dis(x):
    ls = []
    cnt = 0
    while parent[x] != x:
        ls.append(x)
        cnt += dis[x]
        x = parent[x]
    for l in ls:
        parent[l] = x
    return cnt

graph = [[0 for i in range(n)] for j in range(n)]
dis = [0 for i in range(n)]
already = set()
flg = True
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    if l in already and r in already:
        if calc_dis(r) - calc_dis(l) != d:
            flg = False
            break
    if r in already:
        if dis[r] > d:
            parent[l] = parent[r]
            dis[l] = dis[r] - d
            dis[r] = d
        else:
            parent[parent[r]] = l
            dis[parent[r]] = d - dis[r]
    else:
        parent[r] = l
        dis[r] = d
    already.update((l, r))
if flg:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

already = set()
x_ls = [None for i in range(n)]
x_ls[0] = 0
stack = list(range(n))[::-1]
flg = True
while len(stack) > 0:
    cur = stack.pop(-1)
    if cur in already:
        continue
    if x_ls[cur] is None:
        cur_pos = 0
    else:
        cur_pos = x_ls[cur]
    already.add(cur)
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            stack.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
if flg:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import fractions


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


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


### FIXED CODE ###

import fractions


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


n = int(input())
a = list(map(int, input().split()))
num = 1
for i in range(n):
    num = lcm(num, a[i])
ans = 0
for i in range(n):
    ans += num // a[i]
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

from itertools import accumulate 
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S=list(accumulate(A))
S.insert(0,0)

L=[ (s-i)%k  for i,s in enumerate(S)]
def f(l):
    return sum([x*(x-1)//2 for x in l])

from collections import Counter

ans=0
for i in range(n):
    #print(L[i+1:i+k],L[i])
    ans += (L[i+1:i+k].count(L[i]))
print(ans)

### FIXED CODE ###

from itertools import accumulate 
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S=list(accumulate(A))
S.insert(0,0)

L=[ (s-i)%k  for i,s in enumerate(S)]
def f(l):
    return sum([x*(x-1)//2 for x in l])

from collections import Counter

ans=0
d = Counter(L[1:k])
for i in range(n):
    ans += d[L[i]]
    #print(L[i+1:i+k],d)
    d[L[i+1]] -= 1
    if i+k <= n:
        d[L[i+k]] += 1
print(ans)
### BUGGY CODE ###

import numpy as np


N,M=map(int,input().split())
A=np.array(list(map(int,input().split())),dtype=np.int64)
A=np.sort(A)

for i in range(M):
    B,C=map(int,input().split())
    for j in range (B):
        count=np.count_nonzero(A<C)
        if count>0:
            m=min(B,count)
            A[:m]=C
        else:
            continue
    
    A=np.sort(A)

print(np.sum(A))

### FIXED CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int32)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int32)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    change_Num=Arr[j][1]
    count=np.count_nonzero(A<change_Num)
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=change_Num
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))
### BUGGY CODE ###

N = int(input())
S =  input()
max_length = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
print(max_length)

### FIXED CODE ###

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))