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

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

for i, a in enumerate(A):
    table.append([a,i])
table.sort()

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + baby * abs(pos-x+1)) * (x>0),\
                     (DP[x][y-1] + baby * abs(pos-(N-y)) * (y>0)))

ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)


### FIXED CODE ###

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

for i, a in enumerate(A):
    table.append([a,i])
table.sort(reverse=True)

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + table[i-1][0] * abs(table[i-1][1]  - x+1)) * (x>0),\
                     (DP[x][y-1] + table[i-1][0] * abs(table[i-1][1] - (N - y))*(y>0)))


ans = 0
for i in range(N+1):
    for j in range(N+1):
        ans = max(ans, DP[i][j])
print(ans)
### BUGGY CODE ###

import collections

N = int(input())
S = [input() for i in range(N)]

count = collections.Counter(S)

# print(count)

max_k_list = [kv[0] for kv in count.items() if kv[1] == max(count.values())]

max_k_list.sort()

for i in max_k_list:
    print(i)


### FIXED CODE ###

import collections

N = int(input())
S = [input() for i in range(N)]

# print(S)

count = collections.Counter(S)

# print(count)

max_value = max(count.values())

max_k_list = []

for k, v in sorted(count.items(), key=lambda x: x[1], reverse=True):
    if v == max_value:
        max_k_list.append(k)
    else:
        break

max_k_list.sort()

for i in max_k_list:
    print(i)
### BUGGY CODE ###

N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)
#print(Graph,gyaku)
ALL = list(ALL);root = ALL[0]

used = set([])
ans = [0 for _ in range(N)]
Q = [root]
while Q:
  v = Q.pop()
  for w in Graph[v]:
    ans[w] = v+1
    Q.append(w)
for x in ans:
  print(x)
  


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)
#print(Graph,gyaku)
ALL = list(ALL);root = ALL[0]

used = set([])
TS = []
def dfs(v):
  if v in used:
    return
  used.add(v)
  for w in Graph[v]:
    if w in used:
      continue
    dfs(w)
    TS.append(w)
    
dfs(root)
TS.append(root)
TS.reverse()
#print(TS)
ans = [0 for _ in range(N)]
for i in range(N):
  now = TS[i]
  for nxt in Graph[now]:
    ans[nxt] = now+1
    
for x in ans:
  print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    N, M = map(int, input().split())
    C = []
    for i in range(M):
        a, b = map(int, input().split())
        p = min(a, b)
        q = max(a, b)
        C.append([p,q])
    D = get_unique_list(C)
    # print(D)

    # C = [list(map(int, input().split())) for i in range(M)]

    # F = [[0]*(N+1) for i in range(N+1)]
    F = [1]*(N+1)
    for a, b in D:
        F[a] += 1
        F[b] += 1
    # for a,b in D:
    #     if F[a][b] == 0:
    #         F[a][b] += 1
    #     if F[b][a] == 0:
    #         F[b][a] += 1
    # G = [1]*(N+1)
    # for i in range(N+1):
    #     G[i] = sum(F[i])
    ans = max(F)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return -self.parents[self.find(x)]

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 1
    if M == 0:
        print(ans)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

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

N = int(input())
A = list(map(int, input().split()))
S = 0
MOD = 1000000007
for i in range(N - 1):
    for j in range(i + 1, N):
        S += A[i] ^ A[j]
print(S % MOD)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
MOD = 10 ** 9 + 7
ans = 0

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

print(ans % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
import copy

a = int(input())
nums = [0]*a

for i in range(a):
    nums[i] = int(input())
    
for j in range(a):
    thisnums = copy.deepcopy(nums)
    thisnums[j] = 0
    print(max(thisnums))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
import copy

a = int(input())
nums = [0]*a

for i in range(a):
    nums[i] = int(input())
    
maxnum = max(nums)
maxenum = [i for i, x in enumerate(nums) if x == maxnum]
maxquant = len(maxenum)


if maxquant != 1:
    for j in range(a):
        print(maxnum)
else:
    for j in range(a):
        if nums[j] != maxnum:
            print(maxnum)
        else:
            copylist = copy.deepcopy(nums)
            copylist[maxenum[0]] = 0
            print(max(copylist))
### BUGGY CODE ###

from itertools import product as pd
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

def calc(a,b,c,d):
  lx=min(o[a][0],o[b][0])
  rx=max(o[a][0],o[b][0])
  dy=min(o[c][1],o[d][1])
  uy=max(o[c][1],o[d][1])

  cnt=0
  for i in o:
    if lx<=i[0]<=rx and dy<=i[1]<=uy:
      cnt+=1
  if cnt>=k:
    return (rx-lx)*(uy-dy)
  return float("inf")

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    v=min(v,calc(a,b,c,d))
print(v)

### FIXED CODE ###

from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())
lr = [list(map(int, input().split())) for _ in range(q)]

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    si2 = [n for n in si if n in ("A","C")]
    si3 = "".join(si2)
    so= si3.count("AC")
    cntli.append(so)

for p in cntli:
    print(p)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

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

import numpy as np

def is_symmetric(a):
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[] for _ in range(N)]
    for i in range(N):
        for s in list(input()):
            S[i].append(ord(s) - ord("a"))

    S = np.array(S)

    ans = 0
    for A in range(N):
        for B in range(N):
            if is_symmetric(np.roll(np.roll(S, A, axis=0), B, axis=1)):
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# 解説AC
import numpy as np

def is_symmetric(a):
    """
    対象行列判定 O(N * N)
    """
    return np.array_equal(a, a.T)

def main():
    N = int(input())
    S = [[ord(s) - ord("a") for s in list(input())] for _ in range(N)]

    S = np.array(S)

    ans = 0
    for B in range(N):
        if is_symmetric(np.roll(S, B, axis=1)):
            ans += N

    print(ans)

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

s=input();n=len(s)
def f(i,t,k):
 if k>n-i:return 0
 if k==0:return 1
 a=max(t,int(s[i]));i+=1;z=f(i,t,k)
 if a:z=f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,t,k-1)
 return z
print(f(0,0,int(input())))

### FIXED CODE ###

def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))
### BUGGY CODE ###

import fractions

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a // fractions.gcd(lm,a)

ans = 0

for a in A:
    ans += ( lm//a )
    ans %= Mod

print(ans)

### FIXED CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a//gcd(lm,a)

ans = 0
for i in range(N):
    ans += lm//A[i]
ans %= Mod

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

n = int(input())

a = [input() for i in range(n)]

print(max(a[1:]))

for i in range(1, n-1):
    a1 = max(a[:i])
    a2 = max(a[i+1:])
    max_a = a1 if a1 > a2 else a2
    print(max_a)
    
print(max(a[:-1]))

### FIXED CODE ###

n = int(input())

a = [int(input()) for i in range(n)]
 
b = sorted(a, reverse=True)
 
 
for ai in a:
    if ai == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

import numpy as np
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0

S_t=np.array(S).T.tolist()
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                S_t[i][j-k]=ans+1+int(S_t[i][j-k])
            ans=0
        else:
            for k in range(1,ans+1):
                S_t[i][j-k]=ans+int(S_t[i][j-k])
            ans=0
c=0
for p in S_t:
    for q in p:
        if q !='#':
            c=max(int(c),int(q)-1)
print(c)

### FIXED CODE ###

H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in S:
    for j in range(W):
        if i[j]!='#' and j!=W-1:
            ans+=1
        elif i[j]!='#'and j==W-1 :
            for k in range(ans+1):
                i[j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in S_t:
    for j in range(H):
        if i[j]!='#' and j!=H-1:
            ans+=1
        elif i[j]!='#'and j==H-1 :
            for k in range(ans+1):
                i[j-k]+=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]+=ans
            ans=0
            i[j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)
### BUGGY CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

ans = 0
flg = False
for a in range(N):
    S2 = S[a:] + S[:a]
    for i in range(N):
        for j in range(N):
            if S2[i][j] != S2[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)

### FIXED CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

ans = 0
flg = False
for a in range(N):
    S2 = S[a:] + S[:a]
    for i in range(N):
        for j in range(N):
            if S2[i][j] != S2[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)
### BUGGY CODE ###

import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]


checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1


dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp = (dp + np.array(mae_zero)) % 998244353

print(dp[N] % 998244353)

### FIXED CODE ###

import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((l, r, c))
lrc.sort()

inf = 10**18
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)
### BUGGY CODE ###

import math
n=int(input())
l=0
summ=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans=math.gcd(i,j,)
      ans=math.gcd(ans,k)
      summ+=ans
print(summ)

### FIXED CODE ###

import math
n=int(input())
l=0
summ=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans=math.gcd(i,j,)
      ans=math.gcd(ans,k)
      summ+=ans
print(summ)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
flag = [False] * (n - k)
r = [0] * (n - k + 1)
for i in range(n - k + 1):
    r[i] = reduce(mul, a[i : i + k])

    if i > 0:
        if r[i] > r[i - 1]:
            flag[i - 1] = True
for i in flag:
    print("Yes") if i else print("No")


### FIXED CODE ###

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

for i in range(k, n):
    if a[i - k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
l.append(9999999999999)
c = 0
for i in range(n - 2):
    t = i + 2
    for j in range(i + 1, n - 1):
        for k in range(t, n + 1):
            if l[i] + l[j] <= l[k]:
                t = k
                break
        if t > j: c += t - j - 1
        if j + 1 == t: t += 1
print(c)                











# t = 2
# c = 0
# for i in range(n - 2):
#     k = 2
#     for j in range(i + 1, n - 1):
#         for k in range(t, n):
#             print(i, j, k, t)
#             if j == k:
#                 t = k + 1
#                 continue
#             if l[i] + l[j] > l[k]: continue
#             else:
#                 t = k
#                 break
#         print("t, j = ", t, j)
#         c += (t - j - 1)
# print(c)
# 

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
import math


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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    text =[]
    dptx = [[""] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j - 1] + 1 >=dp[i - 1][j] and dp[i - 1][j - 1] + 1 >=dp[i][j - 1]:
                    dptx[i][j] =dptx[i-1][j-1] +s[i-1]
                elif dp[i - 1][j - 1] + 1 <=dp[i - 1][j] and dp[i-1][j ] >=dp[i][j - 1]:
                    dptx[i][j] =dptx[i-1][j]
                else:
                    dptx[i][j] =dptx[i][j-1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i-1][j ] >=dp[i][j - 1]:
                    dptx[i][j] = dptx[i-1][j]
                else:
                    dptx[i][j] =dptx[i][j-1]

    print(dptx[ls][lt])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math


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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt=""
    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    while lt != 0 and ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt +s[ls]

    print(txt[::-1])


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

import sys


def allocate(count, weights):
    """allocate all packages of weights onto trucks.
    returns maximum load of trucks.

    >>> allocate(2, [1, 2, 2, 6])
    6
    >>> allocate(3, [8, 1, 7, 3, 9])
    10
    """
    def sumw(i, j):
        if (i, j) not in sums:
            sums[(i, j)] = sum(weights[i:j])
        elif (i, j-1) in sums:
            sums[(i, j)] = sums[(i, j-1)] + weights[j-1]

        return sums[(i, j)]

    sums = {}
    k = len(weights)
    if count >= k:
        return max(weights)
    elif count == 1:
        return sum(weights)

    maxloads = [sumw(0, i+1) for i in range(k-count+1)]
    for i in range(1, count):
        for j in reversed(range(k - count + 1)):
            ms = []
            for x in range(j+1):
                p1 = i+x
                p2 = i+j+1
                if i == count-1:
                    p2 = k
                ms.append(max(sumw(p1, p2), maxloads[x]))
            maxloads[j] = min(ms)

    return min(maxloads)

def run():
    k, n = [int(i) for i in input().split()]
    ws = []
    for i in sys.stdin:
        ws.append(int(i))

    print(allocate(n, ws))


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys


def allocate(count, weights):
    """allocate all packages of weights onto trucks.
    returns maximum load of trucks.

    >>> allocate(2, [1, 2, 2, 6])
    6
    >>> allocate(3, [8, 1, 7, 3, 9])
    10
    """
    def loadable_counts(maxweight):
        n = 0
        l = 0
        c = count
        for w in weights:
            l += w
            if l > maxweight:
                l = w
                c -= 1

            if c <= 0:
                return n

            n += 1
        return n

    i = max(weights)
    j = max(weights) * len(weights) // count

    while i < j:
        mid = (i + j) // 2
        if loadable_counts(mid) < len(weights):
            i = mid + 1
        else:
            j = mid

    return i


def run():
    k, n = [int(i) for i in input().split()]
    ws = []
    for i in sys.stdin:
        ws.append(int(i))

    print(allocate(n, ws))


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

from collections import deque
H, W = map(int, input().split())
C = []
Q = deque()
dist = [[-1]*W for i in range(H)]

for i in range(H):
  s = list(input())
  yxidx = [(i,x) for x,v in enumerate(s) if v == "#"]
  for (y, x) in yxidx:
    Q.append((y,x))
    dist[y][x] = 0
  C.append(s)
X = [1,0,-1,0]
Y = [0,-1,0,1]


while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dist[ny][nx] == -1) and (C[ny][nx] != "#"):
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

N = int(input())
A_i = list(map(int, input().split()))
uq_A_i = list(set(A_i))
C = ["0\n"] * N
for i in uq_A_i:
    C[i - 1] = "{}\n".format(A_i.count(i))
print("".join(C))


### FIXED CODE ###

N = int(input())
A_i = list(map(int, input().split()))
C = [0] * N
for i in A_i:
    C[i - 1] += 1
print(*C)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr_list = [list(map(int,input().split())) for nesya in range(q)]
ac_set = set()
t = s.replace('AC',' AC')
s_list = list(t.split(' '))
c = len(s_list.pop(0))+1
ac_set.add(c)
for hoge in s_list:
  c += len(hoge)
  ac_set.add(c)
for lr in lr_list:
  ans = 0
  for i in range(lr[0],lr[1]):
    if i in ac_set:
      ans += 1
  print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr_list = [list(map(int,input().split())) for nesya in range(q)]
hoge = [0]*(n+1)
for i in range(n):
  hoge[i+1] = hoge[i] + (1 if s[i:i+2] == 'AC' else 0)
for lr in lr_list:
  l = lr[0]
  r = lr[1]
  print(hoge[r-1] - hoge[l-1])