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

from collections import Counter
n=int(input())
a=[int(A) for A in input().split()]
for k in range(1, n+1):
    ball = a[0:k-1] + a[k:]
    cnt=0
    for cc in Counter(ball).values():
        if cc <2:
            continue
        cnt += cc*(cc-1)/2
    print(int(cnt))


### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(A) for A in input().split()]

cnt=Counter(a)
s=sum([c*(c-1)//2 for c in cnt.values()])

for k in a:
    print(s-(cnt[k]-1))
### BUGGY CODE ###

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

ans = 0
waru = 0
cnt = 0

while True:
    for i in range(n):
        if A[i] % 2 == 0:
            if waru == 1:
                A[i] *= 3
            else:
                A[i] //= 2
                waru = 1
        else:
            A[i] *= 3
    if waru == 0:
        print(ans)
        exit()
    else:
        ans += 1
    waru = 0


### FIXED CODE ###

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

ans = 0

for a in A:
    while a % 2 == 0:
        a /= 2
        ans += 1

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

import numpy as np

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

N = NKQ[0]
K = NKQ[1]
Q = NKQ[2]

A = [int(input()) for i in range(Q)]

points = K*np.ones(N, dtype="int")
for i in range(Q):
    points = points - 1
    points[A[i]-1] = points[A[i]-1] + 1

for i in range(len(points)):
    if points[i] > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import numpy as np

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

N = NKQ[0]
K = NKQ[1]
Q = NKQ[2]

A = [int(input()) for i in range(Q)]

negative = np.ones(N, dtype="int")

for i in range(Q):
    negative[A[i]-1] = negative[A[i]-1] + 1

for i in range(N):
    if negative[i] > Q - K + 1:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
length_list = input().split()

counter = 0
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      a = int(length_list[i])
      b = int(length_list[j])
      c = int(length_list[k])
      if (a < b+c) and (b < c+a) and (c < a+b):
        counter += 1

print(counter)
  

### FIXED CODE ###

import bisect
n = int(input())
length_list = sorted(list(map(int, input().split())))
result = 0
 
for i in range(n-2):
  for j in range(i+1, n-1):
    upper = length_list[i] + length_list[j] - 1
    search_target = length_list[j+1:]
    less_than_upper = bisect.bisect_right(search_target, upper)
    result += less_than_upper
    
print(result)
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

cnt = 0
for t in T:
	if t in S:
		cnt += 1

print(cnt)


### FIXED CODE ###

from bisect import bisect_left

def index(A, x):
	i = bisect_left(A, x)
	if i != len(A) and A[i] == x:
		return i
	else:
		return -1


n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

cnt = 0
for t in T:
	if index(S, t)>=0:
		cnt += 1

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

l,r = map(int, input().split())
MOD = 2019

min = MOD
for i in range(l, r):
    if min == 0: break
    for j in range(i+1, r+1):
        im, jm = i % MOD, j % MOD
        val = (im * jm) % MOD
        if val < min:
            min = val
print(min)


### FIXED CODE ###

l,r = map(int, input().split())
MOD = 2019

if r - l >= MOD:
    print(0)
else:
    min = MOD
    for i in range(l, r):
        if min == 0: break
        for j in range(i+1, r+1):
            im, jm = i % MOD, j % MOD
            val = (im * jm) % MOD
            if val < min:
                min = val
    print(min)
### BUGGY CODE ###

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

for order in range(1, n+1):
    people = people_count.index(order) + 1
    print(people, end=" ")

### FIXED CODE ###

import numpy as np
n = int(input())
people_count = list(map(int, input().split()))


people_count = np.array(people_count)
arg = people_count.argsort()
for i in arg:
    print(i+1, end=" ")
### BUGGY CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    A = [input().strip() for _ in range(H)]

    q = collections.deque()

    ans = [[0] * W for j in range(H)]

    for j in range(H):
        for i in range(W):
            if A[j][i] == '#':
                q.append((j, i, 0))
                ans[j][i] = -1

    while q:
        c = q.popleft()
        y, x, d = c[0], c[1], c[2]
        for ny, nx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if 0 <= y + ny < H and 0 <= x + nx < W:
                if ans[y + ny][x + nx] == 0:
                    ans[y + ny][x + nx] = d + 1
                    q.append((y + ny, x + nx, d + 1))

    a = 0
    for aa in ans:
        a = max(a, max(aa))
    print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    A = [input().strip() for _ in range(H)]

    q = collections.deque()

    ans = [[0] * W for j in range(H)]

    for j in range(H):
        for i in range(W):
            if A[j][i] == '#':
                q.append((j, i, 0))
                ans[j][i] = -1

    while q:
        c = q.popleft()
        y, x, d = c[0], c[1], c[2]
        for ny, nx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if 0 <= y + ny < H and 0 <= x + nx < W:
                if ans[y + ny][x + nx] == 0:
                    ans[y + ny][x + nx] = d + 1
                    q.append((y + ny, x + nx, d + 1))

    a = 0
    for aa in ans:
        a = max(a, max(aa))
    print(a)


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

mod = 10 ** 9 + 7
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))
 
ans = sum(A[i] * A[j] for i in range(0,N-1) for j in range(i+1,N))
 
print(ans % mod)

### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

N = int(input())
S = list(input())
r = S.count('R')
g = S.count('G')
b = S.count('B')
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if(j+(j-i) >= N):
            continue
        if((S[j+(j-i)] != S[i]) and (S[j+(j-i)] != S[j]) and (S[i] != S[j])):
            cnt += 1
print(r*g*b-cnt)

### FIXED CODE ###

N = int(input())
S = list(input())
r = S.count('R')
g = S.count('G')
b = S.count('B')
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if(j+(j-i) >= N):
            break
        if((S[j+(j-i)] != S[i]) and (S[j+(j-i)] != S[j]) and (S[i] != S[j])):
            cnt += 1
print(r*g*b-cnt)
### BUGGY CODE ###

from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if ans == 0:
        break

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W) or A[ni][nj] == "#":
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)


### FIXED CODE ###

from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

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

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

for i in range(0,n-1):
    if max(A[0:i+1])>A[i+1]:
        x=x+((max(A[0:i+1]))-A[i+1])
    else:
        continue

print(x)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
x=0
m=A[0]

for i in range(0,n-1):
    if m>A[i+1]:
        x=x+(m-A[i+1])
    else:
        m=A[i+1]

print(x)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)

for i in range(m):
    if a[0] == 0:
        break
    a[0] = a[0] // 2
    a.sort(reverse = True)
print(sum(a))

### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= -1
heapq.heapify(a)
 
for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))
    
print(sum(a)*(-1))
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

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

g=A[0]
l=A[0]
for i in range(N):
    g=gcd(l,A[i])
    l=l*A[i]//g
    
ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

S = str(input())

for i in range(len(S)-1):
    if S[i] == '?':
        if S[i+1] == 'P':
            S = S[:i] + 'D' + S[i+1:]
        else:
            S = S[:i] + 'P' + S[i+1:]

if S[len(S)-1] == '?':
    S = S[:len(S)-1] + 'D'

print(S)

### FIXED CODE ###

S = list(str(input()))

for i in range(len(S)-1):
    if i == 0 and S[0] == '?':
        if S[i+1] == 'P':
            S[0] = 'D'
        else:
            S[0] = 'P'
    if S[i] == '?':
        if S[i+1] == 'P':
            S[i] = 'D'
        else:
            if S[i-1] == 'P':
                S[i] = 'D'
            else:
                S[i] = 'P'

if S[len(S)-1] == '?':
    S[len(S)-1] = 'D'

strS = "".join(S)

print(strS)
### BUGGY CODE ###

N,M = map(int,input().split())
li = [tuple(map(int,input().split())) for i in range(M)]
numb = [li[i][1] for i in range(M) if li[i][0] == 1]
ans = ''
for i in range(M):
  if li[i][0] in numb and li[i][1] == N:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)
    

### FIXED CODE ###

N,M = map(int,input().split())
li = []
numb = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        li.append(b)
    elif b == N:
        numb.append(a)
ans = set(li) & set(numb)
if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
a = int(input())
c = [a]
c_len = 1
for i in range(1, n):
    a = int(input())
    for j in range(c_len):
        if c[j] < a:
            c[j] = a
            break
    else:
        c.append(a)
        c_len += 1
print(c_len)


### FIXED CODE ###

N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        if l[-1] == a:
            ans += 1
        else:
            i = l.index(a) + 1
            v = l[i]
            if d[v] == 1:
                del d[v]
                l.remove(v)
            else:
                d[v] -= 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
        elif l[-1] > a:
            l.append(a)
            ans += 1
        else:
            left, right = 0, len(l) - 1
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
        d[a] = 1
print(ans)
### BUGGY CODE ###

import math

from operator import mul
from functools import reduce

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result





n, k = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
mod=10**9+7
min=0
max=0
for i in range(n-k+1):
    x=cmb(n-i-1,k-1)%mod
    min+=a[i]*x
    max+=a[n-1-i]*x
    min%=mod
    max%=mod

ans=max-min


print(ans%mod)

### FIXED CODE ###

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10 ** 9 + 7  # 出力の制限
N = 10 ** 5
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod =10**9+7
mi = 0
ma = 0
for i in range(n - k + 1):
    x = cmb(n - i - 1, k - 1, mod)
    mi += a[i] * x
    ma += a[n - 1 - i] * x
    mi %= mod
    ma %= mod

ans = ma - mi

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

n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
from collections import deque
ans = -2*10**9
for idx, root in enumerate(P):
    scores = [C[root]]
    p = P[root]
    while True:
        scores.append(scores[-1] + C[p])
        p = P[p]
        if p == root:
            break

    sc = scores[-1]
    if sc <= 0:
        if k < len(scores):
            ans = max(ans, max(scores[:k]))
        else:
            ans = max(ans, max(scores))
    else:
        kk, r = divmod(k, len(scores))
        if r == 0:
            ans = max(ans, kk*sc, (kk-1)*sc + max(scores))
        else:
            ans = max(ans, kk*sc + max(scores[:r]))
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
CC = [[] for _ in range(n)]
for idx, p in enumerate(P):
    CC[idx].append(C[p])
    pp = P[p]
    for _ in range(n):
        CC[idx].append(C[pp])
        pp = P[pp]
        if pp == p:
            break
        
from itertools import accumulate
ans = -2*(10**9)
for cc in CC:
    cca = list(accumulate(cc))
    if cca[-1] <= 0:
        # 1周分のうちの最大値
        if k < len(cc):
            ans = max(ans, max(cca[:k]))
        else:
            ans = max(ans, max(cca))
    else:
        # kk周したほうが良い
        kk, r = divmod(k, len(cc))
        if r == 0:
            ans = max(ans, kk*cca[-1], (kk-1)*cca[-1]+max(cca))
        else:
            ans = max(ans, kk*cca[-1] + max(cca[:r]))
print(ans)
### BUGGY CODE ###

S=str(input())
num=0
def left(S,num):
    ini=S[0]
    for i in range(len(S)):
        if i==0:
            continue
        if ini==S[i]:
            continue
        if ini!=S[i]:
            g=S[:i-1]
            h=S[i+1:]
            num+=1
            return (g+h,num)
    return ("",num)
def right(S,num):
    S=S[::-1]
    ini=S[0]
    for i in range(len(S)):
        if i==0:
            continue
        if ini==S[i]:
            continue
        if ini!=S[i]:
            g=S[:i-1]
            h=S[i+1:]
            num+=1
            return ((g+h)[::-1],num)
    return ("",num)  
for i in range(len(S)):
    S,num=left(S,num)
    if S=="":
        break
    S,num=right(S,num)
    if S=="":
        break
print(num*2)
    

### FIXED CODE ###

S=input()
#N=int(input())
#H,W=map(int,input().split())
a=0
b=0
for i in range(len(S)):
    if S[i]=="0":
        a+=1
    else:
        b+=1
print(min([a,b])*2)
### BUGGY CODE ###

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

E = [0]*N
W = [0]*N
for i in range(N):
    if S[i] == 'E':
        E[i] = 1
    else:
        W[i] = 1
    
ans = N
for l in range(N):
    num = sum(E[l+1:])
    num += sum(W[:l])
    if ans >= num:
        ans = num

print(ans)

### FIXED CODE ###

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

E = [0]*(N+2)
W = [0]*(N+2)
for i in range(1,N+1):
    if S[i-1] == 'E':
        E[i] = E[i-1] + 1
        W[i] = W[i-1]
    else:
        W[i] = W[i-1] + 1
        E[i] = E[i-1]

ans = 300000
for L in range(1,N+1):
    num = E[N] - E[L] + W[L-1] -W[0]
    if ans > num:
        ans = num

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

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
# precise but slow
# from math import floor
# from fractions import Fraction
# a, b = input().split()
# a = int(a)
# b = Fraction(b)
# print(floor(a * b))
# fast but only decimal fixed point
import sys
from math import floor
from decimal import Decimal
N = int(sys.stdin.readline())
a = tuple(sys.stdin.readline().rstrip() for _ in range(N)) # multi line with single param
#a = [Decimal(e)*1000000000 for e in a]
a = [Decimal(e) for e in a]
ret = 0
for i in range(N):
    for j in range(i):
        if a[i]*a[j] == int(a[i]*a[j]):
            #print(a[i],a[j],a[i]*a[j])
            ret += 1
print(ret)

### FIXED CODE ###

# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
# precise but slow
# from math import floor
# from fractions import Fraction
# a, b = input().split()
# a = int(a)
# b = Fraction(b)
# print(floor(a * b))
# fast but only decimal fixed point
import sys,collections
from math import floor
from decimal import Decimal
N = int(sys.stdin.readline())
a = tuple(sys.stdin.readline().rstrip() for _ in range(N)) # multi line with single param
a = [int(Decimal(e)*1000000000) for e in a]

d = collections.defaultdict(int)
for e in a:#200 000
    b = e
    t = 0
    while b != 0 and b % 2 == 0:
        t += 1
        b = b//2
    b = e
    f = 0
    while b != 0 and b % 5 == 0:
        f += 1
        b = b//5
    d[(min(f,18),min(t,18))] += 1

ret = 0
for ft1,v1 in d.items():
    for ft2,v2 in d.items():
        f1,t1 = ft1
        f2,t2 = ft2
        if ft1 < ft2:
            continue
        if f1+f2 >= 18 and t1+t2 >= 18:
            if ft1 == ft2:
                ret += (v1*(v2-1))//2
            else:
                ret += v1*v2
print(ret)
### BUGGY CODE ###

n = int(input())
import sys
pn = list(map(int, sys.stdin.readline().split()))

ans = 1

for i in range(1, n):
    if min(pn[:i+1])==pn[i]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
import sys
pn = list(map(int, sys.stdin.readline().split()))

ans = 1
mini = pn[0]

for i in range(1, n):
    mini = min(mini, pn[i])
    if mini==pn[i]:
        ans += 1

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

N=int(input())
P=list(map(int,input().split()))
count=0
for i in range(N):
  flag=0
  for j in range(i):
    if P[i]>P[j]:
      flag=1
      break
  if flag==0:
    count=count+1
    
print(count)

### FIXED CODE ###

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

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return set([])
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   
   print(len(qr(i-1,c,0,0,n)))
   
 q-=1


### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[0 for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return 0
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,1<<(ord(s[i])-ord("a")))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,1<<(ord(c)-ord("a")))
 else:
   c=int(c)
   x=0
   z=qr(i-1,c,0,0,n)
   while z:
     if z%2==1:
        x+=1
     z>>=1
   print(x)
 q-=1
### BUGGY CODE ###

n_dice, n_choice = map(int, input().split())
dice_EV_list = tuple(map(lambda x:(x*(x+1))/(2*x) , map(int, input().split())))
sumofEV_list = [sum(dice_EV_list[i:i+n_choice]) for i in range(n_dice - n_choice + 1)]
print(max(sumofEV_list))

### FIXED CODE ###

import itertools

n, k = map(int, input().split())
dices = map(int, input().split())
dices_EV = list(map(lambda x:(x+1)/2, dices))
dices_EV_accumulate = list(itertools.accumulate(dices_EV))
dices_EV_sums = [dices_EV_accumulate[i+k] - dices_EV_accumulate[i] for i in range(n-k)]
dices_EV_sums.append(dices_EV_accumulate[k-1])
print(max(dices_EV_sums))
### BUGGY CODE ###

from functools import reduce

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

before = 1

for a in ai[ 0 : k ]:
    before *= a

for i in range(n - k):
    after = before * ai[i + k] // ai[i]

    if before < after:
        print('Yes')

    else:
        print('No')

    before = after


### FIXED CODE ###

from math import log2

n, k = map(int, input().split())
ai   = list(map(lambda x: log2(int(x)), input().split()))

before = sum(ai[ 0 : k ])

for i in range(n - k):
    after = before + ai[i + k] - ai[i]

    if before < after:
        print('Yes')

    else:
        print('No')

    before = after