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

from collections import Counter
N, M = list(map(int, input().split()))
groups = {i+1:-1 for i in range(N)}
cnt = 0
for _ in range(M):
    a, b = list(map(int, input().split()))
    if groups[a]!=-1 and groups[b]!=-1:
        a_val = groups[a]
        b_val= groups[b]
        for i in range(N):
            if groups[i+1]==b_val:
                groups[i+1]=a_val
    if groups[a]==-1 and groups[b]==-1:
        groups[a] = cnt
        groups[b] = cnt
        cnt+=1
    elif groups[a]==-1:
        groups[a] = groups[b]
    elif groups[b]==-1:
        groups[b] = groups[a]
if cnt==0:
    print(1)
else:
    for n,m in Counter(groups.values()).most_common():
        if n==-1:
            continue
        print(m)
        break




### FIXED CODE ###

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = list(map(int, input().split()))
u = UnionFind(N)
for _ in range(M):
    a, b = list(map(int, input().split()))
    u.union(a-1,b-1)
ans = []
for i in range(N):
    ans.append(u.find(i))
from collections import Counter
c=Counter(ans)
print(max(c.values()))
### BUGGY CODE ###

import heapq

N = int(input())
a = [int(n) for n in input().split()]
former = a[:N]

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappushpop(former, a[N+k])
  former_sum.append(sum(former))

a = [n * (-1) for n in a]
latter = a[2*N:]
heapq.heapify(latter)
latter_sum = [sum(latter)]

for k in range(N):
  heapq.heappushpop(latter, a[2*N-k-1])
  latter_sum.append(sum(latter))

res = [former_sum[k] + latter_sum[N-k] for k in range(N+1)]

print(max(res))

### FIXED CODE ###

import heapq

N = int(input())
a = [int(n) for n in input().split()]
former = a[:N]

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappush(former, a[N+k])
  former_sum.append(former_sum[k]+a[N+k]-heapq.heappop(former))

a = [n * (-1) for n in a]
latter = a[2*N:]
heapq.heapify(latter)
latter_sum = [sum(latter)]

for k in range(N):
  heapq.heappush(latter, a[2*N-k-1])
  latter_sum.append(latter_sum[k] + a[2*N-k-1] - heapq.heappop(latter))

res = [former_sum[k] + latter_sum[N-k] for k in range(N+1)]

print(max(res))
### BUGGY CODE ###

n = int(input())
s_list = list(input())
mod = 10 ** 9 + 7

from math import factorial

l_counter = 0
pair_counter = 0
res = 1

for i in range(2 * n):
    s = s_list[i]
    if i % 2 == 0:
        s = "W" if s == "B" else "B"

    if s == "W":
        l_counter += 1
    else:
        pair_counter += 1
        res *= l_counter
        l_counter -= 1

if pair_counter != n:
    print(0)
else:
    print(res * factorial(n) % mod)

### FIXED CODE ###

import math
n = int(input())
s = [0 if i == "W" else 1 for i in list(input())]
cnt = 0
c = 1
for i in range(n * 2):
    if (s[i] + cnt) % 2 != 0:
        cnt += 1
    else:
        c = (c * (cnt if cnt != 0 else 1)) % (10 ** 9 + 7)
        cnt -= 1
    if cnt < 0:
        print(0)
        exit()
if cnt != 0:
    print(0)
else:
    print((c * math.factorial(n)) % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]

dp = list(beauty)

for i in range(n):
    max_beauty = beauty[i]
    for j in range(i):
        if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
            max_beauty = beauty[i] + dp[j]

    dp[i] = max_beauty

ans = max(dp)
print(ans)


### FIXED CODE ###

n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)
### BUGGY CODE ###

import bisect


def main():
    def isOK(score):
        count = 0
        for a in A:
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
        if count >= M:
            return True
        else:
            return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect.bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


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

import sys
import itertools
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    mi=min(itertools.accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))
    st[i].append(mi)

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

### FIXED CODE ###

import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")
### BUGGY CODE ###

text=input()
string=input()


#common_length[i]は、探索列がstring[i]で探索を終了したときに、
# string[i-common_lneght[i] + 1] 〜string[i]で構成される文字列が、探索価値を持つことを示す


len_string=len(string)
common_length=[0]*len_string
tmp=0
for i in range(1,len_string):
    if(string[i]==string[tmp]):
        common_length[i-1]=0
        tmp+=1
    else:
        common_length[i-1]=tmp
        tmp=0

if(string[-1]==string[tmp-1]):
    common_length[-1]=tmp




tmp=0

for i in range(len(text)):
    if(text[i]!=string[tmp]):
        while(text[i]!=string[tmp] and tmp==0):
            tmp=common_length[max([tmp-1,0])]
        if(text[i]==string[tmp]):
            tmp+=1
    else:
        tmp+=1
        if(tmp==len_string):
            print(i-tmp+1)
            tmp=common_length[-1]


### FIXED CODE ###

text=input()
string=input()


#common_length[i]は、探索列がstring[i]で探索を終了したときに、
# string[i-common_lneght[i] + 1] 〜string[i]で構成される文字列が、探索価値を持つことを示す


len_string=len(string)
common_length=[0]*len_string
tmp=0
tmp_tmp=0
for i in range(1,len_string):
    if(string[i]==string[tmp]):
        tmp_tmp=tmp
        while(string[i]==string[tmp_tmp] and tmp_tmp >0):
            tmp_tmp=common_length[max([tmp_tmp-1,0])]
        common_length[i-1]=tmp_tmp
        tmp+=1
    else:
        common_length[i-1]=tmp
        while(string[i]!=string[tmp] and tmp>0):
            tmp=common_length[max([tmp-1,0])]

if(string[-1]==string[tmp-1]):
    common_length[-1]=tmp
common_length[0]=0


tmp=0

for i in range(len(text)):
    if(text[i]!=string[tmp]):
        while(text[i]!=string[tmp] and tmp>0):
            tmp=common_length[max([tmp-1,0])]
        if(text[i]==string[tmp]):
            tmp+=1
    else:
        tmp+=1
        if(tmp==len_string):
            print(i-tmp+1)
            tmp=common_length[-1]
### BUGGY CODE ###

import copy

N=int(input())
L=[]
tmp=[]
for _ in range(N):
  L.append(int(input()))

h=max(L)

for i in range(N):
  if L[i]!=h:
    print(h)
  else:
    tmp=copy.deepcopy(L)
    del tmp[i]
    print(max(tmp))

### FIXED CODE ###

N=int(input())
L=[]
for _ in range(N):
  L.append(int(input()))
sL=sorted(L)
sL.reverse()
m=max(L)
m2=sL[1]

for i in range(N):
  if L[i]==m:
    print(m2)
  else:
    print(m)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
 
def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    ans=0
    for i in range(n):
        if(a[i]!=M):
            ans=M
        else:
            ans=0
            for j in range(n-1):
                if(j>=i):
                    j+=1
                if(a[j]>ans):
                    ans=a[j]
            
        print(ans)        
main()




### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    cnt=0
    ans=0
    S=0
    for i in range(n):
        if(a[i]!=M and a[i]>S):
            S=a[i]
        elif(a[i]==M):
            cnt+=1
    
    for i in range(n):
        if(a[i]!=M or cnt>1):
            ans=M
        else:
            ans=S
        print(ans)        
main()
### BUGGY CODE ###

# coding: utf-8
N = int(input())
d = {}
for i in range(N):
    a = int(input())
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
ans = 0
for a in d.items():
    ans += a[1] % 2
print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
d = {}
for i in range(N):
    a = int(input())
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
ans = 0
for a in d.items():
    ans += a[1] % 2
print(ans)
### BUGGY CODE ###

from collections import deque

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

A = deque(sorted(A, reverse=True))
for _ in range(M):
  x = A.popleft()//2
  for i, a in enumerate(A):
    if x >= a:
      A.insert(i, x)
      break
  else:
    A.append(x) 
print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)
for _ in range(M):
  heapq.heappush(A, (-((-heapq.heappop(A))//2)))
print(-sum(A))
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))

    count = 0
    for i in range(n):
        b = True
        for j in range(i+1):
            b &= P[i] <= P[j]
        if b:
            count += 1

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))

    count = 0
    small = P[0]
    for i in range(n):
        if P[i] <= small:
            count += 1
        small = min(small, P[i])

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

n = int(input())
s = []
s_cnt = [0] * n
for i in range(n):
    temp = input()
    if not temp in s:
        s.append(temp)
    s_cnt[s.index(temp)] += 1
maxi = max(s_cnt)
ans_lst = []
for i in range(len(s)):
    if s_cnt[i] == maxi:
        ans_lst.append(s[i])
ans_lst.sort()
ans = ""
for i in range(len(ans_lst)):
    ans += ans_lst[i]
    if i != len(ans_lst) - 1:
        ans += "\n"
print(ans)

### FIXED CODE ###

n = int(input())
s_dict = dict()
for i in range(n):
    a = input()
    if a in s_dict:
        s_dict[a] += 1
    else:
        s_dict.update({a : 1})
maxi = max(s_dict.values())
ans_lst = []
for key, value in s_dict.items():
    if value == maxi:
        ans_lst.append(key)
ans_lst.sort()
for i in ans_lst:
    print(i)
### BUGGY CODE ###

N = int(input())
mylist = []
for i in range (N):
  A = int(input())
  mylist.append(int(A))
for j in range (N):
  data = mylist[j]
  my = sorted(mylist,reverse=True)
  if data == my[0]:
    print(my[1])
  else:
    print(my[0])

### FIXED CODE ###

N = int(input())
mylist = []
first=0
second=0
for i in range (N):
  A = int(input())
  if first < A:
    first = A
  elif second < A:
    second = A
  mylist.append(A)
for i in range (N):
  if mylist[i] == first:
    print(second)
  else :
    print(first)
### BUGGY CODE ###

n = int(input())
V = input().split()

d0, d1 = {}, {}
for i in range(n//2):
    v = V[2*i]
    if v in d0.keys():
        d0[v] += 1
    else:
        d0[v] = 1

    v = V[2*i+1]
    if v in d1.keys():
        d1[v] += 1
    else:
        d1[v] = 1
s0 = sorted(d0.items(), key=lambda x: -x[1])
k0_0, v0_0 = s0[0]
s1 = sorted(d1.items(), key=lambda x: -x[1])
k1_0, v1_0 = s1[0]

if k0_0 != k1_0:
    a0 = sum(d0.values()) - v0_0
    a1 = sum(d1.values()) - v1_0
    print(a0 + a1)
else:

    k0_1, v0_1 = s0[1] if len(s0)>1 else [0,0]
    k1_1, v1_1 = s1[1] if len(s1)>1 else [0,0]
    if v0_0 <= v1_0:
        a0 = sum(d0.values()) - v0_1
        a1 = sum(d1.values()) - v1_0
    else:
        a0 = sum(d0.values()) - v0_0
        a1 = sum(d1.values()) - v1_1
    print(a0 + a1)


### FIXED CODE ###

n = int(input())
V = input().split()

d0, d1 = {}, {}
for i in range(n//2):
    v = V[2*i]
    if v in d0:
        d0[v] += 1
    else:
        d0[v] = 1

    v = V[2*i+1]
    if v in d1:
        d1[v] += 1
    else:
        d1[v] = 1

s0 = sorted(d0.items(), key=lambda x: -x[1])
k0_0, v0_0 = s0[0]
s1 = sorted(d1.items(), key=lambda x: -x[1])
k1_0, v1_0 = s1[0]

if k0_0 != k1_0:
    print(n - v0_0 - v1_0)
else:
    k0_1, v0_1 = s0[1] if len(s0)>1 else ('0',0)
    k1_1, v1_1 = s1[1] if len(s1)>1 else ('0',0)
    if v0_0+v1_1 <= v0_1+v1_0:
        print(n - v1_0 - v0_1)
    else:
        print(n - v0_0 - v1_1)
### BUGGY CODE ###

A, B, K = map(int,input().split())
li = [i for i in range(A,B + 1)]
ans = sorted(list(set(li[:K] + sorted(li,reverse = True)[:K])))

for i in ans:
  print(i)

### FIXED CODE ###

A, B, K = map(int,input().split())

ans = []
for i in range(K):
  if A + i <= B:
    ans.append(A + i)
  if B - i >= A:
    ans.append(B - i)

for i in sorted(set(ans)):
  print(i)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(list)
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].append((to, c, 0))
    edges[(to, c)].append((fr, c, 0))

    edges[(fr, c)].append((fr, -1, 0))
    edges[(to, c)].append((to, -1, 0))

    edges[(fr, -1)].append((fr, c, 1))
    edges[(to, -1)].append((to, c, 1))

minDist = defaultdict(lambda: INF)
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for (v, _), d in minDist.items():
    if v == N and ans > d:
        ans = d
print(ans if ans < INF else -1)


### FIXED CODE ###

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

for _ in range(2):
    que = [(minDist[i], 0, i) for i in range(N)]
    heapify(que)
    while que:
        dist, f, now = heappop(que)

        for to, c in edges[now]:
            d = dist
            if not c in minDistList[now]:
                d += 1
            if minDist[to] > d:
                minDist[to] = d
                minDistList[to] = set()
                heappush(que, (d, f + 1, to))
            if minDist[to] == d:
                minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    l = []
    xl = []
    yl = []
    for _ in range(N):
        x, y = map(int, input().split())
        l.append((x, y))
        xl.append(x)
        yl.append(y)
    xl.sort()
    yl.sort()
    xd = {}
    dx = {}
    t = 0
    p = xl[0]
    for i in xl:
        if i != p:
            t += 1
        xd[i] = t
        dx[t] = i
        p = i
    yd = {}
    dy = {}
    t = 0
    p = yl[0]
    for i in yl:
        if i != p:
            t += 1
        yd[i] = t
        dy[t] = i
        p = i
    l2 = []
    for x, y in l:
        l2.append((xd[x], yd[y]))
    m = 10**100
    for si in range(len(xd)-1):
        for ei in range(si+1, len(xd)):
            for sj in range(len(yd)-1):
                for ej in range(sj+1, len(yd)):
                    t = 0
                    for x, y in l2:
                        if si <= x <= ei and sj <= y <= ej:
                            t += 1
                    if t >= K:
                        m = min(m, (dx[ei]-dx[si]) * (dy[ej]-dy[sj]))
    return m
print(main())
                


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    l = []
    xl = []
    yl = []
    for _ in range(N):
        x, y = map(int, input().split())
        l.append((x, y))
        xl.append(x)
        yl.append(y)
    xl.sort()
    yl.sort()
    xd = {}
    dx = {}
    t = 0
    p = xl[0]
    for i in xl:
        if i != p:
            t += 1
        xd[i] = t
        dx[t] = i
        p = i
    yd = {}
    dy = {}
    t = 0
    p = yl[0]
    for i in yl:
        if i != p:
            t += 1
        yd[i] = t
        dy[t] = i
        p = i
    l2 = []
    for x, y in l:
        l2.append((xd[x], yd[y]))
    m = 10**100
    for si in range(len(xd)-1):
        for ei in range(si+1, len(xd)):
            for sj in range(len(yd)-1):
                for ej in range(sj+1, len(yd)):
                    t = 0
                    for x, y in l2:
                        if si <= x <= ei and sj <= y <= ej:
                            t += 1
                    if t >= K:
                        m = min(m, (dx[ei]-dx[si]) * (dy[ej]-dy[sj]))
    return m
print(main())
### BUGGY CODE ###

H,W=map(int,input().split())
INF=10**4
nums=[[INF for i in range(W)] for j in range(H)]
starts=[]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      starts.append([i,j,0])

while starts:
  node=starts.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  if nums[y][x]<=p:
    continue
  for i in range(x,W):
    if nums[y][i]>i-x+p:
      nums[y][i]=i-x+p
    else:
      break
  for i in range(x-1,-1,-1):
    if nums[y][i]>x-i+p:
      nums[y][i]=x-i+p
    else:
      break
  if y-1>=0:
    starts.append([y-1,x,p+1])
  if y+1<H:
    starts.append([y+1,x,p+1])

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

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

N, Q = map(int,input().split())
s = list(input())

count=[]
for i in range(len(s)):
	count.append(0)

for i in range(len(s)-1):
	if s[i] == "A" and s[i+1] == "C":
		count[i]=count[i]+1
		#count[i+1]=count[i+1]+1
#print(count)

result=0
for i in range(Q):
	l, r = map(int,input().split())
	for i in count[l-1:r-1]:
		#if count[i]==1 and count[i+1]==0:
 			result = result+i
	print(result)
	result=0

### FIXED CODE ###

N, Q = map(int,input().split())
s = list(input())

count=[]
num=0
count.append(num)
for i in range(len(s)-1):
	if s[i] == "A" and s[i+1] == "C":
		num=num+1
		count.append(num)
	else:
		count.append(num)

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