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

from collections import Counter
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())

    ac = Counter(a)
    acl = defaultdict(int)
    for ae in ac:
        acl[ae] = ac[ae]

    for _ in range(q):
        b, c = map(int, input().split())
        rmed = acl[b]
        acl[c] += rmed
        acl[b] = 0
        r = sum([i * v for i, v in acl.items()])
        print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    asum = sum(a)
    ac = Counter(a)
    acl = defaultdict(int)
    for ae in ac:
        acl[ae] = ac[ae]

    for _ in range(q):
        b, c = map(int, input().split())
        rmed = acl[b]
        acl[c] += rmed
        acl[b] = 0
        asum -= b * rmed
        asum += c * rmed
        print(asum)

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

n = int(input())
A = list(map(int, input().split()))
A.sort()
ama = A[-1]
ama2 = (ama + 1)//2

for i in range(ama2 + 1):
    a = ama2 + i
    b = ama2 - i

    if b in A:
        print(ama, end=' ')
        print(b)
        exit()
    if a in A:
        print(ama, end=' ')
        print(a)
        exit()

### FIXED CODE ###

import bisect

n = int(input())
A = list(map(int, input().split()))
A.sort()
ama = A[-1]
print(ama, end=' ')
ama2 = (ama + 1)//2
w = bisect.bisect_left(A, ama2)

a = A[w-1]
b = A[w]
if abs(a-ama2) > abs(b-ama2):
    print(b)
else:
    print(a)
### BUGGY CODE ###

H, W, M = map(int, input().split())
targets = [list(map(int, input().split())) for _ in range(M)]
x_counter = [0 for _ in range(W + 1)]
y_counter = [0 for _ in range(H + 1)]
y_index = []
x_index = []
check = 0

for target in targets:
    y_counter[target[0]] += 1
    x_counter[target[1]] += 1

y_max, x_max = max(y_counter), max(x_counter)

for i in range(H + 1):
    if y_counter[i] == y_max:
        y_index.append(i)

for j in range(W + 1):
    if x_counter[j] == x_max:
        x_index.append(j)
check = len(y_index) * len(x_index)
for k in range(M):
    r, c = targets[k]
    if r in y_index and c in x_index:
        check -= 1

print(y_max + x_max if check > 0 else y_max + x_max -1)


### FIXED CODE ###

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)
### BUGGY CODE ###

n, k = map(int, input().split())
if n==k or k==1:
  print(0)
else:
  ans=n
  res=[ans]
  while(1):
    ans=abs(ans-k)
    if ans in res or ans == k:
      break
    res.append(ans)
  print(min(res))

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k - n%k))
### BUGGY CODE ###


S=list(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if t%2 != 0:
            S.reverse()
            t=0
        if T[1]=="1":
            S.insert(0,T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))

### FIXED CODE ###

from collections import deque

S=deque(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if (T[1]=="1" and t%2 == 0) or (T[1]=="2" and t%2 != 0):
            S.appendleft(T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))
### BUGGY CODE ###

import collections
import itertools
N = int(input())
s = "MARCH"
lst = []

for i in range(N):
  begin = list(input())[0] 
  if begin in list(s):
    lst.append(begin)
ans = 0
for i in list(itertools.combinations(lst,3)):
  if (len(set(i)) == 3):
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
N = int(input())
s = "MARCH"
dct = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
  begin = input()[0] 
  if begin in dct.keys():
    dct[begin] += 1
cmb = itertools.combinations(list(dct.keys()), 3)
ans = 0
for i in list(cmb):
  n = 1
  for j in i:
    n *= dct[j]
  ans += n
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 0
m = max(a)
x = 0
while m > 0:
    m >>= 1
    x += 1 
 
for i in range(x):
    cnt = 0
    for j in range(n):
        if a[j]>>i & 1 == 0: cnt += 1
    ans = (ans+pow(2,i,mod)*cnt%mod*(n-cnt)%mod)%mod
    
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)
### BUGGY CODE ###

K = int(input())
n = 1000000

if K % 2 == 0:
    print(-1)
elif K % 7 == 0:
    amari = 10
    for i in range(K):
        if amari % int(9 * (K / 7)) == 1:
            print(i + 1)
            break
        else:
            amari = amari * 10
else:
    amari = 70
    for i in range(K):
        if amari % int(9 * K) == 7:
            print(i + 1)
            break
        else:
            amari = amari * 10

### FIXED CODE ###

k = int(input())
m = 0
 
for i in range(k):
    m = (m * 10 + 7) % k
    if m == 0:
        break
    elif i == k - 1:
        print(-1)
        exit()
 
print(i + 1)
### BUGGY CODE ###

N, M = map(int, input().split())
gate = [0] * N
for i in range(M):
    L, R = map(int, input().split())
    for j in range(L-1, R):
        gate[j] += 1

count = 0
for k in gate:
    if k == M:
        count += 1
print(count)


### FIXED CODE ###

N, M = map(int, input().split())
gate = [0] * N
maxL, minR = 0, N
for i in range(M):
    L, R = map(int, input().split())
    maxL = max(maxL, L-1)
    minR = min(minR, R-1)

count = minR - maxL + 1
if count >= 0:
    print(count)
else:
    print(0)
### BUGGY CODE ###

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x: x[0])

ans = 0

for i in range(N):
    if XH[i][1] <= 0:
        continue
    explode = (XH[i][1] + A - 1) // A
    for j in range(i, N):
        if XH[j][0] <= XH[i][0]+2*D:
            XH[j][1] -= explode*A
        else:
            break

    ans += explode

print(ans)


### FIXED CODE ###

from collections import deque
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()

que = deque([])
ans = 0
total = 0

for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue
    while que and XH[i][0] > que[0][0]:
        _, tmp = que.popleft()
        total -= tmp

    h -= total
    if h > 0:
        atk = (h + A - 1) // A
        damage = atk * A
        ans += atk
        total += damage
        que.append((x+2*D, damage))

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

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def resolve():
    n=int(input())
    s=input()
    for w in range(1,n): # 幅数
        flag=False
        for i in range(n-w+1):
            if s.count(s[i:i+w])>=2:
                flag=True
        if flag is False:
            break
    print(w-1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=sys.stdin.readline
def resolve():
    n=int(input())
    s=input()
    dp=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue # i<j
        if s[i]==s[j]:
            dp[i][j]=dp[i+1][j+1]+1
        else:
            dp[i][j]=0
    ans=0
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue
        ans=max(ans,min(j-i,dp[i][j]))
    print(ans)


resolve()
### BUGGY CODE ###

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

mod = 10**9 + 7

dp = [1] * (N+1)

for i in A:
    dp[i] = 0

for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

### FIXED CODE ###

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

mod = 10**9 + 7

dp = [1] * (N+1)

for i in A:
    dp[i] = 0

for i in range(2, N+1):
        dp[i] *= (dp[i-1] + dp[i-2]) % mod

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

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

ans =[]
for i in range(1,n+1):
    ans.append(str(a.index(i)+1))
print(" ".join(ans))

### FIXED CODE ###

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

b =[]
for i in range(0,len(a)):
    b.append([a[i],i+1])
b.sort()

for i in range(n):
    print(str(b[i][1])+' ',end='')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N + 1):
    print(A.index(i) + 1 , end = ' ')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]* N
for i in range(N):
    B[A[i]-1] = i + 1
print(*B)
### BUGGY CODE ###

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

for i in range(N):
    x=i+1
    a=(A*x)//B
    b=x//B
    f=a-A*b
    if max<f:
        max=f
print(max)


### FIXED CODE ###

A,B,N=map(int,input().split())
if N+1>=B:
    T=int(A*(B-1)/B)
    print(T)
else:
    T=int(A*N/B)
    print(T)
### BUGGY CODE ###

import math

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

result = 0
for x in range(0,len(h)):
    count = 0
    for y in range(x,len(h)):
        if y == len(h)-1:
            break
        if  h[y] >= h[y+1]:
            count += 1
        else:
            break
        if y == len(h):
            break
    if count > result:
        result = count

print(result)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
result = []
count = 0
for x in range(0,n-1):
    if h[x] >= h[x+1]:
        count += 1
    else:
        result.append(count)
        count = 0
result.append(count)
print(max(result))
### BUGGY CODE ###

s = input()
k = int(input())
d=[]
for l in range(1, len(s)+1):
  for j in range(len(s)):
    if j+l > len(s):
      break
    d.append(s[j:j+l])
d=list(set(d))
d=sorted(d)
print(d[k-1])

### FIXED CODE ###

import string
s = input()
k = int(input())
d=set()
for sp in string.ascii_lowercase:
  for i,sd in enumerate(s,start=0):
    if sp == sd:
      e=set()
      for l in range(1, 6):
        if i+l > len(s):
          break
        e.add(s[i:i+l])
      d=d|e
  if len(d) >= k:
    break

d=list(d)
d=sorted(d)
print(d[k-1])
### BUGGY CODE ###

import sys


class BinaryIndexedTree:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.MOD
            i += i & -i

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)


### FIXED CODE ###

import sys


class BinaryIndexedTree:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.MOD
            i += i & -i

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)
### BUGGY CODE ###

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

n = int(input())
s = input()

s1 = list(s)
s2 = list(s)

# print(s1)
# print(s2)
# print('')

numlist = []
for i in range(n):
    if i > 0:
        for j in range(i):
            s2[j] = 'E'
    for j in range(i+1,n):
        s2[j] = 'W'

    temp = 0
    for j in range(n):
        if s1[j] != s2[j]:
            temp += 1

    numlist.append(temp)

    # print(s1)
    # print(s2)
    # print('')

# 出力
print("{}".format(min(numlist)))


### FIXED CODE ###

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

n = int(input())
s = input()

LW_cnt = 0
RE_cnt = s[1:].count('E')


numlist = []
for i in range(n):
    if i > 0:
        if s[i-1] == 'W':
            LW_cnt += 1
        if s[i] == 'E':
            RE_cnt -= 1

    numlist.append(LW_cnt+RE_cnt)

# 出力
print("{}".format(min(numlist)))
### BUGGY CODE ###

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

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                if calcAns(imid+1)<calcAns(imid):
                        imin = imid+1
                elif calcAns(imid-1)<calcAns(imid):
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))

### FIXED CODE ###

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

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                tmp = calcAns(imid)
                if calcAns(imid+1)<tmp:
                        imin = imid+1
                elif calcAns(imid-1)<tmp:
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))
### BUGGY CODE ###

N = int(input())
a=list(map(int,input().split()))
gos=[0]*(N-1)
ans=max(a)
for i in range(1,N):
    mae=sum(a[:i])
    ato=sum(a)-mae
    ans=min(ans,abs(mae-ato))
print(ans)

### FIXED CODE ###

N = int(input())
a=list(map(int,input().split()))
ans=2020202020
s=sum(a)
mae=a[0]
for i in range(1,N):
    mae+=a[i]
    ato=s-mae
    if mae-ato>0:
        ans=min(abs(sum(a[:i])-sum(a[i:])),abs(sum(a[:i+1])-sum(a[i+1:])))
        break
    else:
        ans=min(ans,abs(mae-ato))
print(ans)
### BUGGY CODE ###

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

l = [i for i in range(a, b+1)]
l = sorted(set(l[:k] + l[-k:]))

for i in l:
  print(i)

### FIXED CODE ###

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

if b - a < k*2:
    for j in [i for i in range(a, b+1)]:
        print(j)
else:
    for j in [i for i in range(a, a+k)]:
        print(j)
    for j in [i for i in range(b-k+1, b+1)]:
        print(j)
### BUGGY CODE ###

import  collections

H, W, M = map(int, input().split())

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = []
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.append((h, w))

max_count = 0

for h, h_count in H_count.items():
    for w, w_count in W_count.items():
        count = h_count + w_count
        if (h, w) in points:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

### FIXED CODE ###

H, W, M = map(int, input().split())

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            exit()

print(H_max + W_max -1)
### BUGGY CODE ###

D, G = map(int, input().split())
P = []
C = []
A = []
for i in range(D):
  p, c = map(int, input().split())
  for j in range(p - 1):
    P.append((i + 1) * 100 * (j + 1))
    C.append(j + 1)
    A.append(i + 1)
  P.append((i + 1) * 100 * p + c)
  C.append(p)
  A.append(i + 1)
  
out = 1000
for i in range(2**len(P)):
  total = 0
  count = 0
  solved = []
  for j in range(len(P)):
    if i & (1 << j):
      if A[j] not in solved:
        total += P[j]
        count += C[j]
        solved.append(A[j])
  if total >= G:
    if count < out:
      out = count
print(out)

### FIXED CODE ###

D, G = map(int, input().split())
P = []
C = []
for i in range(D):
  p, c = map(int, input().split())
  P.append(p)
  C.append(c)
  
out = 1000
for i in range(2**D):
  total = 0
  count = 0
  for j in range(D):
    p, c = P[j], C[j]
    if i & (1 << j):
      count += p
      total += p * 100 * (j + 1) + c
    else:
      k = j
      
  if total >= G:
    out = min(out, count) 
    continue
    
  p = P[k]
  for j in range(p):
    count += 1
    total += 100 * (k + 1)
    if total >= G:
      out = min(out, count)
      break

print(out)
### BUGGY CODE ###

N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
for i in cand_1:
    for j in cand_2:
        if i == j:
            ans = "POSSIBLE"
            break
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
heapq.heapify(cand_1)
heapq.heapify(cand_2)


while len(cand_1) != 0 and len(cand_2) != 0:
    if cand_1[0] < cand_2[0]:
        heapq.heappop(cand_1)
    elif cand_1[0] > cand_2[0]:
        heapq.heappop(cand_2)
    else:
        ans = "POSSIBLE"
        break
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(X: str):
    next = X.replace("ST", "")
    while next != X:
        X = next
        next = X.replace("ST", "")
    print(len(X))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = next(tokens)  # type: str
    solve(X)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque


def solve(X: str):
    stack = deque(X[0])
    for i in range(1, len(X)):
        if not stack:
            stack.append(X[i])
            continue
        if stack[-1] == "T":
            stack.append(X[i])
            continue
        if X[i] == "T":
            stack.pop()
            continue
        stack.append(X[i])

    print(len(stack))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = next(tokens)  # type: str
    solve(X)

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

from collections import defaultdict

class BIT(object):
    def __init__(self, N, init=0):
        self.N = N
        self.bit = [init for _ in range(N)]

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            x = (x & (x + 1)) - 1
        return s

n = int(input())
s = list(input())
q = int(input())

d = defaultdict(lambda: BIT(n))
for i, si in enumerate(s):
    d[si].add(i, 1)

for i in range(q):
    k, x, y = input().split()
    if k == '1':
        x = int(x) - 1
        d[s[x]].add(x, -1)
        d[y].add(x, 1)
        s[x] = y
    else:
        l = int(x) - 1
        r = int(y) - 1
        ans = 0
        for v in d.values():
            ans += (v.sum(r + 1) - v.sum(l)) > 0
        print(ans)


### FIXED CODE ###

from collections import defaultdict

class BIT(object):
    def __init__(self, N, init=0):
        self.N = N
        self.bit = [init for _ in range(N)]

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            x = (x & (x + 1)) - 1
        return s

n = int(input())
s = list(input())
q = int(input())

d = defaultdict(lambda: BIT(n))
for i, si in enumerate(s):
    d[si].add(i, 1)

for i in range(q):
    k, x, y = input().split()
    if k == '1':
        x = int(x) - 1
        d[s[x]].add(x, -1)
        d[y].add(x, 1)
        s[x] = y
    else:
        l = int(x) - 1
        r = int(y) - 1
        ans = 0
        for v in d.values():
            ans += (v.sum(r + 1) - v.sum(l)) > 0
        print(ans)