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

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置] = この局面からの結果
memo = [[None] * (N+1) for i in range(N+1)]

def dfs(l, r):
    # 全部取り切ったので終了
    if l > r:
        return 0
    # 既に見た局面ならメモの内容を返す
    if memo[l][r] is not None:
        return memo[l][r]
    turn = 0 if N % 2 != (r-l) % 2 else 1
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(l+1, r) + aN[l])
        mx = max(mx, dfs(l, r-1) + aN[r])
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(l+1, r) - aN[l])
        mn = min(mn, dfs(l, r-1) - aN[r])
        memo[l][r] = mn
        return mn

print(dfs(0, N-1))


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# dp[i][j] := 左からi個、右からj個取った状態での最大(最小)得点
dp = list2d(N+1, N+1, 0)
# 初期化：どちらの手番で使う場所かに合わせて-INFかINFにする
for i in range(N):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        if turn == 0:
            dp[j][k] = -INF
        else:
            dp[j][k] = INF
# 最初の遷移の開始地点(ゲーム終了の状態)は0に
for i in range(N+1):
    dp[i][N-i] = 0
# 終了から順番に戻って見ていく
for i in range(N-1, -1, -1):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        l = j
        r = N - 1 - k
        if turn == 0:
            # 先手番の遷移
            dp[j][k] = max(dp[j][k], dp[j+1][k] + A[l])
            dp[j][k] = max(dp[j][k], dp[j][k+1] + A[r])
        else:
            # 後手番の遷移
            dp[j][k] = min(dp[j][k], dp[j+1][k] - A[l])
            dp[j][k] = min(dp[j][k], dp[j][k+1] - A[r])
ans = dp[0][0]
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n, q = map(int, readline().split())
G = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
count = [0] * n
for _ in range(q):
    p, x = map(int, readline().split())
    count[p-1] += x


def dfs(root, x):
    ans[root] = count[root] + x
    for i in G[root]:
        if ans[i] == -1:
            dfs(i, ans[root])


ans = [-1] * n
dfs(0, 0)
print(*ans)


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n, q = map(int, readline().split())
G = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
count = [0] * n
for _ in range(q):
    p, x = map(int, readline().split())
    count[p-1] += x


def dfs(root, x):
    ans[root] = count[root] + x
    for i in G[root]:
        if ans[i] == -1:
            dfs(i, ans[root])


ans = [-1] * n
dfs(0, 0)
print(*ans)
### BUGGY CODE ###

# 190928 D
from fractions import gcd

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

A,B = list(map(int,input().split()))
koyaku = gcd(A,B)
isprim, solist = sieve(koyaku)
kotable = divisor(koyaku)
output = []
for i in range(len(kotable)):
    if kotable[i] in solist:
        output.append(kotable[i])

print(len(output)+1)


### FIXED CODE ###

# 190928 D

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B = list(map(int,input().split()))
soA = prime_factorize(A)
soB = prime_factorize(B)
output = []
for i in range(len(soA)):
    if soA[i] in soB:
        output.append(soA[i])

print(len(list(set(output))) + 1)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = n - r*i -g*j
    if k >= 0 and k%b == 0:
      #print(i, j, k)
      ans += 1
      
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = n - r*i -g*j
    if k >= 0 and k%b == 0:
      #print(i, j, k)
      ans += 1
      
print(ans)
### BUGGY CODE ###

import math
A, B, N = list(map(int, input().split()))
ans = 0
if B+1 < N:
    C = B+1
else:
    C = N
for i in range(1, C+1):
    val = math.floor(A*i/B) - A*math.floor(i/B)
    
    ans = max(ans, val)

print(ans)


### FIXED CODE ###

import math
A, B, N = list(map(int, input().split()))
ans = 0
if B+1 < N:
    C = B+1
else:
    C = N
if B//A == 0:
    D = 1
elif B//A > 1:
  	D = B//A-1
else:
    D = B//A
for i in range(1, C+1, D):
    val = math.floor(A*i/B) - A*math.floor(i/B)
    #print("i", i, "val", val)
    ans = max(ans, val)

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

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

grid = [[(i+j)% 3 for i in range(n)] for j in range(n)]

# 全ての色について違和感を記録
dst = [[0, 0, 0] for _ in range(c)]
for ci in range(c):
    for i in range(n):
        for j in range(n):
            c_from = C[i][j]
            dst[ci][grid[i][j]] += D[c_from][ci]

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d = min(d, dst[p0][0] + dst[p1][1] + dst[p2][2])
print(d)


### FIXED CODE ###

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

# 全ての色について違和感を記録
dst = [[0, 0, 0] for _ in range(c)]
for ci in range(c):
    for i in range(n):
        for j in range(n):
            c_from = C[i][j]
            dst[ci][(i+j)%3] += D[c_from][ci]

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d = min(d, dst[p0][0] + dst[p1][1] + dst[p2][2])
print(d)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import floor
def main():
    a, b, n = map(int, input().split())

    amariset = set()
    for i1 in range(1, n + 1):
        amari = (i1 / b) % 1
        if amari in amariset:
            break
        else:
            amariset.add(amari)
    r = 0
    for amarie in amariset:
        rt = floor(amarie * a) - floor((amarie * a) % 1)
        r = max(r, rt)
    print(r)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import floor
def main():
    a, b, n= map(int, input().split())
    x = min(n, b - 1)
    r = floor((a * x) / b) - a * floor(x / b)
    print(r)

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

import itertools

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

total = 0
for i, j in itertools.combinations(A, 2):
    if i == j:
        total += 1

for k, val in enumerate(A):
    count = 0
    for i, v in enumerate(A):
        if k == i:
            continue
        if val == v:
            count += 1
    print(total - count)

### FIXED CODE ###

from math import factorial

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

def comb(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))

nums = [0] * (N + 1)
for i, v in enumerate(A):
    nums[v] += 1
combs = list(map(lambda n: comb(n, 2), nums))
total = sum(combs)

for k, val in enumerate(A):
    print(total - (nums[val] - 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    l, r, d = [int(x) for x in input().split()]
    l -= 1
    r -= 1
    g[l].append([r, d])
    g[r].append([l, -d])

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")


### FIXED CODE ###

n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")
### BUGGY CODE ###

from numpy import ceil,array,sum

def is_ok(m):

    tmp = h - m*B

    if not any(tmp):
        return True

    rem = sum([ceil(i/(A-B)) for i in tmp[tmp>0]])
    
    if rem > m:
        return False

    return True

N,A,B = map(int,input().split())
h = array(list(int(input()) for _ in range(N)))
s = sum(h)
##二分散策

r = 10**9
l = 0

while abs(l-r) > 1:

    m = (r+l)//2

    if is_ok(m):
        r = m
    else:
        l = m

print(r)

### FIXED CODE ###

import sys
from math import ceil

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

def check(k):
    tmp = list(h)
    for i in range(N):
        tmp[i] -= B*k
    if sum([int(i<=0) for i in tmp]) == N:
        return True

    lf = 0
    for i in tmp:
        if i > 0:
            lf += ceil(i/(A-B))

    if lf <= k:
        return True
    else:
        return False

N,A,B = map(int,input().split())
h = tuple(int(input()) for _ in range(N))

left = -1
right = 1e9

while abs(left-right) > 1:

    mid = (left+right)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(int(right))
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,m = readInts()
ab = [readInts() for i in range(m)]
go1 = []
for i in range(m):
	if ab[i][0]==1:
		go1.append(ab[i][1])
for i in range(m):
	if ab[i][0] in go1 and ab[i][1]==n:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

import bisect
def isin(arr,x):
	#print(bisect.bisect_left(arr,x))
	return arr[min(bisect.bisect_left(arr,x),len(arr)-1)]==x

n,m = readInts()
ab = [readInts() for i in range(m)]
go1 = []
for i in range(m):
	if ab[i][0]==1:
		go1.append(ab[i][1])
go1.sort()
for i in range(m):
	if isin(go1,ab[i][0]) and ab[i][1]==n:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

from collections import Counter


N = int(input())

s = [ input() for _ in range(N)]

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if(Counter(s[i]) == Counter(s[j])):
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


N = int(input())

s = [ list(input()) for _ in range(N)]
for i in range(N):
    s[i].sort()
    s[i]=''.join(s[i])

s.sort()
s.append('0')
ans_tmp = 0
ans = 0
for i in range(N):
    if(s[i]== s[i+1]):
        ans_tmp += 1
    elif(ans_tmp>=1):
        ans+= cmb(ans_tmp+1, 2)
        ans_tmp=0


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

n = int(input())
while True:
    for i in range(n):
        for j in range(2, 10):
            if n == i**j:
                print(n)
                exit()
    n -= 1

### FIXED CODE ###

n = int(input())
if  n == 1 or n == 2 or n == 3:
    print(1)
    exit()
while n > 0:
    for i in range(n):
        for j in range(2, 10):
            if n == i**j:
                print(n)
                exit()
    n -= 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = list(input().rstrip())

    for x in range(len(S) - 1):
        if S[x] == 'A' and S[x+1] == 'C':
            S[x] = 'a'
    dec_a = S.count('a')


    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    for j in range(Q):
        print(S[L[j]-1:R[j]-1].count('a'))

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()

    cnt_ac = 0
    arr_ac = [0] * (N)
    for x in range(0, N-1):
        if S[x:x+2] == 'AC':
            cnt_ac += 1
        arr_ac[x+1] = cnt_ac

    for i in range(Q):
        L, R = map(int, input().split())
        print(arr_ac[R-1] - arr_ac[L-1])


main()
### BUGGY CODE ###

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

dp = [None] * N
for n in range(N):
    if n == 0:
        dp[n] = 0
    elif n <= K:
        dp[n] = min([abs(A[n] - A[n - k - 1]) + dp[n - k - 1] for k in range(n)])
    else:        
        dp[n] = min([abs(A[n] - A[n - k - 1]) + dp[n - k - 1] for k in range(K)])
print(dp[-1])

### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

print(dp[-1])
### BUGGY CODE ###

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

MOD = 10**9+7
result = 0
for i in range(n-1):
  for j in range(i+1,n):
    result += a[i]*a[j] % MOD
print(result%MOD)



### FIXED CODE ###

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

s=[0]*(n+1)
for i in range(n):
  s[i+1] = s[i] + a[i]

MOD = 10**9+7
result = 0
for i in range(n):
  result += a[i]*(s[n] - s[i+1])%MOD
print(result%MOD)
### BUGGY CODE ###

import itertools

n = int(input())
a_list = list(map(int, input().split()))
max = 0

for a in itertools.combinations(a_list, 2):
    b, c = a
    max += b * c

print(max % 1000000007)


### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a_list = list(map(int, input().split()))
result = 0
a_sum = sum(a_list)
for i in a_list:
    a_sum -= i
    result += i * a_sum
print(result % mod)
### BUGGY CODE ###

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in range(n):
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  for k in r:
    m[k].pop()
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)
    

### FIXED CODE ###

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    if m[k]:
      previous.add(m[k][-1]-1)
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
maze = [input() for _ in range(h)]

dph = [[0 for _ in range(w)] for _ in range(h)]
dpw = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if maze[i][j] == '#':
      continue
    if dpw[i][j] != 0:
      continue
    k = j
    count = 0
    while k< w:
      
      if maze[i][k] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dpw[i][l] = count
      
for i in range(w):
  for j in range(h):
    if maze[j][i] == '#':
      continue
    if dph[j][i] != 0:
      continue
    k = j
    count = 0
    while k< h:
      
      if maze[k][i] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dph[l][i] = count


ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dpw[i][j] + dph[i][j])
print(ans-1)

### FIXED CODE ###

h,w = map(int,input().split())
maze = [input() for _ in range(h)]

dph = [[0 for _ in range(w)] for _ in range(h)]
dpw = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if maze[i][j] == '#':
      continue
    if dpw[i][j] != 0:
      continue
    k = j
    count = 0
    while k< w:
      
      if maze[i][k] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dpw[i][l] = count
      
for i in range(w):
  for j in range(h):
    if maze[j][i] == '#':
      continue
    if dph[j][i] != 0:
      continue
    k = j
    count = 0
    while k< h:
      
      if maze[k][i] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dph[l][i] = count


ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dpw[i][j] + dph[i][j])
print(ans-1)
### BUGGY CODE ###

import queue
import copy
def dfs(L,start,end):
    stack = [start]
 
    visited = [start]
 
    path =[ 0 for i in range((len(L)))]
 
    while stack:
        node = stack.pop()
        for n in L[node]:
            if n[0] not in visited:
 
                path[n[0]] = path[node]  + n[1]
 
                stack.append(n[0])
                visited.append(n[0])
 
    return path
 
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))
 
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])
 
d = dfs(L,K,0)
 
for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

### FIXED CODE ###

import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0 

def bfs(sy, sx):
  q = deque([[sy, sx]])
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx 
      if 0 <= ny < h and 0 <= nx < w and a[ny][nx] == '.' and used[ny][nx] == 0:
        used[ny][nx] = 1
        cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1)
        q.append([ny, nx])

import numpy as np
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used = [[0]*w for _ in range(h)]
      bfs(i, j)

print(np.max(np.array(cnt)))

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

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

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

import itertools


def main():
    N = int(input())
    S = [input() for _ in range(N)]

    march = []
    for s in S:
        if s[0] in ["M", "A", "R", "C", "H"]:
            march.append(s[0])

    result = []
    for comb in list(itertools.combinations(march, 3)):
        if comb[0] != comb[1] and comb[0] != comb[2] and comb[1] != comb[2]:
            result.append(comb)

    print(len(result))


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

from itertools import combinations


def main():

    N = int(input())

    count = {x: 0 for x in "MARCH"}

    for _ in range(N):
        s = input()[0]
        if s in count:
            count[s] += 1

    result = 0
    for a, b, c in combinations("MARCH", 3):
        result += count[a] * count[b] * count[c]

    print(result)


if __name__ == "__main__":
    main()