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

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)
### BUGGY CODE ###

n = int(input())
sum = 0
for i in range(1,n):
  if n // i == n % i:
    sum += i
print(sum)

### FIXED CODE ###

n = int(input())
count = 0
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
l = make_divisors(n)
for i in range(len(l)):
  if l[i]-1 > 0 and n // (l[i]-1) == n % (l[i]-1):
    count += l[i]-1
print(count)
### BUGGY CODE ###

N,M = map(int,input().split())
li = []
numb = []
ans = ''
for i in range(M):
  li.append(tuple(map(int,input().split())))
  if li[i][0] == 1:
    numb.append(li[i][1])
for i in range(M):
  if li[i][0] in numb and li[i][1] == N:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)
    

### FIXED CODE ###

N,M = map(int,input().split())
li = []
numb = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        li.append(b)
    elif b == N:
        numb.append(a)
ans = set(li) & set(numb)
if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
a = list(map(int,input().split()))
 
comb = itertools.combinations(a,k)
 
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(s) for s in input().split()]
b=[0]*k
c=0
for i in range(n-k+1):
    if sum(a[i:i+k])>=c:
        c=sum(a[i:i+k])
        for j in range(k):
            b[j]=a[i+j]
su=0
for i in range(k):
    su+=(b[i]+1)/2
print(su)


### FIXED CODE ###

n,k=map(int,input().split())
a=[int(s) for s in input().split()]
b=[0]*k
c=0
v=[0]*n
v[0]=a[0]
for i in range(n-1):
    v[i+1]=v[i]+a[i+1]
mx=v[k-1]
for i in range(k,n):
    g=v[i]-v[i-k]
    mx=max(mx,g)  
    
print((mx+k)/2)
### BUGGY CODE ###

num = int(input())
l = []
cnt = 0

for i in range(1,num):
    if num % i == 0:
        l.append(i)

for z in l[1:]:
    if num == 1:
        break
    elif num % z == 0:
        num /= z
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

f = factorize(n)
ans = 0
for i,j in f:
    ans += int((-1+pow(1+8*j,0.5))/2)
print(ans)
### BUGGY CODE ###

import sys

n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
dp = [0] * (n+1)
mod = 1000000007
dp[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        sys.exit()
else:
    dp[1] = 1
for i in range(2, n+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
ct = [0] * (n+1)
A = [True] * n
for _ in range(m):
    A[int(input())-1] = False

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])
### BUGGY CODE ###

n = int(input())
s = input()
tmp = set()
si = set()
for i in range(n-2):
  if i in si:
    continue
  else:
    si.add(i)
    sj = set()
    for j in range(i+1,n-1):
      if j in sj:
        continue
      else:
        sj.add(j)
        sk = set()
        for k in range(j+1, n):
          if k in sk:
            continue
          else:
            sk.add(k)
       	    tmp.add(s[i] + s[j] + s[k])
print(len(tmp))

### FIXED CODE ###

n = int(input())
s = input()
tmp = set()
si = set()
for i in range(n-2):
  if s[i] in si:
    continue
  else:
    si.add(s[i])
    sj = set()
    for j in range(i+1,n-1):
      if s[j] in sj:
        continue
      else:
        sj.add(s[j])
        sk = set()
        for k in range(j+1, n):
          if k in sk:
            continue
          else:
            sk.add(s[k])
       	    tmp.add(s[i] + s[j] + s[k])
print(len(tmp))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
count = 0
for i in range(q):
    for j in range(lr[i][0] - 1, lr[i][1] - 1):
        if s[j] == 'A' and s[j + 1] == 'C':
            count += 1

    print(count)
    count = 0

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
s_count = [0 for i in range(n + 1)]
for i in range(n):
    s_count[i + 1] = s_count[i] + (1 if s[i:i + 2] == 'AC' else 0)

for i in range(q):
    print(s_count[lr[i][1] - 1] - s_count[lr[i][0] - 1])
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = list(input())
total = Counter(S)
counter1 = {"R":0,"G":0,"B":0}
ans = 0


for i in range(N-2):
    RGB = {"R","G","B"} - {S[i]}
    counter1[S[i]]+=1
    counter2 = {"R":0,"G":0,"B":0}
    for j in range(i+1,N-1):
        counter2[S[j]]+=1
        tmp = list(RGB - {S[j]})
        if len(tmp)==1:
            target = tmp[0]
            ans+=total[target]-counter1[target]-counter2[target]
            if((j - i)+ j <= N -1 and S[(j - i)+ j] == target):
                ans-=1
print(ans)





### FIXED CODE ###

from collections import Counter
N = int(input())
S = list(input())
dic = Counter(S)
dic2 = {"R":0,"G":0,"B":0}
ans = 0
for i in range(N-2):
    RGB = {"R","G","B"} - {S[i]}
    dic2[S[i]]+=1
    dic3 = {"R":0,"G":0,"B":0}
    for j in range(i+1,N-1):
        dic3[S[j]]+=1
        if len(RGB - {S[j]})!=1:
            continue
        else:
            target = list(RGB - {S[j]})[0]
            ans+=dic[target]-dic2[target]-dic3[target]
            if((j - i)+ j <= N -1):
                if(S[(j - i)+ j] == target):
                    ans-=1
print(ans)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

adj = [[float("inf") for i in range(N)] for j in range(N)]
signs = [-1 for i in range(N)]
not_patrolled = set(range(1, N))
signs[0] = 1

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1][y - 1] = 1
  adj[y - 1][x - 1] = 1

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  used = set()
  for i in not_patrolled:
    c = adj[cur][i]
    if c == 1:
      queue.append(i)
      signs[i] = cur
      used.add(i)
  hoge = len(not_patrolled)
  not_patrolled = not_patrolled - used
  fuga = len(not_patrolled)
  if hoge == fuga:
    break

if all([sign != -1 for sign in signs]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]
# not_patrolled = set(range(1, N))

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1].append(y - 1)
  adj[y - 1].append(x - 1)

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      # not_patrolled.remove(i)

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:56:56 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
s = int(s)
mod = 2019
count = 0

for i in range(1,n-2):
    for j in range(i+3,n+1):
        num1 = 10**(n-i+1)
        num2 = 10**(n-j)
        sample = (s%num1)//num2
        if sample % mod == 0:
            count += 1

print(count)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

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

from bisect import *

def f(n):
    r = []
    for _ in range(n):
        a = int(input())
        if not r:
            r.append(a)
            continue
        i = bisect_left(r, a)
        if i:
            r.insert(i, a)
            del r[i - 1]
        else:
            r = [a] + r
    print(len(r))

n = int(input())
f(n)


### FIXED CODE ###

import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(input())
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print(mi+1)

n = int(input())
inf=10**10
f(n)
### BUGGY CODE ###

S = input()

counter = 0
arr = list(S)
while True:
    x = 0
    for i in range(len(arr)-1):
        if arr[i] == 'B' and arr[i+1] == 'W':
            arr[i] = 'W'
            arr[i+1] = 'B'
            counter += 1
            x = 1
            break
    if x == 0:
        break

print(counter)

### FIXED CODE ###

S = input()

steps = 0
accumulated_W = 0

for i, x in enumerate(list(S)):
    if x == 'W':
        steps += i - accumulated_W
        accumulated_W += 1

print(steps)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] = list(format(a[i],'0b').zfill(60))
g = [0 for i in range(60)]
for i in range(60):
    for j in range(n):
        if a[j][i] == '1':
            g[i] += 1
ans = 0
for i in range(len(g)):
    ans += g[i]*(n-g[i])*(pow(2,59-i,10**9+7))
    ans = ans%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

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

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

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    w, v = map(int, input().split())

    for j in range(W + 1):
        if j < w:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)

print(dp[N][W])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

from math import gcd

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

d = gcd(A, B)
ans = 1
i = 2
for i in range(2, round(pow(d, 2/1))):
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
print(ans)

### FIXED CODE ###

from math import gcd

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

d = gcd(A, B)
ans = 1
i = 2
while i <= pow(d, 1/2)+1:
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
ans += (d > 1)
print(ans)
### BUGGY CODE ###

import bisect

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()

b_bt = []
c_bt = []
for i in range(n):
    b_bt.append(bisect.bisect_left(a, b[i]))
    c_bt.append(bisect.bisect_left(b, c[i])-1)
result = 0
for i in range(n):
    if c_bt[i] >= 0:
        result += sum(b_bt[:c_bt[i]+1])
print(result)

### FIXED CODE ###

import bisect

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()

result = 0
for i in range(n):
    x = bisect.bisect_left(a, b[i])
    y = n - bisect.bisect_right(c, b[i])
    result += x*y


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

N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        flag=True
        for k in range(N):
            if j==k or i==k:
                continue
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            if A[i][j]==A[i][k]+A[k][j]:
                flag=False
        if flag:
            ans+=A[i][j]
print(ans)


### FIXED CODE ###

N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        flag=True
        for k in range(N):
            if j==k or i==k:
                continue
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            if A[i][j]==A[i][k]+A[k][j]:
                flag=False
        if flag:
            ans+=A[i][j]
print(ans)
### BUGGY CODE ###

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

for i in range(m):
    b,c=map(int,input().split())
    A +=[c]*b

print(sum(sorted(A,reverse=True)[:n]))

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

A=deque(A)
for b,c in BC[::-1]:
    if len(A)==0:break
    for i in range(b):
        if A[0]<c:
            A.append(c)
            A.popleft()
        else:break
print(sum(A))
### BUGGY CODE ###

from collections import Counter
N = int(input())
slist = [Counter(list(input())) for _ in range(N)]
counter = 0
for j in range(N):
    js = slist[j]
    for i in range(j):
        if js==slist[i]:
            counter += 1
print(counter)

### FIXED CODE ###

from collections import Counter
N = int(input())
slist = ["".join(sorted(list(input()))) for _ in range(N)]
c = Counter(slist)
ans = 0
for v in c.values():
    ans += sum(range(v))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):
    visited = [False]*N
    curr = 1
    counter = 0
    while curr != 2:
        curr = a[curr-1]
        counter += 1
        if curr == 1:
            print(-1)
            return
    print(counter)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):
    visited = [False]*N
    curr = 1
    counter = 0
    while curr != 2:
        if visited[curr-1]:
            print(-1)
            return
        visited[curr-1] = True
        curr = a[curr-1]
        counter += 1
    print(counter)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

from scipy.misc import comb

x, y = map(int, input().split())

def A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return comb(n+m,m, exact=True)%((10**9)+7)
    else:
        return 0

print(A(x, y))

### FIXED CODE ###

x, y = map(int, input().split())

def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return combinations_count(n+m,m)%((10**9)+7)
    else:
        return 0

print(A(x, y))
### BUGGY CODE ###

import heapq
N,M = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            heapq.heappush(An,tmp_min)
            flag = True
            break
        heapq.heappush(An,C)
    if flag:
        break
print(sum(An))

### FIXED CODE ###

import heapq
N,M = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
decided_sum = []
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            #heapq.heappush(An,tmp_min)
            decided_sum.append(tmp_min)
            flag = True
            break
        decided_sum.append(C)
        if len(An) == 0:
            flag = True
            break
    if flag:
        break
print(sum(decided_sum) + sum(An))
### BUGGY CODE ###

n,y=map(int,input().split())
for a in range(n+1):
    for b in range(n+1):
        c=(y-(a*10000+b*5000))//1000
        if a+b+c>n:
            continue
        if y == (a*10000+b*5000+c*1000):
            if a+b+c==n and a>=0 and b>=0 and c>=0:
              print(a,b,c)
              exit()
print(-1,-1,-1)

### FIXED CODE ###

n,y=map(int,input().split())
for a in range(n+1):
    for b in range(n+1):
        c=(y-(a*10000+b*5000))//1000
        if a+b+c==n and c>=0:
            print(a,b,c)
            exit()
print(-1,-1,-1)
### BUGGY CODE ###

import fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    if n == 1:
        return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0:
        ret += 1
        n = n // cursor
        while n % cursor == 0:
            n = n // cursor
    
    cursor = 3
    while cursor**2 < n:
        if n % cursor == 0:
            ret += 1
            n = n // cursor
            while n % cursor == 0:
                n = n // cursor
            cursor += 2

    if n != 1:
        ret += 1
        
    return ret

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math, fractions


def num_prime_factor(n):
    
    ret = 0

    for i in range(1, int(math.sqrt(n)) + 2):

        composite = False

        if n % i == 0:
            ret += 1
            n = n / i

            if i != 1:
                while n % i == 0:
                    n = n / i

            if n == 1:
                break

            for j in range(2, int(math.sqrt(n)) + 2):
                if n % j == 0:
                    composite = True
                    break

            if not composite:
                ret += 1
                break

    return ret

if __name__ == "__main__":
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = input()
    
    for i in range(Q):
        start, end = list(map(int, input().split()))
        print(S[start-1:end].count('AC'))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    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):
        start, end = map(int, input().split())
        print(t[end - 1] - t[start - 1])
    
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

K,S = map(int,input().split())
res = 0
for X in range(0,K+1):
    if X > S:
        break
    for Y in range(0,K+1):
        if X + Y > S:
            break
        for Z in range(0,K+1):
            if X + Y + Z == S:
                res += 1
            elif X + Y + Z >S:
                break
print(res)

### FIXED CODE ###

K,S = map(int,input().split())
print(sum([0<=S-X-Y<=K for X in range(0,K+1) for Y in range(0,K+1)]))
### BUGGY CODE ###

N,Q = map(int, input().split())
D=[10**10]*N
D[0]=0
A=[[0]*3 for i in range(N-1)]
Ans=[0]*N
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
    if(A[i][0]==1):
        D[A[i][1]-1]=1
    else:
        D[A[i][1]-1]=D[A[i][0]-1]+1
    A[i][2]=D[A[i][1]-1]
while(max(D)>(10**10)):
    for i in range(N-1):
        if(A[i][0]==1):
            D[A[i][1]-1]=1
        else:
            D[A[i][1]-1]=D[A[i][0]-1]+1
        A[i][2]=D[A[i][1]-1]

for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
    Ans[P[i][0]-1]+=P[i][1]
A=sorted(A,key=lambda x: x[2])

for i in range (N-1):
    Ans[A[i][1]-1]+=Ans[A[i][0]-1]
print(*Ans)


### FIXED CODE ###

import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))