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


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[0.0] * (303) for _ in range(303)] for _ in range(303)]
    for c3 in range(N + 1):
        for c2 in range(N + 1):
            for c1 in range(N + 1):
                sm = c1 + c2 + c3
                if sm == 0:
                    continue
                dp[c1][c2][c3] = 1.0 * N / sm
                if c1:
                    dp[c1][c2][c3] += dp[c1 - 1][c2][c3] * c1 / sm
                if c2:
                    dp[c1][c2][c3] += dp[c1 + 1][c2 - 1][c3] * c2 / sm
                if c3:
                    dp[c1][c2][c3] += dp[c1][c2 + 1][c3 - 1] * c3 / sm
    print(dp[one][two][three])


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for sushi in range(1, N + 1):
        for k in range(sushi + 1):
            for j in range(0, sushi - k + 1):
                i = sushi - k - j
                if i != 0:
                    dp[i][j][k] += dp[i - 1][j][k] * i / sushi
                if j != 0:
                    dp[i][j][k] += dp[i + 1][j - 1][k] * j / sushi
                if k != 0:
                    dp[i][j][k] += dp[i][j + 1][k - 1] * k / sushi
                dp[i][j][k] += N / sushi
    print(dp[one][two][three])


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

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]
    immortalskip=set()
    
    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i in immortalskip:
                continue
            if i not in skip.copy():
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
                            
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

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

n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            tar = int(key[j], 0) | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])





### FIXED CODE ###

n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            k = int(key[j], 0)
            tar = k | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

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

Prenum = [[] for i in range(N)]
PreYear = [1 for i in range(M)]
PY = [input().split(' ') for i in range(M)]

for i in range(M):
    Pi, Yi = map(int,PY[i])
    Prenum[Pi-1].append(i)

    count = 1
    for j in range(len(Prenum[Pi-1])-1):
        if int(PY[Prenum[Pi-1][j]][1]) > Yi:
            PreYear[Prenum[Pi-1][j]] = PreYear[Prenum[Pi-1][j]]+1
        elif int(PY[Prenum[Pi-1][j]][1]) < Yi:
            count +=1 
    PreYear[i] = count

for i in range(M):
    Pi, Yi = map(int,PY[i])
    print('{0:06d}{1:06d}'.format(Pi,PreYear[i]))

### FIXED CODE ###

from operator import itemgetter


N, M = map(int, input().split(' '))
data = []
for i in range(M):
    Pi, Yi = map(int, input().split(' '))
    data.append([i,Pi,Yi])

sorted_data = sorted(data, key=itemgetter(1,2))

codes = []
prev_p = 0
for i,p,y in sorted_data:
    if p!=prev_p:
        x = 1
        prev_p = p
    else:
        x+=1

    code = '{0:06d}{1:06d}'.format(p,x)
    codes.append([i,code])

sorted_codes = sorted(codes, key = itemgetter(0))

for code in sorted_codes:
    print(code[1])
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0

for i in range(N-3):
  for j in range(i+1, N-1):
    if S[i] != S[j]:
      for k in range(j+1, N):
       if S[j] != S[k] and S[k] != S[i] and j-i != k-j:
        ans += 1
        
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
A = S.count("R") * S.count("G") * S.count("B")

for i in range(N):
  for j in range(i+1, N):
    k = j-i+j
    if k<N and S[k] != S[j] and S[k] != S[i] and S[i] !=S[j]:
      A -= 1    

print(A)
### BUGGY CODE ###

s=input()
k=int(input())
#s=list(input())

#t=[]
#for kk in range(k):
#    t.append(s)

t=["zzzzz"]*k

for i in range(len(s)):
    for j in range(i,len(s)):
        sij=s[i:j+1]
        for kk in range(k):
            if t[kk]==sij:
                break
        if t[kk]>sij:
            t[kk]=sij
            t.sort()
        
print(t[k-1])  
#print(t) 

### FIXED CODE ###

s=input()
k=int(input())
#s=list(input())

#t=[]
#for kk in range(k):
#    t.append(s)

t=["zzzzz"]*k

for i in range(len(s)):
    for j in range(i,min(len(s),i+k)):
        sij=s[i:j+1]
        for kk in range(k):
            if t[kk]==sij:
                break
        if t[kk]>sij:
            t[kk]=sij
            t.sort()
        
print(t[k-1])  
#print(t)
### BUGGY CODE ###

N = int(input())
C = input()
l = 0
r = N - 1
ans = 0
while l < r:
    if C[l]=='W' and C[r]=='R':
        ans+=1
        l +=1
        r-=1
    elif C[l]=='W':
        r-=1
    elif C[r]=="R":
        l+=1
print(ans)

### FIXED CODE ###

N = int(input())
C = input()

r = C.count('R')
ans = C[:r].count('W')
print(ans)
### BUGGY CODE ###

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

A.sort()
# print(A)

le = -1
ri = len(A)
mid = (le + ri) // 2
while ri - le > 1:
    # print(le,ri,mid)
    DP = [0] * k
    DP[0] = 1
    for i in range(n):
        #print(DP)
        if i != mid:
            for p in range(k-1, -1, -1):
                if p-A[i] >= 0:
                    DP[p] = int(DP[p-A[i]] or DP[p])
        # print(j)
    need = 0
    #print(DP)
    for p in range(max(0, k-A[mid]), k):
        if DP[p] == 1:
            need = 1
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2

print(le + 1)

### FIXED CODE ###

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

A.sort()
# print(A)
A_set = list(set(A))

A_set = [int(i) for i in A_set]
A_set.sort()

#print(A_set)

le = -1
ri = len(A_set)
mid = (le + ri) // 2

while ri - le > 1:
    need = 0
    # print(le,ri,mid)

    DP = [0 for i in range(k)]
    DP[0] = 1
    jogai = 0
    for i in range(n):
        #print(DP)
        if jogai == 0 and A[i] == A_set[mid]:
            jogai = 1
        else:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            # print(j)
    
            #print(DP)
        for p in range(max(0, k-A_set[mid]), k):
            if DP[p] == 1:
                need = 1
                break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2


ans = 0

if le != -1:
    jougen = A_set[le]
    for i in range(n):
        if A[i] <= jougen:
            ans += 1

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

N = int(input())
s = list(map(int, input().split()))
 
sum = 0
 
for i in range(N):
  for j in range(i+1, N):
    a = s[i] * s[j]
    sum += a
 
sum  = sum % (10**9 + 7)    
print(sum)

### FIXED CODE ###

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

sum = 0
f = 0

for i in range(n-1):
    f = f + a[i]
    sum += f * a[i+1]
 
print(sum % mod)
### BUGGY CODE ###

def main():
  X, Y, Z, K = list(map(int, input().split()))
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))
  C = list(map(int, input().split()))

  ab = []
  for i in A:
    for j in B:
      ab.append(i + j)

  ab.sort(reverse = True)

  abc = []
  for i in ab[:3000]:
    for j in C:
      abc.append(i + j)

  abc.sort(reverse = True)

  for i in range(K):
    print(abc[i])

main()

### FIXED CODE ###

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

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
A += [-1e10]
B += [-1e10]
C += [-1e10]

memo = [A[i] + B[0] + C[0] for i in range(X + 1)]
L = [[0 for i in range(Y + 1)] for j in range(X + 1)]

for i in range(K):
  ma = 0
  for j in range(X):
    if memo[ma] < memo[j]:
      ma = j
  print(memo[ma])
  mb = 0
  mn = 0
  for j in range(Y):
    x = B[j] + C[L[ma][j]]
    if mb < x:
      mb = x
      mn = j
  L[ma][mn] += 1
  n = 0
  for j in range(Y):
    n = max(n, B[j] + C[L[ma][j]])
  memo[ma] = A[ma] + n
### BUGGY CODE ###

n = int(input())
s = input()
min_c = 9999999

for i in range(n):
   if i == 0:
      cnt = s.count("E")
      if s[0] == "E":
         cnt = cnt - 1
   elif i == n -1:
      cnt = s.count("W")
      if s[n-1] == "W":
         cnt -= 1
   else: 
      a = s[:i]
      b = s[i+1:]
      a_cnt = a.count("W")
      if a_cnt > min_c: continue
      b_cnt = b.count("E")
      if b_cnt > min_c: continue
      cnt = a_cnt + b_cnt
      if cnt > min_c: continue
   min_c = min(min_c, cnt)

print(min_c)

### FIXED CODE ###

def solve():
    n = int(input())
    s = input()

    cnt = [s[1:n].count("E")]

    for i in range(1, n):
        cnt.append(cnt[i-1] - int(s[i] is "E") + int(s[i-1] is "W"))

    print(min(cnt))

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

import numpy as np
n,k=map(int,input().split())
h=np.array(list(map(int,input().split())),dtype=np.int64)
dp=np.ones(n,dtype=np.int64)*2**64
dp[0]=0
for i in range(n-1):
  cost=np.abs(h[i]-h[i+1:i+k+1])
  np.minimum(dp[i+1:i+k+1],dp[i]+cost,out=dp[i+1:i+k+1])
print(dp[-1])

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
h=np.array(list(map(int,input().split())),dtype=np.int64)
dp=np.full(n,10**10,dtype=np.int64)
dp[0]=0
for i in range(n-1):
  cost=np.abs(h[i]-h[i+1:i+k+1])
  np.minimum(dp[i+1:i+k+1],dp[i]+cost,out=dp[i+1:i+k+1])
print(dp[-1])
### BUGGY CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N, K = mapint_inp()

l = list(range(N+1))
mn_list = []
for i in range(K, N+2):
    mn_list.append(sum(l[:i]))

r = l[::-1]
mx_list = []
for i in range(K, N+2):
    mx_list.append(sum(r[:i]))

ans = 0
for mn, mx in zip(mn_list, mx_list):
    ans += mx-mn+1

print(ans)

### FIXED CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N, K = mapint_inp()
MOD = 10**9+7

ans = 0
for i in range(K, N+2):
    mn = i*(i-1) // 2
    mx = i*(2*N-i+1) // 2
    ans += mx - mn + 1

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

N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
colors[1] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    for u, v, w in UVW:
        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])



for i in range(1, N+1):
    print(colors[i])

### FIXED CODE ###

N = int(input())

u_list = []
v_list = []
w_list = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  u_list.append(u-1)
  v_list.append(v-1)
  w_list.append(w)
  
color_dict = dict()
uvw_list = list(zip(u_list, v_list, w_list))
color_dict[u_list[0]] = 1

def eval_single(u, v, w, color_dict):
  skip = True

  if u in color_dict:
    color_dict[v] = assign_color(color_dict[u], w)
    skip = False
    
  if v in color_dict:
    color_dict[u] = assign_color(color_dict[v], w)
    skip = False
    
  return skip, color_dict
  

def assign_color(color, w):
  if w%2==0:
    return color
  else:
    return color*(-1)+1
  
while True:
  ind_list = []
  for ind, (u, v, w) in enumerate(uvw_list):
    skip, color_dict = eval_single(u, v, w, color_dict)
    
    if skip:
      ind_list.append(ind)

  uvw_list = [uvw_list[ind] for ind in ind_list]
  
  if len(color_dict) == N:
    break

for i in range(N):
  print(color_dict[i])
### BUGGY CODE ###

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

if B > N:
    reverse = True
else:
    reverse = False

if reverse:
    for x in reversed(range(1, N + 1)):
        if x == B:
            break
        else:
            value = int(A * x / B) - A * int(x / B)
            if answer <= value:
                answer = value
else:
    for x in range(1, N + 1):
        if x == B:
            break
        else:
            value = int(A * x / B) - A * int(x / B)
            if answer <= value:
                answer = value

print(answer)

### FIXED CODE ###

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

if N < B:
    x = N
else:
    x = B - 1

value = int(A * x / B) - A * int(x / B)
print(value)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
C = list(map(int,input().split()))
##################################################################
max_point = -10000000000000
for i in range(N):
  point = 0
  now = i
  for j in range(K):
    next_place = P[now]-1
    point += C[next_place]
    max_point = max(point,max_point)
    now = next_place

print(max_point)

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(lambda z:int(z)-1, input().split()))
c = list(map(int, input().split()))

data = [[0 for i in range(n+1)] for j in range(n)]
loop = [10**10 for i in range(n)]
for i in range(n):
    j = i
    for t in range(1,n+1):
        j = p[j]
        data[i][t] += data[i][t-1] + c[j]
        if j == i:
            loop[i] = min(loop[i],t)

ans = -10**10
#print(data)
#print([data[i][loop[i]] for i in range(n)])

for i in range(n):
    for j in range(1,min(n,k)+1):
        if j > loop[i]:break
        if data[i][loop[i]] <= 0:
            ans = max(ans,data[i][j])
        else:
            ans = max(ans,data[i][loop[i]]*((k-j)//loop[i])+data[i][j])

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

n = int(input())
l = list(map(int, input().split()))
L = list(set(l))
count = 0
for x in L:
  num = l.count(x)
  if num == x:
    continue
  elif num > x:
    count += num - x
  else:
    count += num
print(count)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
dic = {}
count = 0

for i in range(n):
  dic.setdefault(l[i],0)
  dic[l[i]] += 1

for x,y in dic.items():
  if x <= y:
    count += y - x
  else:
    count += y
print(count)
### BUGGY CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] * inv[n + k - i] * p25[n + k - i]
    ans %= MOD

print(ans)

### FIXED CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD
    if ans < 0:
        ans += MOD

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

S = input()
S_list = [int(S[i]) for i in range(len(S))]
ans = 0
rm_list = []
for aaa in range(len(S) // 2):
    for i in range(len(S_list) - 1):
        if S_list[i] != S_list[i + 1] and i not in rm_list:
            rm_list.append(i)
            rm_list.append(i + 1)
    S_list = [S_list[i] for i in range(len(S_list)) if i not in rm_list]
    if len(rm_list) == 0:
        break
    ans += len(rm_list)
    rm_list = []
print(ans)


### FIXED CODE ###

S = input()
a = sum([int(S[i]) for i in range(len(S))])
b = len(S) - a
print(2*min(a, b))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
    a[-1]//=2
    a.sort()
print(sum(a))


### FIXED CODE ###

import sys
import heapq
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
heapq.heapify(a)
for i in range(m):
  heapq.heappushpop(a,-(-a[0]//2))
print(-sum(a))
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

d=deque(A)
ans=[]
for i in range(n):
    c=sum(d[i]*((-1)**i) for i in range(n))
    ans.append(c)
    d.append(d.popleft())
print(*ans)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

ans=[0]*n

ans[0]=sum([A[i]*((-1)**i) for i in range(n)])
for i in range(1,n):
    ans[i]=2*A[i-1]-ans[i-1]
print(*ans)
### BUGGY CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        dic[s[a]].remove(a)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)


### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
### BUGGY CODE ###

from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
visited = [False]*(H*W)
q = deque()

field = [input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            visited[i*W+j] = True
            q.append((i, j, 0))

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and visited[ny*W+nx] == False:
            visited[ny*W+nx] = True
            q.append((ny, nx, lv+1))

print(res)


### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)