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

from collections import deque, Counter
import itertools

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

d_h = deque()
d_w = deque()
for h, w in HW:
    d_h.append(h)
    d_w.append(w)

# 出現頻度順にソート
c_h = Counter(d_h).most_common()
c_w = Counter(d_w).most_common()


# 登場頻度の一番高い回数
n_h = c_h[0][1]
n_w = c_w[0][1]

# 同率のものを数える
t_h = deque()
t_w = deque()

for k, v in c_h:
    if v == n_h:
        t_h.append(k)
    else:
        break

for k, v in c_w:
    if v == n_w:
        t_w.append(k)
    else:
        break

q = set(list(itertools.product(t_h, t_w)))

cnt = 0
ans = n_h + n_w
for h, w in q:
    if [h, w] not in HW:
        break
    cnt += 1
    if cnt == M:
        ans -= 1
        break
else:
    ans -= 1

print(ans)



### FIXED CODE ###

import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()
### BUGGY CODE ###

def digit(N,n):#nは正の整数、N進法での桁数、許容は１０＾１０００
    if n<N:
        return 1
    else:
        return 1+digit(N,n//N)

def Nbasenumber(N,m):#N>1,mは正の整数、N進法表記、出力は数、許容はN＾１０００
    if  m<N:
        return m
    else:
        k=digit(N,m)#digitとの併用を忘れないこと
        i=m//(N**(k-1))
        return i*(10**(k-1))+Nbasenumber(N,m%(N**(k-1)))

def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=[0]
                    else:
                        data.append(0)
                if [j+1,1] in check:
                    if j==0:
                        data=[1]
                    else:
                        data.append(1)

            else:
                if j==0:
                    data=[2]
                else:
                    data.append(2)#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!=2:
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=digitsum(Nbasenumber(2,i))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N=int(input())
shougen=[(0,0) for i in range(0,N)]
for i in range(0,N):
    A=int(input())
    honest=0
    unkind=0
    for j in range(0,A):
        x,y=map(int,input().split())
        if y==0:
            unkind+=2**(x-1)
        else:
            honest+=2**(x-1)
    shougen[i]=(honest,unkind)

ans=0
for i in range(0,2**N):
    honest=i
    unkind=2**N-1-i
    check=True
    test=0
    for j in range(0,N):
        if (i>>j)&1 ==1:
            test+=1
            x,y=shougen[j]
            if (honest-x)^x!=honest or (unkind-y)^y!=unkind:
                check=False
    if check:
        if test>ans:
            ans=test

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

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

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10**18:
            ans = -1
            break

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

n = int(input())
a = []
for i in range(n):
  b = int(input())
  if b in a:
    a.remove(b)
  else:
    a.append(b)
print(len(a))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(input()) for i in range(n)]
b = Counter(a).values()
c = [x for x in b if x % 2 != 0]
print(len(c))
### BUGGY CODE ###

a, b, x = map(int, input().split())
sum = 0
count = 0

while(sum<=b):
    if(a<=sum):
        count += 1
    sum += x
        
print(count)

### FIXED CODE ###

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

print((b//x) -((a-1)//x))
### BUGGY CODE ###

import itertools

n=int(input())
lis=[input().split() for i in range(n)]

res=[]
for i in range(n):
    for j in range(i+1,n):
        dist=(int(lis[i][0])-int(lis[j][0]))**2 + (int(lis[i][1])-int(lis[j][1]))**2
        res.append(dist)
sqrt_res = [i**0.5 for i in res]
ans = 0
perm = list(itertools.permutations(sqrt_res, n-1))
for v in perm:
    ans+=sum(v)
print(ans/len(perm))  

### FIXED CODE ###

n = int(input())
lis = [list(map(int, input().split())) for i in range(n)]

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += ((lis[i][0] - lis[j][0]) ** 2 + (lis[i][1] - lis[j][1]) ** 2) ** 0.5

ans *= 2/n

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

from itertools import accumulate
from sys import stdin, stdout

input = lambda: stdin.readline().rstrip()
write = stdout.write

def main():
    N, M = map(int, input().split())
    A = map(int, input().split())

    snacks = [0] + list(accumulate(A))
    cnt = 0
    for i in range(N + 1):
        for j in range(i + 1, N + 1):
            if not (snacks[j] - snacks[i]) % M:
                cnt += 1
    print(cnt)

main()


### FIXED CODE ###

from collections import defaultdict
from sys import stdin, stdout

input = lambda: stdin.readline().rstrip()
write = stdout.write

def main():
    N, M = map(int, input().split())
    A = tuple(map(int, input().split()))

    sum_ = [0] * (N + 1)
    for i in range(N):
        sum_[i+1] = (sum_[i] + A[i]) % M

    ans = 0
    mod = defaultdict(int)
    for i in range(N + 1):
        ans += mod[sum_[i]]
        mod[sum_[i]] += 1

    print(ans)

main()
### BUGGY CODE ###

N, M = map(int, input().split())
L, R = [], []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l), R.append(r)

ans = 0    
for i in range(N):
    if max(L) <= i+1 <= min(R):
        ans += 1
        
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L, R = [], []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l), R.append(r)

if max(L) <= min(R):
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

# https://kato-robotics.hatenablog.com/entry/2019/07/28/204812

S = input()

MOD = 10 ** 9 + 7

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        for x in range(10):
            for j in range(13):
                dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    else:
        x = int(S[i])
        for j in range(13):
            dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])

### FIXED CODE ###

# https://kato-robotics.hatenablog.com/entry/2019/07/28/204812

S = input()

MOD = 10 ** 9 + 7

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        for x in range(10):
            for j in range(13):
                dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    else:
        x = int(S[i])
        for j in range(13):
            dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])
### BUGGY CODE ###

# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, collections.deque()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)

    # 同じ日にできる仕事が二つ以上あったとして、
    # 第一に報酬が最も高い仕事をその日のシフトに入れる
    # それよりも前の日に空きがあれば残りの仕事を報酬の高い順に入れる
    # 空きがなかった場合、前日以前にやる仕事の中で最も報酬の低いものよりも、残りの仕事のなかで
    # 最も報酬の高いものの方が良ければ、その日の予定をを更新する。

    day_rewards = [0 for _ in range(m+1)] # 期限当日は報酬ゼロとして

    for i in range(m, 0, -1):
        latest = i
        while job_list[i]:
            mi = min(day_rewards[latest:])
            if mi < max(job_list[i]):
                latest = day_rewards.index(mi, latest)
                day_rewards[latest] = max(job_list[i])
                job_list[i].remove(max(job_list[i]))
            else:
                break
                
    print(sum(day_rewards))
    # 間に合うかな?


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
import heapq

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] # 当日は報酬0
    q = []
    for i in range(1, m+1):
        for reward in job_list[i]: # 期限i日前にできる仕事の報酬一覧をheqp queueに入れる
            heapq.heappush(q, -reward) 
            # あとで最大値を取り出すために-1かける(heappop()で取り出せるのは最小値)

        if q: # その日できる仕事が一つでもあれば
            # 報酬の最小値(マイナスなので元々の最大値)を取り出して-1をかけ、scheduleにいれる
            schedule[i] = -heapq.heappop(q) # 戻り値を返すと同時にq自体も変更している
        else: # できる仕事がなければ
            pass  # その日の報酬は0のまま

    print(sum(schedule))


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

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[::-1][0]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
    if(temp - (n-i) > min(ma)):
        break
print(min(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

L,R=map(int,input().split())
#print(L,R)
ans=2019
for i in range(L,R):
	for j in range(i+1,R+1):
		ans=min(ans,(i*j)%2019)
print(ans)


### FIXED CODE ###

L,R=map(int,input().split())
ans=2019
for i in range(L,R):
	for j in range(i+1, R+1):
		if j%2019==0:
			print(0)
			exit()
		ans=min(ans,(i*j)%2019)
print(ans)
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*1000001

for i in New_List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,1000001,i):
      Flag[j] = 0
    if New_List.count(i) > 1:
      res += -1
print(res)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)
### BUGGY CODE ###

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

aa = [0]*(N+1)
for i in range(1, N+1):
    aa[i] = aa[i-1]+A[i-1]

bb = [0]*(M+1)
for i in range(1, M+1):
    bb[i] = bb[i-1]+B[i-1]

ans = 0
for i in range(N+1):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue
    mn = 0
    mx = M
    while True:
        if mn == mx:
            if tmp_K >= bb[mn]:
                ans = max(ans, i+mn)
            break

        mid = (mn+mx//2)
        if bb[mid] <= tmp_K:
            if mn == mid:
                mn = mid+1
            else:
                mn = mid
        else:
            if mx == mid:
                mx = mid-1
            else:
                mx = mid
print(ans)


### FIXED CODE ###

import itertools
import bisect

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

aa = [0] + list(itertools.accumulate(A))
bb = [0] + list(itertools.accumulate(B))

ans = bisect.bisect_left(aa, K)-1
ans = max(ans, bisect.bisect_left(bb, K)-1)

for i in reversed(range(N+1)):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if i + M <= ans:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue

    ans = max(ans, bisect.bisect_left(bb, tmp_K)-1+i)
print(ans)
### BUGGY CODE ###

(n, m) = map(int, input().split())
s = []
s.append([0 for _ in range(m + 2)])
for _ in range(n):
    s.append([0] + [1 for _ in range(m)] + [0])
s.append([0 for _ in range(m + 2)])

sans = [[0 for _ in range(m + 2)] for _ in range(n + 2)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        sans[i][j] = (\
        s[i + 1][j + 1]+ \
        s[i + 1][j]+ \
        s[i + 1][j - 1]+ \
        s[i][j + 1]+ \
        s[i][j] + \
        s[i][j - 1]+ \
        s[i - 1][j + 1]+ \
        s[i - 1][j]+ \
        s[i - 1][j - 1]) % 2

sums = 0
for i in range(len(sans)):
    sums += sum(sans[i])
print(sums)

### FIXED CODE ###

(n, m) = map(int, input().split())
if n == 1:
    if m == 1:
        print(1)
    else:
        print(m - 2)
elif m == 1:
    print(n - 2)
else:
    print((n-2)*(m-2))
### BUGGY CODE ###

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

count_list = [[0,0] for i in range(n*10**9+1)]
s = 0
for i in range(n):
  s += a[i]
  if s > 0:
    count_list[s][0] += 1
  elif s < 0:
    
    count_list[-s][1] += 1
  else:
    count_list[s][0] += 1
count = 0
count += count_list[0][0] * (count_list[0][0] + 1) // 2
for i in range(1, len(count_list)+1):
  count+= count_list[i][0] * count_list[i][1]
print(count)

### FIXED CODE ###

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

count_list = {}
s = 0
for i in range(n):
  s += a[i]
  count_list[s] = count_list.get(s, 0) + 1

count = 0
count += count_list.get(0, 0) * (count_list.get(0, 0)+1)
for i in count_list.keys():
  if i!=0:
    #count+= count_list[i] * count_list.get(-i, 0)
    count += count_list[i] * (count_list[i]-1)
print(count//2)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

    N = int(input())
    G = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        G[x].append(y)
        G[y].append(x)

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #xからの動き方を調べる
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

    N = int(input())
    G = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        G[x].append(y)
        G[y].append(x)

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #xからの動き方を調べる
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

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

import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
 
black+=sum(map(lambda x:x.count('#'),l))
 
dist=[[False]*w for i in range(h)]
done=[[float('inf')]*w for i in range(h)]
 

move=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    dist[y][x]=True
   
    for dx,dy in move:
      mx=x+dx
      my=y+dy

      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or dist[my][mx]==True:
        continue
 
      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
    
      if my==h-1 and mx==w-1:
        return True

  return False
 
if __name__=="__main__":
  if bfs()==1:
    print(h*w-done[h-1][w-1]-black-1)
  else:
    print(-1)


### FIXED CODE ###

import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("#") for j in s)
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or done[my][mx]!=float('inf'):
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()
### BUGGY CODE ###

n = int(input())
nums_list = list(map(int, list(input().split())))  # 各数字はint

sum = 0
for i, numi in enumerate(nums_list):
    for j, numj in enumerate(nums_list):
        if i < j:
            product = numi * numj
            amari = product % (10**9 + 7)
            sum += amari

ans = sum % (10**9 + 7)

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = [0] * (N+1)  # 累積和テーブル B[i] = sum(A[:i])
mod = 10**9 + 7
ans = 0

for i in range(N):
    B[i+1] = B[i] + A[i]  # 累積和

for i in range(N):
    sum = (B[N] - B[i+1]) % mod
    ans += A[i] * sum
    ans %= mod

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

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

s_r = []
s_g = []
s_b = []

for i in range(n):
  if s[i] == "R":
    s_r.append(i)
  elif s[i] == "G":
    s_g.append(i)
  else:
    s_b.append(i)

ans = 0
    
def conditions(a, b):
  if (a+b) % 2 == 0:
    x = (a+b) / 2
    y = 2*b - a
    z = 2*a - b
  else:
    x = -1
    y = 2*b - a
    z = 2*a - b
  return (x, y, z)
  
for item in s_r:
  for item2 in s_g:
    count = 0
    for i in conditions(item, item2):
      if i in s_b:
        count += 1
    ans += len(s_b) - count

print(ans)

### FIXED CODE ###

import collections

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

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for d in range(n):
    j = i + d
    k = j + d
    if k >= n:
      break;
    else:
      a = s[i]
      b = s[j]
      c = s[k]
      if noteq(a, b, c):
        ans -= 1
    
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = list()
sum_a = 0
output = 0
cnt = 0
for i in range(q):
  bc.append(list(map(int,input().split())))
a.sort()
for i in range(q):
  flag = False
  try:
    nn = a.index(bc[i][0])
    for j in range(nn-1, len(a)):
      if a[j] == bc[i][0]:
        a[j] = bc[i][1]
        flag = True
      else:
        if flag == True:
          break
  except ValueError:
    pass
  print(sum(a))
  a.sort()

  
  

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
count = [0]*((10**5)+100)
for i in range(len(A)):
  count[A[i]] += 1
sumA = sum(A)
for q in range(Q):
  count[BC[q][1]] += count[BC[q][0]]
  sumA += (BC[q][1] - BC[q][0])*count[BC[q][0]]
  print(sumA)
  count[BC[q][0]] = 0
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import bisect_left, bisect_right
from collections import defaultdict
INF = float("inf")

# Range Add Query, Range Sum Query
class SegmentTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.data1 = [0] * (2*self.N)
        self.data2 = [0] * (2*self.N)

    # [a, b) に x を加算する
    def add(self, a, b, x, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return
        if a <= l and r <= b:
            self.data1[k] += x
        else:
            self.add(a, b, x, k*2+1, l, (l+r)//2)
            self.add(a, b, x, k*2+2, (l+r)//2, r)
            self.data2[k] = max(self.data1[k*2+1]+self.data2[k*2+1], self.data1[k*2+2]+self.data2[k*2+2])

    # [a, b) の和を計算する
    def sum(self, a, b, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data1[k]+self.data2[k]
        vl = self.sum(a, b, k*2+1, l, (l+r)//2)
        vr = self.sum(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr) + self.data1[k]

N = int(input())
S = list(input())
Q = int(input())
Seg = [SegmentTree(N) for i in range(26)]
for i in range(N):
    Seg[ord(S[i])-97].add(i, i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    if q == '1':
        i = int(x)-1
        Seg[ord(S[i])-97].add(i, i+1, -1)
        S[i] = y
        Seg[ord(y)-97].add(i, i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += Seg[i].sum(l-1, r) > 0
        print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
INF = float("inf")

# Binary Indexed Tree
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N = int(input())
S = list(input())
Q = int(input())
bit = [BIT(N+1) for i in range(26)]
for i in range(N):
    bit[ord(S[i])-97].add(i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    q = int(q)
    if q == 1:
        i = int(x)-1
        bit[ord(S[i])-97].add(i+1, -1)
        S[i] = y
        bit[ord(y)-97].add(i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += (bit[i].sum(r)-bit[i].sum(l-1))> 0
        print(ans)