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

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n-1)]

    adj = [[] for _ in range(n)]
    for a,b in ab:
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)


    c = [[0]*n for _ in range(n)]
    d = deque([[0, 0]])
    visited = [0]*n
    visited[0] = 1
    c_l = [i for i in range(1, k+1)]
    while d:
        node, color = d.popleft()
        if color == 0:
            color_list = c_l
        else:
            color_list = c_l[:color-1] + c_l[color:]
        cnt = 0
        for x in adj[node]:
            if visited[x]:
                continue
            visited[x] = 1
            c[node][x] = color_list[cnt]
            d.append([x, color_list[cnt]])
            cnt += 1

    for a,b in ab:
        print(c[a-1][b-1])

    # c = [[0]*n for _ in range(n)]
    # visited = [0]*n
    # def dfs(node):
    #     visited[node] = 1
    #     color = 1
    #     for nextnode in adj[node]:
    #         if visited[nextnode]:
    #             continue
    #         c[node][nextnode] = color
    #         dfs(nextnode)
    #         color += 1


    # c = [[] for _ in range(n)]
    # for a,b in ab:
    #     a -= 1
    #     b -= 1
    #     for i in range(1, k+1):
    #         if not i in c[a] and not i in c[b]:
    #             c[a].append(i)
    #             c[b].append(i)
    #             print(i)
    #             break


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n-1)]

    adj = [[] for _ in range(n)]
    order = []
    for a,b in ab:
        adj[a-1].append(b-1)
        order.append(b-1)

    

    c = [0]*n
    d = deque([0])
    while d:
        v = d.popleft()
        cnt = 1
        for nv in adj[v]:
            if c[v] == cnt:
                cnt += 1
            c[nv] = cnt
            cnt += 1
            d.append(nv)

    print(max(c))

    for i in order:
        print(c[i])

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

K, S = map(int, input().split())


counter = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if x + y + z == S and 0 <= z <= K:
            counter += 1
print(counter)


### FIXED CODE ###

K, S = map(int, input().split())

counter = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            counter += 1
print(counter)
### BUGGY CODE ###

import sys
from collections import deque
import copy
import math
def main():
    N, K = map(int, input().split())
    a = [float(i) for i in input().split()]
    A = [0] * (N + 1)
    if K >= N:
        for i in range(1, N+1):
            if i > 1:
                print(' ', end='')
            print(N, end='')
        print()
        sys.exit()
    for i in range(1, N+1):
        A[i] = a[i - 1]
    for _ in range(K):
        count = [0] * (N + 1)
        for i in range(1, N+1):
            if A[i] >= N:
                left_d = 1
                right_d = N
            else:
                left_d = math.ceil(i - A[i] - 0.5)
                right_d =  math.floor(i + A[i] + 0.5)
                if left_d < 1:
                    left_d = 1
                if right_d > N:
                    right_d = N
            for j in range(left_d, right_d+1):
                count[j] += 1
        A = copy.copy(count)
        flag = True
        for i in range(1, N+1):
            if A[i] != N:
                flag = False
                break
        if flag:
            break
    for i in range(1, N+1):
        if i > 1:
            print(' ', end='')
        print(A[i], end='')
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
import math
def main():
    N, K = map(int, input().split())
    a = [int(i) for i in input().split()]
    A = [0] * (N + 1)
    if K >= 41:
        for i in range(1, N+1):
            if i > 1:
                print(' ', end='')
            print(N, end='')
        print()
        sys.exit()
    for i in range(1, N+1):
        A[i] = a[i - 1]
    for _ in range(K):
        count = [0] * (N + 1)
        for i in range(1, N+1):
            left_d = max(math.ceil(i - A[i]), 1)
            right_d = min(math.floor(i + A[i]), N)
            count[left_d] += 1
            if right_d + 1 <= N:
                count[right_d + 1] -= 1
        for i in range(1, N+1):
            count[i] += count[i - 1]
        A = copy.copy(count)
    
    for i in range(1, N+1):
        if i > 1:
            print(' ', end='')
        print(A[i], end='')
    print()


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

N = int(input())
A = [int(i) for i in input().split()]
  
O = [0] * N

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    O[i] ^= A[j]

print(' '.join([str(s) for s in O]))

### FIXED CODE ###

N = int(input())
SUM = 0
A = []
O = []
for i in input().split():
  i = int(i)
  SUM ^= i
  A.append(i)

for a in A:
  O.append(SUM ^ a)

print(' '.join([str(s) for s in O]))
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

pows = []
for i in range(N):
    pows.append(my_pow(2, i, MOD))

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

pows = [1] * N
for i in range(1, N):
    pows[i] = (pows[i - 1] * 2) % MOD

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)
### BUGGY CODE ###

import numpy as np
A = 'Yes'
N = int(input())
t = np.array([[0,0,0]])
for n in range(N):
     a = [[int(i) for i in input().split()]]
     t = np.append(t, np.array(a), axis=0)
     diff = t[n+1] -t[n]
     cond = np.abs(diff[1]) + np.abs(diff[2])
     if cond > diff[0]:
        A='No'
        break
     if np.sum(np.array(a)) % 2 ==1:
        A = 'No'
        break
print(A)

### FIXED CODE ###

N = int(input())
t_list = [0]
x_list = [0]
y_list = [0]
A = 'Yes'
for i in range(N):
    ti, xi, yi = map(int, input().split())
    t_list.append(ti)
    x_list.append(xi)
    y_list.append(yi)
    if ((abs(x_list[i+1] - x_list[i]) + abs(y_list[i+1] - y_list[i]) > (t_list[i+1] - t_list[i]))):
        A = 'No'
        break
    if (x_list[i+1] + y_list[i+1] - t_list[i+1])%2 != 0:
        A = 'No'
        break
print(A)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
V=list()
for i in range(N-K+1):
  a=1
  for j in range(K):
    a=a*A[(i+j)]
  V.append(a)
for i in range((N-K)):
  if V[i]<V[i+1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
V=list()
for i in range(N-K):
  if A[i]<A[K+i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
count=0
before=0
now=1


for i in range(N):
    now*=A[i]
    if i+1>K:
        now=now/A[i-K]
        if now>before:
            print("Yes")
        else:
            print("No")
    if i+1>=K:
        before=now

### FIXED CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
count=0
before=0
now=1


for i in range(K,N):
    if A[i]>A[i-K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# https://atcoder.jp/contests/agc011/tasks/agc011_b

import sys
input = sys.stdin.buffer.readline

n = int(input())
A = sorted([int(i) for i in input().strip().split()])
_max = A[-1]
cul_sum = [0] * (n + 1)

for i in range(1, n + 1):
    cul_sum[i] = cul_sum[i - 1] + A[i - 1]

ans = -1

cur = 0
ptr = cur
_tmp = cul_sum[ptr]
while True:
    _tmp += A[ptr]
    if _tmp * 2 >= _max:
        ans = cur
        break
    elif _tmp * 2 < A[ptr + 1]:
        cur += 1
        ptr = cur
        _tmp = cul_sum[ptr]
    else:
        ptr += 1

print(n - ans)


### FIXED CODE ###

# https://atcoder.jp/contests/agc011/tasks/agc011_b

import sys
input = sys.stdin.buffer.readline

n = int(input())
A = sorted([int(i) for i in input().strip().split()])
_max = A[-1]
cul_sum = [0] * (n + 1)

for i in range(1, n + 1):
    cul_sum[i] = cul_sum[i - 1] + A[i - 1]

ptr = 0
for i in range(1, n + 1):
    if cul_sum[i] * 2 < A[i]:
        ptr = i
    elif cul_sum[i] * 2 >= _max:
        print(n - ptr)
        sys.exit()
### BUGGY CODE ###

N = int(input())
a = input().rstrip().split()
ans = 0
p = [0]*N
for i in range(N):
  p[i] = int(a[i])
for i in range(N):
  if i == 0:
    ans += 1
  else:
    Plus = True
    for i2 in range(i):
      if p[i2] <= p[i]:
        Plus = False
    if Plus == True:
      ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
a = input().rstrip().split()
P = [0] * N
for i in range(N):
  P[i] = int(a[i])
minP = P[0]
ans = 1
for i in range(N - 1):
  if minP >= P[i + 1]:
    ans += 1
    minP = P[i + 1]
print(ans)
### BUGGY CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb_flag = [[False for i in range(w)] for j in range(h)]

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb_flag[_h - 1][_w - 1] = True

h_max = max(h_cnt)
w_max = max(w_cnt)
flag = True

for i in range(h):
  if not flag:
    break
  if h_cnt[i] != h_max:
    continue
  for j in range(w):
    if w_cnt[j] != w_max:
      continue
    if not bomb_flag[i][j]:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)

### FIXED CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb = set()

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb.add(((_h - 1),(_w - 1)))

h_max = max(h_cnt)
w_max = max(w_cnt)

max_h = []
max_w = []

for i in range(h):
  if h_cnt[i] == h_max:
    max_h.append(i)

for j in range(w):
  if w_cnt[j] == w_max:
    max_w.append(j)

flag = True

for i in max_h:
  for j in max_w:
    if (i, j) not in bomb:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
E - Travel by Car
https://atcoder.jp/contests/abc143/tasks/abc143_e

"""
import sys


def warshall_floyd(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                new_cost = d[i][k] + d[k][j]
                if new_cost < d[i][j]:
                    d[i][j] = new_cost

def main(args):
    N, M, L = map(int, input().split())
    g1 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        g1[i][i] = 0
    for _ in range(M):
        A, B, C = map(int, input().split())
        g1[A][B] = g1[B][A] = C
    warshall_floyd(g1, N+1)

    g2 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        for j in range(N+1):
            if i == j:
                g2[i][j] = 0
            elif g1[i][j] <= L:
                g2[i][j] = g2[j][i] = 1
    warshall_floyd(g2, N+1)
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(-1 if g2[s][t] == float('inf') else g2[s][t] - 1)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
E - Travel by Car
https://atcoder.jp/contests/abc143/tasks/abc143_e

"""
import sys


from scipy.sparse.csgraph import floyd_warshall

def main(args):
    N, M, L = map(int, input().split())
    g1 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        g1[i][i] = 0
    for _ in range(M):
        A, B, C = map(int, input().split())
        g1[A][B] = g1[B][A] = C
    d1 = floyd_warshall(g1)
    g2 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        for j in range(N+1):
            if i == j:
                g2[i][j] = 0
            elif d1[i][j] <= L:
                g2[i][j] = g2[j][i] = 1
    d2 = floyd_warshall(g2)
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(-1 if d2[s][t] == float('inf') else int(d2[s][t]) - 1)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

while True:
    inNums = input().strip().split()
    a = int(inNums[0])
    b = int(inNums[1])
    temp = a+b
    x = 0
    digitNum = 0
    while temp // 10**x > 0:
        digitNum = x
        print(x)
    
    if inNums == None:
        break
    break

### FIXED CODE ###

import sys

for s in sys.stdin:
  a,b = map(int,s.split())
  print(len(str(a+b)))
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC113 C

n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
for p,y in py:
    mi = 1
    for i,j in py:
        if p == i:
            if y > j:
                mi += 1
    p = '00000'+ str(p)
    mi = '00000' + str(mi)
    print(p[-6:]+mi[-6:])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC113 C

from operator import itemgetter
n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    py[i].append(i)
py.sort(key = itemgetter(1))
py.sort(key = itemgetter(0))

x = py[0][0]
c = 0
for i in range(m):
    if x != py[i][0]:
        c = 1
        x = py[i][0]
    else:
        c += 1
    py[i].append(c)
py.sort(key = itemgetter(2))
for i in range(m):
    front = '00000'+str(py[i][0])
    back = '00000'+str(py[i][3])
    print(front[-6:]+back[-6:])
### BUGGY CODE ###

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop()
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    if not (dot[1] - 1 < 0):
        queue.append([dot[0],dot[1]-1,dot[2]])
    if not (dot[1] + 1 >= w):
        queue.append([dot[0],dot[1]+1,dot[2]])
    if not (dot[0]+1 >= h):
        queue.append([dot[0]+1,dot[1],dot[2]])
    if not (dot[0]-1 < 0):
        queue.append([dot[0]-1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            if not(dot[0]+ x < 0 or dot[1]+y < 0 or dot[0]+x >= h or dot[1]+y >= w):
                if not(used_map[dot[0]+x][dot[1]+y] > -1 and used_map[dot[0]+x][dot[1]+y] <= dot[2]+1):
                    queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])

### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]

    A=[0 for i in range(len(subS))]

    for i in range(1,len(subS)-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<len(subS) and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

### FIXED CODE ###

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

# Zアルゴリズムで解く

def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        # prefixが同じ間length加算
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        # prefixの一致数保存
        A[left] = length
        
        # 一文字一致していなければ戻る
        if length == 0:
            left+=1
            continue
        
        # lengthの分だけleftとindexの間を埋めていく(はみ出ていないとこまで)
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)
### BUGGY CODE ###

from collections import Counter
S = input()
T = input()

for w in list(S):
    if w in list(T):
        S = list(S)
        T = list(T)
        #print(S, T)
        idxs = [i for i, x in enumerate(S) if x == w]
        idxt = [i for i, x in enumerate(T) if x == w]
        for num in idxs[::-1]:
            del S[num]
        for num in idxt[::-1]:
            del T[num]
        S = ''.join(S)
        T = ''.join(T)

s_count = Counter(S)
del_s = []
t_count = Counter(T)
del_t = []

for ks, vs in list(s_count.items()):
    for kt, vt in list(t_count.items()):
        if vs == vt:
            del_s.append(ks)
            del_t.append(kt)
            del s_count[ks]
            del t_count[kt]
            break

if len(set(S)) == len(del_s) and len(set(T)) == len(del_t):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict
S = list(input())
T = list(input())
l = len(S)
ds = defaultdict(str)
dt = defaultdict(str)
for i in range(l):
    if ds[S[i]] == "":
        ds[S[i]] = T[i]
    elif ds[S[i]] == T[i]:
        pass
    else:
        print('No')
        exit()
    if dt[T[i]] == "":
        dt[T[i]] = S[i]
    elif dt[T[i]] == S[i]:
        pass
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

N, Q = (int(i) for i in input().split())
S = input()
l = []
r = []
for i in range(Q):
    a, b = (int(i) for i in input().split())
    l.append(a)
    r.append(b)

#print(N, Q, l, r)
#print(S)

for i in range(Q):
    pre_str = S[l[i]-1:r[i]]
    print(pre_str.count('AC'))

### FIXED CODE ###

N, Q = (int(i) for i in input().split())
S = input()
l = []
r = []
for i in range(Q):
    a, b = (int(i) for i in input().split())
    l.append(a)
    r.append(b)

t = [0] * (N+1)
for i in range(N):
    #pre_str = S[l[i]-1:r[i]]
    #print(pre_str.count('AC'))
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    print(t[r[i]-1] - t[l[i]-1])
### BUGGY CODE ###

n,m=list(map(int,input().split(" ")))
al=[0 for i in range(n)]
bl=[0 for i in range(n)]
for i in range(n):
    al[i],bl[i]=list(map(int,input().split(" ")))
have=0
yen=0
while have<m:
    k= [i for i, x in enumerate(al) if x == min(al)]
    lengh=len(k)
    pri=al[k[0]]
    for i in range(lengh):
        num=0
        num+=bl[k[i]]
        al[k[i]]=10**9+1
    have+=num
    yen+=pri*num
if have>m:
    yen-=(have-m)*pri
print(yen)

### FIXED CODE ###

n,m=list(map(int,input().split(" ")))
l=[]
l=[list(map(int,input().split(" "))) for i in range(n)]
have=0
yen=0
i=0
l.sort(key=lambda x: x[0])
while have<m:
    pri=l[i][0]
    num=l[i][1]
    i+=1
    have+=num
    yen+=pri*num
if have>m:
    yen-=(have-m)*pri
print(yen)
### BUGGY CODE ###

import sys
from fractions import Fraction
import math
input = sys.stdin.readline

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

s = sum(a)

w = [(k * a[i]) // s for i in range(n)]
b = [Fraction(a[i] / (w[i] + 1)) for i in range(n)]

r = k - sum(w)

for i in range(r):
    b.sort()
    b[-1] = Fraction(b[-1].numerator, b[-1].denominator + 1)

b.sort()

print(math.ceil(b[-1]))

### FIXED CODE ###

import sys
from fractions import Fraction
import math
import heapq
input = sys.stdin.readline

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

s = sum(a)

w = [(k * a[i]) // s for i in range(n)]
b = [Fraction((w[i] + 1), a[i]) for i in range(n)]

r = k - sum(w)

heapq.heapify(b)
#print(b)

for i in range(r):
    x = heapq.heappop(b)
    heapq.heappush(b, Fraction(x.numerator+1, x.denominator))

y = heapq.heappop(b)

print(math.ceil(Fraction(y.denominator, y.numerator)))