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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
r = []
for _ in range(q):
  r.append(list(map(int, input().split())))

s = {}

for v in a:
  if v in s:
    s[v] += v
  else:
    s[v] = v

for t in r:
  if t[0] in s:
    n = s[t[0]] // t[0] * t[1]
    if t[1] in s:
      s[t[1]] += n
    else:
      s[t[1]] = n
    del s[t[0]]
  print(sum(s.values()))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
r = []
for _ in range(q):
  r.append(list(map(int, input().split())))

s = {}

for v in a:
  if v in s:
    s[v] += v
  else:
    s[v] = v

p = sum(s.values())

for t in r:
  if t[0] in s:
    n = s[t[0]] // t[0] * t[1]
    p = p - s[t[0]] + n
    if t[1] in s:
      s[t[1]] += n
    else:
      s[t[1]] = n
    del s[t[0]]
  print(p)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, s = nm()
a = nl()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        if j >= v:
            dp[j] = (dp[j] * 2 + dp[j-v]) % mod
        else:
            dp[j] = dp[j] * 2 % mod
print(dp[s])


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, s = nm()
a = nl()
mod = 998244353
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        dp[i+1][j] = dp[i][j] * 2 % mod
        if v + j <= s:
            dp[i+1][v+j] = (dp[i+1][v+j] + dp[i][j]) % mod

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

N,K = map(int,input().split())
ary = [0]+list(map(int,input().split()))
dp = [[0]*N for _ in range(N)]
ary = sorted(ary)
a = ary.index(0)
ary.pop(a)
ans = float("Inf")
for i in range(N):
    for j in range(N):
        dp[i][j] = [abs(ary[i]-ary[j]),abs(j-i)]
for i in range(N):
    for j in range(N):
        if i == j:
            k = abs(dp[i][i][1] - a)
            d = abs(ary[i])
            if k >= K and ans > d:
                ans = d
            continue
        k = 1 + dp[i][j][1]
        d = abs(ary[i]) + dp[i][j][0]
        if k >= K and ans > d:
            ans = d
print(0 if ans == float("Inf") else ans)

### FIXED CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary.sort()
zero = ary.index(0)
a = [abs(i - zero) for i in range(N + 1)]
ary.pop(zero)
ans = float("Inf")
for i in range(N - K + 1):
    b = N - i - 1
    d = abs(ary[i])
    if a[i] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[i] - ary[i + K - 1]))
    d = abs(ary[b])
    if a[b] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[b] - ary[b - K + 1]))
print(ans)
### BUGGY CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while True:
  d = abs(N-K)
  if N == 0:
    break
  if d<N:
    N = d
  else:
    break
print(N)

### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while N>K:
  N = N%K
  
print(min([N,K-N]))
### BUGGY CODE ###

import fractions
mod=10**9+7
def lcm(a,b):
  s=fractions.gcd(a,b)
  return a*b//s

n=int(input())
a=list(map(int,input().split()))
l=a[0]
for i in a:
  l=lcm(l,i)
ans=0
for j in a:
  ans=(ans+l//j)%mod
print(ans)

### FIXED CODE ###

from fractions import gcd
MOD=10**9+7
N,*A=map(int,open(0).read().split())

def lcm(a,b):
  return a*b//gcd(a,b)
s=1
for i in A:
  s=lcm(s,i)
s%=MOD
ans=0
for i in A:
  ans+=s*pow(i,MOD-2,MOD)
  ans%=MOD
print(ans)
### BUGGY CODE ###

n=int(input())
counter=[0,0]
i=2
while True:
    while True:
        counter.append(0)
        if n%i==0:
            counter[i]+=1
            n/=i
        else:
            break
    if n==1:
        break
    i+=1

ans=0
for j in range(len(counter)):
    k=1
    while True:
        if counter[j]-k>=0:
            counter[j]-=k
            ans+=1
        else:
            break
        k+=1

print(ans)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n=int(input())
li=factorization(n)
ans=0
for i in range(len(li)):
    k=1
    while True:
        if li[i][1]-k>=0:
            li[i][1]-=k
            ans+=1
        else:
            break
        k+=1
if n<=1:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

from decimal import *

getcontext().prec = 50000
a,b,c, = map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt() <Decimal(c).sqrt():
  print("Yes")
else:
  print("No")


### FIXED CODE ###

from decimal import *

getcontext().prec = 50000
a,b,c, = map(int,input().split())
if a+b+Decimal(4*a*b).sqrt() < c:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

MOD = 10**9+7
list_size = (10**6+10)*4

f_list = [1]*list_size
f_r_list = [1]*list_size

for i in range(list_size - 1):
    f_list[i+1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
    f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)



r1,c1,r2,c2 = map(int,input().split())

ans = f_list[(r2+c2)*2]*f_r_list[r2*2]*f_r_list[c2*2]
ans %= MOD
ans += f_list[(r1+c1-2)*2]*f_r_list[r1*2-2]*f_r_list[c1*2-2]
ans %= MOD
ans -= f_list[(r2+c1)*2]*f_r_list[r2*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(c2+r1)*2]*f_r_list[c2*2]*f_r_list[r1*2]
ans %= MOD

print(ans)




### FIXED CODE ###

MOD = 10**9+7
r1,c1,r2,c2 = map(int,input().split())

size = 1010000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))

ans = func(r2+1,c2+1)-1
ans += func(r1,c1)-1
ans -= func(r2+1,c1)-1
ans -= func(r1,c2+1)-1
print(ans%MOD)
### BUGGY CODE ###

import math

K = int(input())
#K = 200
sum = 0

for a in range (1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      sum += math.gcd(math.gcd(a, b), c)

print(sum)


### FIXED CODE ###

from math import gcd

K = int(input())
#K = 200
sum = 0

for a in range (1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      sum += gcd(gcd(a, b), c)

print(sum)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

import numpy as np
N = int(input())
d = LI()
d.sort()
cnt_k = np.array([0 for i in range(max(d))])

for i in range(N):
    cnt_k[:d[i]] += 1

print(np.count_nonzero(cnt_k==N//2))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

import numpy as np
N = int(input())
d = LI()
d.sort()
cnt = 0
ans = d[N//2]-d[N//2-1]
print(ans)
### BUGGY CODE ###

n = int(input())

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

m = int(input())

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

d.sort()

t.sort()

index = 0

for i in t:
    flag = True
    while index < len(d):
        if i == d[index]:
            d.pop(index)
            flag = False
            break
        else:
            index += 1
    if flag:
        print('NO')
        exit()

print('YES')
           

### FIXED CODE ###

from collections import Counter
 
N = int(input())
D = list(input().split())
 
M = int(input())
T = list(input().split())
 
D_count = Counter(D)
T_count = Counter(T)

for k, v in T_count.items():
    if D_count[k] < v:
        print('NO')
        exit()
 
print('YES')
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    if i<10: i = "00"+str(i)
    elif i<100: i = "0"+str(i)
    else: i = str(i)
    for j in range(n-2):
        if s[j] == i[0]:
            for k in range(j+1, n-1):
                if s[k] == i[1]:
                    for l in range(k+1, n):
                        if s[l] == i[2]:
                            ans += 1
                            break
                    break
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    x = s.find(num[0])
    y = s.find(num[1], x+1)
    z = s.find(num[2], y+1)
    if x != -1 and y != -1 and z != -1:
            ans += 1
print(ans)
### BUGGY CODE ###

N = -1

def _input():
    global N
    N = int(input())

def solve():
    _input()
    snuke_power = 1
    for i in range(1, N+1):
        snuke_power *= i
    print(snuke_power % (10 ** 9 + 7))


if __name__ == '__main__':
    solve()

### FIXED CODE ###

N = -1

def _input():
    global N
    N = int(input())

def solve():
    _input()
    snuke_power = 1
    for i in range(1, N+1):
        snuke_power *= i
        snuke_power %= (10 ** 9 + 7)
    print(snuke_power)


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

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

count=0

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i] and j-i != k-j:
                count+=1

print(count)

### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')

ad=r*g*b
mi=0

for i in range(N):
    for j in range(i+1,N):
        k=j+(j-i)
        if k<N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                mi+=1

print(ad-mi)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(list)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
LC = 0
LP = -1
for i in range(1, N + 1):
  C[i] = int(input())
  DP[i][0] = sum(DP[i - 1]) % p
  if C[i] != C[i - 1]:
    for d in D[C[i]]:
      DP[i][1] += DP[d][0]
    D[C[i]] += [i]
print(sum(DP[N]) % p)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(lambda: -1)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
for i in range(1, N + 1):
  C[i] = int(input())
  DP[i][0] = sum(DP[i - 1]) % p
  if C[i] != C[i - 1]:
    DP[i][1] = sum(DP[D[C[i]]]) if D[C[i]] != -1 else 0
    D[C[i]] = i
print(sum(DP[N]) % p)
### BUGGY CODE ###

N = int(input())
AList = input().split()
result = 1

for element in AList:
    result = result * int(element)
   
if result > 1e+18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

import sys

N = int(input())
AList = input().split()

result = 1

if "0" in AList:
    print(0)
    sys.exit()
    
for element in AList:
    result = result * int(element)

    if result > 1e+18:
        print(-1)
        sys.exit()

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

#左の最頻と右の最頻合計すればいいんじゃないの？
#でも最頻がお互い3万種類までありえる
#その場合は最頻をminから順番に組み合わせていって、最頻＋最頻が該当した瞬間breakでよい
#これなら処理回数はmax3万？だし
#最頻+最頻-1しかない場合は、左右ぞれぞれ2位×1位を同様に試すいやこれいらんわ
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []

for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)

countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)

leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す

for i in range(leftkeyN):
    if flag != 0:
        break
    else:
        for P in range(rightkeyN):
            for T in range(M):
                if c[T] == [leftkeys[i],rightkeys[P]]:
                    cnt = cnt + 1
            if cnt == 0:
                flag = flag + 1
                break
            else:
                cnt = 0

if flag == 0:
    print(int(tempmax - 1))
else:
    print(int(tempmax))
    

### FIXED CODE ###

import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
  
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
 
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す
 
for i in range(M):
    goukei = int(countleft.get(c[i][0])) + int(countright.get(c[i][1]))
    if goukei == tempmax:
        cnt += 1
    else:
        pass

if cnt == int(leftkeyN * rightkeyN):
    print(int(tempmax - 1))
else:
    print(int(tempmax))
### BUGGY CODE ###

h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)]
a=[0 for i in range(h+1)]
b=[0 for _ in range(w+1)]
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a)
bm=max(b)
aa=[i for i, x in enumerate(a) if x==am]
bb=[i for i, x in enumerate(b) if x==bm]
for i in aa:
    for j in bb:
        if not [i,j] in bomb:
            print(am+bm)
            exit()
print(am+bm-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)] #bombの位置
a=[0 for i in range(h+1)] #各行のbombの個数
b=[0 for _ in range(w+1)] #各列のbombの個数
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a) #１行にあるbombの最大値
bm=max(b) #１列にあるbombの最大値
hmax=[0]*(h+1) #最大値をとるh全部
wmax=[0]*(w+1) #最大値をとるw全部
for i in range(h+1):
    if am==a[i]:
        hmax[i]+=1
for i in range(w+1):
    if bm==b[i]:
        wmax[i]+=1
ans=am+bm #基本解
k=sum(hmax)*sum(wmax)
if k>m: #鳩ノ巣原理
    print(ans)
    exit()
for i in bomb:
    if hmax[i[0]]==1 and wmax[i[1]]==1:
        k-=1
if k==0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

n, W =map(int,input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

def ks(W,w,v,n):
    if n == 0 or W == 0 : 
        return 0
    if (w[n-1] > W): 
        return ks(W, w, v, n - 1)
    else:
        return max(v[n - 1] + ks(W - w[n - 1], w, v, n - 1), 
                   ks(W, w, v, n - 1))
print(ks(W,w,v,n))

### FIXED CODE ###

n,W = map(int,input().split())
w,v = [0] * n ,[0] * n
for i in range(n):
    w[i] ,v[i] = map(int,input().split())

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)
for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])
### BUGGY CODE ###

# -*- coding:utf-8 -*-
N = int(input())
TA = []
counter = 0
for tmp in range (N):
    TA.append(list(map(int,input().split())))

whole = TA[0][0] + TA[0][1] #総和
for tmp in range (1,N):
    counter = 0
    tmp2 = TA[tmp][0]+TA[tmp][1]
    before = whole/(TA[tmp-1][0]+TA[tmp-1][1]) #比の数値1が何票か。
    while True:
        if (whole+counter)%tmp2 != 0:
            counter += tmp2 - (whole+counter)%tmp2
        whole += counter
        if (before*TA[tmp-1][0] > ((whole/tmp2)*TA[tmp][0]) or (before*TA[tmp-1][1] > ((whole/tmp2)*TA[tmp][1]))):
            counter = 1
            continue
        else:
            break
print(whole)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
from decimal import *
N = int(input())
A, B = (1, 1)
for tmp in range (N):
    t, a = map(int,input().split())
    n = Decimal(max([math.ceil(A/t),math.ceil(B/a)]))
    A = n*t
    B = n*a
print(A+B)
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
grid = [input() for i in range(H)]

# 黒か白かどうか　初期化
dist = [[-1]*W for _ in range(H)]

# #の位置をキューに追加（今回はスタートが複数 複数追加される）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h,w))
            dist[h][w] = 0
def bfs(black_cells, dist):
    """
        BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        h, w =  black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1,0), (0,1), (-1,0), (0,-1)):
            new_h = h+dy
            new_w = w+dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白であるとき
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
grid = [input() for i in range(H)]

# 黒か白かどうか　初期化
dist = [[-1]*W for _ in range(H)]

# #の位置をキューに追加（今回はスタートが複数 複数追加される）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h,w))
            dist[h][w] = 0
def bfs(black_cells, dist):
    """
        BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        h, w =  black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1,0), (0,1), (-1,0), (0,-1)):
            new_h = h+dy
            new_w = w+dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白であるとき
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

s = list(input())
q = int(input())
judge = 1
for i in range(q):
  d = input()
  if d == '1':
    judge *= -1
  else:
    a, b, c = list(d.split())
    b = int(b)
    if (b == 1 and judge ==1) or (b == 2 and judge == -1):
      s.insert(0, c)
    else:
      s.append(c)
if judge == 1:
  print(*s,sep='')
else:
  print(*s[::-1], sep='')

### FIXED CODE ###

s = list(input())
q = int(input())
judge = 1
front = []
back = []
for i in range(q):
  a = list(map(str,input().split()))
  if int(a[0]) == 1:
    judge *= -1
  else:   
    if (int(a[1]) == 1 and judge == 1) or (int(a[1]) == 2 and judge == -1):
      front.append(a[2])
    else:
      back.append(a[2])
ans = front[::-1] + s + back
if judge == -1:
  ans.reverse()
print(*ans, sep='')
### BUGGY CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, w):
    w += leaves[x]
    for nx in [e for e in edge[x] if V[e] == 0]:
        V[nx] = 1
        dfs(nx, w)
    leaves[x] = w


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

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

leaves = [0] * N
V = [0] * N
V[0] = 1

for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    leaves[p] += x

dfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])


### FIXED CODE ###

from collections import deque


def bfs(x, w):
    q = deque()
    q.append((x, w))

    while len(q):
        x, w = q.popleft()
        leaves[x] += w
        w = leaves[x]
        for nx in edge[x]:
            if V[nx] == 0:
                V[nx] = 1
                q.append((nx, w))


N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
leaves = [0] * N
V = [0] * N

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    leaves[p] += x

V[0] = 1
bfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
    ans=0
    for x in range(1, math.floor(math.sqrt(i))+1):
        for y in range(1, math.floor(math.sqrt(i-x*x))+1):
            for z in range(1, math.floor(math.sqrt(i-x*x-y*y))+1):
                if x*x + y*y + z*z + x*y + y*z + z*x == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

import math
N=int(input())
ans=[0 for _ in range(10**4+1)]
for x in range(1, math.floor(math.sqrt(10**4))+1):
    for y in range(1, math.floor(math.sqrt(10**4))+1):
        for z in range(1, math.floor(math.sqrt(10**4))+1):
            if x*x + y*y + z*z + x*y + y*z + z*x <= 10**4:
                ans[x*x + y*y + z*z + x*y + y*z + z*x]+=1
for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

import re
n,q = map(int, input().split())
s = input()
l = [0]*q
r = [0]*q
for i in range(q):
  l[i],r[i] = map(int, input().split())

counts = [0]*n

pattern = "AC"
result = re.finditer(pattern, s)
for res in result:
  counts[res.start()] = 1

for i in range(q):
  tmp = counts[l[i]-1:r[i]]
  if tmp[-1]==1:
    tmp[-1]=0
  ret=sum(tmp)
  print(ret)

### FIXED CODE ###

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

counts = [1 if s[i:i+2]=="AC" else 0 for i in range(n)]

cum_counts=[0]*n
for i in range(1,n):
  cum_counts[i]=cum_counts[i-1]+counts[i-1]

#print(counts)
#print(cum_counts)

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