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

from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
import math
import string
import fractions
import re
import array
import copy
import functools

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop

# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


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

    # eprint("=======================")
    while True:
        xx = min([x for x in l if x > 0])
        l = [(tt if tt==xx else tt%xx) for tt in l]

        # eprint(l)
        if all(x==l[0] for x in l):
            print(l[0])
            return 0
        if 1 in l:
            print(1)
            return 0
        if sum(l)==xx:
            print(xx)
            return 0
        # eprint("=======================")

    print(xx)
    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
import math
import string
import fractions
import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop

# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


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

    eprint("=======================")
    while True:
        xx = min([x for x in l if x > 0])
        # eprint("min_index: "+str(min_index))
        eprint("xx: "+str(xx))
        flag = 0
        for i in range(len(l)):
            if l[i] == xx and flag == 0:
                flag=1
            else:
                l[i] = l[i]%xx

        # eprint(l)
        if all(x==l[0] for x in l):
            # eprint(l)
            print(l[0])
            return 0
        if 1 in l:
            print(1)
            return 0
        if sum(l)==xx:
            print(xx)
            return 0
        eprint("=======================")

    print(xx)
    return 0


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

K, S = map(int, input().split())
cnt = 0
for x in range(S + 1) :
    for y in range(S - x + 1) :
        z = S - x - y
        if x <= K and y <= K and z <= K :
            cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(S + 1) :
    if x > K :
        continue
    for y in range(S - x + 1) :
        if y > K :
            continue
        z = S - x - y
        if z > K:
            continue
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
s = input() #sys.stdin.readlineは最後が改行
s = s[:-1]
n =len(s)

num=0
tmp=0

amari= [0]

for i in range(n):
    num = tmp + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari.append(tmp)

from collections import Counter
ctr = Counter(amari)
ans = 0
for val in ctr.values():
        ans += val*(val-1)//2
print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

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

n, k = map(int, input().split())
s = str(input())

u = s + s[::-1]
ss = s

times = min(n, k)
for i in range(times):
    for j in range(n):
        part = u[j:j+n]
        if u[j:j+n] < ss:
            ss = part
    s = ss
    u = s[::-1] + s

print(s)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
s = str(input())

u = s + s[::-1]
ss = s

if n < k**2:
    smallest = sorted(s)[0]
    print(smallest * n)

else:
    times = min(n, k)
    for i in range(times):
        for j in range(n):
            part = u[j:j+n]
            if part < ss:
                ss = part
        s = ss
        u = s[::-1] + s
    print(s)
### BUGGY CODE ###

import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
memo_array = [-1]*(m+1)

for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(np.sum(l[:idx]) + np.sum(l[idx:])*(loop_num)+np.sum(l[idx:idx+mod]))
        sys.exit()
    l = np.append(l,ans)
    memo_array[ans]=i
print(np.sum(l))

### FIXED CODE ###

import sys

n,x,m = (int(i) for i in input().split())
l = [x]
ans = x
memo_array = [-1]*(m+1)

for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(sum(l[:idx]) + sum(l[idx:])*(loop_num)+sum(l[idx:idx+mod]))
        sys.exit()
    l.append(ans)
    memo_array[ans]=i
print(sum(l))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():

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

    if n < b:
        print((a*n)//b)
        exit()

    num = n//b
    ans = 0

    for i in range(1,num+1):
        num2 = i*b-1
        #print(num2)
        temp = (a*num2)//b - a * (num2//b)
        ans = max(temp,ans)

    print(max(ans,(a*n)//b - a * (n//b)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():

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

    if n < b:
        print((a*n)//b)
        exit()

    num = n//b

    ans = (a*(b-1))//b
    print(max(ans,(a*n)//b - a * (n//b)))

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

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

B=[]

if(N%2==0):
    for i in range(N):
        if(i%2==1):
            B.insert(0,A[i])
        else:
            B.append(A[i])
else:
    for i in range(N):
        if(i%2==0):
            B.insert(0,A[i])
        else:
            B.append(A[i])
for i in B:
    print(i,end=" ")

### FIXED CODE ###

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

B=[]

if(N%2==0):
    for i in range(N-1,-1,-2):
        print(A[i],end=" ")
    for i in range(0,N,2):
        print(A[i],end=" ")
        
else:
    for i in range(N-1,-1,-2):
        print(A[i],end=" ")
    for i in range(1,N,2):
        print(A[i],end=" ")
### BUGGY CODE ###


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

edge = [[] for _ in range(n)]

counter = [0] * n

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

for _ in range(q):
    a, b = map(int, input().split())
    counter[a-1] += b

parent = [0]
s_next = {0}

for i in parent:
    for v in edge[i]:
        # if v in parent:
        #     continue
        if v in s_next:
            continue
        s_next.add(v)
        parent.append(v)
        counter[v] += counter[i]
        
for i in range(n):
    print(counter[i], end=" ")
print("")

### FIXED CODE ###


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

# edge = [[] for _ in range(n)]

# counter = [0] * n

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

# for _ in range(q):
#     a, b = map(int, input().split())
#     counter[a-1] += b

# parent = [0]
# visited = []

# for i in parent:
#     visited.append(i)
#     for v in edge[i]:
#         if v in visited:
#             continue
#         parent.append(v)
#         counter[v] += counter[i]
        
# for i in range(n):
#     print(counter[i], end=" ")
# print("")

import sys
input = sys.stdin.readline
 
N, Q = [int(x) for x in input().split()]
 
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
 
cost = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    cost[p - 1] += x
 
next = [0]
s_next = {0}
for i in next:
    for v in edge[i]:
        if v in s_next:
            continue
        s_next.add(v)
        next.append(v)
        cost[v] += cost[i]
 
print(" ".join(map(str, cost)))
### 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)]
modl = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        modl[((i+1)+(j+1))%3].append(c[i][j])
ans = float('inf')
for i in range(C):
    total = 0
    tmp1 = 0
    for e in modl[0]:
        tmp1 += D[e-1][i]
    total += tmp1
    for j in range(C):
        if i!=j:
            tmp2 = 0
            for e in modl[1]:
                tmp2 += D[e-1][j]
            total += tmp2
            for k in range(C):
                tmp3 = 0
                if i!=k and j!=k:
                    for e in modl[2]:
                        tmp3 += D[e-1][k]
                    total += tmp3
                    ans = min(ans,total)
                    total -= tmp3
            total -= tmp2
print(ans)


### FIXED 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)]
modl = [[0 for i in range(C)] for i in range(3)]
for i in range(N):
    for j in range(N):
        modl[((i+1)+(j+1))%3][c[i][j]-1] += 1
ans = float('inf')
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or i==k or j==k:
                continue
            total = 0
            for l in range(C):
                total += D[l][i]*modl[0][l]+D[l][j]*modl[1][l]+D[l][k]*modl[2][l]
            ans = min(ans,total)
print(ans)
### BUGGY CODE ###

from statistics import median

N = int(input())
X = list(map(int, input().split()))

for i in range(N):
  tmp_X = [X[j] for j in range(N) if j != i]
  #print(tmp_X)
  print(median(tmp_X))

### FIXED CODE ###

from statistics import median

N = int(input())
X = list(map(int, input().split()))

X_sorted = sorted(X)
X_med = median(X)
for i in range(N):
  if X[i] < X_med:
    res = X_sorted[N // 2]
  elif X_med < X[i]:
    res = X_sorted[N // 2 - 1]
  else:
    res = X[i]

  print(res)
### BUGGY CODE ###


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

data = {}
ps = []
ACs = []

num_ac = 0
num_wa = 0

for i in range(M):
    p, S = input().split()
    p = int(p)

    if not (p in ps):
        ps.append(p)
        data[p] = {'AC':0, 'WA':0}

    if S == 'AC' and data[p]['AC'] == 0:
        ACs.append(p)
        data[p]['AC'] += 1
        num_ac += 1
        num_wa += data[p]['WA']

    if S == 'WA' and data[p]['AC'] == 0:
        data[p][S] += 1

print(num_ac, num_wa)


### FIXED CODE ###


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

data = {}
ps = [0] * N
ACs = []

num_ac = 0
num_wa = 0


for i in range(M):
    p, S = input().split()
    p = int(p) - 1

    if ps[p] == 0:
        ps[p] = 1
        data[p] = {'AC':0, 'WA':0}

    if S == 'AC' and data[p]['AC'] == 0:
        ACs.append(p)
        data[p]['AC'] += 1
        num_ac += 1
        num_wa += data[p]['WA']

    if S == 'WA' and data[p]['AC'] == 0:
        data[p][S] += 1

print(num_ac, num_wa)
### BUGGY CODE ###

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

max_n=max(sum(lr,[]))
primelist=primes(max_n)
for query in lr:
  print(sum([(item in primelist) and ((item+1)/2 in primelist) for item in range(query[0],query[1]+1,2)]))

### FIXED CODE ###

import numpy as np

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

primelist=[0,]*(100000+1)
for n in primes(100000):
  primelist[n]=1

list2017=[primelist[n] and primelist[(n+1)//2] for n in range(1,100000,2)]
cumsum=np.cumsum(list2017)
for query in lr:
  print(cumsum[(query[1]-1)/2]-cumsum[max(0,(query[0]-1)/2-1)])
### BUGGY CODE ###

R, C, K = map(int, input().split())
T = [[0]*(C+1) for _ in range(R+1)]
dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
for i in range(K):
    r, c, v = map(int, input().split())
    T[r][c] = v
dp[1][1][1] = T[1][1]
dp[0][1][1] = 0

for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            for l in range(4):
                dp[0][i][j] = max(dp[0][i][j], dp[l][i-1][j])
                dp[1][i][j] = max(dp[1][i][j], dp[l][i-1][j] + T[i][j])
            dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
            if k >= 1:
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1] + T[i][j])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][R][C])
print(ans)

### FIXED CODE ###

R, C, K = map(int, input().split())
T = [[0]*(C+2) for _ in range(R+2)]
dp = [[[0]*(C+2) for _ in range(R+2)] for _ in range(4)]
for i in range(K):
    r, c, v = map(int, input().split())
    T[r][c] = v
dp[1][1][1] = T[1][1]
dp[0][1][1] = 0

for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
            dp[1][i+1][j] = max(dp[1][i+1][j], dp[k][i][j] + T[i+1][j])
            dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
            if k <= 2:
                dp[k+1][i][j+1] = max(dp[k+1][i][j+1], dp[k][i][j] + T[i][j+1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][R][C])
print(ans)
### BUGGY CODE ###

import numpy as np

Height, Width = map(int,input().split(" "))

lineBlocks = [(input()) for i in range(Height)]

twoDimMap = []
for Block in lineBlocks:
  twoDimMap.append(list(Block))
  
ansList = []
heightList = np.zeros((Height, Width), dtype=int)
widthList  = np.zeros((Height, Width), dtype=int)

for i in range(Height):
  for j in range(Width):
    
    if '#' == twoDimMap[i][j]:
      heightList[i][j] = 0
      widthList[i][j]  = 0
      continue

    else:
        if heightList[i][j] == 0:

            k_up = i+1
            height_len = 0
            while( k_up < Height and twoDimMap[k_up][j] != "#"):
                height_len += 1
                k_up += 1
                
            
            k_down = i-1
            while( k_down >= 0 and twoDimMap[k_down][j] != "#"):
                height_len += 1
                k_down -= 1
            
            for k in range(k_down+1,k_up):
                heightList[k][j] = height_len + 1


        if widthList[i][j] == 0:
            k_right = j+1
            width_len = 0
            while(k_right < Width and twoDimMap[i][k_right] != "#"):
                width_len += 1
                k_right += 1

            k_left = j-1
            while(k_left >= 0 and twoDimMap[i][k_left] != "#"):
                width_len += 1
                k_left -= 1
            
            for k in range(k_left+1,k_right):
                widthList[i][k] = width_len

print(np.array(heightList + widthList).max())

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
table = np.array([list(input())for _ in range(h)]) == '.'
 
d = np.zeros((h, w), dtype = int)
u = np.zeros((h, w), dtype = int)
r = np.zeros((h, w), dtype = int)
l = np.zeros((h, w), dtype = int)

for i in range(h):
    d[i] = (d[i-1]+1) * table[i]
    u[-i-1] = (u[-i]+1) * table[-i-1]

for i in range(w):
    r[:, i] = (r[:, i-1]+1) * table[:, i]
    l[:, -i-1] = (l[:, -i]+1) * table[:, -i-1]
print(np.max(d+u+r+l)-3)
### BUGGY CODE ###

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


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [{} for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i].get(i_w - item[0], 0) + item[1], dp[i].get(i_w, 0))
            else:
                dp[i + 1][i_w] = dp[i].get(i_w, 0)

    print(dp[n][w])


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i][i_w - item[0]] + item[1], dp[i][i_w])
            else:
                dp[i + 1][i_w] = dp[i][i_w]

    print(dp[n][w])


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

#D
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0

for i in range(0, N-K+1):
    sum_P = sum(P[i:i+K])
    ans = max(ans, sum_P)
#     ans = max(ans, K+0.5*(sum_P-K))
    
print(K+0.5*(ans-K))

### FIXED CODE ###

#D
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = sum(P[0:K])
sum_P = ans

for i in range(1, N-K+1):
    sum_P = sum_P - P[i-1] + P[i+K-1]
    ans = max(ans, sum_P)
#     ans = max(ans, K+0.5*(sum_P-K))
    
print(K+0.5*(ans-K))
### BUGGY CODE ###

N,M=map(int,input().split())
li=[]
ans=[]
H=list(map(int,input().split()))

for i in range(M):
    A,B=map(int,input().split())
    C=H[A-1]
    D=H[B-1]
    if C>D:
        li.append(B)
    elif D>C:
        li.append(A)
    else:
        li.append(A)
        li.append(B)

for j in range(N):
    if j+1 in li:
        pass
    else:
        ans.append(j+1)

print(len(ans))


### FIXED CODE ###

N,M=map(int,input().split())
h=list(map(int,input().split()))
li=[1]*N
for i in range(M):
    a,b=list(map(int,input().split()))
    if h[a-1]>h[b-1]:
        li[b-1]*=0
    elif h[a-1]==h[b-1]:
        li[a-1]*=0
        li[b-1]*=0
    else:
        li[a-1]*=0

ans=li.count(1)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

r = [0] * (n)
g = [0] * (n)
b = [0] * (n)
if s[0] == 'R':
  r[0] = 1
elif s[0] == 'G':
  g[0] = 1
else:
  b[0] = 1

for i in range(n-1):
  r[i+1] = r[i]
  g[i+1] = g[i]
  b[i+1] = b[i]
  
  if s[i+1] == 'R':
    r[i+1] += 1
  elif s[i+1] == 'G':
    g[i+1] += 1
  else:
    b[i+1] += 1
    
ans = 0
for i in range(n):
  if s[i] == 'R':
    for j in range(i+1,n):
      if j+1 >= n:
        continue
        
      if s[j] == 'G':
        ans += b[-1] - b[j]
        if j+j-i < n and s[j+j-i] == 'B':
          ans -= 1
          
      if s[j] == 'B':
        ans += g[-1] - g[j]
        if j+j-i < n and s[j+j-i] == 'G':
          ans -= 1        
        
  if s[i] == 'G':
    for j in range(i+1,n):
      if j+1 >= n:
        continue
        
      if s[j] == 'R':
        ans += b[-1] - b[j]
        if j+j-i < n and s[j+j-i] == 'B':
          ans -= 1        
        
      if s[j] == 'B':
        ans += r[-1] - r[j]
        if j+j-i < n and s[j+j-i] == 'R':
          ans -= 1        
        
  if s[i] == 'B':
    for j in range(i+1,n):
      if j+1 >= n:
        continue
        
      if s[j] == 'G':
        ans += r[-1] - r[j]
        if j+j-i < n and s[j+j-i] == 'R':
          ans -= 1        
        
      if s[j] == 'R':
        ans += g[-1] - g[j]
        if j+j-i < n and s[j+j-i] == 'G':
          ans -= 1        

        
print(ans)
        

### FIXED CODE ###

n = int(input())
s = input()

r = len(s.replace('G','').replace('B',''))
g = len(s.replace('R','').replace('B',''))
b = len(s.replace('G','').replace('R',''))

ans = r*g*b

for i in range(n):
  for j in range(n):
    if i+j+j+2 >= n:
      break
    
    if (not s[i] == s[i+j+1]) and (not s[i+j+1] == s[i+j+j+2]) and (not s[i+j+j+2] == s[i]):
      ans -= 1
      
print(ans)
### BUGGY CODE ###

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            for xvv, yvv in [[xv + 1, yv], [xv, yv + 1]]:
                if 0 <= xvv < h and 0 <= yvv < w:
                    if (xvv, yvv) not in fq and a[xvv][yvv] != "#":
                        ql.append([cost + 1, xvv, yvv])
                        fq[xvv, yvv] = fq[xv, yv]
                    else:
                        fq[xvv, yvv] += fq[xv, yv]
        else:
            break
    print(fq[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[-1][-1])


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

import math
a = int(input())
ans = 0

for i in range(1, a+1):
    for j in range(1, a+1):
        for k in range(1, a+1):
            ans += math.gcd(math.gcd(i, j), k)
print(ans)

### FIXED CODE ###

import math
a = int(input())
ans = 0

for i in range(1, a+1):
    for j in range(1, a+1):
        num = math.gcd(i, j)
        for k in range(1, a+1):
            ans += math.gcd(num, k)
print(ans)
### BUGGY CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    W[A][B] = C
    W[B][A] = C

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    heapq.heappush(heap, (0, i))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

### FIXED CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    W[A][B] = C
    W[B][A] = C

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    for j in range(1, i+1):
        heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i+1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                W[k][i] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)