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

import sys
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = [0 for _ in range(H)]
    A = [[[-1, -1] for _ in range(W)] for _ in range(H)]
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i] |= 1 << j
    ans = 1
    tate = 0
    yoko = 0
    for i in range(H):
        yoko = 0
        for j in range(W):
            if (S[i] >> j) & 1:
                yoko = 0
                continue
            if yoko == 0:
                for k in range(j+1, W):
                    if (S[i] >> k) & 1:
                        break
                    yoko += 1
                for k in range(j+1, W):
                    if (S[i] >> k) & 1:
                        break
                    A[i][k][0] = yoko
                A[i][j][0] = yoko
            tate = 0
            if A[i][j][1] == -1:
                for k in range(i+1, H):
                    if (S[k] >> j) & 1:
                        break
                    tate += 1
                for k in range(i+1, H):
                    if (S[k] >> j) & 1:
                        break
                    A[k][j][1] = tate
                A[i][j][1] = tate
            ans = max(ans, sum(A[i][j]) + 1)
    print(ans)


main()

### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = np.ones((H, W), dtype=int)
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i][j] = 0

    L = S.copy()
    R = S.copy()
    U = S.copy()
    D = S.copy()
    for j in range(1, W):
        L[:, j] = (L[:, j-1] + 1)*S[:, j]
        R[:, W-j-1] = (R[:, W-j] + 1) * S[:, W-j-1]

    for i in range(1, H):
        U[i][:] = (U[i-1][:] + 1)*S[i][:]
        D[H-i-1][:] = (D[H-i][:] + 1)*S[H-i-1][:]

    ans = (L+R+U+D).max() - 3
    print(ans)


main()
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
DI={}
for i in A:
  if i not in DI:
    DI[i]=1
  else:
    DI[i]+=1  
d=0
B=sorted(list(set(A)))
n=len(B)
for i in range(n):
  if DI[B[i]]==1:
    d+=1
    for j in range(0,i):
      if B[i]<B[j]*2:
        break
      if B[i]%B[j]==0:
        d-=1
        break
print(d)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
D=[1]*(A[-1]+1)
for i in A:
  if D[i]==1:
    for j in range(A[-1]//i):
      D[i*(j+1)]=0
    D[i]=1
dic={}
for i in A:
  if i not in dic:
    dic[i]=1
  else:
    dic[i]+=1

for i in dic:
  if dic[i]>1:
    D[i]=0
    
ans=0
for i in A:
  if D[i]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
s = []
for x in map(int,input().split()):
    s += [x]
    s = s[::-1]
print(*s,sep=" ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 0:
    a = a[::-2]+a[0::2]
else: a = a[::-2] +a[1::2]
print(*a,sep=" ")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
t = [a.count(i) for i in range(n)]
for i in range(n//2):
  if t[i*2+n%2] != 0 or t[i*2+1+n%2] != 2 or t[0] > 1:
    print(0)
    exit()
print(2**(n//2))

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
d = dict()
mod = 10**9 + 7
for i in l:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1
d2 = dict()
for i in range(1+n%2,n,2):
  d2[i] = 2
if n%2:
  d2[0] = 1
if d == d2:
  print(2**(n//2)%mod)
else:
  print(0)
### BUGGY CODE ###

N = int(input())

node = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    node[a-1].append(b-1)
    node[b-1].append(a-1)

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))
stack = [0]

# ノードの選択
while stack:
    p = stack.pop()
    # 子ノードの選択
    for c in node[p]:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]
            stack.append(c)
true_num = sum(map(int, group))
false_num = N - true_num
p = [0] * N
mod_0 = [int(i) for i in range(1,N+1) if i%3 == 0]
mod_1 = [int(i) for i in range(1,N+1) if i%3 == 1]
mod_2 = [int(i) for i in range(1,N+1) if i%3 == 2]

if true_num >= N/3 and false_num >= N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            if mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
elif false_num < N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)
elif true_num < N/3:
    for i in range(N):
        if not group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)

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

### FIXED CODE ###

N = int(input())

node = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    node[a-1].append(b-1)
    node[b-1].append(a-1)

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))
stack = [0]

# ノードの選択
while stack:
    p = stack.pop()
    # 子ノードの選択
    for c in node[p]:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]
            stack.append(c)

p = [0] * N
three = 3
if group.count(True) <= N // 3:
    other = 1
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if not group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3
elif group.count(False) <= N // 3:
    other = 1
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3

else:
    one, two = 1, 2
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if not group[i] and one <= N:
            p[i] = one
            one += 3
        elif group[i] and two <= N:
            p[i] = two
            two += 3
        else:
            p[i] = three
            three += 3
print(" ".join(map(str, p)))
### BUGGY CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]]
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] +dp[i-L[k][0]]
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n


### FIXED CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]] %mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] %mod +dp[i-L[k][0]] %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n
### BUGGY CODE ###

import collections
N=int(input())
S = [str(input()) for _ in range(N)]
c = collections.Counter(S)
most = []
for i in c.most_common():
    if i[1]==c.most_common()[0][1]:
        most.append(i[0])
most.sort()
for i in most:
    print(i)

### FIXED CODE ###

import collections
N=int(input())
S = [str(input()) for _ in range(N)]
c = collections.Counter(S)
most = []
most_num=c.most_common()[0][1]
for i in c.most_common():
    if i[1]==most_num:
        most.append(i[0])
most.sort()
for i in most:
    print(i)
### BUGGY CODE ###

S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()
t[0]=1
for i in range(n):
  if S[i]=='?':
    tcopy=s.copy()
    for j in range(10):
      for k in range(13):
        tcopy[(10*k+j)%13]=(tcopy[(10*k+j)%13]+t[k])%(10**9+7)
    t=tcopy.copy()
  else:
    j=int(S[i])
    tcopy=s.copy()
    for k in range(13):
      tcopy[(10*k+j)%13]=(tcopy[(10*k+j)%13]+t[k])%(10**9+7)
    t=tcopy.copy()
print(t[5])

### FIXED CODE ###

S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    tcopy=[0]*13
    for j in range(10):
      for k in range(13):
        tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    for j in range(13):
      t[j]=tcopy[j]
  else:
    j=int(S[i])
    tcopy=[0]*13
    for k in range(13):
      tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    for j in range(13):
      t[j]=tcopy[j]
print(t[5])
### BUGGY CODE ###

import heapq

N, M = [int(i) for i in input().split()]
H = [-int(i) for i in input().split()]

G = [[0] * N for i in range(N)]
#print(G)

for i in range(M):
  a, b = [int(j) for j in input().split()]
  #print(a, b)
  G[a-1][b-1] = H[b-1]
  G[b-1][a-1] = H[a-1]

#for g in G:
#  print(g)
NG = []  
for ixa, g in enumerate(G):
  #print(g)
  ha = -H[ixa]
  heapq.heapify(g)
  hb = -heapq.heappop(g)
  #print(ha, hb)
  if ha <= hb:
    if ixa not in NG:
      NG.append(ixa)
      
#print(NG)
print(N - len(NG))

### FIXED CODE ###

import heapq

N, M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

NG = []

for i in range(M):
  a, b = [int(j) for j in input().split()]
  if H[a-1] < H[b-1]:
    NG.append(a)
  elif H[a-1] > H[b-1]:
    NG.append(b)
  else:
    NG.append(a)
    NG.append(b)
NG = set(NG)
#print(NG)
print(N - len(NG))
### BUGGY CODE ###

n, q = map(int, raw_input().split())
s = raw_input()
g1 = [1] * n
for _ in range(q):
    t, d = raw_input().split()
    g2 = [0] * n
    for i in range(n):
        if s[i] != t:
            g2[i] += g1[i]
        elif d == 'L' and i > 0:
            g2[i - 1] += g1[i]
        elif d == 'R' and i < n - 1:
            g2[i + 1] += g1[i]
    g1 = g2
print sum(g1)

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = raw_input()
td = [raw_input().split() for _ in range(q)];
left, right = 0, n
for t, d in reversed(td):
    if d == 'L':
        if left < n and s[left] == t:
            left += 1
        if right < n and s[right] == t:
            right += 1
    elif d == 'R':
        if left > 0 and s[left - 1] == t:
            left -= 1
        if right > 0 and s[right - 1] == t:
            right -= 1
print max(0, right - left)
### BUGGY CODE ###

N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i) for i in input().split()] for _ in range(N)]

top3 = [[[0,1000*500*500] for _ in range(5)] for _ in range(3)]

for i in range(C):
        dif = [0]*3
        for j in range(N):
                for k in range(N):
                        dif[(j+k)%3] += D[c[j][k]-1][i]

        for l in range(3):
                for m in range(3):
                        if top3[l][m][1] > dif[l]:
                                top3[l][m+2][0] = top3[l][m+1][0]
                                top3[l][m+2][1] = top3[l][m+1][1]
                                top3[l][m+1][0] = top3[l][m][0]
                                top3[l][m+1][1] = top3[l][m][1]
                                top3[l][m][0] = i
                                top3[l][m][1] = dif[l]
                                break


ans = 1000*500*500
for i in range(3):
        for j in range(3):
                for k in range(3):
                        if top3[0][i][0] != top3[1][j][0] and top3[0][i][0] != top3[2][k][0] and top3[1][j][0] != top3[2][k][0]:
                                if ans > top3[0][i][1] + top3[1][j][1] + top3[2][k][1]:
                                        ans = top3[0][i][1] + top3[1][j][1] + top3[2][k][1]

print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for j in range(C)]
c = [[int(i) for i in input().split()] for j in range(N)]

c_sum = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_sum[(i+j)%3][c[i][j]-1] += 1

D_sum = [[0]*C for _ in range(3)]
for i in range(C):
    for j in range(C):
        for k in range(3):
            D_sum[k][j] += D[i][j] * c_sum[k][i]

ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
d = dd(list)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz].append(i)
  a.append(zz)
#print(d)
res = 0
for i in range(N):
  x = a[i]
  for k in d.keys():
    z = x * k
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    if c < 18: continue
    res += bl(d[k], i)
    #print(x, k, bl(d[k], i))
print(res)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for x in ks:
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc * d[x]
print(res // 2)
### BUGGY CODE ###

N = int(input())
n = round(N**0.5)
counter = 0
for g in range(1,N+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      for k in range(1,n+1):
        if i**2+j**2+k**2+i*j+j*k+k*i == g:
          counter += 1
  print(counter)
  counter = 0

### FIXED CODE ###

N = int(input())
n = round(N**0.5)
counter = [0]*N
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      f = i**2+j**2+k**2+i*j+j*k+k*i
      if f <= N:
        counter[f-1] += 1
for i in range(N):
  print(counter[i])
### BUGGY CODE ###

import numpy as np
n,q=map(int,input().split())
d={i:[] for i in range(n)}
for i in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
bubunki={i:[] for i in range(n)}
for i in range(n):
    idx = n-1-i
    bubunki[idx].append(idx)
    if idx in d.keys():
        for children in d[idx]:
            bubunki[idx] += bubunki[children]
counter = np.zeros(n)
for i in range(q):
    p,x=map(int,input().split())
    s=bubunki[p-1]
    counter[s]+=x
print(' '.join(map(str, map(int,(counter)))))

### FIXED CODE ###

n,q=map(int,input().split())
d={i:[] for i in range(n)}
for i in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
counter = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
for i in range(n-1):
    for child in d[i]:
        counter[child]+=counter[i]
print(' '.join(map(str, map(int,(counter)))))
### BUGGY CODE ###

MOD = 10**9+7
def fact(n, factors):
    rtn = factors
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if i in rtn:
                rtn[i] = max(rtn[i],cnt)
            else:
                rtn[i] = cnt

    if temp!=1:
        if temp in rtn:
            rtn[temp] = max(rtn[temp],1)
        else:
            rtn[temp] = 1

    return rtn

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    LCM = 1
    factors = {}
    for a in A:
        factors = fact(a,factors)
    for k,v in factors.items():
        LCM *= pow(k,v,MOD)
    for a in A:
        ans += (LCM//a)%MOD
        ans %= MOD
    print(ans)

main()


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=pow(10,9)+7
    lcma={}
    for ai in a:
      f=factorization(ai)
      for fi in f:
        if fi[0] in lcma:
          lcma[fi[0]]=max(lcma[fi[0]],fi[1])
        else:
          lcma[fi[0]]=fi[1]
    l=1
    for k,v in lcma.items():
      l*=pow(k,v,mod)
      l%=mod
    ans=0
    for ai in a:
      ans+=l*pow(ai,mod-2,mod)
      ans%=mod
    print(ans)

main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
    buy = max(a)
    a.remove(buy)
    a.append(int(buy/2))
print(sum(a))


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))

heapq.heapify(a)
for _ in range(m):
    val = heapq.heappop(a) * (-1)
    heapq.heappush(a, (val // 2) * (-1))
print(-sum(a))
### BUGGY CODE ###

# from collections import Counter
n, p = map(int, input().split())
s = input()
s += '0'
p_cnt = 0

div_dic = dict(zip(range(p), [0] * p))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        div_dic[int(s[i:]) % p] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
print(int(p_cnt))

### FIXED CODE ###

n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
        
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ring = [A[0], A[1]]
ans = A[0]
for i in range(2, N):
    max_tmp = 0
    num_tmp = 0
    for j in range(len(ring) - 1):
        if max_tmp < min(ring[j], ring[j + 1]):
            max_tmp = min(ring[j], ring[j + 1])
            num_tmp = j + 1
    if max_tmp < min(ring[0], ring[-1]):
        max_tmp = min(ring[0], ring[-1])
        num_tmp = -1
    if num_tmp == -1:
        ring.append(A[i])
    else:
        ring.insert(num_tmp, A[i])
    ans += max_tmp
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
s = (N - 2) // 2
if s > 0:
    ans += sum(A[1:1 + s]) * 2
if (N - 2) % 2:
    ans += A[1 + s]
print(ans)
### BUGGY CODE ###

from itertools import permutations

##def permutation(lst):
##    if len(lst) < 2:
##        return[lst]
##    l = []
##    for i in range(len(lst)):
##        m = lst[i]
##        remLst = lst[:i] + lst[i+1:]
##        for p in permutation(remLst):
##            l.append([m] + p)
##    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1 for x in range(N+1)] for x in range(N+1)]

for i in range(M):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

### FIXED CODE ###

from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

if n == 1:
  print(1)
  exit()

import fractions
#from functools import reduce
def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

ans = 0
cl = 1
for i in range(n):
  x = l[i]
  y = lcm_base(cl, l[i])
  ans *= y//cl
  ans += y//x
  ans %= (10**9+7)
  cl = y
print(ans)

### FIXED CODE ###

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

def gcd(a, b):
  while b != 0:
    a, b = b, a%b
  return a

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

t = 1
for i in range(n):
  t = lcm(t, l[i])

ans = 0
for i in range(n):
  ans += t//l[i]
ans %= 10**9+7

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

import re

def calc(people):
    ans = 10 ** 6

    for i, p in enumerate(people):
        Ws = people[0:i].count("W")
        Es = people[i+1:].count("E")

        ans = min(ans, Ws + Es)
    
    return ans


if __name__ == "__main__":
    _ = input()
    people = input()

    print(calc(people))


### FIXED CODE ###

import re

def calc(people):
    Ws = 0
    Es = people[1:].count("E")
    ans = Ws + Es

    for i in range(1, len(people)):
        if people[i] == "E":
            Es -= 1
        
        if people[i - 1] == "W":
            Ws += 1

        ans = min(ans, Ws + Es)
    
    return ans


if __name__ == "__main__":
    _ = input()
    people = input()

    print(calc(people))