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

N,Q=map(int,input().split())
S=input()
L=[None]*Q
for i in range (Q):
    L[i] = list(map(int,input().split()))

def check(S): #1 moji
    if S == "AC":
        return True
    else:
        return False

ans = [0]*Q

for i in range(Q):
    for j in range(L[i][0]-1,L[i][1]-1):
        if check(S[j:j+2]):
            ans[i]+=1
for i in range(Q):
    print(ans[i])


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
L = [None]*Q
for i in range(Q):
    L[i] = list(map(int,input().split()))

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

for i in range(Q):
    print(rui[L[i][1]-1]-rui[L[i][0]-1])
### BUGGY CODE ###


n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))



def search(s,T):
    left = 0 ; right = len(T)-1
    while left <= right:
        mid = (left + right)//2
        if T[mid]==s: return True
        elif T[mid]>s: right = mid
        else: left = mid+1

count = 0
for s in S:
    if search(s,T): count+=1


print(count)

### FIXED CODE ###


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

ans=len(set(s)&set(t))

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

def main():
    N = int(input())
    a = list(map(int, input().split()))

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i, x in enumerate(a):
        s[i+1] = s[i] + x
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            D = dp[i]
            for k in range(i, j):
                if D[j] > D[k]+dp[k+1][j] + tmp:
                    D[j] = D[k]+dp[k+1][j] + tmp

    print(dp[0][N-1])
main()


### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i in range(N):
        s[i+1] = s[i] + a[i]
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j] + tmp)

    print(dp[0][N-1])


main()
### BUGGY CODE ###

s = input()
s = list(s)
q = int(input())
query = list(list(input().split()) for _ in range(q))

for i in range(q):
    qry = query[i]
    if qry[0] == '1':
        s.reverse()
    else:
        if qry[1] == '1':
            s.insert(0, qry[2])
        else:
            s.append(qry[2])
            
s = ''.join(s)
print(s)

### FIXED CODE ###

s = input()
s = list(s)
q = int(input())
query = list(list(input().split()) for _ in range(q))

rs_cnt = 0

head = []
tail = []

for i in range(q):
    qry = query[i]
    if qry[0] == '1':
        rs_cnt += 1
    else:
        if qry[1] == '1':
            if rs_cnt % 2 == 0:
                head.append(qry[2])
            else:
                tail.append(qry[2])
        else:
            if rs_cnt % 2 == 0:
                tail.append(qry[2])
            else:
                head.append(qry[2])
            
if rs_cnt % 2 == 0:
    head.reverse()
    head = ''.join(head)
    s = ''.join(s)
    tail = ''.join(tail)
    print(head + s + tail)
else:
    s.reverse()
    tail.reverse()
    head = ''.join(head)
    s = ''.join(s)
    tail = ''.join(tail)
    print(tail + s + head)
### BUGGY CODE ###

n = int(input())
from collections import Counter as cnt
from itertools import combinations as cm
lis = []
for i in range(n):
  count = cnt(list(input()))
  lis.append(count)
  
counter = 0
for pair in cm(lis, 2):
  if pair[0] == pair[1]:
    counter += 1
print(counter)

### FIXED CODE ###

n = int(input())
from collections import defaultdict as dd
dic = dd(lambda: 0)

counter = 0
for i in range(n):
  s = input()
  s_s = sorted(s)
  s_s_s = "".join(s_s)
  counter += dic[s_s_s]
  dic[s_s_s] += 1

print(counter)
### BUGGY CODE ###

N = int(input())
ls = [sorted(list(input())) for i in range(N)]
print(sum([ls[i:N].count(ls[i])-1 for i in range(N)]))

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input().rstrip())) for _ in range(N)]

memo = {}
for x in s:
    if x not in memo:
        memo[x] = 1
    else:
        memo[x] += 1

print(sum(x*(x-1)//2 for x in memo.values()))
### BUGGY CODE ###

import numpy as np

#def gcd(*numbers):
#    return reduce(math.gcd, numbers)

a = int(input())
list1 = [np.gcd(np.gcd(x, y),z) for x in range(1, a+1) for y in range(1, a+1) for z in range(1, a+1)]
result = sum(list1)
      
print(result)

### FIXED CODE ###

from functools import reduce
import math

#def gcd(*numbers):
#    return reduce(math.gcd, numbers)

a = int(input())
result = 0

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

N = int(input())
A = list(map(int,input().split()))
mod = 1000000000+7
T = 0
#print(A[1])
for i in range(N-1):
    for j in range(N-i-1):
        T += A[i]*A[j+i+1]%mod
        #print(T)
T = T%mod
print(T)

### FIXED CODE ###

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

S = sum(A)
S2 = sum(map(lambda x: x*x,A))

print((S*S - S2) // 2 % 1000000007)
### BUGGY CODE ###

import numpy as np
import copy
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

for i in range(N):
    tmp = A[i]
    A[i] = 0
    print(np.max(A))
    A[i] = tmp

### FIXED CODE ###

import numpy as np
import copy
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

tmp = copy.deepcopy(A)
tmp = list(sorted(A, reverse=True))

Amax = tmp[0]
Asecond = tmp[1]

for i in range(N):
    if A[i] != Amax:
        print(Amax)
    else:
        print(Asecond)
### BUGGY CODE ###

n=int(input())
A = []
for _ in range(n):
  x = int(input())
  A.append(x)
standard = max(A)
for i in range(n):
  if A[i] != standard:
    print(standard)
  else:
    temp = 0
    for t in range(n):
      if t != i:
        if A[t] >= temp:
          temp = A[t]
    print(temp)

### FIXED CODE ###

n=int(input())
A = []
for _ in range(n):
  x = int(input())
  A.append(x)
standard = max(A)
counter = A.count(max(A))
for i in range(n):
  if A[i] != standard:
    print(standard)
  elif counter >=2:
    print(standard)
  else:
    temp = 0
    for t in range(n):
      if t != i:
        if A[t] >= temp:
          temp = A[t]
    print(temp)
### BUGGY CODE ###

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

each_bit_sum = [{"0": 0, "1": 0} for _ in range(62)]
result = 0
for a in A:
    for i, b in enumerate(format(a, "b").zfill(62)[::-1]):
        each_bit_sum[i][b] += 1

for i, b in enumerate(each_bit_sum):
    result += ((b["0"] * b["1"]) * (2**i)) % ((10**9) + 7)

print(result % ((10**9) + 7))


### FIXED CODE ###

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

result = 0
for i in range(60):
    target = 1 << i
    on = sum([target & a for a in A]) >> i
    result += (on * (N - on)) << i
    result %= ((10**9) + 7)

print(result)
### BUGGY CODE ###

def sadden_value(a, b):
    total = 0
    for i in range(0, len(a)):
        total += abs(a[i]-b-i-1)
    return total

n = int(input())
a = list(map(int, input().split()))
b = 1 - n
now = sadden_value(a, b)
while True:
    nex = sadden_value(a, b + 1)
    if now <= nex:
        print(now)
        break
    now = nex
    b += 1


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
tmp = [a[x] - (x+1) for x in range(0,n)]
tmp.sort()
b = tmp[n // 2]
print(sum((abs(tmp[i] - b) for i in range(0,n))))
### BUGGY CODE ###

import sys
import numpy

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

sum_x = numpy.cumsum(x_list)

max_robo = -(-1 * N // 2)
ans = sys.maxsize
for k in range(1, max_robo + 1):
    t_ans = 0
    # t_ans += 5 * (sum_x[N] - sum_x[max(N - k * 2, 0)])
    t_ans += 5 * sum_x[N]
    for j in range(1, -(-(N - k) // k)):
        tmp = sum_x[N - (j + 1) * k]
        t_ans += tmp * 2

    t_ans += (N + k) * X
    ans = min(ans, t_ans)


print(ans)

### FIXED CODE ###

import sys
# import numpy

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

tmp = 0
sum_x = []
for x in x_list:
    tmp += x
    sum_x.append(tmp)
# sum_x = numpy.cumsum(x_list)

max_robo = -(-1 * N // 2)
ans = sys.maxsize
for k in range(1, max_robo + 1):
    t_ans = (N + k) * X + 5 * sum_x[N]
    for j in range(1, -(-(N - k) // k)):
        t_ans += 2 * sum_x[N - (j + 1) * k]

    ans = min(ans, t_ans)

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

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int32)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = np.zeros([N-1, T], dtype = np.int32)
DP[0,A[0]:] = B[0]

for i in range(1, N-1):
	for j in range(T):
		if j - A[i] >= 0:
			DP[i,j] = max(DP[i-1, j], DP[i-1,j-A[i]] + B[i])
		else:
			DP[i,j] = DP[i-1,j]

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp

C = DP[:,T-1] + B[1:]
print(np.max(C))

### FIXED CODE ###

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x: x[0])

DP = [[0] * T for _ in range(N-1)]

for i in range(N-1):
	for j in range(T):
		if i == 0:
			if j >= AB[0][0]:
				DP[i][j] = AB[0][1]
		else:
			if j >= AB[i][0]:
				DP[i][j] = max(DP[i-1][j], DP[i-1][j-AB[i][0]] + AB[i][1])
			else:
				DP[i][j] = DP[i-1][j]

ans = 0
tmp = 0

for i in reversed(range(N-1)):
	tmp = max(tmp, AB[i+1][1])
	ans = max(ans, DP[i][T-1] + tmp)

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
ans=0
for i in range(1,n):
    ans+=len(make_divisors(i))
print(ans)

### FIXED CODE ###

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table
n=int(input())
print(sum(num_divisors_table(n-1)))
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  
  n,q=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  ans=[0]*(n+1)
  for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
  
  l,parent=deque([1]),[0]*(n+1)
  while l:
    x=l.popleft()
    for i in ab[x]:
      if not i in parent or i in l:
        l.append(i)
        ans[i]+=ans[x]
        parent[i]=x
      
  print(*ans[1:])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  
  n,q=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  ans=[0]*(n+1)
  for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
  
  l,parent=deque([1]),[0]*(n+1)
  parent[1]=1
  while l:
    x=l.popleft()
    for i in ab[x]:
      if parent[i]:
        continue
      l.append(i)
      ans[i]+=ans[x]
      parent[i]=1
      
  print(*ans[1:])
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())
S = input()
rs = [s=="R" for s in S]
gs = [s=="G" for s in S]
bs = [s=="B" for s in S]

ind_r = [i for i,s in enumerate(rs) if s == 1]
ind_g = [i for i,s in enumerate(gs) if s == 1]
ind_b = [i for i,s in enumerate(bs) if s == 1]

ans = 0
ng = sum(gs)
for i in ind_r:
    for j in ind_b:
        # print(i,j)
        kM = max(i,j) + abs(i-j)
        km = min(i,j) - abs(i-j)
        ans += ng
        if (max(i,j) - min(i,j))%2==0:
            # print("aaa",(max(i,j)+min(i,j))//2)
            ans -= gs[(max(i,j)+min(i,j))//2]
        if kM < n:
            ans -= gs[kM]
        if 0 <= km:
            ans -= gs[km]
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

from collections import defaultdict
d = defaultdict(list)

for i,s in enumerate(S):
    d[s].append(i)

Bs = [0] * 8000
cnt_b = len(d["B"])

for i in  d["B"]:
    Bs[i] += 1

ans = 0
for i_r in d["R"]:
    for i_g in d["G"]:
        ls = []
        mx = max(i_r,i_g)
        mn = min(i_r,i_g)
        if (mx-mn) % 2 == 0:
            ls.append((mx+mn)//2)    
        ls.append(mx + (mx-mn))
        if  mn - (mx-mn) >= 0: 
            ls.append(mn-(mx-mn)) 
        cnt = 0
        for l in ls:
            cnt += Bs[l]
        # print(i_r,i_g,ls)
        ans += cnt_b - cnt
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
count=0
for i in range(0,n-2):
    s1=s[i]
    for j in range(i+1,n-1):
        s2=s[j]
        if s1!=s2:
            for k in range(j+1,n):
                if j-i!=k-j and s1!=s[k] and s2!=s[k]:
                    count=count+1
print(count)

### FIXED CODE ###

n=int(input())
s=input()
count=0
A=[[0,0,0]for i in range(n)]
for i in range(0,n):
    if s[n-i-1]=="R":
        A[n-i-2][0]=A[n-i-1][0]+1
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="G":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]+1
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="B":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]+1
for i in range(0,n-3):
    s1=s[i]
    for j in range(i+1,n-1):
        s2=s[j]
        if s1!=s2:
            if s1=="R" and s2=="G":
                s3="B"
            elif s1=="G" and s2=="R":
                s3="B"
            elif s1=="R" and s2=="B":
                s3="G"
            elif s1=="B" and s2=="R":
                s3="G"
            elif s1=="B" and s2=="G":
                s3="R"
            elif s1=="G" and s2=="B":
                s3="R"
            if s3=="R":
                s4=0
            if s3=="G":
                s4=1
            if s3=="B":
                s4=2
            count=count+A[j][s4]
            if j+j-i+1<=n: 
                if s[j+j-i]==s3:
                    count=count-1
print(count)
### BUGGY CODE ###

s=[1 if i=="R" else -1 for i in input()]
count = [0 for i in range(len(s))]
for i in range(len(s)):
    c=0
    now=i
    while True:
       c+=1
       ne=s[now]
       nextstep=s[now+ne]
       if nextstep == ne:
           now+=ne
       else:
           break
    if (10**100-c)%2 == 0:
        count[now+ne] += 1
    else:
        count[now] += 1
print(" ".join([str(i) for i in count]))

### FIXED CODE ###

s=[1 if i=="R" else -1 for i in input()]
count = [0 for i in range(len(s))]
for i in range(len(s)):
    c=0
    now=i
    if i>0 and s[now]==s[i-1]:
        count[pre_ot] += 1
        pre_re, pre_ot = pre_ot, pre_re
        continue
        
    while True:
       c+=1
       ne=s[now]
       nextstep=s[now+ne]
       if nextstep == ne:
           now+=ne
       else:
           break
    if (10**100-c)%2 == 0:
        count[now+ne] += 1
        pre_re = now+ne
        pre_ot = now
    else:
        count[now] += 1
        pre_re = now
        pre_ot = now+ne
print(" ".join([str(i) for i in count]))
### BUGGY CODE ###

from collections import Counter
import math

cmb2 = [0] * 200001
for n in range(2, 200001):
    num = 1
    r = 2
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

n = int(input())
a = list(map(int, input().split()))
nn = len(a) - 1
ctr = Counter(a)

memo = {}
for aa in a:
    if aa not in memo:
        x = 0
        for k, v in ctr.items():
            if k == aa:
                v -= 1
            if v >= 2:
                x += cmb2[v]
        memo[aa] = x
    print(memo[aa])


### FIXED CODE ###

from collections import Counter
import math

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

ctr = Counter(aa)

cmb2 = [0] * 200001
for n in range(2, 200001):
    r = 2
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

x = 0
for k, v in ctr.items():
    x += cmb2[v]

for a in aa:
    k = ctr[a] - 1
    print(x - k)
### BUGGY CODE ###

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

m = N

while m > abs (m - K):
  m = abs (m - K)
    
print(m)


### FIXED CODE ###

import numpy as np
N, K  = map(int, input().split())

m = np.mod(N,K)

while m > abs (m-K):
  m = abs (m-K)

print(m)
### BUGGY CODE ###

s = input()
t = input()
ls = len( s)
lt = len( t)
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                CNT[i][j] = CNT[i][j-1]
            else:
                CNT[i][j] = CNT[i-1][j]
i = lt
j = ls
ans = ""
while i > 0 and j > 0:
    if t[i-1] == s[j-1]:
        ans += t[i-1]
        i -= 1
        j -= 1
    else:
        if CNT[i-1][j] > CNT[i][j-1]:
            i -= 1
        else:
            j -= 1
print( ans[::-1])

### FIXED CODE ###

s = input()
t = input()
ls = len( s)
lt = len( t)
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                CNT[i][j] = CNT[i][j-1]
            else:
                CNT[i][j] = CNT[i-1][j]
i = lt
j = ls
ans = ""
while i > 0 and j > 0:
    if t[i-1] == s[j-1]:
        ans += t[i-1]
        i -= 1
        j -= 1
    else:
        if CNT[i-1][j] > CNT[i][j-1]:
            i -= 1
        else:
            j -= 1
print( ans[::-1])
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        for j in friend[i]:
            union(uft, j, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-block[i])-len(friend[i])-1) for i in range(1, n+1))

print(answer())



### FIXED CODE ###

from collections import defaultdict, Counter
import sys

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, rank, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return

    if rank[x] >= rank[y]:
        uft[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        uft[x] = y

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(int)
    block = defaultdict(int)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    rank = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, rank, a, b)
        friend[a] += 1
        friend[b] += 1
    for j in range(k):
        c, d = map(int, input().split())
        if not same(uft, c, d):
            continue
        block[c] += 1
        block[d] += 1
    for i in range(1, n+1):
        root(uft, i)
    c = Counter(uft)
    return [c[uft[i]]-block[i]-friend[i]-1 for i in range(1, n+1)]

print(*answer())
### BUGGY CODE ###

"""
解説を参考に作成
提出 #5799729:
    TLE -> dequeではなくリストにしてみた
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = [Hi, Wi, massHi[Wi]]
            if massHi[Wi] == 1:
                queue1.append(mass[Hi][Wi])

    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break

        while len(queue1) > 0:
            # h, w, a = queue1.popleft()
            h, w, a = queue1.pop()
            # left
            if w != 0 and mass[h][w - 1][2] == 0:
                mass[h][w - 1][2] = 1
                queue2.append(mass[h][w - 1])
            # right
            if w < W - 1 and mass[h][w + 1][2] == 0:
                mass[h][w + 1][2] = 1
                queue2.append(mass[h][w + 1])
            # top
            if h < H - 1 and mass[h + 1][w][2] == 0:
                mass[h + 1][w][2] = 1
                queue2.append(mass[h + 1][w])
            # button
            if h != 0 and mass[h - 1][w][2] == 0:
                mass[h - 1][w][2] = 1
                queue2.append(mass[h - 1][w])

        count += 1
        queue1 = queue2
        queue2 = deque([])
    print(count)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


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

def logic(N, K):
    if K == 1:
        return N**3
    count = 0
    for a in range(1, N + 1):
        b_s = K - (a % K)
        for b in range(b_s, N + 1, K):
            for c in range(b_s, N + 1, K):
                if (b + c) % K == 0:
                    count += 1
    return count

def main():
    N, K = map(int, input().split())
    print(logic(N, K))

if __name__ == '__main__':
    main()

### FIXED CODE ###

N, K = map(int,input().split())
print(int(N/K)**3+[int((N+K/2)/K)**3,0][K%2])
### BUGGY CODE ###

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

w = []
v = []

for x in range(n):
    peso,valor = map(int,input().split())
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

for i in range(n):
    for j in range(W,-1,-1):
        if j + w[i] <= W:
            dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i])


resposta = 0

for x in dp:
    resposta = max(x,resposta)

print(resposta)


### FIXED CODE ###

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

w = []
v = []

for x in range(n):
    peso,valor = map(int,input().split())
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

for i in range(n):
    for j in range(W,-1,-1):
        if j + w[i] <= W:
            dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i])


resposta = 0

for x in dp:
    resposta = max(x,resposta)

print(resposta)