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

#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7
INF = float('INF')
#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
COSTS = [INF] * (1 << N)
COSTS[0] = 0
KEYS = [0]
A = [0]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    key = 0
    for c in C:
        key |= (1 << (c-1))
    A.append(a)
    KEYS.append(key)

for pat in range(1 << N):
    for a, key in zip(A, KEYS):
        COSTS[pat | key] = min(COSTS[pat | key], COSTS[pat] + a)

ans = COSTS[(1 << N) - 1] 
if ans == INF:
    ans = -1 
print(ans)


### FIXED CODE ###

#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7
INF = float('INF')
#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
COSTS = [INF] * (1 << N)
COSTS[0] = 0
KEYS = [0]
A = [0]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    key = 0
    for c in C:
        key |= (1 << (c-1))
    A.append(a)
    KEYS.append(key)

for pat in range(1 << N):
    for a, key in zip(A, KEYS):
        COSTS[pat | key] = min(COSTS[pat | key], COSTS[pat] + a)

ans = COSTS[(1 << N) - 1] 
if ans == INF:
    ans = -1 
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = map(int, input().split())
    Query.append((r, l, i))
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for r, l, i in Query:
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = map(int, input().split())
    Query.append(r * 10 ** 12 + l * 10 ** 6 + i)
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for q in Query:
    r = q // 10 ** 12
    l = (q % 10 ** 12) // 10 ** 6
    i = q % 10 ** 6
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)
### BUGGY CODE ###

from itertools import combinations as comb
import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    hh = len(li)
    tmp = [0]*hh
    cnt = 0
    for i in range(w):
        for j in range(hh):
            if li[j][i]>k:
                return -1
            if tmp[j]+li[j][i]>k:
                cnt += 1
                for x in range(hh):
                    tmp[x] = li[x][i]
                break
            tmp[j] += li[j][i]
    return cnt

ans = 1000000
l = list(np.sum(s, axis=0))
cnt = count([l])
if cnt>=0:
    ans = min(ans, cnt)

li = list(range(1, h))
for i in range(1, h):
    combs = list(comb(li, i))
    for cmb in combs:
        r = 0
        l = []
        for j in cmb:
            l.append(list(np.sum(s[r:j, :], axis=0)))
            r = j
        l.append(list(np.sum(s[r:, :], axis=0)))
        cnt = count(l)
        if cnt>=0:
            ans = min(ans, cnt+i)
print(ans)


### FIXED CODE ###

import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

import bisect


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

for _ in range(m):
    a_tmp = a.pop()
    a_tmp //= 2
    if(len(a)==0):a.append(a_tmp)
    else:
        if(a_tmp >= a[-1]):a.append(a_tmp)
        elif(a_tmp <= a[0]):a.insert(0,a_tmp)
        else:
            index = bisect.bisect_left(a,a_tmp)
            a.insert(index,a_tmp)


print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))

heapq.heapify(a)

for _ in range(m):
    x = heapq.heappop(a) * -1
    x //= 2
    heapq.heappush(a,-1*x)
print(-sum(a))
### BUGGY CODE ###

N,K = map(int,input().split())
A = [int(a) for a in input().split()]

n = 1
c = 0

for j in A[:K]:
    n *= j

for i in range(K,N):
    tmp = n
    tmp /= A[c]
    tmp *= A[i]

    if tmp > n:
        print("Yes")
    else:
        print("No")

    c += 1



### FIXED CODE ###

N,K = map(int,input().split())
A = [int(a) for a in input().split()]

n = 0

for i in range(K,N):
    if A[i] > A[n] :
        print("Yes")
    else:
        print("No")
    n+=1
### BUGGY CODE ###

i = input()
N = int(i)
A = []
for x in range(N):
    j = input()
    A.append(int(j))

for x in range(N):
    #print(x)
    t = A[:x] + A[x+1:]
    print(max(t))


### FIXED CODE ###

import numpy as np

i = input()
N = int(i)
A = np.array([0]*N)
i = input()
a = int(i)
A[0] = a
i = input()
b = int(i)
A[1] = b
snd = min(a, b)
fst = max(a, b)
for x in range(N - 2):
    j = input()
    y = int(j)
    A[x+2] = y
    if y <= fst:
        snd = max(snd, y)
    fst = max(fst, y)

for x in range(N):
    if A[x] < fst:
        print(fst)
    else:
        print(snd)
### BUGGY CODE ###

def main():
  number = list(map(int,input().split()))
  line = list(map(int,input().split()))
 
  num = number[0]
  K = number[1]
  dp = [float("inf")]* num
  dp[0] = 0
 
  for i in range(1, num):
    I = min(i + 1 , K + 1)
    dp[i] = min([dp[i - k] + abs(line[i] - line[i - k]) for k in range(1 , I)])
  #kの範囲: k = 1,2,3...K 無理なときは k = 1,2..i
  
  print(dp[-1])
  
main()

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  
  for a in A:
    prod *= a
    
  if prod > 1000000000000000000:
    print(-1)
  
  else:
    print(prod) 

main()

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  A.sort()
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  
  print(prod) 
 
main()
### BUGGY CODE ###

from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    else:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

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

import numpy as np

n = int(input())
l = sorted(list(map(int, input().split())))
nl = np.array(l)

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        cnt += sum(nl[j+1:] < a + b)

print(cnt)


### FIXED CODE ###

from bisect import *

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

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        lower = max(j+1, bisect_right(l, b-a))
        upper = bisect_left(l, a+b)
        cnt += max(0, upper-lower)

print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
c = [0] * (n + 1)
d = [0] * (n + 1)
for i in a:
    c[i] += 1
    d[i] = c[i] * (c[i] - 1) // 2
for i in a:
    if c[i] > 2:
        r = (((c[i] - 1) * (c[i] - 2)) // 2)
    else:
        r = 0
    print(sum(d) - d[i] + r)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
c = [0] * (n + 1)
d = [0] * (n + 1)
for i in a:
    c[i] += 1
    d[i] = c[i] * (c[i] - 1) // 2
t = sum(d)
for i in a:
    if c[i] > 2:
        r = (((c[i] - 1) * (c[i] - 2)) // 2)
    else:
        r = 0
    print(t - d[i] + r)
### BUGGY CODE ###

def grid_bfs(h,w,start,maze):
#    debug_print(maze)
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        for s in start:
            queue.append(s)
            distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx]>distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                start.append([i,j])
    D = grid_bfs(H,W,start,A)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()


### FIXED CODE ###

def grid_bfs(h,w,start,maxD):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = deque()
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h):
                if (distance[ny][nx] > distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
                    if maxD<distance[ny][nx]:
                        maxD = distance[ny][nx]
    return maxD
def examA():
    H, W = LI()
    A = [[1 if a == "#" else 0 for a in SI()] for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]==1:
                start.append([i,j])
    ans = grid_bfs(H,W,start,0)
#    print(D,V)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

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

N, C = [int(x) for x in input().split()]
D = [[0] * C for _ in range(C)]
c = [[0] * N for _ in range(N)]

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

for color in range(C):
    for i in range(N):
        for j in range(N):
            pattern = (i + j) % 3
            I[color][pattern] += D[c[i][j] - 1][color]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

print(ans)


### FIXED CODE ###

N, C = [int(x) for x in input().split()]
D = [[0] * C for _ in range(C)]
c = [[0] * N for _ in range(N)]

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

COL = [[0, 0, 0] for _ in range(C)]

for i in range(N):
    for j in range(N):
        COL[c[i][j] - 1][(i + j) % 3] += 1

for p in range(3):
    for toC in range(C):
        for fromC in range(C):
            I[toC][p] += D[fromC][toC] * COL[fromC][p]

# I[toC][pattern] += D[c[i][j] - 1][toC]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

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

import numpy as np

def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    mod = 998244353
    dp = np.zeros((n + 1, s + 1), dtype=int)
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, s = map(int, input().split())
    a = sorted([int(i) for i in input().split()])
    mod = 998244353
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 % mod + dp[i][j - ai]) % mod
    print(dp[n][s])

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

# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    s = input()

    cnt = 0
    for i in range(4, len(s) + 1):
        # print('i',i)
        for j in range(i-4, -1, -1):
            # print(s[j:i])
            n = int(s[j:i])
            if n % 2019 == 0:
                cnt = cnt + 1
    print(cnt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

h,w,k=list(map(int,input().split()))

s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[(i>>j)&1 for j in range(h)]

    curcnt=sum(split)
    nsplit=curcnt+1
    sumlst=[0]*(nsplit)
    
    cw=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[l]+=s[ch][cw]

            if sumlst[l]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break

            if split[ch]:
                l+=1
        else:
            cw+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

### FIXED CODE ###

h,w,k=list(map(int,input().split()))
s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]

    cw=0
    memo=0
    chk=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[memo][l]+=s[ch][cw]

            if sumlst[memo][l]>k:
                memo+=1
                chk+=1
                break

            if split[ch]:
                l+=1
        else:
            chk=0
            cw+=1
            continue

        if chk>1:
            break
    else:
        cnt=min(cnt,curcnt+memo)

print(cnt)
### BUGGY CODE ###

#coding:utf-8
n, x, y = map(int, input().split())
anslist = []
for i in range(n-1):
    anslist.append(0)

for s in range(1,n):
    for p in range(s+1,n+1):
        dsp = abs(p - s)
        dsxyp = abs(x - s) + 1 + abs(p - y)
        dsyxp = abs(y - s) + 1 + abs(p - x)
        distance = min(dsp,dsxyp,dsyxp)
        anslist[distance - 1] += 1

for k in range(len(anslist)):
    print("{}".format(anslist[k]))

### FIXED CODE ###

#coding:utf-8
n, x, y = map(int, input().split())
anslist = []
for i in range(n-1):
    anslist.append(0)

for s in range(1,n):
    for p in range(s+1,n+1):
        distance = min(abs(p - s),abs(x - s) + 1 + abs(p - y),abs(y - s) + 1 + abs(p - x))
        anslist[distance - 1] += 1

for k in range(len(anslist)):
    print("{}".format(anslist[k]))
### BUGGY CODE ###

n = int(input().rstrip())

line = input().rstrip().split(' ')

a = []
for i in range(n):
    a.append(int(line[i]))

a.sort()

q = int(input().rstrip())

b = []
c = []

for i in range(q):
    line = input().rstrip().split(' ')
    b = int(line[0])
    c = int(line[1])

    for j in range(len(a)):
        if a[j] == b:
            a[j] = c

    ans = 0
    for j in range(len(a)):
        ans += a[j]

    print(ans)


### FIXED CODE ###

n = int(input().rstrip())

line = input().rstrip().split(' ')

a = {}
ans = 0
for i in range(n):
    n = int(line[i])
    ans += n
    if n in a:
        a[n] += 1
    else:
        a[n] = 1

q = int(input().rstrip())

for i in range(q):
    line = input().rstrip().split(' ')
    b = int(line[0])
    c = int(line[1])

    if b in a:
        ab = a[b]
        a[b] = 0
        if c in a:
            ac = a[c]
            a[c] += ab
        else:
            a[c] = ab
    else:
        ab = 0

    ans -= ab * b
    ans += ab * c

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

n, q = [int(i) for i in input().split()]
s = input()
l = [0] * q
r = [0] * q
ans = ""
for i in range(q):
  l[i], r[i] = [int(j) for j in input().split()]
  t = s[l[i]-1:r[i]]
  cnt = 0
  for k in range(len(t)-1):
    if t[k:k+2] == "AC":
      cnt += 1
      k += 1
  ans = ans+str(cnt)+"\n"
print(ans)

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
ans = ""
table = [0] * n
cnt = 0
for i in range(n-1):
  if s[i:i+2] == "AC":
    cnt += 1
  table[i+1] = cnt
for i in range(q):
  l, r = [int(j) for j in input().split()]
  print(table[r-1] - table[l-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

def res(b):
    return np.sum(np.abs(A-(b+np.array(range(1, N+1)))))

tmp = np.sum(A) // N
a = []
for i in range(tmp-100, tmp+100):
    a.append(res(i))
print(min(a))


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
A -= np.arange(1,N+1)

def sad(b):
    return int(np.sum(np.abs(A - b)))

l = -1e10
r =  5e10
m = 2e30
tmp = 5e30
tmp2 = 1e30
while tmp2 != sad(m):
    if tmp > sad(m):
        tmp = sad(m)
    tmp2 = sad(m)
    m = (l + r) // 2
    if sad(m) - sad(m+1) >= 0:
        l = m
    else:
        r = m

print(tmp)