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

N,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if j<w:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for i 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]=max(dp[i][j-w]+v,dp[i][j])
    else:
      dp[i+1][j]=dp[i][j]
print(dp[N][W])
### BUGGY CODE ###

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

px_dict = {}
for i in range(Q):
    p, x = map(int, input().split())
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

for p, x in px_dict.items():
    kk_list = [p]
    while(1):
        k = kk_list[0]
        value_dict[k] += x
        if k in tree_dict:
            kk_list += tree_dict[k]
        kk_list.pop(0)
        if len(kk_list) == 0:
            break

print(' '.join([str(v) for k, v in value_dict.items()]))

### FIXED CODE ###

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_list = list(set(ab_list))

px_dict = {}
for i in range(Q):
    p, x = map(int, input().split())
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

out = ""
for v in value_list:
    if v in px_dict:
        x = px_dict[v]
        if v in tree_dict:
            tree_list = tree_dict[v]
            for t in tree_list:
                if t in px_dict:
                    px_dict[t] += x
                else:
                    px_dict[t] = x
        o = str(px_dict[v])
    else:
        o = str(0)
    out += o + " "

print(out[:-1])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n - k + 1):
    ref = sum(p[i: i + k])/2 + k*0.5
    if ref > ans:
        ans = ref

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ref = sum(p[:k])
    ans = ref

    for i in range(1, n - k + 1):
        ref = ref - p[i - 1] + p[i + k - 1]
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()
### BUGGY CODE ###

n = int(input())
if n == 1:
  print(0)
  exit()
li = [i for i in range(n)]
ans = sum(li)
print(ans)

### FIXED CODE ###

n = int(input())
ans = n * (n - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()

st=set()
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            pas=str(s[i])+str(s[j])+str(s[k])
            st.add(pas)


print(len(st))

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(0,10):
    a=s.find(str(i))    #findは文字列を検索して最初のインデックスを返す
    if a==-1:
        continue
    for j in range(0,10):
        b=s.find(str(j),a+1)
        if b==-1:
            continue
        for k in range(10):
            if s.find(str(k),b+1) != -1:
                ans+=1

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

n = int(input())
a=[]
c=1
p=1
for i in input().split():
  if c % 2 ==1:
    a=a+[i]
  else:
    a=[i]+a
  c+=1
  p=p*-1
  
print(*a[::p])


### FIXED CODE ###

n = int(input())
a=input().split()
l=n - n %2-1
e=[i for i in a[l::-2]]  
o=[i for i in a[::2]]
e.extend(o)
if n==1:
  print(*a)
elif n % 2 ==0:
  print(*e)
else:
  print(*e[::-1])
### BUGGY CODE ###

def main():
    # 整数の入力
    N = int(input())
    A = list(map(int, input().split()))

    count = 0
    for i in range(1, N + 1):
        for a in A:
            if a == i:
                count += 1
        print(count)
        count = 0


if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = list(map(int, input().split()))

    counter = np.zeros(N)
    for a in A:
        counter[a - 1] += 1

    for c in counter:
        print(int(c))


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

nums = input().split(" ")
N = int(nums[0])
A = int(nums[1])
B = int(nums[2])
time = 0

while N > (A + B):
  N -= (A + B)
  time += 1
if N - A <= 0:
  print(N + A*time)
else:
  print(A + A*time)

### FIXED CODE ###

nums = input().split(" ")
N = int(nums[0])
A = int(nums[1])
B = int(nums[2])

time = int(N / (A + B))

if time == 0 or (time == 1 and N / (A + B) == 1):
  if N - A <= 0:
    print(N)
  else:
    print(A)
else:
  N -= (A + B) * time
  if N - A <= 0:
    print(N + A*time)
  else:
    print(A + A*time)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1

C = [input() for i in range(H)]
dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
      else:
        break

print(dist[x2][y2])

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

a, b = map(int, input().split())
p = 1
for i in range(a, b + 1):
    p *= i
if p > 0:
    print("Positive")
elif p == 0:
    print("Zero")
else:
    print("Negative")


### FIXED CODE ###

a, b = map(int, input().split())
res = "Positive"
if b < 0:
    if (b - a + 1) & 1:
        res = "Negative"
elif b >= 0:
    if a <= 0:
        res = "Zero"
print(res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
length = int(raw_input())
li = list(map(int,raw_input().split()))
for i in range(length):
    part_li = li[:i]+li[i+1:]
    part_li = sorted(part_li)
    print part_li[length/2-1]

### FIXED CODE ###

# coding: utf-8
# Your code here!
length = int(raw_input())
li = list(map(int,raw_input().split()))
li_sort = sorted(li)
if li_sort[length/2] == li_sort[length/2-1]:
    for i in range(length):
        print li_sort[length/2]
else:
    for i in li:
        if i <= li_sort[length/2-1]:
            print li_sort[length/2]
        else:
            print li_sort[length/2-1]
### BUGGY CODE ###

x,k,d=map(int, input().split()) 
ans = x

for i in range(k):
    if abs(ans) <= d and (k-i)%2 == 0:
        print(abs(ans))
        exit()
    elif ans >= 0:
        ans = ans - d
    elif ans < 0:
        ans = ans + d

print(abs(ans))


### FIXED CODE ###

x,k,d=map(int, input().split()) 
tmp = k

ans = abs(x)%d
k = k - int(abs(x)/d)

if k < 0:
    ans = abs(x)
    ans = ans - (tmp * d)
    print(ans)
    exit()

for i in range(k):
    if abs(ans) <= d and (k-i)%2 == 0:
        print(abs(ans))
        exit()
    elif ans >= 0:
        ans = ans - d
    elif ans < 0:
        ans = ans + d

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

a,b,c=map(int,input().split())
k=int(input())
if a<b:
    if b<c:
        print('Yes')
    else:
        count=0
        while b>=c:
            b*=2
            count+=1
        if count<=k:
            print('Yes')
        else:
            print('No')
else:
    count=0
    while a>=b:
        b*=2
        count+=1
    while b>=c:
        c*=2
        count+=1
    if count<=k:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

a,b,c=map(int,input().split())
k=int(input())
if a<b:
    if b<c:
        print('Yes')
    else:
        count=0
        while b>=c:
            c*=2
            count+=1
        if count<=k:
            print('Yes')
        else:
            print('No')
else:
    count=0
    while a>=b:
        b*=2
        count+=1
    while b>=c:
        c*=2
        count+=1
    if count<=k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    for i in range(n + 1):
        for j in range(n + 1):
            if j > 0:
                t[i][j] += t[i][j - 1]

    ans = [
        str(sum([t[i][q] - t[i][p - 1]
                 for i in range(p, q + 1)]))
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))


### FIXED CODE ###

def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    for i in range(n + 1):
        for j in range(n + 1):
            if j > 0:
                t[i][j] += t[i][j - 1]

    ans = [
        str(sum([t[i][q] - t[i][p - 1]
                 for i in range(p, q + 1)]))
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
act = np.array([[int(item) for item in input().split()] for _ in range(N)])

dp = np.zeros((2, 3), dtype='int64')

for i in range(0,N):
    for j in range(3):
        prev_dp_array = [dp[i%2][k] if k != j else 0 for k in range(3)]
        dp[i%2 ^ 1][j] = max(prev_dp_array + act[i][j])
    # print(dp)
print(np.max(dp))

### FIXED CODE ###

N = int(input())
act = [[int(item) for item in input().split()] for _ in range(N)]

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

for i in range(N):
    for j in range(3):
        temp_hp = []
        for k in range(3):
            if k != j:
                temp_hp.append(dp[i-1][k] + act[i][j])
        dp[i][j] = max(temp_hp)
# print(dp)
print(max(dp[N-1]))
### BUGGY CODE ###

S = list(input())
S.reverse()
def check(s):
    if s[:5] == ["m","a","e","r","d"]:
        del s[:5]
        return True
    elif s[:7] == ["r","e","m","a","e","r","d"]:
        del s[:7]
        return True
    elif s[:5] == ["e","s","a","r","e"]:
        del s[:5]
        return True
    elif s[:6] == ["r","e","s","a","r","e"]:
        del s[:6]
        return True
    else:
        return False

while check(S):
    c = 0

if S == []:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = list(input())
 
while len(a) >= 5:
    if a[-5:] == list('dream'):
        del a[-5:]
        continue
    if a[-7:] == list('dreamer'):
        del a[-7:]
        continue
    if a[-5:] == list('erase'):
        del a[-5:]
        continue
    if a[-6:] == list('eraser'):
        del a[-6:]
        continue
    break
 
if a == []:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]


n = readInt()
M = 10 ** 9 + 7


dp = np.zeros((n + 1, 256), dtype=np.uint32)
dp[0, 255] = 1


for i in range(n):
    for l4 in range(4):
        for l3 in range(4):
            for l2 in range(4):
                for l1 in range(4):
                    j = 64 * l4 + 16 * l3 + 4 * l2 + l1
                    for l0 in range(4):
                        l = (64 * l3 + 16 * l2 + 4 * l1 + l0),

                        if 6 not in [
                            (16 * l2 + 4 * l1 + l0),
                            (16 * l3 + 4 * l1 + l0),
                            (16 * l1 + 4 * l2 + l0),
                            (16 * l2 + 4 * l0 + l1),
                            (16 * l3 + 4 * l2 + l0)
                        ]:
                            dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % M

ret = 0
for v in dp[-1]:
    ret = (ret + v) % M
print(ret)

### FIXED CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]


n = readInt()
M = 10 ** 9 + 7


dp = np.zeros((n + 1, 256), dtype=np.uint32)
dp[0, 255] = 1


for i in range(n):
    for j4 in [0, 64, 128, 192]:
        for j3 in [0, 16, 32, 48]:
            j43 = j4 + j3
            for j2 in [0, 4, 8, 12]:
                j432 = j43 + j2
                for j1 in range(4):
                    j = j432 + j1
                    l321 = 4 * (j3 + j2 + j1)
                    for l0 in range(4):
                        if (6 == (j3 + 4 * j1 + l0)) or (6 == (j3 + j2 + l0)) or (6 == (4 * j2 + 4 * j1 + l0)) or (6 == (16 * j1 + j2 + l0)) or (6 == (4 * j2 + 4 * l0 + j1)):
                            continue
                        l = l321  + l0
                        dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % M

ret = 0
for v in dp[-1]:
    ret = (ret + v) % M
print(ret)
### BUGGY CODE ###

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

min = N
for border in range(N):
    # 入れ替える回数
    count = 0
    for i in range(N):
        if i < border:
            if S[i] == 'W':
                count += 1
        elif i > border:
            if S[i] == 'E':
                count += 1

        if count > min:
            continue

    if count < min:
        min = count

print(min)

### FIXED CODE ###

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

countE = S.count('E')
countW = 0
min = countE + countW
for i in range(N):
    if S[i] == 'E':
        countE -= 1
    elif S[i] == 'W':
        countW += 1

    if countE + countW < min:
        min = countE + countW

print(min)
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(list(map(int, input().split())))

ans = 0

# 2回のループが☓ O(n^2)なので
for i, p in enumerate(P):
    if np.any(P[0:i] < p):
    # if any([True for p2 in P[0:i] if p2 < p]):
        pass
    else:
        ans += 1

print(ans)


### FIXED CODE ###

from itertools import accumulate

N = int(input())
P = list(map(int, input().split()))

ans = 0

"""
for i, p in enumerate(P):
    # if np.any(P[0:i] < p): あまり以下と変わらなかった
    # if any([True for p2 in P[0:i] if p2 < p]): # 2回のループが☓ O(n^2)なので
        pass
    else:
        ans += 1
"""

P_min = list(accumulate(P, min))

for p, p_min in zip(P, P_min):
    if p == p_min:
        ans += 1

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

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[]
for i in range(length):
    if i%2==0:
        num=0
        for j in range(width):
            if i+j>=length:
                break
            num+=s_seqcnt[i+j]
        s_sum.append(num)
# print(s_sum)
print(max(s_sum))


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
s_ruiseki=[0 for i in range(length+1)]
s_ruiseki[0]=0
s_ruiseki[1]=s_seqcnt[0]
for i in range(1,length):
    s_ruiseki[i+1]=s_seqcnt[i]+s_ruiseki[i]
# print(s_ruiseki)
for i in range(length//2+length%2):
    num=0
    if 2*i+width-1>=length:
        s_sum[i]=s_ruiseki[length]-s_ruiseki[2*i]
        break
    else:
        s_sum[i]=s_ruiseki[2*i+width]-s_ruiseki[2*i]
# print(s_sum)
print(max(s_sum))
### BUGGY CODE ###

n, m = map(int, input().split())
al = map(int, input().split())
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1


for i in range(m):
    b, c = map(int, input().split())
    
    keys = list(ad.keys())
    keys.sort()
    for a in keys:

        if a >= c:
            break
        
        k = 0
        if b > ad[a]:
            k = ad[a]
            ad[a] = 0
            b -= k
        else:
            ad[a] -= b
            k = b
            b = 0
        
        if c not in ad:
            ad[c] = k
        else:
            ad[c] += k


sum = 0
for a in ad.keys():
    sum += a * ad[a]

print(sum)

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

LIMIT = 12
luns = []


def make_lunlun(l):
    if len(l) == LIMIT:
        return
    luns.append(int(''.join(list(map(str,l)))))

    if l[-1]!=0:
        make_lunlun(l+[(l[-1]-1)%10])
    make_lunlun(l+[(l[-1])%10])
    if l[-1]!=9:
        make_lunlun(l+[(l[-1]+1)%10])


for i in range(1,10):
    make_lunlun([i])

print(sorted(luns)[k-1])

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

luns = []


def make_lunlun(l):
    if l > 3234566667:
        return
    luns.append(l)

    last = l-l//10*10

    if last!=0:
        make_lunlun(l*10 + last-1)
    make_lunlun(l*10+last)
    if last!=9:
        make_lunlun(l*10 + last+1)


for i in range(1,10):
    make_lunlun(i)

print(sorted(luns)[k-1])
### BUGGY CODE ###

n,m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
l = [0] * (m-1)
ans = 0
if n < m:
  for i in range(m-1):
    l[i] = x[i+1] - x[i]
  for i in range(m-n):
    ans += min(l)
    l.pop(l.index(min(l)))
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
x = sorted(list(map(int, input().split())))
l = [0] * (m-1)
if n >= m:
  print(0)
  exit()
else:
  for i in range(m-1):
    l[i] = x[i+1] - x[i]
  print(sum(sorted(l)[:m-n]))
### BUGGY CODE ###

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

a_types = set(A)

count_dict = {}
for each in a_types:
    count_dict[each] = A.count(each)

all_types = 0
for value in count_dict.values():
    all_types += value * (value - 1) // 2

# result_dict = {}
# for each in a_types:
#     result_dict[each] = all_types - count_dict[each] + 1

for a in A:
    print(all_types - count_dict[a] + 1)

### FIXED CODE ###

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

c = [0]*n

for i in range(n):
    c[a[i]-1] = c[a[i]-1] + 1
    
total = 0
for x in c:
    total = total + x*(x-1)//2

for i in range(n):
    print(total - c[a[i]-1] + 1)
### BUGGY CODE ###

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
la=N

def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
    else:
        l[X]=l[Y]
        if r[X]==r[Y]:
            r[Y]+=1

for i in range(M):
    union(a[i],b[i])

for i in range(N+1):
    l[i]=find(i)
t=[]
for i in range(N+1):
    p=l.count(l[i])-1
    indexes = [j for j, x in enumerate(a) if x == i]
    for j in range(len(indexes)):
        if l[b[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(b) if x == i]
    for j in range(len(indexes)):
        if l[a[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(d) if x == i]
    for j in range(len(indexes)):
        if l[c[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(c) if x == i]
    for j in range(len(indexes)):
        if l[d[indexes[j]]] == l[i]:
            p -= 1
    t.append(p)

print(" ".join(map(str, t[1:])))


### FIXED CODE ###

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
size=[1]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
        size[X]+=size[Y]
    else:
        l[X]=l[Y]

        if r[X]==r[Y]:
            r[Y]+=1
        if X!=Y:
            size[Y] += size[X]
for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

t=[]
for i in range(N+1):
    p=size[find(i)]-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))
### BUGGY CODE ###

import collections
n = int(input())
log = []
arr = []
ans = 0
for _ in range(n):
  S = sorted(list(input()))
  s = ''.join(S)
  if s not in log:
    log.append(s)
    arr.append(1)
  else:
    i = log.index(s)
    ans += arr[i]
    arr[i] += 1
    
print(ans)
  



### FIXED CODE ###


n = int(input())
arr = {}
ans = 0
for _ in range(n):
  S = sorted(list(input()))
  s = ''.join(S)
  if s in arr:
    ans += arr[s]
    arr[s] += 1
  else:
    arr[s] = 1
print(ans)
### BUGGY CODE ###

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

s = b + c
counter = 1
ans = 0
while True:
  if a < s * counter:
    ans = b*(counter-1)
    if a - (s * (counter-1)) <= b:
      ans += a - (s * (counter-1))
    else:
      ans += b
    break
  else:
    counter += 1

print(ans)


### FIXED CODE ###

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

s = b + c

counter = a//s
ans = b*counter
if a - (s * counter) <= b:
  ans += a - (s * counter)
else:
  ans += b

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

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
    
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    ans = 0
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            break
if ans <= 10**18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
lr = []
for i in range(Q):
    k = map(int, input().split())
    lr.append(k)

index = []
result = re.finditer('AC', S)
for r in result:
    index.append(r.start())

for i in range(Q):
    count = 0
    l, r = lr[i]
    for ind in index:
        if ind >= l-1 and ind <= r-2:
            count += 1
    print(count)


### 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])