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

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m,q = map(int,input().split())
    l = [[0]*(n) for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        l[a-1][b-1] += 1

    for i in range(q):
        a,b = map(int,input().split())
        count = 0
        for i in range(a-1,b):
            for j in range(a-1,b):
                count += l[i][j]
        print(count)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n,m,q = map(int,input().split())
l = [[0]*(n) for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    l[a-1][b-1] += 1


for i in range(n):
    for j in range(n):
        if i != 0:
            l[i][j] += l[i-1][j]
        if j != 0:
            l[i][j] += l[i][j-1]
        if i!= 0 and j != 0:
            l[i][j] -= l[i-1][j-1]
    

for i in range(q):
    a,b = map(int,input().split())
    ans = l[b-1][b-1]
    if a >= 2:
        ans -= l[a-2][b-1]
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
 
N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
def rec(i, choice):
  if i == len(H):
    return 0
  return max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
print(max(rec(0, j) for j in range(3)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
 
N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
memo = {}
def rec(i, choice):
  if (i, choice) in memo:
    return memo[(i, choice)]
  if i == len(H):
    return 0
  m = max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
  memo[(i, choice)] = m
  return m
print(max(rec(0, j) for j in range(3)))
### BUGGY CODE ###

#長方形ができるかの判定を行いながら、長方形の面積を求める
N=int(input()) 
A=list(map(int,input().split()))
A.sort()
max1=0
max2=0
max3=0
max4=0
for i in range(0,len(A)): 
    if A.count(A[i])>=2: 
        a=max1
        b=max2
        c=max3
        max1=A[i]
        max2=a
        max3=b
        max4=c
print(max1*max4)
#これは求めるべき答えを見出せたが、TLEとなった
#これはcount関数を使ったため

### FIXED CODE ###

#長方形ができるかの判定を行いながら、長方形の面積を求める
N=int(input()) 
A=list(map(int,input().split()))
A.sort() 
max1=0
max2=0
if A[0]==A[1]:
        a=max1
        max1=A[0]
        max2=a     
for i in range(2,len(A)-1): 
    if A[i]==A[i+1] and (A[i]!=A[i-1] or  A[i]==A[i-1]==A[i-2]):
        a=max1
        max1=A[i]
        max2=a 
print(max1*max2)
### BUGGY CODE ###

import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

### FIXED CODE ###

import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]

        for k in range(1, min(a, H) + 1):
            mp_for_damage[k] = min(mp_for_damage[k], b)
            # print(k, b)

        if a >= H:
            mp_for_damage[H] = min(mp_for_damage[H], b)
            continue

        if a < H and mp_for_damage[a] < b:
            continue

        for j in range(H-a+1):
            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
now = 1

sum = np.zeros(60,dtype=int)
for i in a:
    ii = i
    aa = np.zeros(60,dtype=int)
    for j in range(60):
        aa[j] = ii%2
        ii //= 2
        if ii == 0:
            break
    sum += aa

for i in range(60):
    k = (sum[i]*(n-sum[i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc147/submissions/12994515を見た

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7
m2 = [1 for i in range(60)]
for i in range(1,60):
    m2[i] = (m2[i-1]*2)%mod

ans = 0
for i in range(60):
    ni = np.count_nonzero(a&1)
    ans = (ans+ni*(n-ni)%mod*m2[i])%mod
    a >>= 1

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

n = int(input())
a = list(map(int, input().split()))
c = n
i = 0
s = a[0]
xor = []
d = 0
for i in range(n):
	s = a[i]
	j = i
	d = 0
	while j < n-1:
		xs = s ^ a[j+1]
		s += a[j+1]
		if s == xs:
			d += 1
		else:
			break
		j += 1
	c += d
for i in xor:
	c += i*(i-1)//2
print (c)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
s = 0
d = 0
j = 0
for i in range(n):
	d = 0
	while j < n and s & a[j] == 0:
		s += a[j]
		j += 1
	s -= a[i]
	c += j-i
print (c)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
for i in range(n):
    k = x.pop(i)
    s=sorted(x)
    print(s[n//2-1])
    x.insert(i,k)

### FIXED CODE ###

from math import *

n = int(input())

a = [int(x) for x in input().split()]

a_sort = sorted(a)

median_right = a_sort[floor(len(a_sort) / 2)]
median_left = a_sort[floor(len(a_sort) / 2) - 1]

for i in range(len(a)):
	if a[i] > median_left:
		print(median_left)
	else:
		print(median_right)
### BUGGY CODE ###

s = input()


count = 0

for i,x in enumerate(s):
  if x=='B':
    count += s[i:].count('W')

print(count)

### FIXED CODE ###

s = input()

count = 0
black = 0
for i in s:
  if i=='W':
    count += black
  else:
    black+=1

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

S = [s for s in input()]
ans = 0
i = 1
while len(S) > 1 and i < len(S):
    if S[i] == S[i - 1]:
        i += 1
    else:
        S.pop(i)
        S.pop(i - 1)
        ans += 2
        i = 1
print(ans)        


### FIXED CODE ###

import re
S = input()
num_1 = S.count("1")
num_0 = S.count("0")
print(min(num_0, num_1) * 2)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
index = [0] *(N+1)
for i in range(N-2):
  if S[i:i+2] == 'AC':
    index[i] = 1
for _ in range(Q):
  l, r = map(int,input().split())
  print(sum(index[l-1:r-1]))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
index = [0] *(N+1)
for i in range(N):
  index[i+1] = index[i] + (1 if S[i:i+2] =='AC' else 0)
for _ in range(Q):
  r, l = map(int,input().split())
  print(index[l-1] - index[ r -1])
### BUGGY CODE ###

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

def f(N, P):
  d = 1
  i = 2
  if N == 1:
    return P
  else:
    while i <= pow(P, 1/N)+1:
      if P % i**N == 0:
        P //= i**N
        d *= i
      else:
        i += 1
    return d

print(f(N, P))

### FIXED CODE ###

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

if N == 1:
  d = P
else:
  d = 1
  i = 2
  while i <= round(pow(P, 1/N)):
    if P % i**N == 0:
      P //= i**N
      d *= i
    else:
      i += 1
print(d)
### BUGGY CODE ###

#import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
    a=B[:N]        
  if min(a)==N:
    break
print(*a)

### FIXED CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u


def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * modinv(tmp2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u


def combination(n, r): #nCrを求める
    if n - r < r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * modinv(tmp2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)
### BUGGY CODE ###

import bisect

n = int(input())
a_li = list(map(int, input().split()))
b_li = list(map(int, input().split()))
c_li = list(map(int, input().split()))

b_li.sort()
c_li.sort()

check_li = [0]*(n+10)

for i in range(len(b_li)):
    s = bisect.bisect_right(c_li, b_li[i])
    check_li[i] = len(c_li[s:])

tmp = 0
for i in range(1, n+11):
    check_li[-i] = check_li[-i] + tmp
    tmp = check_li[-i]

ans = 0

for i in a_li:
    s = bisect.bisect_right(b_li, i)
    ans += check_li[s]

print(ans)

### FIXED CODE ###

import bisect

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

a.sort()
b.sort()
c.sort()

ans = 0

for middle in b:
    tmp1 = bisect.bisect_left(a, middle)
    tmp2 = bisect.bisect_right(c, middle)
    ans += tmp1 * (n - tmp2)

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

from itertools import product

#最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


k = int(input())

ans = 0
for i in product(range(1, k+1), repeat=3):
    a, b, c = i
    res = gcd(a, b)
    res = gcd(res, c)
    ans += res
print(ans)

### FIXED CODE ###

from math import gcd

k = int(input())

res = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        g1 = gcd(a, b)
        for c in range(1, k + 1):
            g2 = gcd(g1, c)
            res += g2
print(res)
### BUGGY CODE ###

N = int(input())
A =list(map(int, input().split(" ")))
 
r = N
asum = [0]
axor = [0]
 
for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)
 
for i in range(len(A)):
    for j in range(i+1, len(A)):
        if (asum[j+1] - asum[i]) == (axor[j+1] ^ axor[i]):
            r += 1
        else:
            break
 
print(r)

### FIXED CODE ###

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

res = 0
asum = [0]
axor = [0]

for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)

for l in range(N):
    ok = l+1
    ng = N+1
    while(ng - ok > 1):
        r = (ok + ng) // 2
        s = (axor[r] ^ axor[l])
        t = (asum[r] - asum[l])
        if s == t:
            ok = r
        else:
            ng = r
    
    res += ok - l
         
print(res)
### BUGGY CODE ###

n,k,q=map(int,input().split())
i=0
a=[]
while i!=q:
    a.append(int(input()))
    i+=1
a.sort()
if k>q:
    i=0
    while i!=n:
        print("Yes")
        i+=1
else:
    i=0
    while i!=n:
        if q-a.count(i+1)<k:
            print ("Yes")
        else:
            print("No")
        i+=1

### FIXED CODE ###

n,k,q=map(int,input().split())
i=0
a=[]
j=0
tm=0
while i!=q:
    a.append(int(input()))
    i+=1
a.sort()
if k>q:
    i=0
    while i!=n:
        print("Yes")
        i+=1
else:
    i=0
    while i!=n:
        while j!=q:
            if a[j]==(i+1):
         
                tm+=1
                j+=1
            else:
                break

        if q-tm<k:
            print ("Yes")
        else:
            print("No")
        tm=0
        i+=1
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
total = 0
for i in range (N):
  for j in range(N):
    total += A[i]*A[j]
for k in range(N):
  total -= A[k]*A[k]
total = total/2
print(int(total%(10**9+7)))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
a=sum(A)
a=a**2
b=0

for j in range(n):
  b+=A[j]**2
if a-b<0:
  c=a-b
  while c<=0:
    c+=mod
  
  ans=c//2
  ans=ans%(10**9+7)
 
else:
  ans=(a-b)//2
  ans=ans%(10**9+7)
 
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from decimal import Decimal, getcontext
getcontext().prec = 100000
A, B, C = map(Decimal, readline().split())
half = Decimal(0.5)
print('Yes' if A**half + B**half < C**half else 'No')

### FIXED CODE ###

import sys
readline = sys.stdin.readline

a, b, c = map(int, readline().split())
print('Yes' if 4*a*b < (c-a-b)**2 and (c-a-b) > 0 else 'No')
### BUGGY CODE ###

""" AtCoder """

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

l = []
pos = 0

for _ in range(S.count("AC")):
    i = S.index("AC")
    l.append(i + pos + 1)
    pos = pos + i + 2
    S = S[i + 2:]

check = True

for i in range(Q):
    while True:
        if lr[i][0] not in l:
            lr[i][0] += 1
        else:
            break
        if lr[i][0] > lr[i][1]:
            check = False
            break
    while True:
        if (lr[i][1] - 1) not in l:
            lr[i][1] -= 1
        else:
            break
        if lr[i][1] < lr[i][0]:
            check = False
            break
    if check:
        print(l.index(lr[i][1] - 1) - l.index(lr[i][0]) + 1)
    else:
        print(0)
    check = True


### FIXED CODE ###

""" AtCoder """

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

tmp = 0
l = [0]

for i in range(1, N):
    if S[i - 1] + S[i] == "AC":
        tmp += 1
    l.append(tmp)

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

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=1
t.sort(reverse=True)
if s[0]>=2:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
    if t[0]<t[1]:
      t.sort(reverse=True)
else:
  for j in range(s[1]):
    b=b*2
  t[0]=math.floor(t[0]/b)

a=sum(t)
print(a)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
n = len(s)
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    if s[i] == '?':
        for k in range(10):
            l = (k*10**c) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        l = (int(s[i])*10**c) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]    
            now[(j+l)%13] = now[(j+l)%13] % mod
    # print(now)
print(now[5])


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

s = input()
l = len(s)
r = 0
for i in range(l-3):
    for j in range(i+3,l):
        n = int(s[i:j+1])
        if n % 2019 == 0:
            r += 1
print(r)

### FIXED CODE ###

s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
for i in range(M):
  B,C = map(int, input().split())
  for j in range(B):
    D.append(C)

import bisect
from collections import deque

D = sorted(D,reverse=True)
A = sorted(A)

for i in range(min(len(D),N)):
  if D[i]>A[i]:
    A[i] = D[i]
  else:
    break
    
print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [[] for _ in range(M)]
for i in range(M):
  BC[i] = list(map(int, input().split()))

BC.sort(key=lambda x: x[1], reverse=True)

for i in BC:
  A.extend([i[1]]*i[0])
  if len(A) > 2*N:
    break
    
A = sorted(A,reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)


### FIXED CODE ###

def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print((maxv + k) * 0.5)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = tempsum = sum(P[:k])
for i in range(1, n-k+1):
	tempsum = tempsum - P[i-1] + P[i+k-1]
	maxv = max(maxv, tempsum)
print((maxv + k) * 0.5)