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

import collections
n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    tmp=s[l-1:r]
    print(tmp.count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*(n+10)
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]
for i in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

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

from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    # print('Search Start: ' + str(n))
    # print(graph)
    stack1 = graph[n]
    while stack1:
        x = stack1.popleft()
        dfs(x)
    for i in range(N):
        if n in graph[i]:
            dfs(i)
    checked[n] = True
    # print('Search End: ' + str(n))

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

graph = {i: deque() for i in range(N)}
checked = [False for _ in range(N)]

con_com = 0

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    graph[min(x, y)-1].append(max(x, y)-1)

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    # print('--- Connected Components ---')
    con_com += 1

print(con_com)


### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10 ** 6)

class UnionFind(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
        self.components = n

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
            self.size[x] += self.size[y]
            self.components -= 1

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

    def getSize(self, x):
        return self.size(self.find(x))

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

edge = [] * M
uf = UnionFind(N)

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    uf.union(x-1, y-1)

print(uf.components)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))  
tempA = 1
for i in range(K):
  tempA *= A[i]

for i in range(N - K):
  mulA = tempA / A[i] * A[K+i]
  if tempA < mulA:
    print('Yes')
  else:
    print('No')
  tempA = mulA

  

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))  
for i in range(N - K):
  if A[i] < A[K+i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import heapq
from itertools import accumulate

def dijkstra(ad_lst, n, s, t):
    inf = float('inf')
    costs = [inf for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
result=list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1],min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
### BUGGY CODE ###

n,q = map(int,input().split())
s = str(input())
a=[i for i in range(len(s) - 1) if s[i]+s[i+1] == "AC"]

for i in range(q):
    l1, l2 = map(int, input().split())
    b = [i for i in a if  l1 <= i+1 < l2]
    print(len(b))

### FIXED CODE ###

n,q = map(int, input().split())
s= input()
counter = 0
countlist = [0, 0]

for i in range(1, n):
    if s[i] == "C" and s[i - 1] == "A":
        counter += 1
    countlist += [counter]

for i in range(q):
    l, r = map(int, input().split())
    print(countlist[r] - countlist[l])
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1, i):
        ans += j
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for X in range(1, N+1):
  Y = N // X
  ans += Y * (Y + 1) // 2 * X
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect

def main():
  mod=998244353
  pp=pow(2,mod-2,mod)

  n,s=map(int,input().split())
  l=list(map(int,input().split()))
#l.sort()
  dp=[[0 for j in range(s+1)] for i in range(n+1)]
  dp[0][0]=pow(2,n,mod)

  for i in range(n):
      for j in range(s+1):
          if dp[i][j]>=1:
              if j+l[i]<=s:
                  dp[i+1][j+l[i]]+=dp[i][j]*pp# +pow(2,n-1,mod)
                  dp[i+1][j+l[i]]%=mod
              dp[i+1][j]+=dp[i][j]
  print(dp[-1][-1]%mod)
if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=998244353
pp=pow(2,mod-2,mod)

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

dp=[[0 for j in range(s+1)] for i in range(n+1)]
dp[0][0]=pow(2,n,mod)

for i in range(n):
    for j in range(s+1):
        if dp[i][j]>=1:
            if j+l[i]<=s:
                dp[i+1][j+l[i]]+=dp[i][j]*pp# +pow(2,n-1,mod)
                dp[i+1][j+l[i]]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
print(dp[-1][-1]%mod)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    b=[]
    for i in range(n):
        b.append(a[i])
        b=b[::-1]
    print(*b)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    a=list(input().split())
    akisu=a[0::2]
    agusu=a[1::2][::-1]
    b=agusu+akisu
    if n%2==0:
        print(*b)
    else:
        print(*b[::-1])
resolve()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    colors = [-1] * len(graph)
    visited = [False] * len(graph)
    def dfs(inode, color):
      visited[inode] = True
      colors[inode] = color
      for ichild in graph[inode]:
        if not visited[ichild]:
          if not dfs(ichild, abs(color - 1)):
            return False
        else:
          if colors[ichild] == color:
            return False
      return True
    return dfs(0, 0)
        
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    mod_dict[num_int] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

print(ans)

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    t %= mod
    mod_dict[num_int] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

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


from queue import Queue



def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    q = Queue()
    q_next = Queue()

    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                q.put([i, j])

    count = 0

    while 1:
        while 1:
            if q.empty():
                break

            now_data = q.get()
            i, j = now_data

            kari_i1, kari_i2 = i - 1, i + 1
            kari_j1, kari_j2 = j - 1, j + 1

            if kari_i1 >= 0:
                a, b = kari_i1, j
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_j1 >= 0:
                a, b = i, kari_j1
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

        q = q_next
        q_next = Queue()


        if q.empty():
            break
        else:
            count += 1


    print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    now_list = []
    next_list = []

    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                now_list.append([i, j])

    count = 0

    while 1:
        for now_data in now_list:
            i, j = now_data

            kari_i1, kari_i2 = i - 1, i + 1
            kari_j1, kari_j2 = j - 1, j + 1

            if kari_i1 >= 0:
                a, b = kari_i1, j
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_j1 >= 0:
                a, b = i, kari_j1
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

        now_list = next_list
        next_list = []


        if len(now_list) == 0:
            break
        else:
            count += 1


    print(count)



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

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

ans = 0
for i in range(n-2) :
  si = s[i]
  for j in range(i+1,n-1) :
    sj = s[j]
    if si == sj :
      continue
    for k in range(j+1,n) :
      sk = s[k]
      if si == sk or sj == sk or j-i == k-j :
        continue
      ans += 1
      
print(ans)

### FIXED CODE ###

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

R_i = {}
G_i = {}
B_i = {}

ans = 0
for i in range(n) :
  if s[i] == 'R' :
    R_i[i] = 1
  if s[i] == 'G' :
    G_i[i] = 1
  if s[i] == 'B' :
    B_i[i] = 1

ans = len(R_i)*len(G_i)*len(B_i)

for ri in R_i :
  for gi in G_i :
    # Rが真ん中
    if 2*ri-gi in B_i :
      ans -= 1
    # Gが真ん中
    if 2*gi-ri in B_i :
      ans -= 1
    # Bが真ん中
    if (ri+gi)%2 == 0 :
      if (ri+gi)//2 in B_i :
        ans -= 1
    
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**10
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for a,b in x:
        for i in range(a,H+ma+1):
            if dp[i-a] != INF:
                dp[i] = min(dp[i],dp[i-a]+b)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for i in range(1,H+ma+1):
        dp[i] = min(dp[i-a]+b for a,b in x)
    
    print(min(dp[H:]))

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

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB,key=lambda x:x[0],reverse=True)
AB = sorted(AB,key=lambda x:x[1],reverse=True)
dp = [0 for _ in range(M)]
rest = M
for a,b in AB:
    aa = a-1
    if aa >= rest:
        continue
    if dp[aa] == 0:
        dp[aa] = b
    else:
        flag = False
        for i in range(aa,rest):
            if dp[i] == 0:
                dp[i] = b
                flag = True
                break
        if flag is False:
            rest = aa
print(sum(dp))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB,key=lambda x:x[0])
dp = [0 for _ in range(M)]
p = 0
q = []
for a,b in AB:
    n = a-1
    if n > M-1:
        break
    if n != p:
        while q and p < n:
            dp[p] = heapq.heappop(q)
            p += 1
        p = n
    heapq.heappush(q,b*(-1))
while q and p < M:
    dp[p] = heapq.heappop(q)
    p += 1
print(sum(dp)*(-1))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * P
            if affords <= 0:
                result += 1
                continue
            
            affords -= sum([min(A[n] + M - A[p], M) for p in range(P, n)])
            affords -= (N-n-1) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0

    cumsum = [0 for i in range(N+1)]
    for n in range(N-1):
        cumsum[n+1] = A[n] + cumsum[n]

    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * (P-1)
            if affords <= 0:
                result += 1
                continue
            
            sunmmation = A[n] * (n-P) + M * (n-P) - (cumsum[n] - cumsum[P])
            affords -= sunmmation
            affords -= (N-n) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

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

N = int(input())
X = list(map(int,input().split()))
MOD = 10 ** 9 + 7
goal = X[-1]
ans = goal - X[0]
x = 1
for i in range(1,N-1):
    tmp = goal - X[i]
    ans = (ans * (i+1) + (x*tmp)) % MOD
    x *= i+1
    #print(tmp,ans,x)
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy
N = int(input())

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

for i in range(N):
  c_lst = copy.copy(lst)
  c_lst.pop(i)
  idx = len(c_lst) // 2
  sorted_lst = sorted(c_lst)
  print(sorted_lst[idx])

### FIXED CODE ###

import copy
N = int(input())

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

sorted_lst = sorted(lst)
idx = (N-1) // 2
low = sorted_lst[idx]
high = sorted_lst[idx+1]
for i in range(N):
  if lst[i] <= low:
    print(high)
  else:
    print(low)
### BUGGY CODE ###

import itertools


def main():
    N, M, R = list(map(int, input().split(' ')))

    r = [int(a)-1 for a in input().split()]

    d = [[float('inf')]*N for _ in range(N)]

    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for a in range(N):
        d[a][a] = 0

    res = float('inf')

    for a, b, c in itertools.product(range(N), repeat=3):
        d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys

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

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


if __name__ == '__main__':
    main()