Harryxun/stf_run huggingface dataset:
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

used = [[False for _ in range(W)] for _ in range(H)]


def dfs(x, y):
    global nb, nw
    if S[y][x] == '#':
        nb += 1
    if S[y][x] == '.':
        nw += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if used[ny][nx]:
            continue
        if S[y][x] == '#' and S[ny][nx] == '#':
            continue
        if S[y][x] == '.' and S[ny][nx] == '.':
            continue
        used[ny][nx] = True
        dfs(nx, ny)

ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j]:
            used[i][j] = True
            nb = 0
            nw = 0
            dfs(j, i)
            ans += nb*nw
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

used = [[False for _ in range(W)] for _ in range(H)]


def dfs(x, y):
    global nb, nw
    if S[y][x] == '#':
        nb += 1
    if S[y][x] == '.':
        nw += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if used[ny][nx]:
            continue
        if S[y][x] == '#' and S[ny][nx] == '#':
            continue
        if S[y][x] == '.' and S[ny][nx] == '.':
            continue
        used[ny][nx] = True
        dfs(nx, ny)

ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j]:
            used[i][j] = True
            nb = 0
            nw = 0
            dfs(j, i)
            ans += nb*nw
print(ans)
N,K = map(int,input().split(' '))
d = int(input())
lst = [map(int,input().split(' ')) for i in range(K+1)]
lst1 = [0]*N
decision_flag = True
for i in lst:
    if decision_flag == True:
        decision_flag = False
        for i1 in i:
            lst1[i1-1] = 1

    else:
        decision_flag = True
print(lst1.count(0))

### FIXED CODE ###

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

sunuke = [1] * N

for i in range(K):
    di = int(input())
    tmp = map(int, input().split())
    for t in tmp:
        sunuke[t - 1] = 0

print(sum(sunuke))
A, B, K = map(int, input().split())
a = max(0, A-K)
K = max(0, K-A)
print(max(0, K-A))
if K > 0:
    b = max(0, B-K)
print(str(a) + ' ' + str(b))

### FIXED CODE ###

A, B, K = map(int, input().split())
a = max(0, A-K)
K = max(0, K-A)
b = max(0, B-K)
print(str(a) + ' ' + str(b))
from collections import defaultdict
from itertools import combinations
n=int(input())
s=[input() for i in range(n)]
cnt=defaultdict(lambda :0)
cnt['M']=0
for i in range(n):
    if s[i][0] in 'MARCH':
        cnt[s[i][0]]+=1

if len(cnt)<=2:print(0)
else:
    num=len(cnt)
    ans=0
    for x,y,z in combinations(list(cnt.values()), 3):
        ans+=x*y*z
print(ans)


### FIXED CODE ###

from collections import defaultdict
from itertools import combinations

n=int(input())
s=[input() for i in range(n)]
name=['M','A','R','C','H']

cnt=defaultdict(lambda:0)
for i in range(n):
    if s[i][0] in name:
        cnt[s[i][0]]+=1

cnt=cnt.values()
if len(cnt)<3:
    print(0)
    exit()
ans=0

# listから２つ選ぶ組み合わせ
for x,y,z in combinations(cnt,3):
    ans+=x*y*z

print(ans)
import math
A,B = map(int, input().split())

 

 
for i in range(1,100001):
    if A == int(i * 0.08) and B == int(i * 0.1):
        print(i)
        sys.exit()
 
print(-1)

### FIXED CODE ###

import sys

a, b = [int(w) for w in input().split()]

max_n = (b + 1) * 10

for i in range(max_n):
    if a == int(i * 0.08) and b == int(i * 0.1):
        print(i)
        sys.exit()

print(-1)
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()
s = int(input())
s_r = s[::-1]
cnt = 0
for i in range(len(s)):
    if s[i] != s_r[i]:
        cnt += 1
print(cnt//2)

### FIXED CODE ###

s = input()
s_r = s[::-1]
cnt = 0
for i in range(len(s)):
    if s[i] != s_r[i]:
        cnt += 1
print(cnt//2)
# coding: utf-8
s = raw_input().split()[0]
t = raw_input().split()[0]

s1 = list(s)
t1 = list(t)

s1.sort
t1.sort(reverse=True)

if s1<t1:
  print 'Yes'
else:
  print 'No'

### FIXED CODE ###

# coding: utf-8
import math

a,b = map(int,raw_input().split())
print -(-(a+b)//2)
a=int(input())
b=int(input())
c=int(input())
d=int(input())
print (a*b-(b*c+a*d-c*d))

### FIXED CODE ###

a,b=map(int,input().split())
c,d=map(int,input().split())
print ((a-c)*(b-d))
a , b = input().split()
a = int(a)
b = int(b)
print(a,b)
if b > a:
    print(a+1)
else:
    print(a)

### FIXED CODE ###

a , b = input().split()
a = int(a)
b = int(b)
if b >= a:
    print(a)
else:
    print(a-1)
s = input()
t  =input()
print(s.replace('1','')[0])

### FIXED CODE ###

s = input()
t =int(input())
for i in range(t):
  if s[i]!='1':
    print(s[i])
    exit()
print('1')
a=[]
for i in range(10):
    a.append(input())
a.sort()
a=a[::-1]
a=a[-4]
print(a[0])
print(a[1])
print(a[2])

### FIXED CODE ###

a=[]
for i in range(10):
    a.append(input())
a.sort()
a=a[::-1]
a=a[:3]
print(a[0])
print(a[1])
print(a[2])
n,k = map(int,input().split())
A = list(map(int,input.split()))

if (n-1)%%(k-1) == 0:
  print(n-1/k-1)
else:
  print((n-1//k-1)+1)
  






### FIXED CODE ###

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

print(-((1-n)//(k-1)))
N,K = map(int,input().split())
H = list(map(int,input().split()))
h = H.sort()
i = 0
count = 0
while sum(h[N-K]) == 0:
  while h[N-K] == 0:
    count += 1
    while i <= N-K:
      i += 1
print(count)

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
H.sort(reverse=True)
 
sum = 0
for count in range(N):
        if count >= K:
            sum += H[count]
 
print(sum)
N = int(input())
A = list(map(int,input().split()))
ans = 1
re = 0
for i in range(N-1):
    if A[i+1] > A[i]:
        dire = '<'
        break
    if A[i+1] < A[i]:
        dire = '>'
        break
    else:
        dire = '='
if dire != '=':
    for i in range(2,N,1):
        #print()
        
        if re == 0:
            if dire == '>':

                if A[i] <= A[i-1] <= A[i-2]:
                    re = 0
                    dire =  '>'

                else:
                    ans += 1
                    re = 1
                    dire = '<'
            elif dire == '<':
                if A[i-2] <= A[i-1] <= A[i]:
                    re = 0
                    dire = '<'
                else:
                    ans += 1
                    dire = '>'
                    re = 1
        else:
            re = 0

            



print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
re = 0

for i in range(2,N,1):
    #print(re)
    if re == 0:
        if A[i-2] >= A[i-1] >= A[i]:
            re = 0
            if A[i-1] == A[i]:
                A[i-1] = A[i-2]
            
        elif A[i-2] <= A[i-1] <= A[i]:
            re = 0
            if A[i-1] == A[i]:
                A[i-1] = A[i-2]
            
        else:
            ans +=1
            re = 1
    else:
        re = 0



print(ans)
N=int(input())

#h=max(H-|X-Cx|-|Y-Cy|,0)
#h=H-|X-Cx|-|Y-Cy|    h=0
#H=h+|X-Cx|+|Y-Cy|
S=[]
for i in range(N):
  x,y,h=map(int, input().split())
  S.append((x,y,h))

for cx in range(100+1):
  for cy in range(100+1):
    isans=True
    preH=0
    late=[]
    for i in range(N):
      x,y,h=S[i]
      if h==0:
        late.append((x,y,z))
      else:
        H=h+abs(x-cx)+abs(y-cy)
        #print(H)
        if preH==0:
          preH=H
        elif preH!=H:
          isans=False
        preH=H
    for x,y,h in late:
      if preH!=0 and preH>abs(x-cx)+abs(y-cy):
          isans=False
    if isans:
      print(cx, cy, H)



### FIXED CODE ###

N=int(input())

#h=max(H-|X-Cx|-|Y-Cy|,0)
#h=H-|X-Cx|-|Y-Cy|    h=0
#H=h+|X-Cx|+|Y-Cy|
S=[]
for i in range(N):
  x,y,h=map(int, input().split())
  S.append((x,y,h))

for cx in range(100+1):
  for cy in range(100+1):
    isans=True
    preH=0
    late=[]
    for i in range(N):
      x,y,h=S[i]
      if h==0:
        late.append((x,y,h))
      else:
        H=h+abs(x-cx)+abs(y-cy)
        #print(H)
        if preH==0:
          preH=H
        elif preH!=H:
          isans=False
        preH=H
    for i in range(len(late)):
      x,y,h=late[i]
      if preH!=0 and preH>abs(x-cx)+abs(y-cy):
          isans=False
    if isans:
      print(cx, cy, H)
import argparse


def main():
    parser = argparse.ArgumentParser()

    parser.add_argument('input', metavar='a', type=int)

    args = parser.parse_args()

    a = args.input

    print('{0}'.format(a+a*a+a*a*a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

a = int(input())
print('{0}'.format(a+a*a+a*a*a))
a, b = (int(i) for i in input().split())

if sum(a,b) > 9:
  print("error")
else:
  print(sum(a,b))



### FIXED CODE ###

a = [int(i) for i in input().split()] 

if sum(a) > 9:
  print("error")
else:
  print(sum(a))
N,K = map(int,input().split())
N_d = N*2
ans = 0
kl = [K*x for x in range(1,N_d//K+1)]
s=kl[-1]
t=kl[-2]
if K%2==1:
  a=s//K
  if a%2==0:
    b = a//2
    ans = pow(b,3)
    
  else:
    b=a//2
    ans = pow(b,3)+3
    
else:
  half_K = K//2
  a = s//K
  if a%2==0:
    b = a//2
    ans+=pow(b,3)
  else:
    b=a//2
    ans += pow(b,3)+3
    
  b = t//K
  if b%2==0:
    c = b//2
    ans+=pow(c,3)
  else:
    c=b//2
    ans+=pow(b,3)+3
  
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
ans = 0
if K%2==1:
  ans = (N//K) ** 3
else:
  half_K = K//2
  a = N//K
  b = N//half_K - a
  ans = a**3+b**3

print(ans)
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, -1, -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, (total - a1) // 2), -1, -1):
            a3 = k - a1 - a2
            if a1 + 2 * a2 + 3 * a3 > total:
                break
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])


### FIXED CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])
n = int(input())
m = int(input())
l1 = []
for i in range (m):
    a1 = int(input())
    l1.append(a1)
s = sum(l1)
r = n - s
print(r)

### FIXED CODE ###

n, m = map(int, input().split())
ai = map(int, input().split())
li = map(int, list(ai))
s = sum(li)
r = (n - s)
if r >= 0:
    print(r)
else:
    print("-1")
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

# print(sc)

a = ["0" for _ in range(n)]

for i in range(m):
    s, c = sc[i]
    s -= 1
    if n == 3 and s == 0 and c == 0:
        print(-1)
        exit()
    if n == 2 and s == 1 and c == 0:
        print(-1)
        exit()
    if n == 1 and s == 2 and c == 0:
        print(-1)
        exit()
    c = str(c)
    if i == s and a[i] != "0" and a[i] != c:
        print(-1)
        exit()
    a[s] = c

# print(a)
if a[0] == "0":
    a[0] = 1 
ans = int("".join(a))
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

# print(sc)

a = ["0" for _ in range(n)]

for i in range(m):
    s, c = sc[i]
    if n == 3 and s == 1 and c == 0:
        print(-1)
        exit()
    if n == 2 and s == 1 and c == 0:
        print(-1)
        exit()
    s -= 1
    c = str(c)
    if a[s] != "0" and a[s] != c:
        print(-1)
        exit()
    a[s] = c

# print(a)
if n == 1 and a[0] == "0":
    pass
elif a[0] == "0":
    a[0] = "1"
ans = int("".join(a))
print(ans)
n, m = map(int, input().split())

jouken_1 = []
jouken_2 = []
jouken_3 = []

for _ in range(m):
    array = tuple(map(int, input().split()))
    if array[0] == 1:
        jouken_1.append(array)
    elif array[0] == 2:
        jouken_2.append(array)
    elif array[0] == 3:
        jouken_3.append(array)

a = set(jouken_1)
b = set(jouken_2)
c = set(jouken_3)
a = list(a)
b = list(b)
c = list(c)

if len(a) > 1:
    print(-1)
    exit()
elif len(b) > 1:
    print(-1)
    exit()
elif len(c) > 1:
    print(-1)
    exit()

if n == 1:
    if len(b) > 0 or len(c) > 0:
        print(-1)
        exit()
    else:
        print(a[0][1])
elif n == 2:
    if len(c) > 0:
        print(-1)
        exit()
    elif a[0][1] == 0:
        print(-1)
        exit()
    elif len(b) == 0 and len(a) == 1:
        num = a[0][1] * 10
        print(num)
    elif len(a) == 1 and len(b) == 1:
        num = b[0][1]+ a[0][1] * 10
        print(num)
elif n == 3:
    if a[0][1] == 0:
        print(-1)
        exit()
    if len(b) == 1:
        if len(c) == 1:
            num = a[0][1] * 100 + b[0][1] * 10 + c[0][1]
        else:
            num = a[0][1] * 100 + b[0][1] * 10
    else:
        if len(c) == 1:
            num = a[0][1] * 100 + c[0][1]
        else:
            num = a[0][1] * 100
    print(num)


### FIXED CODE ###

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

jouken_1 = []
jouken_2 = []
jouken_3 = []

if m == 0:
    if n == 1:
        print(0)
        exit()
    elif n == 2:
        print(10)
        exit()
    else:
        print(100)
        exit()

for _ in range(m):
    array = tuple(map(int, input().split()))
    if array[0] == 1:
        jouken_1.append(array)
    elif array[0] == 2:
        jouken_2.append(array)
    elif array[0] == 3:
        jouken_3.append(array)

a = set(jouken_1)
b = set(jouken_2)
c = set(jouken_3)
a = list(a)
b = list(b)
c = list(c)
flag = False

if len(a) > 1:
    print(-1)
    exit()
elif len(a) == 1:
    a = a[0][1]
else:
    flag = True
    a = 0

if len(b) > 1:
    print(-1)
    exit()
elif len(b) == 1:
    b = b[0][1]
else:
    b = 0

if len(c) > 1:
    print(-1)
    exit()
elif len(c) == 1:
    c = c[0][1]
else:
    c = 0

if n == 1:
    if b > 0 or c > 0:
        print(-1)
        exit()
    for i in range(10):
        if i == a:
            print(a)
            exit()
    print(-1)
elif n == 2:
    if c > 0:
        print(-1)
        exit()
    if a == 0 and flag is True:
        a = 1
    for i in range(10, 100):
        if str(i)[0] == str(a) and str(i)[1] == str(b):
            print(i)
            exit()
    print(-1)
elif n == 3:
    if a == 0 and flag is True:
        a = 1
    for i in range(100, 1000):
        if str(i)[0] == str(a) and str(i)[1] == str(b) and str(i)[2] == str(c):
            print(i)
            exit()
    print(-1)
a = list(int(i) for i in input().split()) 
a.sort()
b = " ".join(a)

### FIXED CODE ###

a = list(i for i in input().split()) 
a.sort()
b = " ".join(a)
print(b)
#!/usr/bin/env python3

import sys
input = sys.stdin.readline

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
L = list(map(int, input().split()))
M = [0] *(N+1)
cnt = [0] *(N+1)

for i in L:
    cnt[i] += 1
    C = cnt[i]
    if C == 2:
        M[i] = 2
    elif C > 2:
        M[i] *= C
        M[i] //= (C-2)     
ans = sum(M)//2

for i in range(N):
    B = cnt[L[i]]
    if B == 2:
        print(ans - 1)
    elif B > 2:
        print(ans -combinations_count(B,2) +combinations_count(B-1,2))
    else:
        print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

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

print(N*(N-1)//2 + M*(M-1)//2)
from math import gcd
x=range(int(input()))
y=0
for a in z:
  for b in z:
    for c in z:
      y+=gcd(gcd(a+1,b+1),c+1)
print(y)


### FIXED CODE ###

from math import gcd
z=range(1,1+int(input()))
y=0
for a in z:
  for b in z:
    for c in z:
      y+=gcd(gcd(a,b),c)
print(y)
S = input()

if S.count("R") == 2 and S[1] != R:
  print(1)
  
else:
  print(S.count("R"))

### FIXED CODE ###

S = input()
 
if S.count("R") == 2 and S[1] != "R":
  print(1)
  
else:
  print(S.count("R"))
n = int(input())
import math
start = math.floor(math.sqrt(n))
for i in reversed(range(start)):
    if n/i == int(n/i):
        break
print(i+n//i-2)

### FIXED CODE ###

n = int(input())
import math
start = math.floor(math.sqrt(n))
for i in reversed(range(start+1)):
    if i == 0:
        i = n
    else:
        if n/i == int(n/i):
            break
print(i+n//i-2)
n=int(input())
s=list(input())
count=0
for i in range(n):
  if s[i]== 'A':
    if (s[i+1]) =='B':
      if (s[i+2])=='C':
        count+=1
print(count)



    
  
    
    

### FIXED CODE ###

n=int(input())
s=list(input())
count=0
for i in range(n-2):
  if s[i]== 'A':
    if (s[i+1]) =='B':
      if (s[i+2])=='C':
        count+=1
print(count)
r,g,b,n = map(int,input().split())
ans = 0
for i in range(r):
  for j in range(g):
    for k in range(b):
      if i*r + j*g + k*b = n:
        ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
count = 0
for i in range(3001):
	for j in range (3001):
		if i*R+j*G<=N:
			tmp = N-(i*R+j*G)
			if tmp % B == 0:
				count += 1
print(count)
# dict形式で既出分をもたせる
N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
test_dict = {}
for j, temp in enumerate(a):
    #print(temp)
    str_sub = string[temp[0]-1:temp[1]]
    if j == 0:
        test_dict[str_sub] = str_sub.count('AC')
        result = str(test_dict[str_sub])
    if test_dict.get(str_sub):
        #print(test_dict.get(str_sub))
        result += '\n' + str(test_dict.get(str_sub))
        continue
    test_dict[str_sub] = str_sub.count('AC')
    result += '\n' + str(test_dict[str_sub])
    #print(test_dict[str_sub])

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
import sys
Imp = [int(i) for i in sys.stdin]
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")
        

### FIXED CODE ###

Imp = list(map(int, input().split()))
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")
from sys import stdin


stdin = io.StringIO(__INPUT)

D,T,S = [ int(x) for x in stdin.readline().rstrip().split()]

if ( S * T) > D:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

from sys import stdin


D,T,S = [ int(x) for x in stdin.readline().rstrip().split()]

if ( S * T) >= D:
    print('Yes')
else:
    print('No')
import collections
from itertools import accumulate
from scipy.special import comb

n = int(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = collections.Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += comb(v,2,exact=True)
print(cnt)

### FIXED CODE ###

import math
from collections import Counter
from itertools import accumulate

def P(n,r):
    return math.factorial(n)//math.factorial(n-r)

def C(n,r):
    return P(n,r)//math.factorial(r)

n = int(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += C(v,2)
print(cnt)