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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), a.count(3)]

    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(A[3]+1):
        for j in range(A[2]+A[3] + 1 - k):
            for i in range(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                P = N * 1.0
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P / (i+j+k)

    print(dp[A[1]][A[2]][A[3]])
main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用色リスト
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
    maxi=max(maxi,len(d[a[i]-1]),len(d[b[i]-1]))

v=deque([0])
e[0]=0
all=set(i+1 for i in range(maxi) )

while len(v)>0:
  k=v.popleft()
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
    
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

def conb(m, n):
    a = 1
    for i in range(n-m):
        a *= n - i
        a //= i+1
    return a

N, M, K = map(int, input().split())

sum = 0
c = conb(K-2, N*M-2)
for m in range(M):
    sum += c * (M-m) * (N**2) * m
    sum %= 1000000007
for n in range(N):
    sum += c * (N-n) * (M**2) * n
    sum %= 1000000007

print(sum)

### FIXED CODE ###

mod = 10**9 + 7
 
 
def comb(n, k):
    x, y = 1, 1
    k = min(k, n - k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod

N, M, K = map(int, input().split())

c = comb(N*M-2,K-2)

ans = c * (M**2 * (N**2 * (N+1)//2 - N*(N+1)*(2*N+1)//6) + N**2 * (M**2 * (M+1)//2 - M*(M+1)*(2*M+1)//6)) % mod

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

n,a,b = (int(x) for x in input().split())
mod = pow(10,9)+7

def minus(k):
    x,y =1,1
    for i in range(k):
        x*=(n-i)%mod
        y*=(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(a)-minus(b)
while ans<0:
    ans+=mod
print(ans%mod)


### FIXED CODE ###

n,a,b = map(int, input().split())
mod = 10**9+7

def minus(n,k):
    x,y =1,1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(n,a)-minus(n,b)
while ans<0:
    ans+=mod
print(ans)
### BUGGY CODE ###

x,y=map(int, input().split())
while not (x == 0 and y == 0) :
 if x < y : print(x, y)
 else : print(y, x)

### FIXED CODE ###

x, y = map(int, input().split())
while not( x == 0 and y == 0 ):
 if x < y : print(x, y)
 else : print(y, x)
 x, y = map(int, input().split())
### BUGGY CODE ###

n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  elif i<x and y-(y-x)//2+1<=j<=y:
    d=y-j+1+x-i
  elif x<=i<=x+(y-x)//2-1 and y<j:
    d=j-y+1+i-x
  elif x<=i and j<=y:
    d=min(j-i,i+y-x+1-j)
  elif i<x and y<j:
    d=j-y+1+x-i
  else:
    d=j-i
  return d
distmap=[dist(k+1,l+1) for k in range(n-1) for l in range(n)]
[print(distmap.count(i+1)) for i in range(n-1)]

### FIXED CODE ###

n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  else:
    d=min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
  return d
distmap=[0]*n
for l in range(2,n+1):
  for k in range(1,l):
    distmap[dist(k,l)]+=1
print('\n'.join(map(str,distmap[1:])))
### BUGGY CODE ###

N, K = map(int, input().split())
p = tuple(map(int, input().split()))

E = [None]*N
for i in range(N):
    E[i] = sum(range(1, p[i]+1))/p[i]

max = 0
ite = N - K
for i in range(ite+1):
    tmp = sum(E[i:K+i])
    if tmp > max:
        max = tmp

print(max)

### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
p = tuple(map(int, sys.stdin.readline().split()))

max = 0
ite = N - K
base = sum(p[0:K])
max = base
index = 0
for i in range(ite):
    tmp = base + p[i+K] - p[i]
    if tmp > max:
        max = tmp
        index = i+1
    base = tmp

E = [(1+p[index+i])/2 for i in range(K)]
print(sum(E))
### BUGGY CODE ###

N = int(input())

c = 0
for i in range(1, N):
    c += i

print(c)


### FIXED CODE ###

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

N = int(input())
S = [sorted(input()) for i in range(N)]
SS = []
for i in S:
    SS.append("".join(i))
count = 0

SSS = set(SS)

for i in SSS:
    A = SS.count(i)
    count += (A*(A-1)) // 2

print(count)

### FIXED CODE ###

N = int(input())
S = [sorted(list(input())) for _ in range(N)]
import collections
A = []
for a in S:
    A.append("".join(a))
count = 0
c = collections.Counter(A)
for a in c.values():
    count += a*(a-1)//2

print(count)
### BUGGY CODE ###

h, w = map(int,input().split())
#alist = list(map(int, input().split()))

road=[]

for i in range(h):
    row=input()
    road.append(row)

ikel=0

for i in range(h):
    for j in range(w):
        if road[i][j]=='.':
            ikel+=1

maxrecord=0

for i in range(h):
    for j in range(w):
        turn=1
        ima=1
        now=[[i, j]]
        rlist=[]
        for hh in range(h):
            rlist.append([999]*w)
        rlist[i][j]=0
        while ima<ikel:
            #while turn<10:
            koho=[]
            for nw in now:
                koho.append([nw[0]-1, nw[1]])
                koho.append([nw[0]+1, nw[1]])
                koho.append([nw[0], nw[1]-1])
                koho.append([nw[0], nw[1]+1])
            #print(rlist)
            now=[]
            for kh in koho:
                if kh[0]>=0 and kh[1]>=0 and kh[0]<h and kh[1]<w:
                    #print(kh)
                    if road[kh[0]][kh[1]]=='.':
                        #print(kh, rlist[kh[0]][kh[1]])
                        if rlist[kh[0]][kh[1]]>turn:
                            #print(kh)
                            rlist[kh[0]][kh[1]]=turn
                            now.append([kh[0], kh[1]])
                            ima+=1
                            record=turn
            turn+=1
        #print('result', rlist)
        if record>maxrecord:
            maxrecord=record

print(maxrecord)

### FIXED CODE ###

h, w = map(int,input().split())
#alist = list(map(int, input().split()))

road=[]

for i in range(h):
    row=input()
    road.append(row)

ikel=0

for i in range(h):
    for j in range(w):
        if road[i][j]=='.':
            ikel+=1

maxrecord=0

for i in range(h):
    for j in range(w):
        turn=1
        ima=1
        now=[[i, j]]
        rlist=[]
        for hh in range(h):
            rlist.append([999]*w)
        rlist[i][j]=0
        if road[i][j]=='.':
            while ima<ikel:
                koho=[]
                for nw in now:
                    if nw[0]>0:
                        koho.append([nw[0]-1, nw[1]])
                    if nw[0]<h-1:
                        koho.append([nw[0]+1, nw[1]])
                    if nw[1]>0:
                        koho.append([nw[0], nw[1]-1])
                    if nw[1]<w-1:
                        koho.append([nw[0], nw[1]+1])
                now=[]
                for kh in koho:
                    if road[kh[0]][kh[1]]=='.':
                        if rlist[kh[0]][kh[1]]>turn:
                            rlist[kh[0]][kh[1]]=turn
                            now.append([kh[0], kh[1]])
                            ima+=1
                            record=turn
                turn+=1
            if record>maxrecord:
                maxrecord=record

print(maxrecord)
### BUGGY CODE ###

def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += s1[i - 1]
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]


s1 = input()
s2 = input()

print(LCS_iter(s1, s2))


### FIXED CODE ###

def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += s1[i - 1]
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]
 
 
s1 = input()
s2 = input()
 
print(LCS_iter(s1, s2))
### BUGGY CODE ###

import numpy as np
import sys
n = int(input())
a = np.array(sys.stdin.read().split(), dtype=np.int64)
mod = 10 ** 9 + 7
ans = [0] * 60
for x in a:
    x = bin(x)[2:].zfill(60)
    for i in range(60):
        ans[i] += int(x[i])
for i in range(60):
    ans[i] = ans[i] * (n - ans[i]) % mod
    ans[i] = ans[i] * pow(2, 59 - i, mod) % mod
ans_sum = 0
for x in ans:
    ans_sum = (ans_sum + x) % mod
print(ans_sum)

### FIXED CODE ###

import numpy as np
import sys
n = int(input())
a = np.array(sys.stdin.read().split(), dtype=np.int64)
mod = 10 ** 9 + 7
ans = 0
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    x = x * (n - x)
    ans += x * pow(2, i, mod) % mod
print(ans % mod)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    B=[0]*n
    while True:
        for i in range(1,n):
            B[i]=A[i-1]-B[i-1]
        if B[0]==A[-1]-B[-1]:
            print(*[2*x for x in B])
            break
        B[0]+=1
    

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    B=[0]*n
    B[0]=sum(A)-sum(A[1::2])*2
    for i in range(1,n):
        B[i]=(A[i-1]-B[i-1]//2)*2
    print(*B)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
S = 0
MOD = 1000000007

for i in range(N - 1):
    for j in range(i + 1, N):
        S += A[i] ^ A[j]
        
ans = S % MOD
print(ans)

### FIXED CODE ###

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

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

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

# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

INF = 100000000

def solve(v, e, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        if i in dic:
            for t, d in dic[i]:
                dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, e, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")


### FIXED CODE ###

# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

from heapq import heappush, heappop

INF = 10000000000

def solve(r, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        if vtx not in dic:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(r, v, dic)
for t in range(0, v):
    print(dp[t] if dp[t] != INF else "INF")
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

S = readline().rstrip()
gx,gy = map(int,readline().split())

C = []

import itertools
for key,g in itertools.groupby(S):
  C.append([key,len(list(g))])
  
x,y = 0,0
ind = 0
if C[0][0] == "F":
  x += C[0][1]
  ind = 1

# Xの方向を向いている
dirX = True
now = set([(x,y)])
for i in range(ind,len(C)):
  if C[i][0] == "F":
    step = C[i][1]
    nex = set()
    if dirX:
      for n in now:
        nex.add((n[0] + step,n[1]))
        nex.add((n[0] - step,n[1]))
    else:
      for n in now:
        nex.add((n[0],n[1] + step))
        nex.add((n[0],n[1] - step))
    now = nex
  else:
    if C[i][1] % 2 == 1:
      dirX ^= True
    
if (gx,gy) in now:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S = input()
X,Y = map(int,input().split())

# [文字,その文字が連続する数]
from collections import deque
sumS = deque()
import itertools
for key,g in itertools.groupby(S):
  sumS.append([key,len(list(g))])
  
startx = 0 # Fで始まる場合はX軸の正の方向にあらかじめ進めて置く
# 最初のTが出るまではX軸正の方向に進む
if sumS[0][0] == "F":
  startx = sumS[0][1]
  sumS.popleft()

xdir = True # X軸方向を向いている
dpXcur = set()
dpXcur.add(startx)
dpYcur = set()
dpYcur.add(0) # Y軸は必ず0から始まる
dpXnex = set()
dpYnex = set()
for i in range(len(sumS)):
  if sumS[i][0] == "F":
    steps = sumS[i][1] # 進む数
    if xdir: # X軸方向を向いている場合
      for x in dpXcur:
        dpXnex.add(x + steps)
        dpXnex.add(x - steps)
      dpXcur = dpXnex
      dpXnex = set()
    else:
      for y in dpYcur:
        dpYnex.add(y + steps)
        dpYnex.add(y - steps)
      dpYcur = dpYnex
      dpYnex = set()
  elif sumS[i][0] == "T":
    turns = sumS[i][1] # 方向転換する数
    if turns % 2 == 1:
      # 奇数回の場合はX/Y軸の切り替え (偶数回の場合は何も起こらない)
      xdir ^= True
      
if X in dpXcur and Y in dpYcur:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flag] != -1:
        return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
            ret %= MOD
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
            ret %= MOD

    memo[digit][current_sum][flag] = ret
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        left = j
        right = N
        v = L[i] + L[j]
        while right - left > 1:
            mid = (left + right) // 2
            if L[mid] < v:
                left = mid
            else:
                right = mid
        cnt += left - j
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        a = L[i]
        b = L[j]
        v = bisect.bisect_left(L, a + b)
        cnt += v - j - 1
print(cnt)
### BUGGY CODE ###

N = int(input())
Alist = list(map(int,input().split(" ")))
ansList = list(range(N))
count = 0
for i in range(N):
    flag = False
    for j in range(N):
        if i != j:
            if (Alist[i]%Alist[j]==0):
                flag = True
    if flag==False:
        count+=1


print(count)

### FIXED CODE ###

N = int(input())
Alist = list(map(int,input().split(" ")))
Alist.sort()
Amax = Alist[-1]
dp = [1]*(Amax+1)
count = 0
for i in range(len(Alist)-1):
    p = Alist[i]
    if dp[p] == 1:
        for j in range(Amax//p+1):
            dp[p*j] = 0
        if Alist[i] != Alist[i+1]:
            count+=1
if dp[Amax] == 1:
    count += 1
print(count)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
#  LR = []
#  for i in range(Q):
#      LR.append(LI())
#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
for _ in range(Q):
    l,r = LI()
    tmp = S[l-1:r]
    result.append(tmp.count('AC'))
for i in result:
    print(i)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(end-start)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def root(x):
    global par
    global d2p
    if par[x] == x:
        return (x, 0)
    else:
        r = root(par[x])
        par[x] = r[0]
        d2p[x] += r[1]
        #print(par, d2p)
        return (r[0], d2p[x])


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx, dx = root(x)
    ry, dy = root(y)
    if rx != ry:
        par[rx] = ry
        d2p[rx] = dy + d - dx
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * m
r = [0] * m
d = [0] * m

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

if f and max(d2p) <= 10**9:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import queue

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

for i in range(1, n + 1):
    if not v_asn[i]:
        q = queue.Queue()
        v_asn[i] = True
        q.put(i)
        while not q.empty():
            qi = q.get()
            for a in g[qi]:
                if not v_asn[a[0]]:
                    v_asn[a[0]] = True
                    v[a[0]] = v[qi] + a[1]
                    q.put(a[0])
                else:
                    if v[a[0]] != v[qi] + a[1]:
                        f = False
                        break
        if not f:
            break

if f:
    print("Yes")
else:
    print("No")