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

# D - Dice in Line

N, K = map(int, input().split())
P = [int(p) for p in input().split()]
mx = 0
mx_i = 0
for i in range(N - K + 1):
    if mx < sum(P[i:i + K]):
        mx = sum(P[i:i + K])
        mx_i = i

total = 0
for i in range(mx_i, mx_i + K):
    for j in range(1, P[i] + 1):
        total += j / P[i]

print(total)


### FIXED CODE ###

# D - Dice in Line

N, K = map(int, input().split())
P = [int(p) for p in input().split()]

Q = [0] * (N + 1)
for i in range(N):
    q = ((1 + P[i]) * P[i] / 2) / P[i]
    Q[i + 1] = Q[i] + q

mx = 0
for i in range(N - K + 1):
    mx = max(mx, Q[i + K] - Q[i])

print(mx)
### BUGGY CODE ###

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

from1 = []
toN = []
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1.append(a if a!=1 else b)
  if a == N or b == N:
    toN.append(a if a!=N else b)

F = False

for i in from1:
  for j in toN:
    if i == j:
      F = True
      break
  if F:
    break
print("POSSIBLE" if F else "IMPOSSIBLE")

### FIXED CODE ###

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

from1 = [False]*max(N,M)
toN = [False]*max(N,M)
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1[a-1 if a!= 1 else b-1]=True
  if a == N or b == N:
    toN[a-1 if a!= N else b-1]=True
cnt =0 
for i in range(M):
  cnt+=from1[i]&toN[i]
print("POSSIBLE" if cnt else "IMPOSSIBLE")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():

    """
    # color: 親と自らを繋ぐ辺の色
    # now: 現在地
    """
    def dfs(color,now):
        # 現在地が葉のとき
        if not now in a:
            return

        # 現在地から伸びる辺のインデックス
        index = [i for i in range(N-1) if now == a[i]]

        # 子ノードに伸びる辺を色塗り
        number = 1
        for i in index:
            if number == color:
                number += 1
            K[i] = number
            # 子ノードで色塗り開始
            dfs(number, b[i])
            number += 1

    N = int(input())
    a = [0] * (N-1)
    b = [0] * (N-1)
    for i in range(N-1):
        a[i],b[i] = map(int,input().split())
    # 辺の色
    K = [0] * (N-1)
    dfs(0,min(a))
    print(len(set(K)))
    for i in K:
        print(i)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]

# graph[i]: 頂点iの親と子の集合
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 根
root = 1
# parent[i]: 頂点iの親
parent = [0]*(N+1)
# トポロジカル順序
order = []
# 未探索の頂点
stack = [root]

# dfsでparentを求める
while stack:
    # n: 探索する頂点
    n = stack.pop()
    order.append(n)
    for j in graph[n]:
        # jがnの親の場合
        if j == parent[n]:
            continue
        parent[j] = n
        stack.append(j)

# color[i]: 頂点iと親を繋ぐ辺の色
color = [-1] * (N+1)
# dfsで色を塗る
for i in order:
    # 既に使用した色
    ng = color[i]
    # 色
    c = 1
    for j in graph[i]:
        # jがiの親の場合(塗装済みなのでcontinue)
        if j == parent[i]:
            continue
        if c == ng:
            c += 1
        # 頂点iと頂点jの辺に色を塗る
        color[j] = c
        c += 1

# 入力順に辺の色を出力する
answer = [color[a] if parent[a]==b else color[b] for a,b in AB]
print(max(answer))
print("\n".join(map(str,answer)))
### BUGGY CODE ###

import bisect
import itertools

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

t = list(itertools.combinations(l,3))

ans = 0

for i in range(len(t)):
	tmp = list(t[i])
	tmp.sort()
	if tmp[0] + tmp[1] > tmp[2]:
		ans += 1

print(ans)


### FIXED CODE ###

import bisect

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

l.sort()
#print(l)
ans = 0
for i in range(n-1):
	a = l[i]
	for j in range(i+2,n):
		b = l[j]
		c = bisect.bisect_left(l,b-a+1)
		if j - c > 0:
			if i >= c:
				ans += j-i-1
			else:
				ans += j-c
		#print(i,j,c,ans)

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

K = int(input())

if K%2 == 0 or K%2 ==0:
    print(-1)
    exit(0)

count = 0
an = 0
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
    break
print(count)

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

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

for i in range(K):
    a = A
    b = B
    c = C

    A = b + c
    B = a + c
    C = a + b

ans = A - B

if ans >= 10**8:
    ans = 'Unfair'
elif ans <= -1*10**8:
    ans = 'Unfair'

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

'''
A, B, C, K = map(int, input().split()) 

for i in range(K):
    a = A
    b = B
    c = C

    A = b + c
    B = a + c
    C = a + b

ans = A - B

if ans >= 10**8:
    ans = 'Unfair'
elif ans >*10**8:
    ans = 'Unfair'

print(ans)
'''



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

if K%2==1: 
    ans = B - A
else:
    ans = A - B

if ans >= 10**18 or (-1)*ans >= 10**18:
    ans = 'Unfair'

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

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

buf = set(range(1, n+1))
for i in range(m):
    l, r = map(int, input().split())
    buf = buf & set(range(l, r+1))
print(len(buf))


### FIXED CODE ###

a = 1

n, m = map(int, input().split())
ans_r = 10 ** 5

l_list = []
r_list = []
for i in range(m):
    l, r = map(int, input().split())
    l_list.append(int(l))
    r_list.append(int(r))
for r in r_list:
    if ans_r > r:
        ans_r = r
for l in l_list:
    if a < l:
        a = l

if ans_r >= a:
    print(ans_r - a + 1)
else:
    print(0)
### BUGGY CODE ###

 
 
def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	c = a % b
	return gcd(b, c)
 


n = int(input())
a = list(map(int,input().split()))
gcds = []
for i in range(n):
	listgcd = 0
	b = []
	for k in range(n):
		if (i != k):
			b.append(a[k])
	tmp = b[0]
	for bi in b:
		tmp = gcd(tmp,bi)
		
	gcds.append(tmp)
 
print (max(gcds))

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


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

l = [0]*(n+2) # l(i) = A1, A2, ..., A(i-1)のgcd
r = [0]*(n+2) # r(i) = Ai, A(i+1), ..., A(n)のgcd

for i in range(n):
	l[i+1] = gcd(l[i],a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i+1],a[i])

ext = [0] * n
for i in range(n):
	ext[i] = gcd(l[i],r[i+1])

print (max(ext))
### BUGGY CODE ###

N = int(input())

*H, = map(int, input().split())

max = 0
count = 0

for node in range(N):
    n = node
    while n<N-1:
        if H[n]<H[n+1]:
            if max<count:
                max = count
            break 
        count = count + 1
        n  = n + 1  
    if max<count:
        max = count
    count = 0
print(max)

### FIXED CODE ###

N = int(input())
*H, = map(int, input().split())


count_max = 0
count_temp = 0
flg = 0
#全探索
for i in range(0, len(H)-1, 1):

    if H[i] < H[i+1]:
        if count_max < count_temp:
            count_max = count_temp
        count_temp = 0
        flg = 1
        continue

    count_temp = count_temp + 1

    if H[i+1]==H[len(H)-1]:
        if count_max < count_temp:
            count_max = count_temp
        flg = 1

if flg == 1:
    print(count_max)
else:
    print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int , input().split()))
b = [0] * (n-k+1)
b0 = 1
for i in range(k):
    b0 = b0 * a[i]
b[0] = b0
for i in range(k, n):
    b[i-k+1] = b[i-k] // a[i-k] * a[i]
    if b[i-k+1] > b[i-k]:
        print('Yes')
    else:
        print('No')
#print(a, b, b0)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int , input().split()))
b = [0] * (n-k+1)
b0 = 1
for i in range(k):
    b0 = b0 + a[i]
b[0] = b0
for i in range(k, n):
    b[i-k+1] = b[i-k] - a[i-k] + a[i]
    if b[i-k+1] > b[i-k]:
        print('Yes')
    else:
        print('No')
#print(a, b, b0)
### BUGGY CODE ###

n,k,q = map(int,input().split())
p = [k] * n
for i in range(q):
  a = int(input())-1
  for j in range(n):
    if j != a:
      p[j] -= 1
for i in p:
  if i <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

n,k,q = map(int,input().split())
c = [0] * n
for i in range(q):
  c[int(input())-1] += 1
for i in c:
  if k-q+i <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

import sys
try:
    from scipy.special import comb
except:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    """
    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD
    """

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, MOD) - comb(m, i-1, MOD)
        print(int(ans) % MOD)


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

S = list(input())
sl = len(S)
dp = [[0] * 13 for _ in range(sl+1)]
dp[0][0] = 1

c = ''
for i in range(sl):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki] 

print(dp[-1][5] % (10**9 + 7))

### FIXED CODE ###

S = str(input())
ans = [0] * 13
ans[0] = 1
MOD = 10**9 + 7
for i in S:
    dp = [0] * 13
    for j in range(13):
        dp[(j * 10) % 13] = ans[j] % MOD
    dp += dp
    if i == '?':
        for j in range(13):
            ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13):
            ans[j] = dp[j + 13 - int(i)]
print(ans[5] % MOD)
### BUGGY CODE ###

import math
f = int(input())
for n in range(1,f+1):
	try:
		l = int(-1+math.sqrt(-2+n)+0.999)
	except:
		print(0)
		continue
	e = 0
	p = []
	for x in range(1,l+1):
		for y in range(1,x+1):
			try:
				q = (-(x+y)+math.sqrt((x+y)**2-4*(x**2+y**2+x*y-n)))/2
				if q==int(q) and q > 0 and (x+y+q) not in p:
					if q == x and q == y:
						e += 1
						p.append(x+y+q)
					else:
						e += 3
						p.append(x+y+q)
			except:
				pass
	print(e)

### FIXED CODE ###

n = int(input())
ret = [0 for _ in range(1,n+1)]
def f(x,y,z):
	return x*x + y*y + z*z + x*y + y*z + x*z

for x in range(1,n+1):
	for y in range(1,n+1):
		for z in range(1,n+1):
			if f(x,y,z) > n:
				z = 1
				break
			ret[f(x,y,z)-1] += 1
		if f(x,y,z) > n:
			y = 1
			break
	if f(x,y,z) > n:
		x = 1
		break

for i in ret:
	print(i)
### BUGGY CODE ###

#13:27
s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i-1:i+1] == 'FF':
    raw[-1] += 1
  elif s[i-1:i+1] == 'TF':
    raw.append(1)
  if s[i-1:i+1] == 'TT':
    raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
now = [0 for _ in range(16001)]
now[8000] = 1
for aa in a:
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+aa] = 1
      now[i-aa] = 1
if now[8000+x] == 0:
  print('No')
  exit()
now = [0 for _ in range(16001)]
now[8000] = 1
for bb in b:
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+bb] = 1
      now[i-bb] = 1
if now[8000+y] == 1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i] == 'F':
    if s[i-1] == 'F':
      raw[-1] += 1
    else:
      raw.append(1)
  if s[i] == 'T':
    if s[i-1] == 'T':
      raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
nowa = {0}
for aa in a:
  lasta = nowa
  nowa = set()
  for aaa in lasta:
    nowa.add(aaa+aa)
    nowa.add(aaa-aa)
nowb = {0}
for bb in b:
  lastb = nowb
  nowb = set()
  for bbb in lastb:
    nowb.add(bbb+bb)
    nowb.add(bbb-bb)
#print(nowa,nowb)
#print(x,y)
if x in nowa and y in nowb:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

inp = input()
inp = inp.split()
N = int(inp[0])
M = int(inp[1])
BigM = N+2

E = []
for m in range(M):
    abinp = input()
    abinp = abinp.split()
    a = int(abinp[0])
    b = int(abinp[1])
    E.append(set([a,b]))

# program
output = [0] + [0] + [BigM]*(N-1)
prev = set([])
prev_cnt = 0
now = [1]

while len(now) > 0:
    n = now.pop(0)
    prev_cnt += 1
    prev.add(n)
    elist = []
    for e in E:
        if n in e:
            elist.append(e)
    for e in elist:
        next = list(e - set([n]))[0]
        if next not in now:
            if next not in prev:
                output[next] = n
                now.append(next)
        E.remove(e)

if prev_cnt == N:
    print("Yes")
    for n in range(2,N+1):
        print(output[n])
else:
    print("No")




### FIXED CODE ###

inp = input()
inp = inp.split()
N = int(inp[0])
M = int(inp[1])
BigM = N+2

E = []
for m in range(M):
    abinp = input()
    abinp = abinp.split()
    a = int(abinp[0])
    b = int(abinp[1])
    E.append([a,b])

# program
Edict = [[] for n in range(N+1)]
for e in E:
    Edict[e[0]].append(e[1])
    Edict[e[1]].append(e[0])

output = [0] + [0] + [BigM]*(N-1)
prev = [0 for n in range(N+1)]
prev_cnt = 0
now = [1]

prev[1] = 1
while len(now) > 0:
    n = now.pop(0)
    prev_cnt += 1
    for next in Edict[n]:
        if prev[next] == 0:
            output[next] = n
            now.append(next)
            prev[next] = 1

if prev_cnt == N:
    print("Yes")
    for n in range(2,N+1):
        print(output[n])
else:
    print("No")
### BUGGY CODE ###

#D問題
N = int(input())
A = list(map(int,input().split()))

srui = [0]
xrui = [0]

for a in A:
    srui.append(srui[-1]+a)
    xrui.append(xrui[-1]^a)
    
#print(srui,xrui)
ans = 0
for i in range(N):
    I = i+1
    for j in range(N-i):
        J = I+j
        if J > N+1:
            break
            
        if (srui[J]-srui[I-1]) == (xrui[J]^xrui[I-1]):
            ans+=1
            #print(I,J)
        else:
            break
            
print(ans)

### FIXED CODE ###

#D問題
N = int(input())
A = list(map(int,input().split()))

srui = [0]
xrui = [0]

for a in A:
    srui.append(srui[-1]+a)
    xrui.append(xrui[-1]^a)
    
#print(srui,xrui)
ans = 0
J = 1
for i in range(N):
    I = i+1
    while J <= N and (srui[J]-srui[I-1]) == (xrui[J]^xrui[I-1]):
        J+=1
    J-=1
    ans += J-I+1
            
print(ans)
### BUGGY CODE ###

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

Q = 998244353
S = [0] * (N + 1)

for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S[i] = 1

P = [0] * N
P[0] = 1

for i in range(1, N):
    for j in range(i):
        P[i] += S[i-j] * P[j]
        P[i] = P[i] % Q

print(P[-1])

### FIXED CODE ###

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

Q = 998244353
L, R = [], []

for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    
L = sorted(L)
R = sorted(R)

P = [0] * N
P[0] = 1

C = [0] * N
C[0] = 1
S = 1

for i in range(1, N):
    for l, r in zip(L, R):
        if l > i:
            break
        
        if r >= i:
            P[i] += C[i-l]
        else:
            s = C[i-l] - C[i-r-1]
            if s < 0:
                s += Q
            P[i] += s

        P[i] = P[i] % Q
    S += P[i]
    S %= Q
    C[i] = S


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

import sys
readline = sys.stdin.buffer.readline
r1,c1,r2,c2 = map(int,readline().split())
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=20**6+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
def fermat_cmb(n, r, mod=10**9+7): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
fact = factrial_memo()
r1,c1,r2,c2 = r1+1,c1+1,r2+1,c2+1
al = fermat_cmb(r2+c2,r2)
sub_r = fermat_cmb(r1-1+c2,r1-1)
sub_c = fermat_cmb(r2+c1-1,c1-1)
add_rc = fermat_cmb(r1-1+c1-1,r1-1)

al -= sub_r+sub_c
al += add_rc

print(al%mod)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
r1,c1,r2,c2 = map(int,readline().split())
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=3*10**6+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
def fermat_cmb(n, r, mod=10**9+7): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
fact = factrial_memo()
r1,c1,r2,c2 = r1+1,c1+1,r2+1,c2+1
al = fermat_cmb(r2+c2,r2)
sub_r = fermat_cmb(r1-1+c2,r1-1)
sub_c = fermat_cmb(r2+c1-1,c1-1)
add_rc = fermat_cmb(r1-1+c1-1,r1-1)

al -= sub_r+sub_c
al += add_rc

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

s=input()
q=int(input())
for i in range(q):
	a=input()
	if a[0]=="1":
		s=s[::-1]
	elif a[2]=="1":
		s=a[4]+s
	else:
		s=s+a[4]
print(s)

### FIXED CODE ###

from collections import deque

deq=deque()
k = input()
for i in range(len(k)):
	deq.append(k[i])
q=int(input())
x=True
for i in range(q):
	a=input()
	if a[0]=="1":
		x = not x
	elif a[2]=="1":
		if x==True:
			deq.appendleft(a[4])
		else:
			deq.append(a[4])
	else:
		if x==True:
			deq.append(a[4])
		else:
			deq.appendleft(a[4])
if x==True:
	c="".join(deq)
else:
	deq.reverse()
	c="".join(deq)
print(c)
### BUGGY CODE ###

def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1

    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]


n = int(input())
L = list(map(int, input().split()))
L = count_sort(L)
count = 0
for i, l1 in enumerate(L):
    for k, l2 in enumerate(L[i+1:]):
        num = i + k + 2
        for l3 in L[num:]:
            if l1 + l2 < l3:
                break
            if l1 < l2 + l3 and l2 < l1 + l3 and l3 < l2 + l1:
                count += 1
            else:
                break

print(count)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        k = bisect.bisect_left(L[j+1:], L[i]+L[j])
        count += k

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

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

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

root = [[] for i in range(n)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

dp = [False]*n

ans = 0

for j in range(n):
    if dp[j]:
        continue
    check = [-1]*n
    check[j] = 0
    stack=[j]
    dp[j] = True
    while len(stack):
        v = stack.pop()
        for i in root[v]:
            if check[i] == -1:
                dp[i] = True
                check[i]=i
                stack.append(i)
    for k in range(n):
        if check[k] != -1 and check[p[k]-1] != -1:
            ans += 1

print(ans)

### FIXED CODE ###

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

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

root = [[] for i in range(n)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

check = [-1]*n

ans = 0

for j in range(n):
    if check[j] != -1:
        continue
    stack=[j]
    check[j]=j
    while len(stack):
        v = stack.pop(0)
        for i in root[v]:
            if check[i] == -1:
                check[i]=j
                stack.append(i)
for k in range(n):
    if check[k] == check[p[k]-1] :
        ans += 1

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

import re
words = (re.compile("^dreamer"), re.compile("^eraser"), re.compile("^dream"), re.compile("^erase"))

s = input()

while s != "":
    for w in words:
        if w.match(s) is not None:
            s = w.sub("", s)
            break
    if s == "":
        print("YES")
        exit()
print("NO")


### FIXED CODE ###

words = ("dream", "erase", "eraser", "dreamer")

s = input()

while len(s) > 0:
    match = False
    for w in words:
        if s.endswith(w):
            s = s[:-len(w)]
            match = True
            break
    if match is False:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    N,Q=map(int,input().split())
    S=str(input())

    L, R = [0] * Q, [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())
        L[i], R[i] = L[i]-1, R[i]-1

    where=[]

    for i in range(N-1):
        if S[i:i+2]=='AC':
            where.append(i)

    for j in range(Q):
        cnt=0
        for i in where:
            if L[j]<=i and i+1<=R[j]:
                cnt+=1
        print(cnt)


resolve()

### FIXED CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    N,Q=map(int,input().split())
    S=str(input())

    L, R = [0] * Q, [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())
        L[i], R[i] = L[i]-1, R[i]-1

    A=[0]*N
    for i in range(N-1):
        if S[i:i+2]=='AC':
            A[i]=1

    B = [0] + A
    B = list(accumulate(B))  # 累積和を格納したリスト作成

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
    for j in range(Q):
        ans=B[R[j]]-B[L[j]]
        print(ans)



resolve()