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

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0

q = [[0,0]]


#print (d)

inqueue = [False] * (N+2)
inqueue[0] = True

while len(q) > 0:

    np = heapq.heappop(q)
    now = np[1]
    inqueue[now] = False

    for i in range(N+2):
        if ans[i] > ans[now] + d[now][i]:
            ans[i] = ans[now] + d[now][i]

            if not inqueue[i]:
                heapq.heappush(q,[ans[i] , i])

#print (ans)
print (ans[-1])
    


### FIXED CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0
used = [False] * (N+2)

while True:

    v = -1

    #未到達の点に関して最も数値の小さい点を選ぶ
    for i in range(N+2):
        if not used[i] and (v == -1 or ans[v] > ans[i]):
            v = i
    
    if v == -1:
        break
    
    used[v] = True
    for i in range(N+2):
        ans[i] = min(ans[i] , ans[v] + d[v][i])

#print (used,ans)
print (ans[-1])
### BUGGY CODE ###

from itertools import groupby

[H, W] = map(int, input().split())
Ss = [list(input()) for _ in range(H)]

res = 0
count = [[-1 * int(Ss[i][j] == ".") for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * (x[0] == ".")
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * (x[0] == ".")
            if res < new_res:
                res = new_res
            i += 1

print(res)


### FIXED CODE ###

from itertools import groupby
 
[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]
 
res = 0
count = [[-Ss[i][j] for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * x[0]
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * x[0]
            if res < new_res:
                res = new_res
            i += 1

print(res)
### BUGGY CODE ###

S = list(input())
Q = int(input())
for i in range(Q) :
    a = list(input().split())
    if a[0] == "1" :
        S = S[::-1]
    else :
        if a[1] == "1" :
            S.insert(0,a[2])
        else :
            S.append(a[2])
print("".join(S))


### FIXED CODE ###

S = list(input())
Q = int(input())

c = 0
w = []

for i in range(Q) :
    a = input()
    if a[0] == "1" :
        c ^= 1
    else :
        if a[2] == "1" :
            if c == 0 :
                w.append(a[4])
            else :
                S.append(a[4])
        else :
            if c == 0 :
                S.append(a[4])
            else :
                w.append(a[4])
S = w[::-1] + S
print("".join(S) if c == 0 else "".join(S[::-1]))
### BUGGY CODE ###

H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)

### FIXED CODE ###

H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)
### BUGGY CODE ###

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

sum = 0

for i in range(K):

  if A > 0:
    sum += 1
    A -= 1
  elif B > 0:
    B -= 1
  else:
    sum -= 1
    C -= 1

print(sum)


### FIXED CODE ###

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

if K <= A:
  print(K)
elif K <= A + B:
  print(A)
else:
  print(A-(K-A-B))
### BUGGY CODE ###

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

cnt = 0

for i in range(10):
    x = 0
    while S[x] != str(i) and x != (len(S)-3):
        x += 1
    if S[x] == str(i):
        for j in range(10):
            y = x + 1
            while S[y] != str(j) and y != (len(S)-2):
                y += 1
            if S[y] == str(j):
                for k in range(10):
                    z = y + 1
                    while S[z] != str(k) and z != (len(S)-1):
                        z +=1
                    if S[z] == str(k):
                        cnt +=1

print(cnt)             

### FIXED CODE ###

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

cnt = 0

for i in range(10):
    x = 0
    while S[x] != str(i) and x != (len(S)-3):
        x += 1
    if S[x] == str(i):
        for j in range(10):
            y = x + 1
            while S[y] != str(j) and y != (len(S)-2):
                y += 1
            if S[y] == str(j):
                for k in range(10):
                    z = y + 1
                    while S[z] != str(k) and z != (len(S)-1):
                        z +=1
                    if S[z] == str(k):
                        cnt +=1

print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*10**n)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
    print(dp[N][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        else:
            k = int(c)
            for j in range(13):
                dp[n+1][(j + k*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


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

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * (10**i) + r) % 13] += dp[i-1][r]
        else:
            dp[i][(int(s[-(i+1)]) * (10**i) + r) % 13] += dp[i-1][r]
            
print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

# D - String Formation

S = str(input())
Q = int(input())

for _ in range(Q):
    q = [str(x) for x in input().split()]
    if q[0] == '1':
        S = ''.join(list(reversed(S)))
    elif q[1]=='1':
        S = q[2]+S
    else:
        S = S+q[2]

print(S)

### FIXED CODE ###

# D - String Formation

S = str(input())
Q = int(input())

# 1の数
c = 0
l = ''
r = ''

for _ in range(Q):
    q = [str(x) for x in input().split()]
    if q[0] == '1':
        c += 1
        l, r = r, l
    elif q[1]=='1':
        l = l + q[2]
    else:
        r = r + q[2]

if c%2==1:
    S = ''.join(reversed(S))

l = ''.join(reversed(l))

print(l+S+r)
### BUGGY CODE ###

def code(n,p):
    flg = 1

    for idx in range(1,n):
        if min(p[0:idx]) >= p[idx]:
            flg+=1
    return flg

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

idx = code(n,p)
if idx == None:
    print(n)
else:
    print(idx)


### FIXED CODE ###

n=int(input())
plist = list(map(int,input().split()))
cnt = 0
pmax=plist[0]
for i in range(n):
    if plist[i]<=pmax:
        pmax=plist[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
chars=[i for i in set(s)]
chars.sort() 
i=0 
l=[]
while i<len(chars): 
    for ind in range(n): 
        if s[ind]==chars[i]:
            curr=''
            for j in range(ind,n):
                curr+=s[j]
                if curr not in l:
                    l.append(curr)
    if len(l)>k:
        break 
    i+=1 
l.sort()
#print(l)
print(l[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
l=set()
for i in range(n):
    curr=''
    for j in range(i,min(i+7,n)):
        curr+=s[j]
        l.add(curr)
l=[i for i in l]
l.sort()
#print(l)
print(l[k-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
C - Unification
https://atcoder.jp/contests/abc120/tasks/abc120_c

"""
import sys
import re


def my_sub(m):
    len1 = len(m.group(1))
    len2 = len(m.group(2))
    if len1 > len2:
        return m.group(1) * (len1 - len2)
    return m.group(2) * (len2 - len1)


def solve(S):
    orig_len = len(S)
    while True:
        t = re.sub(r'01', '', S)
        t = re.sub(r'10', '', t)
        if t == S:
            break
        S = t
    return orig_len - len(S)


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


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


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
C - Unification
https://atcoder.jp/contests/abc120/tasks/abc120_c

"""
import sys


def solve(S):
    orig_len = len(S)
    num_value = {'0': -1, '1': 1}
    status = 0

    for s in S:
        status += num_value[s]
        #if s == '0':
        #    status -= 1
        #else:
        #    status += 1
    return orig_len - abs(status)


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


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

N=int(input())

power=1

for i in range(1,N+1):
    power=power*i

ans=power%(1000000000+7)
print(ans)

### FIXED CODE ###

import math
N=int(input())

power=math.factorial(N)

ans=power%(1000000000+7)
print(ans)
### BUGGY CODE ###

import sys

a,b,k=map(int,input().split())

if a+b==k:
  print(0,0)
  sys.exit()

while k>0 and a>0 and b>0:
  if a>0:
    while a>0 or k>0:
      if a==0 or k==0:
        break
      a-=1
      k-=1
  if b>0:
    while b>0 or k>0:
      if b==0 or k==0:
        break
      b-=1
      k-=1
print(a,b)

### FIXED CODE ###

import sys

a,b,k=map(int,input().split())

if a<=k:
  k=k-a
  a=0
elif a>k:
  a=a-k
  print(a,b)
  sys.exit()
  
if b<=k:
  b=0
else:
  b=b-k
print(a,b)
### BUGGY CODE ###

h, n = map(int, input().split())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [float('inf')]*(h+max(a))
dp[0] = 0 
for i in range(1, h+max(a)):
  for j in range(n):
    dp[i] = min(dp[i], dp[i-a[j]]+b[j])
print(min(dp[h:]))


### FIXED CODE ###

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

dp = [float('inf')]*(h+max(a))
dp[0] = 0 
for i in range(1, h+max(a)):
  for j in range(n):
    dp[i] = min(dp[i], dp[i-a[j]]+b[j])
print(min(dp[h:]))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
a=[]
for i in range(Q):
    a.append(int(input()))
for i in range(N):
	if 0<K-Q+a.count(i+1):
	    print("Yes")
	else:
	    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
a = [0 for i in range(N)]
for i in range(Q):
  a[int(input())-1]+=1
for i in a:
  if K-Q+i>0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
while True:
    a[0] = a[0] % a[1]
    if a[0] <= 0:
        a = a[1:]
    a.sort(reverse=True)
    if len(a) == 1:
        print(a[0])
        break


### FIXED CODE ###

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

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

if n==1:
    print(x[0])
else:
    element = gcd(x[0], x[1])
    if n==2:print(element)
    else:
        for i in range(2,n):
            element=gcd(element,x[i])
        print(element)
### BUGGY CODE ###

N,K = map(int, input().split())
X = [int(x) for x in input().split()]

ref = []
for i in range(N-K+1):
    ref.append(X[i:i+K])


List = []
for k in range(len(ref)):
    if ref[k][0]<=0 and ref[k][-1]>=0:
        List.append(ref[k][-1]-ref[k][0]+min(abs(ref[k][-1]),abs(ref[k][0])))
    else:
        List.append(max(abs(ref[k][-1]),abs(ref[k][0])))

print(min(List))

### FIXED CODE ###

N,K = map(int, input().split())
X = [int(x) for x in input().split()]

List = []
for j in range(N-K+1):
    if X[j]<=0 and X[j+K-1]>=0:
        List.append(X[j+K-1]-X[j]+min(abs(X[j]),X[j+K-1]))
    else:
        List.append(max(abs(X[j]),abs(X[j+K-1])))

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

from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math

from scipy.sparse.csgraph import floyd_warshall

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

for i in range(M):
    A[A.index(max(A))] /= 2

print(sum(map(int,A)))


### FIXED CODE ###

from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math
import heapq

from scipy.sparse.csgraph import floyd_warshall

N,M = map(int,input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

for _ in range(M):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))
### BUGGY CODE ###

import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        punc = factorial(
            k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        # color = M * ((M - 1)**(N - k - 1))
        color = M
        for _ in range(N - k - 1):
            color *= M - 1
            color = color % 998244353
        res += ((punc % 998244353) * (color % 998244353)) % 998244353
        res = res % 998244353
    print((res) % 998244353)

### FIXED CODE ###

import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
inv = [1] * N
FAC = factorial(N - 1) % MOD
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for i in range(1, N):
        inv[i] = (inv[i - 1] * pow(i, MOD - 2, MOD)) % MOD
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        # punc = (N-1)!/k!/(N-k-1)!
        # punc = factorial(
        #     k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        punc = FAC
        # punc *= pow(factorial(k), MOD - 2, MOD)
        punc *= inv[k]
        punc = punc % MOD
        # punc *= pow(factorial(N - k - 1), MOD - 2, MOD)
        punc *= inv[N - k - 1]
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)
    done = [False] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if not done[current]:
            done[current] = True
            mark[current] = str(prev)
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    #mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()
### BUGGY CODE ###

import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
child = defaultdict(int)
for s in ss:
	u = ""
	for i in range(len(s)):
		child[u] |= int(s[i]) + 1
		u += s[i]

grundy = 0
for k, v in child.items():
	#print(k, v)
	le = len(k)
	if v == 1 or v == 2:
		grundy ^= (l-le) & (-l+le)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

### FIXED CODE ###

import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [list(input())[::-1] for _ in range(n)]

def addTree(tree, sentence):
	if not sentence:
		return None   

	if sentence[-1] not in tree:
		tree[sentence[-1]] = {}

	p = sentence.pop()
	tree[p] = addTree(tree[p], sentence)

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")
### BUGGY CODE ###

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

c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += sum(l[i]+l[j] > x for x in l[j+1:])

print(c)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += bisect_left(l, l[i]+l[j]) - j - 1
 
print(c)
### BUGGY CODE ###

# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue

n, k = map(int, input().split())
p = np.array(list(int(i) for i in input().split()))
pp = (1 + p) / 2
# print(p)
# print(pp)
ans = 0.00

for i in range(0, n - k + 1):
	ans = max(np.sum(pp[i : (i + k)]), ans)
print('{:.10f}'.format(ans))


### FIXED CODE ###

# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue

n,k = map(int, input().split())
p = (1.00 + np.array(list(int(i) for i in input().split()))) / 2
temp = np.sum(p[:k])
ans = temp

for i in range(k, n):
	temp += (p[i] - p[i - k])
	ans = max(ans, temp)

print('{:.10f}'.format(ans))
### BUGGY CODE ###

#segtree
#https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
#####segfunc######
def segfunc(x,y):
    return x|y
def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
#####単位元######
ide_ele = set()
#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{ord(i)-97}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{ord(c)-97})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))


### FIXED CODE ###

import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))