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

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

r=[[] for _ in range(n)]
d=[]
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        f+=1
        o=d[0]
        del d[0]
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())

r=[[] for _ in range(n)]
d=deque()
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        o=d.popleft()
        f+=1
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")
### BUGGY CODE ###

import math
S=int(input())
x_1=10**9
y_1=10**9
x_2=10**9
y_3=10**9

i=int(math.sqrt(S))
while 1:
    if S%i==0:
        print(x_1,y_1,x_2,(10**9)-i,10**9-(S//i),y_3)
        break
    else:
        i+=1

### FIXED CODE ###

S=int(input())
x_1=0
y_1=0
x_2=10**9
y_2=1

if S%10**9==0:
    x_3=0
    y_3=S//10**9
else:
    x_3=10**9-S%10**9
    y_3=1+S//10**9

print(x_1,y_1,x_2,y_2,x_3,y_3)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
cnt = 0
for i in range(len(s)-3):
    for j in range(i+3,len(s)):
        if int(s[i:j+1])%2019 == 0:
            cnt+=1
print(cnt)


### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

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

def listup(s):
    ans = [0 for i in range(10)]
    for i in range(len(s)):
        ans[int(s[i])] += 1
    return ans

ans = [0 for i in range(1000)]
l = '0123456789'
for i in range(1,N):
    b = S[i]
    for a in l:
        A = listup(S[:i])
        if A[int(a)] > 0:
            for c in l:
                C = listup(S[i+1:])
                if C[int(c)] > 0:
                    s = a + b + c
                    ans[int(s)] = 1
print(sum(ans))

### FIXED CODE ###

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

def judge(A,B,C):
    s = S
    a = s.find(A)
    if a < 0:
        return False

    s = s[a+1:]
    b = s.find(B)
    if b < 0:
        return False

    s = s[b+1:]
    c = s.find(C)
    if c < 0:
        return False
    return True

l = '0123456789'
print(sum([int(bool(judge(a,b,c))) for a in l for b in l for c in l]))
### BUGGY CODE ###

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

all_length = k*2
point = []
for i in range(n):
    a_left  = k-a[i]
    a_right = k+a[i]
    point.append(a_left)
    point.append(a_right)
point = list(set(point))
point.sort()

num = len(point)
distance = []
for i in range(num-2):
    dis = 0
    for j in range(n-1):
        dis += point[i+j+1] - point[i+j]
    distance.append(dis)
mindis = min(distance)
print(mindis)

### FIXED CODE ###

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

A.append(A[0]+k)
l = 0
for i in range(n):
    l = max(l, A[i+1]-A[i])
print(k-l)
### BUGGY CODE ###

n,q = map(int,input().split())
str = input()
q = int(q)
for i in range(q):
  s,e = map(int,input().split())
  tmp = str[s-1:e]
  ans = tmp.count('AC')
  print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
str = input()
q = int(q)
dic = {}

for j in range(len(str)):
  if (j > 0):
    if (str[j-1] == 'A' and str[j] == 'C'):
      dic[j] = dic[j-1] + 1
    else:
      dic[j] = dic[j-1]
  else:
    dic[j] = 0

for i in range(q):
  s,e = map(int,input().split())
  ans = dic[e-1] - dic[s-1]
  print(ans)
### BUGGY CODE ###

# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

# for j in range(1, 10 ** 5 + 10):
#     for i in range(1, C + 1):
#         lst[i][j] += lst[i - 1][j]

# print (max(lst[-1]))

import numpy as np
lst = np.array(lst)
lst = np.cumsum(lst, axis = 0)

print (np.max(lst[-1]))

### FIXED CODE ###

# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

for j in range(1, 10 ** 5 + 10):
    for i in range(1, C + 1):
        lst[i][j] += lst[i - 1][j]

print (max(lst[-1]))
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num%3] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num%3] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)
### BUGGY CODE ###


def count(char):
  l, r = map(int, input().split())
  char1 = char[l-1:r]
  char1 = char1.split('AC')
  print(len(char1)-1)

N, Q = map(int, input().split())
char = input()

for i in range(Q):
  count(char)

### FIXED CODE ###

N, Q = map(int, input().split())
char = input()
num_list = [0]
for i in range(1,N):
  if char[i-1:i+1] == 'AC':
    num_list.append(num_list[-1]+1)
  else:
    num_list.append(num_list[-1])

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

n=int(input())
a=[]
for i in range(n):
    m=int(input())
    if m in a:
        a.remove(m)
    else:
        a.append(m)
print(len(a))

### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=[]
d=defaultdict(int)
D=[]
for i in range(n):
    a.append(input())

for key in a:
    d[key]+=1

for k,v in d.items():
    if v%2==1:
        D.append(k)
print(len(D))
### BUGGY CODE ###

from itertools import combinations
N = int(input())
name = []

for i in range(N):
    a = input()
    if a[0] == 'M' or a[0] == 'A' or a[0] == 'R' or a[0] == 'C' or a[0] == 'H':
        name += [a[0]]
count = 0

if len(name) < 3:
    print(0)
else:
    for i in combinations(name, 3):
        if i[0] != i[1] and i[1] != i[2] and i[2] != i[0]:
            count += 1
    print(count)



### FIXED CODE ###

from itertools import combinations
N = int(input())
name = [0]*5
ans = 0
for i in range(N):
    a = input()
    if a[0] == 'M': name[0] += 1
    elif a[0] == 'A': name[1] += 1
    elif a[0] == 'R': name[2] += 1
    elif a[0] == 'C': name[3] += 1
    elif a[0] == 'H': name[4] += 1
if sum(name) < 3:
    print(0)
else:
    for i in combinations(name, 3):
        ans += i[0]*i[1]*i[2]
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [a-1 for a in A]

L = 65
D = [[0]*n for _ in range(L+1)]

for i, a in enumerate(A):
    D[0][i] = a

for i in range(L):
    for j in range(n):
        D[i+1][j] = D[i][D[i][j]]

ans = 0
for i in range(L):
    if k & (1 << i):
        ans = D[i][ans]
print(ans+1)


### FIXED CODE ###

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

A = [a-1 for a in A]

g = [[] for i in range(n)]
for i, a in enumerate(A):
    g[i].append(a)

s = []
visit = [-1]*n
s.append(0)
visit[0] = 0
while s:
    v = s.pop()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = visit[v]+1
            s.append(u)
        else:
            temp = visit[u]
#print(temp)
#print(visit)
d = max(visit)-temp+1
#print(d)
if k < temp:
    for i in range(n):
        if visit[i] == k:
            print(i+1)
            exit()
else:
    q, r = divmod(k-temp, d)
    for i in range(n):
        if visit[i]-temp == r:
            print(i+1)
            exit()
### BUGGY CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    sl = g[input()]
    if sl == 0:
        return
    print(N-1)
    sr = g[input()]
    if sr == 0:
        return
    l = 0
    r = N-1
    while True:

        m = (l+r)//2
        print(m)
        a = g[input()]
        if a == 0:
            return
        
        if (m-1-l) % 2 == 1:
            if sl == sr:
                r = m-1
                print(r)
                sr = g[input()]
                if sr == 0:
                    return
            else:
                l = m+1
                print(l)
                sl = g[input()]
                if sl == 0:
                    return
        else:
            if sl != sr:
                r = m-1
                print(r)
                sr = g[input()]
                if sr == 0:
                    return
            else:
                l = m+1
                print(l)
                sl = g[input()]
                if sl == 0:
                    return


        




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
#    print(p)
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_right(c, a[i]-1)
        c[p-1]=a[i]
#        c.sort()

print(len(c))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [-999]*n

for i in range(0,n):
#    if c[0] >= a[i]:
#        c.insert(0,a[i])
#    else:
    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]
#        print(c)
#        print(p)

print(len(c) - bisect.bisect_left(c, -1))
### BUGGY CODE ###

import fractions
import copy

n1 = int(input())
nl1 = [int(i1) for i1 in input().split()]

r1 = 0

for  i2 in range(n1):
    nl2 = copy.copy(nl1)
    if i2 == 0:
        nl2[i2] = nl1[1]
    else:
        nl2[i2] = nl1[i2 - 1]
    r2 = nl2[0]
    for i3 in range(n1 - 1):
        r2 = fractions.gcd(r2 ,nl2[i3 + 1])
        if r2 <= r1:
            break

    r1 = max(r1,r2)

print(str(r1))

### FIXED CODE ###

import fractions
import sys

n1 = int(input())
nl1 = [int(i1) for i1 in input().split()]

if n1 == 2:
    print(max(nl1))
    sys.exit()

r1 = 0

nl1.sort()

if n1 >= 3:
    n2 = fractions.gcd(nl1[0], nl1[1]) 
    n2 = max(n2, fractions.gcd(nl1[1], nl1[2]))
    n2 = max(n2, fractions.gcd(nl1[0], nl1[2]))

c1 = 0
for i2 in range(n1):
    if nl1[i2] % n2 != 0:
        c1 += 1
    if c1 >= 2:
        break
    if i2 == (n1 - 1):
        r1 = n2

i3 = n2

while r1 == 0:
    c1 = 0
    for i4 in range(n1):
        if nl1[i4] % i3 != 0:
            c1 += 1
        if c1 >= 2:
            break
        if i4 == (n1 - 1):
            r1 = i3
    i3 -= 1

print(str(r1))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):                
        if(S[i][j]=="."):
            if(j == W-1):
                right[i][j]=1
            else:
                right[i][j]=right[i][j+1]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W):     
        if(S[i][j]=="."):
            if(i == H-1):
                down[i][j]=1
            else:
                down[i][j]=down[i+1][j]+1
ans = 0
X = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j] = left[i][j]+right[i][j]+up[i][j]+down[i][j]-3
    ans = max(ans,max(X[i]))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):                
        if(S[i][j]=="."):
            if(j == W-1):
                right[i][j]=1
            else:
                right[i][j]=right[i][j+1]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W):     
        if(S[i][j]=="."):
            if(i == H-1):
                down[i][j]=1
            else:
                down[i][j]=down[i+1][j]+1
ans = 0
X = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j] = left[i][j]+right[i][j]+up[i][j]+down[i][j]-3
    ans = max(ans,max(X[i]))
print(ans)
### BUGGY CODE ###

from collections import Counter

N, M = map(int, raw_input().split())
Q = [map(int, raw_input().split()) for _ in range(M)]

cnt = Counter()
for q in Q:
    cnt += Counter(q)

for k in cnt:
    if cnt[k] % 2 != 0:
        print "NO"
        exit()
print "YES"


### FIXED CODE ###

N, M = map(int, raw_input().split())
Q = [map(int, raw_input().split()) for _ in range(M)]

cnt = [0 for _ in range(N)]
for a, b in Q:
    cnt[a-1] += 1
    cnt[b-1] += 1

for k in range(N):
    if cnt[k] % 2 != 0:
        print "NO"
        exit()
print "YES"
### BUGGY CODE ###

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

from bisect import bisect_left

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = [liA[0]]
  for a in liA[1:]:
    if a <= colors[0]:
      colors = [a] + colors
    else:
      i = bisect_left(colors, a)
      colors[i-1] = a

  print(len(colors))
  pass

if __name__=='__main__':
  main()


### FIXED CODE ###

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

from bisect import bisect_left
from collections import deque

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = deque([liA[0]])
  for a in liA[1:]:
    if a <= colors[0]:
      colors.appendleft(a)
    else:
      i = bisect_left(colors, a)
      colors[i-1] = a

  print(len(colors))
  pass

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

from itertools import combinations

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

ans = 0

for i in range(1,N-1):
    for j in range(i+1,N):
        for k in range(j+1,N+1):
            if (2*j != k+i)&(len(set([S[i-1],S[j-1],S[k-1]]))==3):
                ans +=1

print(ans)


### FIXED CODE ###

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

ans = S.count('R')*S.count('G')*S.count('B')

for i in range(N):
    for j in range(N):
        if i+2*j < N:
            if len(set([S[i],S[i+j],S[i+2*j]]))==3:
                ans -=1
print(ans)
### BUGGY CODE ###

n,k,*h=map(int,open(0).read().split());
dp=[0]*n;
for i in range(1,n):
    dp[i]=min(dp[j+max(i-k,0)]+abs(a-h[i])for j,a in enumerate(h[max(i-k,0):i]));
print(dp[-1])

### FIXED CODE ###

n,k,*h=map(int,open(0).read().split());
dp=[0]*n;
for i in range(1,n):
    dp[i]=min(dp[j+max(i-k,0)]+abs(a-h[i])for j,a in enumerate(h[max(i-k,0):i]));
print(dp[-1])
### BUGGY CODE ###

import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
import collections
N = int(input()) # 1行, 単数
A = list(map(int, input().split())) # 1行, 配列
Q = int(input()) # 1行, 単数
counter = collections.Counter(A)

while True:
  try:
    ans = 0
    B,C = list(map(int, input().split())) # 1行, 配列
    counter[C] = counter[C] + counter[B]
    counter[B] = 0
    for i in counter.keys():
      ans = ans + i * counter[i]
  # A = [C if i == B else i for i in A]
    print(ans)
  except:
    break;

### FIXED CODE ###

import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
import collections
N = int(input()) # 1行, 単数
A = list(map(int, input().split())) # 1行, 配列
Q = int(input()) # 1行, 単数
counter = collections.Counter(A)
ans = 0
for i in counter.keys():
  ans = ans + i * counter[i]

while True:
  try:

    B,C = list(map(int, input().split())) # 1行, 配列
    old = C * counter[C] + counter[B] * B
    counter[C] = counter[C] + counter[B]
    del counter[B]
    new = C * counter[C]
    ans = ans + (new - old)
    print(ans)
  except:
    break;
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r])
    
import re
    
for i in range(len(lr)):
    #print(S[lr[i][0]-1 : lr[i][1]])
    #print(re.findall("AC", S[lr[i][0]-1 : lr[i][1]]))
    print(len(re.findall("AC", S[lr[i][0]-1 : lr[i][1]])))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

import re

s = [i.span()[0] for i in list(re.finditer("AC", S))]
#print(s)

count = [0] * (N+1)
c = 0
for i in range(N):
    try:
        if s[0]+1 == i:
            s.pop(0)
            c += 1
    except:
        pass
            
    count[i] = c
    
#print(count)

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

print(" ".join(map(str, ans)))
### BUGGY CODE ###

from collections import Counter
N, M = map(int, input().split())
print("YES" if all(x % 2 == 0 for x in Counter(sum([list(map(int, input().split())) for _ in range(M)], [])).values()) else "NO")


### FIXED CODE ###

from collections import Counter
N, M = map(int, input().split())
cnt = Counter()
for _ in range(M):
    a, b = map(int, input().split())
    cnt[a] += 1
    cnt[b] += 1
print("YES" if all(x % 2 == 0 for x in cnt.values()) else "NO")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

a,b,k = map(int,input().split())

for i in range(k):
    if a>0:
        a-=1
    elif b>0:
        b-=1
    else:
        pass

print(str(a)+" "+str(b))

### FIXED CODE ###

a,b,k = map(int,input().split())

if k<=a:
    a -= k
elif k<a+b:
    b -= k-a
    a = 0
elif k>=a+b:
    a = 0
    b = 0

print(str(a)+" "+str(b))
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = [ -int(x) for x in input().split() ]
bc = []
heapq.heapify(a)

for _ in range(m):
    b, c = map(int, input().split())
    bc += [ (b, c) ]

bc.sort(key=lambda x: -x[1])
min_a = min(a)

for b, c in bc:
    if c < min_a:
        min_a = c
        continue
    for _ in range(b):
        heapq.heappush(a, -c)

ans = 0
for i in range(n):
    t = (-heapq.heappop(a))
    ans += t
print(ans)



### FIXED CODE ###

n, m = map(int, input().split())
a = sorted([ int(x) for x in input().split() ], reverse=True)
bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc += [ (b, c) ]

bc.sort(key=lambda x: -x[1])
i, j, cnt, ans = 0, 0, 0, 0

while cnt < n:
    if j < m and a[i] < bc[j][1]:
        b, c = bc[j]
        ans += c * min(n-cnt, b)
        j += 1
        cnt += b
    else:
        ans += a[i]
        i += 1
        cnt += 1

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

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(0, n-1):
    a_i = a[0:i] + a[i+1:n]
    print(max(a_i))
print(max(a[0:n]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_sorted = sorted(a, reverse=True)
for i in range(0, n):
    if a[i]==a_sorted[0]:
        print(a_sorted[1])
    else:
        print(a_sorted[0])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, 3001):
    for g in range(0, 3001):
        if (N - r * R - g * G) // B >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, 3001):
    for g in range(0, 3001):
        if (N - r * R - g * G) // B >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1
print(ans)