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

H, W = map(int, input().split())
Ss = [input() for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*H for _ in range(W)]
U = [[0]*H for _ in range(W)]
for i in range(H):
    for j in range(W):
        if Ss[i][j] == '.':
            if j == 0:
                L[i][0] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        if Ss[i][-j-1] == '.':
            if j == 0:
                R[i][-1] = 1
            else:
                R[i][-j-1] = R[i][-j] + 1
                
for j in range(W):
    for i in range(H):
        if Ss[i][j] == '.':
            if i == 0:
                U[j][0] = 1
            else:
                U[j][i] = U[j][i-1]+1
        if Ss[-i-1][j] == '.':
            if i == 0:
                D[j][-1] = 1
            else:
                D[j][-i-1] = D[j][-i] + 1

ans = 0
for i in range(H):
    for j in range(W):
        x = L[i][j] + R[i][j] + D[j][i] + U[j][i] - 3
        if ans < x:
            ans = x
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
Ss = [input() for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*H for _ in range(W)]
U = [[0]*H for _ in range(W)]
for i in range(H):
    for j in range(W):
        if Ss[i][j] == '.':
            if j == 0:
                L[i][0] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        if Ss[i][-j-1] == '.':
            if j == 0:
                R[i][-1] = 1
            else:
                R[i][-j-1] = R[i][-j] + 1
                
for j in range(W):
    for i in range(H):
        if Ss[i][j] == '.':
            if i == 0:
                U[j][0] = 1
            else:
                U[j][i] = U[j][i-1]+1
        if Ss[-i-1][j] == '.':
            if i == 0:
                D[j][-1] = 1
            else:
                D[j][-i-1] = D[j][-i] + 1

ans = 0
for i in range(H):
    for j in range(W):
        x = L[i][j] + R[i][j] + D[j][i] + U[j][i] - 3
        if ans < x:
            ans = x
print(ans)
### BUGGY CODE ###

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

def main():
    _, m = map(int, input().split())

    l, r = map(int, input().split())
    ans = {i for i in range(l, r+1)}
    for _ in range(m-1):
        l, r = map(int, input().split())
        ans &= {i for i in range(l, r+1)}
    print(len(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    _, m = map(int, input().split())

    max = -1
    min = 10 ** 5 + 1
    for _ in range(m):
        l, r = map(int, input().split())
        if l > max:
            max = l
        if r < min:
            min = r
    if min - max < 0:
        print(0)
    else:
        print(min - max + 1)

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

import numpy as np
N=int(input())
PP=np.array(input().split(),dtype=np.int64)
P_list=PP.tolist()
index=P_list.index(1)
#print(index)
count=1
if (N==1):
    print(count)
else:
    for i in range(1,index+1):
        P1=PP[0:i+1]
        MIN=np.min(P1)
        TAR=P1[i]
        if (MIN==TAR):
            count += 1

    print(count)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = list(map(int, readline().split()))
temp = p[0]
lis = p[1:]
ans = 1

for i in lis:
    if (i > temp):
        pass
    else:
        temp = i
        ans += 1

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

n=int(input())

s=[]
for i in range(n):
  read=list(input())
  read.sort()
  s.append(read)

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

print(ans)

  
  

### FIXED CODE ###

n=int(input())
from collections import Counter
s=[]
for i in range(n):
  read=list(input())
  read.sort()
  s.append("".join(read))

ans=0
dic=Counter(s)
for i in dic:
  ans=ans+dic[i]*(dic[i]-1)//2
print(ans)
### BUGGY CODE ###

from math import factorial

def comb(n, k, p):
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 0
    n_fact = factorial(n) % p
    k_fact = factorial(k) % p
    n_k_fact = factorial(n - k) % p
    return (n_fact * pow(k_fact, p - 2, p) * pow(n_k_fact, p - 2, p)) % p

mod = 10**9 + 7
n, a, b = map(int, input().split())
result = pow(2, n) - 1

for i in (a, b):
    result -= comb(n, i, mod)

result %= mod

print(result)


### FIXED CODE ###

def comb_mod(n, k, p):
    """
    nCk mod p
    """
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator *= n - i
        numerator %= p
        denominator *= i + 1
        denominator %= p
    return numerator * pow(denominator, p-2, p) % p

mod = 10**9 + 7
n, a, b = map(int, input().split())
result = pow(2, n, mod) - 1

for i in (a, b):
    result -= comb_mod(n, i, mod)
result %= mod

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

import copy

n = int(input())
l = [int(input()) for i in range(n)]
for i in range(n):
    s = copy.copy(l)
    s.pop(i)
    print(max(s))

### FIXED CODE ###

import copy

n = int(input())
l = [int(input()) for i in range(n)]
Max1 = sorted(l)[-1]
Max2 = sorted(l)[-2]
for i in range(n):
    if l[i] == Max1:
        print(Max2)
    else:
        print(Max1)
### BUGGY CODE ###

n = int(input())

# i = format(n, 'b')[::-1].find('1')
i = 0
ans = 0
while True:
  n //=2
  ans += 2**i
  i += 1
  if n == 1:
    break

print(ans+2**i)

### FIXED CODE ###

n = int(input())

# i = format(n, 'b')[::-1].find('1')
ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n == 1:
    print(ans+k)
    break
  elif n < 1:
    print(ans)
    break
### BUGGY CODE ###

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[largest] < A[l]:
        largest = l
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
while True:
    c = raw_input()
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
d=dict()
def help(a,i,j):
    if d.get(str(i)+" "+str(j),None)!=None:
        return d[str(i)+" "+str(j)]
    if j<i:
        return 0
    if i==j:
        return a[i]
    t1=a[i]-help(a,i+1,j)
    t2=a[j]-help(a,i,j-1)
    # print(i,j)
    # print(t1,t2)
    if t1>t2:
        d[str(i)+" "+str(j)]=t1 
    else:
        d[str(i)+" "+str(j)]=t2 
    return d[str(i)+" "+str(j)]
print(help(a,0,len(a)-1))

### FIXED CODE ###

import sys
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(2,n+1):
    for j in range(n-i+1):
        k=j+i-1 
        dp[j][k]=max(a[k]-dp[j][k-1],a[j]-dp[j+1][k])
print(dp[0][len(a)-1])
### BUGGY CODE ###

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

from math import ceil

def solve(A, B, C, D):
    zaiko = A
    visited = set([zaiko])
    while zaiko >= B:
        zaiko -= B
        if zaiko > C:
            zaiko -= ceil((zaiko - C) / B) * B
            if zaiko < 0 or zaiko > C: return False
        zaiko += D
        if zaiko in visited: return True
        visited.add(zaiko)
    return False


T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')

### FIXED CODE ###

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

from math import ceil

def gcd(a, b):
    assert a > 0 and b > 0
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

def solve(A, B, C, D):
    if A < B or D < B: return False
    if A % B > C: return False
    if D % B == 0: return True

    g = gcd(B, D)
    r = A % g  # +D -B を繰り返すと x % g == r であるxを訪れる
    # x % g == r and C < x < B である x が存在するなら False を返す
    return not (C < B - g + r)

T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]

s = sorted(set(a))
i = 0
while i < len(s):
    l = len(s)
    for j in range(l-1, i, -1):
        if s[j] % s[i] == 0:
            s.pop(j)
    i += 1
s = set(s)

from collections import Counter
c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]

a.sort()
a_max = a[-1] + 1   # aの最大値
lst = [0] * a_max   # a_max個のリストを生成

for x in a:
    lst[x] += 1                         # リストの該当の数字に1追加 
    if lst[x] == 1:                     # まだ他の数値の倍数でなければ、リストへ2倍、3倍…の数字を1追加していく
        for i in range(x*2, a_max, x):
            lst[i] += 1

output = 0
for x in a:
    if lst[x] == 1:
        output += 1
print(output)
### BUGGY CODE ###

N = int(input())


def count_comb(a, b):
    if a == b:
        return 1
    else:
        return 2


count = 0
for A in range(1, N):
    for B in range(A, N):
        seki = A*B
        if seki > N-1:
            break
        count += count_comb(A, B)

print(count)


### FIXED CODE ###

N = int(input())

count = 0
for A in range(1, N):
    max_a = int((N-1)/A)
    # AとBが同じものが1件あるので-1する
    count += max_a

print(count)
### BUGGY CODE ###

import math
N ,X ,Y = map(int,input().split())
x = [0] * (N-1)
for i in range(1,N+1):
    for u in range(i+1,N+1):
        y =[abs(u - i), abs(X - i) + 1 + abs(u - Y ), abs(Y - i) + 1 + abs(u - X)]
        x[min(y)-1] += 1
for h in x:
    print(h)

### FIXED CODE ###

import math
N ,X ,Y = map(int,input().split())
x = [0] * (N-1)
for i in range(1,N+1):
    for u in range(i+1,N+1):
        y =[abs(u - i), abs(X - i) + 1 + abs(u - Y ), abs(Y - i) + 1 + abs(u - X)]
        x[min(y)-1] += 1
for h in x:
    print(h)
### BUGGY CODE ###

[k,s]=[int(i) for i in input().split()]
a=[]
for i in range(k+1):
    x=i
    for j in range(s-x+1):
        y=s-x-j
        z=s-x-y
        if y<=k and z<=k:
            a.append([x,y,z])
#print(a)
print(len(a))

### FIXED CODE ###

[k,s] = [int(i) for i in input().split()]
count = 0
for x in range(k+1):
  for y in range(min(s-x+1,k+1)):
      if s - x - y <= k:
          count += 1
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 300001
for i in range(N):
  tmp = 0
  for j in range(max(l[i]-K, 0), min(l[i]+K+1, 300000)):
    tmp = max(tmp, cnts[j])
  cnts[l[i]] = tmp+1
print(max(cnts))


### FIXED CODE ###

N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [1] * N
for i in range(N):
  for j in range(max(0, i-200), i):
    if abs(l[i]-l[j]) <= K:
      cnts[i] = max(cnts[i], cnts[j]+1)
print(max(cnts))
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)

a = []
for i in range(n):
    for j in range(i,n):
        a.append(s[i:j+1])
b = sorted(set(a))
print(b[k-1])


### FIXED CODE ###

s = input()
k = int(input())
n = len(s)

a = []
for i in range(n):
    for j in range(i+1,n+1):
        if j - i > k:break
        a.append(s[i:j])
b = sorted(set(a))
print(b[k-1])
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            if s[i] == t[j]:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
            else:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j])%MOD
    print(dp[-1][-1] + 1)

if __name__ =='__main__':
    main()   


### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            if s[i] == t[j]:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
            else:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j])%MOD
    print((dp[-1][-1] + 1)%MOD)

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

n = int(input())
lis = list(map(int, input().split()))
count = 0
minn = lis[0]
flug = 0
for i in range(n):
    if flug == 0:
        newlis = lis[0:i+1]
        if  minn >= lis[i]:
            count += 1
            minn = lis[i]
            if minn == 1:
                count += lis[i+1:].count(1)
                flug = 1
print(count)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
count = 0
minn = lis[0]
minl = min(lis)
flug = 0
for i in range(n):
    if flug == 0:
        if  minn >= lis[i]:
            count += 1
            minn = lis[i]
            if minn == minl:
                count += lis[i+1:].count(minl)
                flug = 1
print(count)
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(x):
    for j in range(y):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(min(k,w)):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.4))):
    for j in range(min(y,int(k*1.4))):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(w):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)
### BUGGY CODE ###

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

INF = sum(h)*2
dp = [INF for _ in range(N+K)]
dp[0] = 0
h = h + [INF]*K
for i in range(N-1):
  for j in range(1, K+1):
    dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])


### FIXED CODE ###

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

dp = [0 for _ in range(N)]

for i in range(1, N):
  dp[i] = min([dp[i-j-1]+abs(h[i]-h[i-j-1]) for j in range(min(i,K))])

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

from operator import mul
from functools import reduce
cnt = 10 **18
N = map(int, input().split())
nums = list(map(int, input().split()))


count  = reduce(mul, nums)
if count  > cnt :
        print(-1)
else:
         print(count)

### FIXED CODE ###

#from operator import mul
#from functools import reduce
#cnt = 1000000000000000000
ans =1
N = int(input())
nums = list(map(int, input().split()))

if 0 in nums:
        print(0)
        exit()
for num in nums:
    ans *= num
    if ans > 10**18 :
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())
for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
        
print(A, B)

### FIXED CODE ###

A,B,K = map(int,input().split())
A = A - K
if A >= 0:
    print(A,B)
else:
    B = B + A
    if B >= 0:
        print(0,B)
    else:
        print(0,0)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
from numba import jit

INF = 1 << 50
EPS = 1e-8
@jit
def solve(S):
    count = 0
    N, _ = S.shape
    N //= 2
    #print(N)
    #print(S.shape)
    #print(S)
    for i in range(N):
        for j in range(N):
            cut_S = S[i:i+N, j:j+N]
            #print(cut_S)
            if (cut_S == cut_S.T).all():
                count+=1
    return count



def run():
    N = int(input())
    S = []

    for i in range(N):
        s = input()
        s = [ord(ss)-96 for ss in s]
        S.append(s)
    S = np.array(S, dtype=np.int32)

    S = np.tile(S, (2,2))
    print(solve(S))

if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8


def run():
    N = int(input())
    S_ = []

    for i in range(N):
        s = input()
        s = [ord(ss)-96 for ss in s] * 2
        S_.append(s)

    #for s in S_:
    #    print(s)
    S = []
    for s in S_:
        S.append(s)
    for s in S_:
        S.append(s)

    #for s in S:
    #    print(s)


    axises = [(i, 0) for i in range(N)]
    for i in range(1, N):
        axises.append((0, i))

    ans = 0

    #print(axises)
    for axis in axises:
        ci, cj = axis
        done = False
        for i in range(N):
            if done:break
            for j in range(i, N):
                if S[ci+i][cj+j] == S[ci+j][cj+i]:continue
                else:
                    #print((ci, cj), (i, j))
                    done=True
                    break
        if not done:
            ans += min(N-ci, N-cj)


    print(ans)

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

def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 1300
    m = n//2
    dp = [[[False]*n for j in range(w)] for i in range(h)]
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            q = min(min((i+j+2), (h-1-i)+(w-1-j)+2)*80, m)
            if 0 < i and 0 < h:
                for k in range(m-q, m+q):
                    if dp[i-1][j][k] or dp[i][j-1][k]:
                        if x <= k:
                            dp[i][j][k-x] = True
                        if k < n-x:
                            dp[i][j][k+x] = True
            elif 0 < i:
                for k in range(m-q, m+q):
                    if dp[i-1][j][k]:
                        if x <= k:
                            dp[i][j][k-x] = True
                        if k < n-x:
                            dp[i][j][k+x] = True
            elif 0 < j:
                for k in range(m-q, m+q):
                    if dp[i][j-1][k]:
                        if x <= k:
                            dp[i][j][k-x] = True
                        if k < n-x:
                            dp[i][j][k+x] = True
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:r-=1;data[r-1]=x
            if l&1:data[l-1]=x;l+=1
            l>>=1;r>>=1
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

for i in range(q):
  a,b=list(map(int, input().split()))
  counter=0
 
  for j in range(len(S[a-1:b])-1):
    if S[a-1:b][j] == "A":
      if S[a-1:b][j+1] == "C":
        counter +=1

  print(counter)

### FIXED CODE ###

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

t=[0]*n

s=s.replace("AC", "Ac")
#s=s.translate(str.maketrans({'AC':'aC'})) maketransは置換元一文字じゃないといけんみたい
for i in range(n):
  if s[i] == "c":
    if i !=0:
      t[i]=1+t[i-1]
    else:
      t[i]=1
  else:
    t[i]=t[i-1]

#print(t)
for _ in range(q):
  l,r=list(map(int, input().split()))
  print(t[r-1]-t[l-1])