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

N = int(input())
S = [input() for _ in range(N)]
cnt = []
for i in S:
    cnt.append(S.count(i))
M = max(cnt)

ans = []
for k in range(N):
    if cnt[k] == M:
        ans.append(S[k])
print(*sorted(set(ans)), sep = "\n")

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for _ in range(N)]

counter = Counter(S)
max_cnt = max(counter.values())
ans = [name for name, cnt in counter.items() if cnt == max_cnt]
ans.sort()
 
print(*ans, sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

def merge_sort(a, left, right):
    #global cnt
    #cnt += 1
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)

def merge(a, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    
    l = [None for _ in range(n1+1)]
    r = [None for _ in range(n2+1)]
    for i in range(n1):
        l[i] = a[left + i]
    for i in range(n2):
        r[i] = a[mid + i]
    
    l[n1] = float('Inf')
    r[n2] = float('Inf')
    i = 0
    j = 0
    
    for k in range(left, right):
        cnt += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

def merge_sort(a, left, right):
    #global cnt
    #cnt += 1
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)

def merge(a, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    
    l = a[left:mid].copy()
    r = a[mid:right].copy()
    
    l.append(10**10)
    r.append(10**10)
    i = 0
    j = 0
    
    for k in range(left, right):
        cnt += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	skill = []
	for _ in range(Q):
		t, d = input().split(" ")
		skill.append((t, d))
	
	gorlm_num = [1] * len(S)
	
	for i, val in enumerate(skill):
		t, d = val
		#print(gorlm_num)
		for j, vol in enumerate(S):
			if t == vol:
				tt = gorlm_num[j]
				gorlm_num[j] = 0
				if d == "R" and j != len(S)-1:
					gorlm_num[j+1] += tt
				if d == "L" and j != 0:
					gorlm_num[j-1] += tt
						
	ans = 0
	for i in gorlm_num:
		ans = ans + i
		
	print(ans)
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
	
def main():
	N, Q = map(int, input().split())
	S = "_" + input() + "_"
	
	TD = []
	for _ in range(Q):
		tmp = input().split(" ")
		t = tmp[0]
		d = tmp[1]
		TD.append((t, d))
		
	TD.reverse()
	gake_L = 0
	gake_R = N - 1 + 2
	
	for i, val in enumerate(TD):
		t, d = val
		
		if d == "R":
			if t == S[gake_R-1]:
				gake_R -= 1
			if t == S[gake_L]:
				gake_L -= 1
		
		if d == "L":
			if t == S[gake_R]:
				gake_R += 1
			if t == S[gake_L+1]:
				gake_L += 1
	
	print(max(0, gake_R-gake_L-1))
	
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def maxspeed(left,right,t,vmax):
    if t<=left:
        return vmax+(left-t)
    elif left< t < right:
        return vmax
    else:
        return vmax+t-right
funcs=[]
funcs.append((0,0,0))
left=0
for i in range(N):
    funcs.append((left,left+T[i],V[i]))
    left+=T[i]
funcs.append((left,left,0))
dist=0.0
speed=0
t=0
while t<=left:
    speed2=min(maxspeed(pm[0],pm[1],t,pm[2]) for pm in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
    t+=0.5
print(dist)

### FIXED CODE ###

N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
vtmax=[0]
tmp=0
Tsum=sum(T)
for t,v in zip(T,V):
    vtmax[-1]=min(tmp,v) #境界は小さい方が制約
    vtmax+=[v]*(t*2)
    tmp=v
vtmax[-1]=0

for i in range(1,2*Tsum):
    vtmax[i]=min(vtmax[i],vtmax[i-1]+0.5)
for i in range(2*Tsum-1,0,-1):
    vtmax[i]=min(vtmax[i],vtmax[i+1]+0.5)
area=0
for i,vt in enumerate(vtmax):
    if i==0:continue
    area+=0.5*(vt+vtmax[i-1])/2
print(area)
### BUGGY CODE ###

#coding:utf-8
import math
from functools import reduce

def gcd(*num):
    return reduce(math.gcd, num)


if __name__ == "__main__":

    k = int(input())
    ans = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += gcd(a, b, c)

    print(ans)


### FIXED CODE ###

#coding:utf-8
from math import gcd

def main():
    k = int(input())
    ans = 0

    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += gcd(gcd(a, b), c)

    print(ans)

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

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

### FIXED CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]
_l = l.copy()
_l.sort(reverse=True)
lmax = _l[0]
lsec = _l[1]

for i in range(n):
    if l[i] == lmax:
        print(lsec)
    else:
        print(lmax)
### BUGGY CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

for i in range(len(A)):
    #Aを1つ決めた時、BがA以下の値
    A_miman = bisect.bisect_right(B,A[i])
    for j in range(A_miman,N):
        #Bを1つ決めた時、CがBより大きい値
        ans += N - bisect.bisect_right(C, B[j])
        


print(ans)

### FIXED CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()


#A<B<Cの組み合わせの数が答え
for i in range(N):
    #Bを1つ決めた時、AがB未満の場合の総数
    B_miman = bisect.bisect_left(A,B[i])
    #Bを1つ決めた時、CがB以上の場合の総数
    B_ijou = N - bisect.bisect_right(C, B[i])

    ans+= B_miman*B_ijou

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

n,m = map(int,input().split())
As = list(map(int,input().split()))
for i in range(m):
  a = max(As)
  As[As.index(a)] = int(a/2)
print(sum(As))
  




### FIXED CODE ###

import heapq

n,m = map(int,input().split())
As = [-i for i in list(map(int,input().split()))]
heapq.heapify(As)
for i in range(m):
  a = -heapq.heappop(As)
  heapq.heappush(As,-int(a/2))
print(-sum(As))
### BUGGY CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
mod=10**9+7
ans=0
MOD=10**9+7
def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret
for i in range(n-k+1):
    ans-=a[i]*comb(n-i-1,k-1)
    ans%=mod
a=a[::-1]
for i in range(n-k+1):
    ans+=a[i]*comb(n-i-1,k-1)
    ans%=mod

print(ans%mod)

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
mod=10**9+7
ans=0
MOD=10**9+7

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))
 
 
# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD
for i in range(n-k+1):
    ans-=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod
a=a[::-1]
for i in range(n-k+1):
    ans+=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod

print(ans%mod)
### BUGGY CODE ###

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

while k != 0:
    if a > b:
        b *= 2
        k -= 1
    if b > c:
        c *= 2
        k -= 1
if a < b and b < c:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a, b, c = map(int, input().split())
k = int(input())
ans = 'Yes'

while a >= b:
    b *= 2
    k -= 1

while b >= c:
    c *= 2
    k -= 1

if k < 0:
    ans = 'No'

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

def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j]%mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j]%mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

### FIXED CODE ###

def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j] %= mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j] %= mod
  ans = sum(dp[0])%mod
  return ans
print(solve())
### BUGGY CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

ans = 0
for i in range(1,n+1):
    ans += msum[:i].count(msum[i])
print(ans)

### FIXED CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

ans = 0
for i in range(MOD):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

import heapq

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

B = []
C = []
BC = []

A.sort()

for i in range(M):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)
    BC.append([b, c])


sorted(BC, key=lambda x: x[1])
BC = BC[::-1]
C = C.sort()

heapq.heapify(A)

# print(A)
# print(BC)

buff = []
counter = 0
for i in range(M):
    # if counter > N*2:
    #     break
    for j in range(BC[i][0]):
        # buff.append(BC[i][1])
        # counter += 1
        heapq.heappush(A, BC[i][1])
        heapq.heappop(A)
        if counter > N*2:
            break

# A = A + buff
# A.sort()
# A = A[::-1]
# print(A)
print(sum(A))

### FIXED CODE ###

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

B = []
C = []
BC = []

A.sort()

for i in range(M):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)
    BC.append([b, c])


BC = sorted(BC, key=lambda x: x[1])
BC = BC[::-1]
C = C.sort()

# print(A)
# print(BC)

buff = []
counter = 0
for i in range(M):
    if counter > N*2:
        break
    for j in range(BC[i][0]):
        buff.append(BC[i][1])
        counter += 1
        if counter > N*2:
            break

A = A + buff
A.sort()
A = A[::-1]
print(sum(A[:N]))
### BUGGY CODE ###

from fractions import gcd

K = int(input())

res = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp = gcd(i,j)
        for k in range(1,K+1):
            res += gcd(tmp,k)
print(res)

### FIXED CODE ###

from math import gcd

K = int(input())

res = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp = gcd(i,j)
        for k in range(1,K+1):
            res += gcd(tmp,k)
print(res)
### BUGGY CODE ###

s=input()
q=int(input())
for c in range(q):
    l=input()
    if l=="1":
        s=s[::-1]
    else:
        j=l.split()
        if j[1]=="1":
            s=j[2]+s
        else:
            s=s+j[2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
l=[]
for c in range(q):
    i=input().split()
    if i==["1"]:
        l.append([1,0,0])
    else:
        l.append([2,int(i[1]),i[2]])
d=0
for c in range(1,q+1):
    if l[-c][0]==1:
        d=d+1
    else:
        l[-c][1]+=d%2
a=""
for c in range(1,q+1):
    if l[-c][0]==2 and l[-c][1]%2==1:
        a=a+l[-c][2]
if d%2==0:
    a=a+s
else:
    a=a+s[::-1]
for c in range(q):
    if l[c][0]==2 and l[c][1]%2==0:
        a=a+l[c][2]
print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    # AB = sorted(list(zip(A,B)),key=lambda x: -x[0]/x[1])

    # dp[i][j] i番目までの技からいくつか選んで体力H以下にするときの最小MP

    dp = [[10**9]*(H+10**4+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for h in range(H+10**4+1):
            if h - A[i] >= 0:
                dp[i+1][h] = min(dp[i+1][h-A[i]]+B[i],dp[i][h])
            else:
                dp[i+1][h] = dp[i][h]
 

    answer = 10**9
    for i in range(H,H+10**4+1):
        answer = min(answer,dp[-1][i])
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    # AB = sorted(list(zip(A,B)),key=lambda x: -x[0]/x[1])

    # dp[i][j] i番目までの技からいくつか選んで体力H以下にするときの最小MP

    dp = [[10**9]*(H+10**4+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for h in range(H+10**4+1):
            if h - A[i] >= 0:
                dp[i+1][h] = min(dp[i+1][h-A[i]]+B[i],dp[i][h])
            else:
                dp[i+1][h] = dp[i][h]
 

    answer = 10**9
    for i in range(H,H+10**4+1):
        answer = min(answer,dp[-1][i])
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

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

import sys
input = sys.stdin.readline

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

l = [str(a.index(i)+1) for i in b]

l=" ".join(l)
print(l)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N
 
 
for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)
 
  
print(" ".join(List))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
INF = 10**10
dp = [INF] * (H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(0, j-A[i])]+B[i])
print(dp[H])


### FIXED CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
INF = 10**10
dp = [INF] * (H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(0, j-A[i])]+B[i])
print(dp[H])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())
A = []
B_place = []
for i in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=="#":
      B_place.append([i,w])
  A.append(a)

all_map = [[10**10 for i in range(W)] for i in range(H)]
def f(h,w,cou):
  global H,W,all_map
  if h<0 or H<=h or w<0 or W<=w:
    return
  if cou>=all_map[h][w]:
    return
  else:
    all_map[h][w]=cou
  f(h-1,w,cou+1)
  f(h+1,w,cou+1)
  f(h,w-1,cou+1)
  f(h,w+1,cou+1)

for B in B_place:
  f(B[0],B[1],0)

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

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
  query = list(input().split())
  if(query[0] == '1'):
    S = S[::-1]
  else:
    if(query[1] == '1'):
      S = query[2] + S
    else:
      S = S + query[2]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
  x = list(input().split())
  if(int(x[0]) == 1):
    cnt += 1
  else:
    if((cnt+int(x[1])) % 2 == 1):
      S.appendleft(x[2])
    else:
      S.append(x[2])

S = list(S)
if(cnt % 2 == 1):
  S = S[::-1]
print("".join(S))
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**12
def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if not(i in used):
                cost=d[a,i] if a<=i else d[i,a]
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]


N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])]

d=np.array([[INF for j in range(N)] for i in range(N)])
for i in range(N):
    d[i,i]=0
l=np.array([i+1 for i in range(N)])
l[-1]=N
for m in range(M):
    L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
    for i in range(L,R+1):
        if l[i]<N:
            d[i,l[i]:R+1]=C
            l[i]=R+1

ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
for i in range(Q):
  l,r = map(int,input().split())
  tmp = S[l-1:r]
  tmp = tmp.replace('AC','z')
  print(tmp.count('z'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

n = int(input())

s = []
cnt = [0] * n
_max = 0
for i in range(n):
  tmp = input()
  if tmp not in s:
    s.append(tmp)
  else:
    cnt[s.index(tmp)] += 1
    if _max < cnt[s.index(tmp)]:
      _max = cnt[s.index(tmp)]
    
results = []
for i in range(len(cnt)):
  if cnt[i] == _max:
    results.append(s[i])

results.sort()
for result in results:
  print(result)

### FIXED CODE ###

n = int(input())

dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

_max = 0
for v in dic.values():
  if _max < v:
    _max = v
dic2 = sorted(dic.items())

for (k,v) in dic2:
  if v == _max:
    print(k)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
x=[]
y=[]
for i in lst:
  if i[0]==1:
    x+=[i[1]]
for i in lst:
  if i[1]==n:
    y+=[i[0]]
ans='IMPOSSIBLE'
for i in x:
  if i in y:
    ans='POSSIBLE'
    break
print(ans)


### FIXED CODE ###

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

x=[]
y=[]

for i in lst:
  if i[0]==1:
    x+=[i[1]]
    
for i in lst:
  if i[1]==n:
    y+=[i[0]]
    
ans='POSSIBLE'

if len(list(set(x)))+len(list(set(y)))==len(list(set(x+y))):
  ans='IMPOSSIBLE'
    
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
N = int(input())
S = input().rstrip()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = [0]*n
for i in range(n):
    b[i] = a[i]-i
for i in range(n):
    c[i] = a[i]+i
cb = Counter(b)
cc = Counter(c)
mb = cb.most_common()
mc = cc.most_common()
mb.sort(reverse = True)
mc.sort()
lb =len(mb)
lc =len(mc)
ans = 0
for i in range(lb):
    for j in range(lc):
        if mb[i][0]==mc[j][0]*(-1):
            ans += mb[i][1]*mc[j][1]
            break
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = [0]*n
for i in range(n):
    b[i] = a[i]-i
for i in range(n):
    c[i] = a[i]+i
cb = Counter(b)
cc = Counter(c)
k=cb.keys()
ans = 0
for i in k:
    ans += cb[i]*cc[i*(-1)]
print(ans)
### BUGGY CODE ###

H,N=map(int,input().split())
dp = [10**10]*(H+1)
dp[0]=0
for _ in range(N):
    A,B=map(int,input().split())
    for idx in range(H):
        nidx = min(idx+A,H)
        dp[nidx]=min(dp[nidx],dp[idx]+B)
print(dp[-1])


### FIXED CODE ###

H,N=map(int,input().split())
dp = [10**10]*(H+1)
dp[0]=0
for _ in range(N):
    A,B=map(int,input().split())
    for idx in range(H):
        nidx = min(idx+A,H)
        dp[nidx]=min(dp[nidx],dp[idx]+B)
print(dp[-1])
### BUGGY CODE ###

x = int(input())
a, b = 0,0
done = False
for i in range(0,x+1):
    for l in range(0, -i-1, -1):
        if((i**5)-(l**5)==x):
            a = i
            b = l
            done  = True
            break
    if(done):
        break
print(a,b)

### FIXED CODE ###

x = int(input())
a, b = 0,0
done = False
for i in range(-2000, 2000):
    for l in range(2000,-2000, -1):
        if((i**5)-(l**5)==x):
            a = i
            b = l
            print(a,b)
            done  = True
            break
    if(done):
        break