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

import itertools
import math
import fractions
import functools
n = int(input())
s = []
for i in range(n):
    s.append(input())

dic = {}

for i in range(n):
    if (s[i] in dic.keys()):
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1
result = []
maximum = max(list(dic.values()))
for key in dic:
    if dic[key] == maximum:
        result.append(key)

result.sort()
for i in range(len(result)):
    print(result[i])

### FIXED CODE ###

import itertools
import math
import fractions
import functools
n = int(input())
s = []
for i in range(n):
    s.append(input())

dic = {}

for i in range(n):
    current = dic.get(s[i],0)
    dic[s[i]] = current + 1

result = []
maximum = max(list(dic.values()))
for key in dic:
    if dic[key] == maximum:
        result.append(key)

result.sort()
for i in range(len(result)):
    print(result[i])
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
count=0
flag=True

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



if N>=M:
    for i in range(M):
        x1=np.argmax(A)
        x1=A.pop(x1)


    print(sum(A))
else:
    print(0)


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())


A = list(map(int, input().split()))
A.sort()

count=0
if N>=M:
    for i in range(N-M):
        count+=A[i]
    print(count)



else:
    print(0)
### BUGGY CODE ###

N,M=map(int,input().split())
ans=1
for i in range(2,int(M/N)+1):
    if (M-((N-1)*i))%i==0:
        ans=i
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
ans=0
for i in range(1,10**5):
    if M%i==0:
        a=max(M//i,i)
        b=min(M//i,i)
        if M//a>=N and ans<a:
            ans=a
        if M//b>=N and ans<b:
            ans=b
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = [int(num) for num in input().split(" ")]
a_set = set(a_list)
total_comb = 0
ball_num_count = {}
for i in a_set:
    i_count = a_list.count(i)
    total_comb += int(i_count*(i_count-1)/2)
    ball_num_count[i] = i_count-1
for k in range(n):
    except_num = a_list[k]
    print(total_comb - ball_num_count[except_num])


### FIXED CODE ###

import collections

n = int(input())
a_list = [int(num) for num in input().split(" ")]
c_dict = collections.Counter(a_list)

total_comb = 0
for i in c_dict:
    i_count = c_dict[i]
    total_comb += int(i_count*(i_count-1)/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (c_dict[except_num]-1))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(a):
    return reduce(math.gcd, a)

a=[0,0,0]
N = int(input())

wa=0
for i in range(1, N+1):
    a[0]=i
    for j in range(1,N+1):
        a[1]=j
        for k in range(1,N+1):
            a[2]=k
            
            wa=wa+gcd(a)

print(wa)


### FIXED CODE ###

import math
from functools import reduce

def gcd(a):
    return reduce(math.gcd, a)

a=[0,0,0]
N = int(input())

wa=0
for i in range(1, N+1):
    a[0]=i
    for j in range(1,N+1):
        a[1]=j
        for k in range(1,N+1):
            a[2]=k
            
            wa=wa+gcd(a)

print(wa)
### BUGGY CODE ###

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

scores = list()
for i in range(n):
    score = list(map(int,input().split()))
    scores.append(score)

smax=None
for i in range(n):
    scores_ = copy.deepcopy(scores)
    for j in range(len(scores[i])):    
        if scores[i][j]<0:
            for k in range(n):
                scores_[k][j] = -scores[k][j]
        else:
            for k in range(n):
                scores_[k][j] = scores[k][j]
    ssum=list()
    for j in range(n):
        ssum.append(sum(scores_[j]))
    ssum.sort()
    tmp=0
    for j in range(m):
        tmp+=ssum[-1]
        ssum.pop()
    if smax==None or tmp>smax:
        smax=tmp

print(smax)

### FIXED CODE ###

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

#取得
scores = list()
for i in range(n):
    score = list(map(int,input().split()))
    scores.append(score)

smax=None
for x in range(2):
    scores_=copy.deepcopy(scores)
    
    for i in range(n):
        scores_[i][0] = pow(-1,x)*scores[i][0]
    for y in range(2):
        for i in range(n):
            scores_[i][1] = pow(-1,y)*scores[i][1]
        for z in range(2):
            for i in range(n):
                scores_[i][2] = pow(-1,z)*scores[i][2]
        
            sumlist=list()
            for i in range(n):
                sumlist.append(sum(scores_[i]))
            sumlist.sort()
            
            tmp=0
            for eat in range(m):
                tmp+=sumlist[-1]
                sumlist.pop()
            if smax==None or tmp>smax:
                smax=tmp
print(smax)
### BUGGY CODE ###

n = int(input())

def divisor(n): 
    i = 1
    num = 0
    while i * i <= n:
        if n%i == 0:
            num+=2
            if i==n//i:
                num-=1
        i += 1
    return num

ans=0
for c in range(1, n):
    ab = n-c
    ans+=divisor(ab)

print(ans)

### FIXED CODE ###

n = int(input())
ans=0
for a in range(1, n):
    b=(n-1)//a
    ans+=b
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
num = 0
for i in b:
    if i < a.count(i):
        num += (a.count(i)-i)
    elif a.count(i) < i:
        num += a.count(i)
print(num)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a = Counter(a).most_common()
num = 0
for i,j in a:
    if i < j:
        num += (j-i)
    elif j < i:
        num += j
print(num)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split(' ')))
MOD = 10**9+7

SUM = 0
for i, a in enumerate(A):
    for b in A[i+1:]:
        SUM += a ^ b
        SUM %= MOD

print(SUM)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split(' ')))
A = np.array(A)

ans = 0
for i in range(60):
    c_1 = int((A&1).sum())
    ans += c_1*(N-c_1)*(2**i)
    A >>= 1

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

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
for i in range(2,10**6+1):
    B[i] = pow(A[i],p-2)

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    cnt = (A[k]*B[n]*B[k-n])%p
print(cnt)

### FIXED CODE ###

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
B[10**6] = pow(A[10**6],p-2)
for i in range(10**6-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    if X<k:
        cnt = 0
    else:
        cnt = (((A[k]*B[n])%p)*B[k-n])%p
print(cnt)
### BUGGY CODE ###

import math
n,m = map(int,input().split())
ans = 1
for i in range(2,m//2+1):
    if m % i == 0:
        if m // i >= n:
            ans = i
    if m // i < n:
        break
if m % m == 0:
    if m // m >= n:
        ans = m
print(ans)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

divisor_ls = make_divisors(m)

ans = 1
for divisor in divisor_ls:
    if m // divisor < n:
        break
    else:
        ans = divisor

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

import heapq

n, m = map(int,input().split())
a = list(map(int,input().split()))
heapq.heapify(a)
for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        heapq.heappush(a,c)
        if min(a) > c:
            break
print(sum(heapq.nlargest(n, a)))

### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
a = deque(sorted(list(map(int,input().split()))))
bc = [list(map(int,input().split()))[::-1] for i in range(m)]
bc.sort(reverse=True)
def hoge(n,m,a,bc):
    cur_sum = sum(a)
    for x in bc:
        c = x[0]
        for i in range(x[1]):
            prv_sum = cur_sum
            cur_sum -= a.popleft()
            cur_sum += c
            a.append(c)
            if prv_sum >= cur_sum:
                print(prv_sum)
                return
    print(cur_sum)
    return
hoge(n,m,a,bc)
### BUGGY CODE ###

from collections import defaultdict
import queue

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.judge = "Yes"
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.dist[s] = 0
		self.Q.put(s)
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
				else:
					if (self.dist[i] - self.dist[v]) % 2 == 0:
						self.judge = "No"

	def ans(self):
		return max(self.dist)

#処理内容
def main():
	#初期化
	N = int(input())
	L = []
	for i in range(N):
		S = list(input())
		L.append(S)
	G = Graph()
	for i in range(N):
		for j in range(i + 1, N):
			if L[i][j] == "1":
				G.add_edge(i, j)
				G.add_edge(j, i)
	#BFS
	jud = "Yes"
	A = - INF
	for i in range(N):
		bfs = BFS(G, i, N)
		A = max(bfs.ans(), A)
		if bfs.judge == "No":
			jud = "No"
	if jud == "No":
		print(-1)
	else:
		print(A + 1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

from collections import defaultdict
import queue

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.judge = "Yes"
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.dist[s] = 0
		self.Q.put(s)
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
				else:
					if (self.dist[i] - self.dist[v]) % 2 == 0:
						self.judge = "No"

	def ans(self):
		return max(self.dist)

#処理内容
def main():
	#初期化
	N = int(input())
	L = []
	for i in range(N):
		S = list(input())
		L.append(S)
	G = Graph()
	for i in range(N):
		for j in range(i + 1, N):
			if L[i][j] == "1":
				G.add_edge(i, j)
				G.add_edge(j, i)
	#BFS
	jud = "Yes"
	A = - INF
	for i in range(N):
		bfs = BFS(G, i, N)
		A = max(bfs.ans(), A)
		if bfs.judge == "No":
			jud = "No"
	if jud == "No":
		print(-1)
	else:
		print(A + 1)

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

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for ai, bi, ci in zip(a, b, c):
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M_a = int(next(tokens))  # type: int
    M_b = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M_a, M_b, a, b, c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def solve():
    N, M_a, M_b = [int(x) for x in input().split()]
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for _ in range(N):
        ai, bi, ci = [int(x) for x in input().split()]
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


solve()
### BUGGY CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)

### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

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

n = int(input())

l = [int(x) for x in input().split()]
l.sort()
mp = [1]*n
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if(l[j]==l[i]):
            mp[i] = 0
        if(l[j]%l[i]==0):
            mp[j] = 0
print(sum(mp))

### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

A,B=[int(x) for x in input().strip().split()]
ans=[]
if A==B:
    print(A)
else:
    for i in range(40):
        if i >= 1:
            numList=[]
            temp=A
            while True:
                if format(temp,'040b')[39-i]=='1':
                    numList.append(temp)
                    temp+=1
                else:
                    break
            temp=B
            while True:
                if format(temp,'040b')[39-i]=='1':
                    numList.append(temp)
                    temp-=1
                else:
                    break
        else:
            numList=[x for x in range(A,B+1)]
        temp=0
        for c,num in enumerate(numList):
            temp=temp^num
        temp=format(temp,'040b')
        ans.append(temp[39-i])
    ans.reverse()
    print(int(''.join(ans),2))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    def count1(d, i):
        i2 = 2 ** i
        ret = (d // i2) * (i2 // 2)
        d -= 2 * ret
        if d >= i2 // 2:
            ret += d - (i2 // 2) + 1
        return ret

    A, B = [int(x) for x in input().strip().split()]
    ans = 0
    for i in range(40):
        ans += ((count1(B, i+1) - count1(A-1, i+1)) % 2) * 2 ** i
    
    print(ans)

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

a,b,x=map(int,input().split())
count = 0
for i in range(a,b+1):
    if i%x==0:
        count += 1
print(count)

### FIXED CODE ###

a,b,x=map(int,input().split())
count = (b//x)-(a//x)
if a%x==0:
    count += 1
print(count)
### BUGGY CODE ###

from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

s = [0] * (len(c) + 1)
for i in range(len(c)):
    s[i + 1] = s[i] + c[i]

def bin_search_max(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            l = c
        else:
            r = c
    return l

for i in range(1, n + 1):
    rest = len(c) - i
    if rest < 0:
        print(0)
        continue
    def f(v):
        lim = bin_search_max(-1, len(c), lambda x: c[x] < v) + 1
        return lim * v - s[lim] <= rest * v
    print(bin_search_max(0, c[-1] * len(c) + 1, f))


### FIXED CODE ###

from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

clen = len(c)

s = [0] * (clen + 1)
for i in range(clen):
    s[i + 1] = s[i] + c[i]

for i in range(1, n + 1):
    rest = clen - i
    if rest < 0:
        print(0)
        continue
    l1 = 0
    r1 = s[clen] // i + 2
    while r1 - l1 > 1:
        c1 = (l1 + r1) // 2

        l2 = -1
        r2 = clen
        while r2 - l2 > 1:
            c2 = (r2 + l2) // 2
            if c[c2] < c1:
                l2 = c2
            else:
                r2 = c2

        if (r2 - rest) * c1 <= s[r2]:
            l1 = c1
        else:
            r1 = c1
    print(l1)
### BUGGY CODE ###

mod = 10**9+7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*10**i)%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*10**i)%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])

### FIXED CODE ###

mod = 10**9+7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*pow(10,i,13))%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*pow(10,i,13))%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])
### BUGGY CODE ###

# 深さ優先探索の問題
import numpy as np
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in readline().split()]
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
s = [0] * N
for _ in range(Q):
    p, x = [int(i) for i in readline().split()]
    #s[p-1] = s[p-1] + x
    s[p-1] += x

ans = [0] * N

# 深さ優先探索
def dfs(v, p, value):
    #value = value + s[v]
    value += s[v]
    #ans[v] = ans[v] + value
    ans[v] += value
    for c in t[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)


### FIXED CODE ###

# 深さ優先探索の問題
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in readline().split()]
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
s = [0] * N
for _ in range(Q):
    p, x = [int(i) for i in readline().split()]
    #s[p-1] = s[p-1] + x
    s[p-1] += x

ans = [0] * N

# 深さ優先探索
def dfs(v, p, value):
    #value = value + s[v]
    value += s[v]
    ans[v] = value
    for c in t[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

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

N, M = map(int, input().split())
judge_lis = [[] for i in range(N)]
for i in range(M):
  problem, result = input().split()
  judge_lis[int(problem)-1].append(result)

ans_lis = [0 for i in range(N)]
ans_num = 0
for i in range(N):
  j = 0
  while j < len(judge_lis[i]):
    if not "AC" in judge_lis[i]:
      break
    if judge_lis[i][j] == "WA":
      ans_lis[i] += 1
    if judge_lis[i][j] == "AC":
      ans_num += 1
      break
    j += 1
      
print(ans_num, sum(ans_lis))

### FIXED CODE ###

N, M = map(int, input().split())
lis = [[] for _ in range(N)]
for _ in range(M):
  question, result = input().split()
  question = int(question)
  lis[question-1].append(result)  

AC_times = 0
WA_times = 0
for i in range(N):
  pre_WA_times = 0
  for j in lis[i]:
    passed = False
    if not passed:
      if j == "AC":
        passed = True
        WA_times += pre_WA_times
      elif j == "WA":
        pre_WA_times += 1
    if passed:
      AC_times += 1
      break
      
print(AC_times, WA_times)
### BUGGY CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = []

for _ in range(q):
    l, r = list(map(int, input().split()))
    lr_list.append((l, r))

# あらかじめACがある位置を検索した方が良いのかもしれない
work_s = s.replace('AC', '*_')
matched_index_list = [i for i, x in enumerate(work_s) if x == '*']

for l, r in lr_list:
    count = len([x for x in matched_index_list if l-1 <= x < r-1])
    print(count)


### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = [0] * n
for i in range(n-1):
    # print('{}: {}'.format(i, s[i:i+2]))
    if s[i:i+2] == 'AC':
        count_ac_list[i+1] = count_ac_list[i] + 1
    else:
        count_ac_list[i+1] = count_ac_list[i]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1]) for l, r in lr_list]

print('\n'.join(count_list))