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

from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x-=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
    
  Map[x][y]+=1
  Map[x][y-K]+=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]+=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]+=-1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))

    
  
  


### FIXED CODE ###

from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x-=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
    
  Map[x][y]+=1
  Map[x][y-K]+=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]+=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]+=-1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))
### BUGGY CODE ###

import sys
read = sys.stdin.read

N, *A = map(int, read().split())
mod = 10 ** 9 + 7
answer = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        answer += A[i] ^ A[j]
        answer %= mod

print(answer)

### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.read

N, *A = map(int, read().split())
a = np.array(A, np.int64)
mod = 10 ** 9 + 7
answer = 0
for i in range(60):
    bit = np.count_nonzero(a & 1)
    answer += 2 ** i * bit * (N - bit)
    answer %= mod
    a >>= 1

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

r , g , b , n = map(int,input().split())
ans = 0
R = -(-n//r)
G = -(-n//g)
for i in range(R+1):
    for j in range(G+1):
        if (n-r*i-g*j)/b < 0:
            break
        else:
            if ((n-r*i-g*j)/b).is_integer():
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
r , g , b , n = map(int,input().split())
ans = 0
R = -(-n//r)
G = -(-n//g)
for i in range(R+1):
    for j in range(G+1):
        su = n-r*i-g*j
        if n-r*i-g*j < 0:
            break
        else:
            if (su/b).is_integer():
                ans += 1
print(ans)
### BUGGY CODE ###

n = input()

v = [[0, 0] for i in range(n)]
for i in range(n):
	v[i] = map(int, raw_input().split(' '))

a, b = 1, 1

for i in range(n):
	while a * v[i][1] != b * v[i][0]:
		if a * v[i][1] < b * v[i][0]:
			a += 1
		else:
			b += 1

print a + b


### FIXED CODE ###

n = input()

v = [[0, 0] for i in range(n)]
for i in range(n):
	v[i] = map(int, raw_input().split(' '))

a, b = 1, 1

for i in range(n):
	change = v[i][0] * b - a * v[i][1]
	while change != 0:
		if change < 0:
			additions = (-change + v[i][0] - 1) / v[i][0]
			change += additions * v[i][0]
			b += additions
		if change > 0:
			additions = (change + v[i][1] - 1) / v[i][1]
			change -= additions * v[i][1]
			a += additions

print a + b
### BUGGY CODE ###

def calc_expected_value(n):
    sum_n = [i for i in range(1, n+1)]
    return sum(sum_n) / n


n, k_range = map(int, input().split())
p = list(map(int, input().split()))
ans = 0.0

for i in range(n-k_range+1):
    e = sum([calc_expected_value(p[i+k]) for k in range(k_range)])
    ans = max(ans, e)

print(ans)

### FIXED CODE ###

def calc_expected_value(n):
    return (n+1) / 2


n, k_range = map(int, input().split())
p = list(map(int, input().split()))
e_list = [0] * n
ans_list = [0] * n
ans = 0.0

for i in range(n):
    e_list[i] = calc_expected_value(p[i])
    if i == k_range-1:
        ans_list[i] = sum([e_list[i-k] for k in range(k_range)])
    else:
        ans_list[i] = ans_list[i-1] + e_list[i] - e_list[i-k_range]

print(max(ans_list))
### BUGGY CODE ###

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

from itertools import combinations

MOD = 10**9+7
ans = 0

for c in combinations(a, 2):
    tmp = c[0]^c[1]
    tmp %= MOD
    ans += c[0]^c[1]
    ans %= MOD

print(ans%MOD)

### FIXED CODE ###

"""
ビット演算, XOR

XORは桁ごとに独立して計算できるので、桁ごとに計算する
XORが1になるのは0と1を足した時。2つの数を足す時、一方の数のi桁目が1でもう一方の数のi桁目が0であれば、2つの数を足した時のi桁目が1になる
全部で数がn個あるとき、i桁目が1の数がx個ある場合は、i桁目が0の数がn-x個あることになるので、x*(n-x)個の組み合わせでi桁目のXORが1になる
"""

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

MOD = 10**9+7
ans = 0

for i in range(60):
    x = 0 # i桁目が1である数の個数
    for j in range(n):
        if a[j]>>i&1: # "a[j]のi桁目が1である"という意味
            x += 1
    now = x*(n-x)%MOD
    for j in range(i):
        now = now*2%MOD # 2**60をかけると容易にオーバーフローするので、安全に2をかけるごとにMODをとっている
    ans += now
    ans %= MOD
    
print(ans)
### BUGGY CODE ###

import numpy as np

N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = np.full((N_max + 1, N_max * a_max + 1, N_max * b_max + 1), inf, dtype='int16')
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[[inf for _ in range(N_max * b_max + 1)] for _ in range(N_max * a_max + 1)] for _ in range(N_max + 1)]
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            if a + aa < N_max * a_max + 1 and b + bb < N_max * b_max + 1:
                dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)
### BUGGY CODE ###

n,k = map(int,input().split())
p=0
a=0
p_s=(1/n)
for i in range(1,n+1):
    while i<k:
        i*2
        p_s/=2
    p+=p_s
print(p)


### FIXED CODE ###

from math import log2
from math import ceil
n,k=map(int,input().split())
p=0


for i in range(1,n+1):
    if i>=k:
        p+=1/n
    else:
        cnt=ceil(log2(k)-log2(i))
        p+=(1/n)*((1/2)**cnt)
    

print(p)
### BUGGY CODE ###


import fractions
import sys

n1 = int(input())
nl1 = [int(i1) for i1 in input().split()]

if n1 == 2:
    print(max(nl1))
    sys.exit()

r1 = 0
n2 = fractions.gcd(nl1[0], nl1[1])

if n1 >= 3:
    n2 = max(n2, fractions.gcd(nl1[1], nl1[2]))
    n2 = max(n2, fractions.gcd(nl1[0], nl1[2]))

c1 = 0
for i2 in range(n1):
    if nl1[i2] % n2 != 0:
        c1 += 1
    if c1 >= 2:
        break
    if i2 == (n1 - 1):
        r1 = n2

i3 = n2

while r1 == 0:
    c1 = 0
    for i4 in range(n1):
        if nl1[i4] % i3 != 0:
            c1 += 1
        if c1 >= 2:
            break
        if i4 == (n1 - 1):
            r1 = i3
    i3 -= 1

print(str(r1))


### FIXED CODE ###

import fractions
import sys

n1 = int(input())
nl1 = [int(i1) for i1 in input().split()]

if n1 == 2:
    print(max(nl1))
    sys.exit()

r1 = 0

nl1.sort()

if n1 >= 3:
    n2 = fractions.gcd(nl1[0], nl1[1]) 
    n2 = max(n2, fractions.gcd(nl1[1], nl1[2]))
    n2 = max(n2, fractions.gcd(nl1[0], nl1[2]))

c1 = 0
for i2 in range(n1):
    if nl1[i2] % n2 != 0:
        c1 += 1
    if c1 >= 2:
        break
    if i2 == (n1 - 1):
        r1 = n2

i3 = n2

while r1 == 0:
    c1 = 0
    for i4 in range(n1):
        if nl1[i4] % i3 != 0:
            c1 += 1
        if c1 >= 2:
            break
        if i4 == (n1 - 1):
            r1 = i3
    i3 -= 1

print(str(r1))
### BUGGY CODE ###

h,w = map(int,input().split())
M = []
for i in range(h):
    M.append(input())
L = []
R = []
U = []
D = []
Total = []
for i in range(h):
    s = [0]*w
    L.append(s)
for i in range(h):
    s = [0]*w
    R.append(s)
for i in range(h):
    s = [0]*w
    U.append(s)
for i in range(h):
    s = [0]*w
    D.append(s)
for i in range(h):
    s = [0]*w
    Total.append(s)
for i in range(h):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1]+1
for i in range(h):
    for j in range(w-1,-1,-1):
        if M[i][j] == '#':
            None
        else:
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1]+1
for i in range(h):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j]+1
for i in range(h-1,-1,-1):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j]+1
for i in range(h):
    for j in range(w):
        Total[i][j] += L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
ans = 0
for i in range(h):
    for j in range(w):
        if Total[i][j] > ans:
            ans = Total[i][j]
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
M = []
for i in range(h):
    M.append(input())
L = []
R = []
U = []
D = []
Total = []
for i in range(h):
    s = [0]*w
    L.append(s)
for i in range(h):
    s = [0]*w
    R.append(s)
for i in range(h):
    s = [0]*w
    U.append(s)
for i in range(h):
    s = [0]*w
    D.append(s)
for i in range(h):
    s = [0]*w
    Total.append(s)
for i in range(h):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1]+1
for i in range(h):
    for j in range(w-1,-1,-1):
        if M[i][j] == '#':
            None
        else:
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1]+1
for i in range(h):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j]+1
for i in range(h-1,-1,-1):
    for j in range(w):
        if M[i][j] == '#':
            None
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j]+1
for i in range(h):
    for j in range(w):
        Total[i][j] += L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
ans = 0
for i in range(h):
    for j in range(w):
        if Total[i][j] > ans:
            ans = Total[i][j]
print(ans)
### BUGGY CODE ###

n = int(input())

digit_sum = 0

while n > 0:
    digit_sum += n % 10
    n = n // 10

ans = digit_sum % 9

if ans == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n = int(input())

result = sum(list(map(int, str(n))))

if result % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b=0
for i in range(n):
  for j in range(n-1):
    if(a[j]==i+1):
      b+=1
  print(b)
  b=0

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b=0
c = [0]*n+[0]
for i in range(n-1):
  c[a[i]] +=1
for j in range(1,n+1):
  print(c[j])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)
### BUGGY CODE ###

N = int(input())
S = input()

a = N - 3

s = set()
for i in range(0, N - 2):
    s1 = S[i]
    for j in range(i + 1, N - 1):
        s2 = s1 + S[j]
        for k in range(j + 1, N):
            s3 = s2+S[k]
            s.add(s3)

print(len(s))

### FIXED CODE ###

N = int(input())
S = input()

s = set()
sub = set()
for i in range(0, N - 2):
    s1 = S[i]
    if s1 in sub:
        continue
    sub.add(s1)
    for j in range(i + 1, N - 1):
        s2 = s1 + S[j]
        if s2 in sub:
            continue
        sub.add(s2)
        for k in range(j + 1, N):
            s3 = s2+S[k]
            s.add(s3)

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

from heapq import heappop,heappush
from math import sqrt
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  todo=[[0,n]]
  mi=set(range(n+2))
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v not in mi:continue
    mi.remove(v)
    for nv in mi:
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
  print(seen[n+1])
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

input()
A=list(map(int,input().split()))
B=set(A)
dict={}
for x in B:
  dict[x]=A.count(x)
max=0
for x in B:
  tmp = dict[x]
  if x-1 in B:
    tmp+=dict[x-1]
  if x+1 in B:
    tmp+=dict[x+1]
  if tmp>max:
    max=tmp
print(max)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
Ap = [a+1 for a in A]
Am = [a-1 for a in A]
label = set(A+Ap+Am)
dict = {l:0 for l in label}
for a in A+Ap+Am:
    dict[a]+=1
print(max(dict.values()))
### BUGGY CODE ###

x = int(input())

my_dict = dict()

for i in range(10 ** 6):
    my_dict[i**5] = i

for i in range(-10 ** 6, 10 ** 6):
    target = x + (i ** 5)
    if (- target) in my_dict:
        print(-my_dict[target], i)
        exit()
    elif target in my_dict:
        print(my_dict[target], i)
        exit()


### FIXED CODE ###

x = int(input())

my_dict = dict()

for i in range(1000):
    my_dict[i**5] = i

for i in range(-1000, 1000):
    target = x + (i ** 5)
    if (- target) in my_dict:
        print(-my_dict[-target], i)
        exit()
    elif target in my_dict:
        print(my_dict[target], i)
        exit()
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
rt = [[] for i in range(n)]
dk = [10**10] * n
srb = [None]*n

for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

d = dict()
dk[0] = 0
for i in rt[0]:
    d[i] = 1
    dk[i] = 1
    srb[i] = 1

while len(d) != 0:
# for j in range(20):
    # ルートが最小のnodeを見つける
    mincost = 10**6
    minnode, mincost = min(d.items(),key=lambda x: x[1])
    # for i in l:
    #     if mincost > dk[i]:
    #         mincost = dk[i]
    #         minnode = i
    # そのnodeの数字を確定し、
    del d[minnode]
        
    # 隣接する確定してないnodeにコストを上書き（小さければ）
    # queueに隣接nodeをappend
    for i in rt[minnode]:
        if dk[i] > dk[minnode]:
            dk[i] = dk[minnode]+1
            srb[i] = minnode+1
            d[i] = dk[minnode]+1

    
print('Yes')
for i in range(1,n):
    print(srb[i])






### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()

rt = [[] for i in range(n)]
srb = [None] * n
dk = [10**10]*n


for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

from collections import deque
l = deque()

srb[0] = 0
for i in rt[0]:
    l.append(i)
    srb[i] = 1

while len(l) != 0:
    c = l.popleft()
    for i in rt[c]:
        if srb[i] == None:
            l.append(i)
            srb[i] = c+1

print('Yes')
for i in range(1,n):
    print(srb[i])
### BUGGY CODE ###

from collections import deque

d = deque(list(input()))
q = int(input())
flag = 1
for i in range(q):
    query = input().split()
    if query[0] == '1':
        flag = - flag
    elif query[0] == '2':
        if flag == 1:
            if query[1] == '1':
                d.appendleft(query[2])
            elif query[1] == '2':
                d.append(query[2])
        else:
            if query[1] == '1':
                d.append(query[2])
            elif query[1] == '2':
                d.appendleft(query[2])
if flag == -1:
    d.reverse()
ans = ''
l = len(d)
for i in range(l):
    ans += d[i]
print(ans)

### FIXED CODE ###

from collections import deque

d = deque(list(input()))
q = int(input())
flag = 1
for i in range(q):
    query = input().split()
    if query[0] == '1':
        flag = - flag
    elif query[0] == '2':
        if flag == 1:
            if query[1] == '1':
                d.appendleft(query[2])
            elif query[1] == '2':
                d.append(query[2])
        else:
            if query[1] == '1':
                d.append(query[2])
            elif query[1] == '2':
                d.appendleft(query[2])
if flag == -1:
    d.reverse()
print(''.join(list(d)))
### BUGGY CODE ###

    # -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        # if cnt >= N-i:
        #     print(cnt)
        #     return
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                if cnt >= N-j+1:
                    print(cnt)
                    return
                break
        if cnt < tmp:
            cnt=tmp
    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        if cnt >= N-i:
            print(cnt)
            return
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                if cnt >= N-j+1:
                    print(cnt)
                    return
                break
        if cnt < tmp:
            cnt=tmp
    print(cnt)


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

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    mod = 10**9 +7
    N = int(input())
    A = list(map(int,input().split()))
    l = A[0]
    for i in range(1,N):
        l = lcm(l,A[i])

    ans = 0
    for a in A:
        ans += l//a
        ans %= mod
    print(ans)
main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

n = int(input())

a = [int(input()) for _ in range(n)]

for i in range(n):
    tmp = a[i]
    a[i] = 0
    print(max(a))
    a[i] = tmp

### FIXED CODE ###

n = int(input())

a = [int(input()) for _ in range(n)]
b = sorted(a)
m1 = b[-1]
m2 = b[-2]

for i in range(n):
    if a[i] == m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

#!/usr/bin/env python3
n, m = map(int, input().split())
ba = [None] * n
for i in range(n):
    a, b = map(int, input().split())
    ba[i] = [b, a]
ba.sort(reverse=True)
li = [0] * m
for i in range(n):
    b, a = ba[i]
    for j in range(m - a + 1)[::-1]:
        if li[j] == 0:
            li[j] = b
            break
print(sum(li))


### FIXED CODE ###

#!/usr/bin/env python3
from queue import PriorityQueue
n, m = map(int, input().split())
jobs = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[m - a].append(b)
pq = PriorityQueue()
ans = 0
for i in range(m)[::-1]:
    for b in jobs[i]:
        pq.put(-b)
    if not pq.empty():
        ans += -pq.get()
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
import sys
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
 
 
def main():
    # n, q
    n, q = map(int, input().split())
 
    trees = [[] for i in range(n+1)]
    # a, b
    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        trees[a].append(b)
        trees[b].append(a)
 
    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    process(1, -1, trees, values)
    print(*values[1:])
 
 
def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)


def main():
    # n, q
    n, q = map(int, input().split())

    trees = [[] for i in range(n+1)]
    # a, b
    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        trees[a].append(b)
        trees[b].append(a)

    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    process(1, -1, trees, values)
    print(*values[1:])


def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)


if __name__ == "__main__":
    main()