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

N=int(input())
dict = {}

for i in range(N):
  s=input()
  if s in dict:
    dict[s]=dict[s]+1
  else:
    dict[s]=1
    
keys = [k for k, v in dict.items() if v == max(dict.values())]
res = sorted(keys)
for word in res:
  print(word)

### FIXED CODE ###

N=int(input())
dict = {}
 
for i in range(N):
  s=input()
  if s in dict:
    dict[s]=dict[s]+1
  else:
    dict[s]=1

dict_maxval=max(dict.values())
    
res = [k for k, v in dict.items() if v == dict_maxval]
res.sort()
for word in res:
  print(word)
### BUGGY CODE ###

L, R = map(int, input().split())

D = R - L
Ans = {2018}
J_Set = {2018}


for i in range(min(D, 2019)):
    A = L+i
    for j in range(D-i):
        B = (L+i+j+1)%2019
        Ans.add((A*B)%2019)
        if j > 2019:
            break

print(min(Ans))

### FIXED CODE ###

L, R = map(int, input().split())

D = R - L
Ans = {2018}
J_Set = {2018}


for i in range(min(D, 2019)):
    A = L+i
    for j in range(D-i):
        B = L+i+j+1
        Ans.add((A*B)%2019)
        if j > 2019:
            break

print(min(Ans))
### BUGGY CODE ###

n, w = map(int, input().split())

ws, vs = zip(*[map(int, input().split()) for _ in range(n)])

dp = [0] * (w + 1)

for i in range(n):
  for j in reversed(range(w + 1)):
    if j + ws[i] <= w:
      dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i])
      
print(dp[w])

### FIXED CODE ###

n, w = map(int, input().split())

ws = [0] * n
vs = [0] * n

for i in range(n):
  a, b = map(int, input().split())
  ws[i] = a
  vs[i] = b
  
dp = [0] * (w + 1)

for i in range(n):
  for j in range(w, -1, -1):
    if j + ws[i] <= w:
      dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i])
      
print(dp[w])
### BUGGY CODE ###

from itertools import accumulate
from bisect import bisect_right

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


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(2 * N + 2)  # N+1番目が真ん中
target = (N * (N + 1) // 2 + 1) // 2

# にぶたん
l, r = -1, 10 ** 9 + 1

while r - l > 1:
    X = (r + l) // 2
    Binary = [0] + [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    temp = sorted(Binary)
    order = [bisect_right(temp, b) for b in Binary]
    inversion = 0

    for x in order:
        inversion += BIT.sum(x)
        BIT.add(x, 1)

    if inversion >= target:
        l = X
    else:
        r = X

print(r)

### FIXED CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
A_sorted = sorted(A)


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(2 * N + 1)  # N+1番目が真ん中
target = (N * (N+1)) // 4

# にぶたん
l, r = -1, 10**9+1
if N == 1:
    print(A[0])
    exit()
while r - l > 1:
    X = (r + l) // 2
    Binary = [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    inversion = 0

    for j in range(N):
        inversion += BIT.sum(Binary[j] + N + 1) + (Binary[j] >= 0)
        BIT.add(Binary[j] + N + 1, 1)

    #print(X, inversion, Binary)
    if inversion >= target:
        l = X
    else:
        r = X

#print(X, inversion)
print(r)
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=list(range(n+1))
for f in range(k):
    a1=[0 for s in a1]
    for x in range(n):
        y=x-a[x]
        if y<0:
            y=0
        a1[y]=a1[y]+1    
        z=x+a[x]
        if z>n-1:
            z=n-1
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

def main(N,A):
    B=[0]
    count = 0
    for i in range(N):
        T = A[i] + B[i]
        #print(B)
        if T in B:

            #print('count:',count)
            count += B.count(T)


    # B = [A[i] +B[i] for i in range(N)]
    #
    # count = [ count + 1 for m in range(len(B)) if B[i] - B[i-m] == 0]

        # for m in range(len(B)):
        #     if T - B[m] == 0:
        #         # print(i, m)
        #         # print(B[i],B[i-m])
        #         # print(T)
        #         # print("kore",B[i],B[i-m])
        #         count += 1
        B.append(T)


    #print(count)
    #print(B)
    return print(count)

if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))

    main(N,A)

### FIXED CODE ###

import collections

def main(N,A):
    B=[0]
    count = 0
    for i in range(N):
        T = A[i] + B[i]

        B.append(T)
    c = collections.Counter(B)

    for i in range(len(c)):
        k, v = c.popitem()
        for z in range(v):
            count += z

    return print(count)

if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))

    main(N,A)
### BUGGY CODE ###

x = int(input())
ans = 0
for a in range((x//100)+1):
  for b in range((x//101)+1):
    for c in range((x//102)+1):
      for d in range((x//103)+1):
        for e in range((x//104)+1):
          for f in range((x//105)+1):           
            if (100*a) + (101*b) + (102*c) + (103*d) + (104*e) + (105*f)== x:
              ans += 1
if ans == 0:
  print(0)
else:
  print(1)



### FIXED CODE ###

x = int(input())
ans = 0
flag = False
for a in range((x//100)+1):
  for b in range((x//101)+1):
    for c in range((x//102)+1):
      for d in range((x//103)+1):
        for e in range((x//104)+1):
          for f in range((x//105)+1):           
            if (100*a) + (101*b) + (102*c) + (103*d) + (104*e) + (105*f)== x:
              ans += 1
              flag = True
              break
          if flag:
            break
        if flag:
          break
      if flag:
        break
    if flag:
      break
  if flag:
    break
  
if ans == 0:
  print(0)
else:
  print(1)
### BUGGY CODE ###

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

M = 0
for x in range(n+1):
    M = max(int(a*x/b)-(a*int(x/b)), M)

print(M)

### FIXED CODE ###

import math

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

M = 0
t = min(b-1, n)
M = math.floor(a*t/b) - a*math.floor(t/b)

print(M)
### BUGGY CODE ###

from collections import deque

N = int(input())
slime = list(map(int, input().split()))
cumSlime = [0] * (N + 1)
for i in range(1, N + 1):
    cumSlime[i] = cumSlime[i - 1] + slime[i - 1]

def calc(qLeft, qRight):
    st = deque([(False, qLeft, qRight)])
    memo = dict()

    while st:
        canCalc, left, right = st.pop()

        if left + 1 == right:
            memo[(left, right)] = slime[left]
            continue

        if (left, right) in memo:
            continue

        if canCalc:
            ret = float('inf')
            for mid in range(left + 1, right):
                ret = min(ret, memo[(left, mid)] + memo[(mid, right)])
            ret += cumSlime[right] - cumSlime[left]
            memo[(left, right)] = ret
        else:
            st.append((True, left, right))
            for mid in range(left + 1, right):
                if not (left, mid) in memo:
                    st.append((False, left, mid))
                if not (mid, right) in memo:
                    st.append((False, mid, right))

    return memo[(qLeft, qRight)]

ans = calc(0, N) - sum(slime)
print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(input().split(), np.int64)

Acum = np.zeros((N, N + 1), dtype=np.int64)
for i in range(N):
    Acum[i, i + 1:] = A[i:].cumsum()

dp = np.zeros((N, N + 1), dtype=np.int64)

for length in range(2, N + 1):
    for left in range(N - length + 1):
        right = left + length
        dp[left, right] = (dp[left, left + 1: right] + dp[left + 1: right, right]).min() + Acum[left, right]

print(dp[0, N])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def generate_intervals(n):
    a = 1
    while a == 1 or a <= n // 2:
        yield a
        a = 3 * a + 1


class Sort(object):

    def __init__(self, array, num):
        self.a = array
        self.n = num
        self.cnt = 0
        self.gs = list(reversed(list(generate_intervals(self.n))))
        self.m = len(self.gs)

    def insertionsort(self, g):
        for i in range(g, self.n):
            v = self.a[i]
            j = i - g
            while j >= 0 and self.a[j] > v:
                self.a[j + g] = self.a[j]
                j = j - g
                self.cnt += 1
            self.a[j + g] = v

    def shellsort(self):
        for i in range(0, self.m):
            self.insertionsort(self.gs[i])


def main():
    n = int(input())
    a = [int(input()) for i in range(n)]
    s = Sort(a, n)
    s.shellsort()
    print(s.m)
    print(" ".join(map(str, s.gs)))
    print(s.cnt)
    for i in range(n):
        print(s.a[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def construct_gs(n):
    gs = []
    g = 1
    while g <= n:
        gs.append(g)
        g = 3 * g + 1
    return gs[::-1]


def shell_sort(xs, n):
    global cnt
    cnt = 0
    gs = construct_gs(n)
    m = len(gs)
    def insertion_sort(g):
        global cnt
        for i in range(g, n):
            v = xs[i]
            j = i - g
            while j >= 0 and xs[j] > v:
                xs[j + g] = xs[j]
                j = j - g
                cnt += 1
            xs[j + g] = v
    for g in gs:
        insertion_sort(g)
    return m, gs, cnt, xs


def main():
    n = int(input())
    xs = [int(input()) for _ in range(n)]
    m, gs, cnt, xs = shell_sort(xs, n)
    print(m)
    print(" ".join(map(str, gs)))
    print(cnt)
    for x in xs:
        print(x)


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

n=int(input())
a=[int(input()) for _ in range(n)]
cnt=0
ans=0
used=[False]*n
while cnt<n:
    ans+=1
    mx = -1
    for i in range(n):
        if used[i]:continue
        if a[i]>mx:
            used[i]=True
            mx=a[i]
            cnt+=1
print(ans)

### FIXED CODE ###

import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(input())
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print(mi+1)

n = int(input())
inf=10**10
f(n)
### BUGGY CODE ###

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

# １からNまでの値をもつサイコロを振ったときの期待値
def ex(x:int):
    return (x*(x+1)/2)/x

kitaichi = []
kitaichi_goukei = []
for i in range(len(p)):
    kitaichi.append(ex(p[i]))
    if i+1 >= k:
        kitaichi_goukei.append(sum(kitaichi[i+1-k:i+1]))
print (max(kitaichi_goukei))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ex = [1/2*(i+1) for i in p]
total = [0]

for i in range(N):
    total.append (total[i] + ex[i])

ans = 0
for i in range(N+1-K):
    tmp = total[i+K] - total[i]
    if ans < tmp:
        ans = tmp

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

from collections import deque

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

def bfs(maze,visited,gx,gy):
    stack = deque([[0,0]])
    if maze[0][0] == '#':
        visited[0][0] = 1 
    else:
        visited[0][0] = 0 
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[0,1]):
            new_y,new_x = y+j,x+k
            if  new_x >= gx or  new_y >= gy:
                continue
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.':
                visited[new_y][new_x] = min(count+1,visited[new_y][new_x])
                stack.appendleft([new_y, new_x])
            else:
                visited[new_y][new_x] = min(count,visited[new_y][new_x])
                stack.appendleft([new_y, new_x])
    return visited[gy-1][gx-1]

inf = float('inf')
visited = [[inf]*W for _ in range(H)]
print(bfs(maze,visited,W,H))


### FIXED CODE ###

from collections import deque

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

def bfs(maze,visited,gx,gy):
    stack = deque([[0,0]])
    if maze[0][0] == '#':
        visited[0][0] = 1 
    else:
        visited[0][0] = 0 
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[0,1]):
            new_y,new_x = y+j,x+k
            if  new_x >= gx or  new_y >= gy:
                continue
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.' and visited[new_y][new_x] > count+1:
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.' and visited[new_y][new_x] <= count+1:
                continue
            elif visited[new_y][new_x] > count:
                visited[new_y][new_x] = count
                stack.appendleft([new_y, new_x])
    return visited[gy-1][gx-1]

inf = float('inf')
visited = [[inf]*W for _ in range(H)]
print(bfs(maze,visited,W,H))
### BUGGY CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

def lcm(a, b):
    return a*b//gcd(a,b)

g = 1
for a in A:
    if lcm(g, a) == g * a:
        g *= a
    else:
        if reduce(gcd, A) == 1:
            print("setwise coprime")
        else:
            print('not coprime')
        break
else:
    print('pairwise coprime')
    exit()

### FIXED CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

lines = sys.stdin.readlines()
edges = list(map(lambda s:list(map(int, s.split(" "))), lines[:n-1]))
queries = list(map(lambda s:list(map(int, s.split(" "))), lines[n-1:]))

scores = [0] * (n+1)

for q in queries:
    scores[q[0]] += q[1]

queue = deque()
mark = [False] * (n+1)
mark[1] = True

for e in edges:
    queue.append(e)

while queue:
    e = queue.popleft()
    
    a = e[0]
    b = e[1]
    if mark[a]:
        scores[b] += scores[a]
        mark[b] = True
    elif mark[b]:
        scores[a] += scores[b]
        mark[a] = True
    else:
        queue.append(e)
        print()

print(" ".join(map(str,scores[1:])))


### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

lines = sys.stdin.readlines()
edges = list(map(lambda s:list(map(int, s.split(" "))), lines[:n-1]))
queries = list(map(lambda s:list(map(int, s.split(" "))), lines[n-1:]))

scores = [0] * (n+1)

for q in queries:
    scores[q[0]] += q[1]

queue = deque()
mark = [False] * (n+1)
mark[1] = True


childrens = [ [] for _ in range(n+1) ]
for e in edges:
    a = e[0]
    b = e[1]
    childrens[a].append(b)
    childrens[b].append(a)


queue.append(1)

while queue:
    a = queue.popleft()
    children = childrens[a]
    for b in children:
        if not mark[b]:
            scores[b] += scores[a]
            mark[b] = True
            queue.append(b)

print(" ".join(map(str,scores[1:])))
### BUGGY CODE ###

N, K = map(int,input().split())
cost= input().split()
cost = [int(i) for i in cost]
ans_list = [0]*N
ans_list[1] = abs(cost[0] - cost[1])
temp = 10 **10

for i in range(2,N):
    temp = 10**10
    for j in range(1,K+1):
        if i-j >=0:
            compare = ans_list[i-j] + abs(cost[i-j]-cost[i])
            temp2 = min(compare, temp)
            temp = temp2
    if temp != 10 ** 10:
        ans_list[i] = temp
print(ans_list.pop())


### FIXED CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
result = 0

temp = []

for i in range(1, K+1):
    for j in range(1, K+1):
        temp.append(gcd(i, j))

for k in range(1, K+1):
    for t in temp:
        add = gcd(t, k)
        result += add

print(result)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
result = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            add = gcd(i, j, k)
            result += add

print(result)
### BUGGY CODE ###

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

for i in range(M):
    for j in range(BC[i][0]):
        if A[0] < BC[i][1]:
            A[0] = BC[i][1]
            A = sorted(A)

print(sum(A))

### FIXED CODE ###

import collections

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

c = collections.Counter(A)
values,counts = zip(*c.most_common())
D=[]
for i in range(len(counts)):
    D.append([counts[i],values[i]])
for i in range(M):
    D.append(BC[i])
D=sorted(D,key=lambda x:x[1], reverse=True)

t=0
i=0
ans=0
while t<N:
    if D[i][0]+t<=N:
        ans+=D[i][1]*D[i][0]
        t+=D[i][0]
        i+=1
    else:
        ans+=D[i][1]*(N-t)
        t+=N-t
print(ans)
### BUGGY CODE ###

import sys
import os
from bisect import bisect_left
def index(a, x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return True
    return False

R, G, B, N = map(int,input().split())
listB = [ i for i in range(N//B+1) ]
cnt = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if (N - R*r - G*g)%B == 0 and  index(listB,(N - R*r - G*g)//B):
            cnt += 1
print(cnt)


### FIXED CODE ###

*j, N = map(int,input().split())
j.sort()
a,b,c = j
cnt = 0
for r in range(N//b+1):
    for g in range((N-b*r)//c+1):
        v = b*r+c*g
        if (N-v)%a == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
numbers = []
for _ in range(N):
    A = int(input())
    if A in numbers:
        numbers.remove(A)
    else:
        numbers.append(A)

print(len(numbers))

### FIXED CODE ###

import collections
N = int(input())
A = [] 
for _ in range(N):
    A.append(int(input()))
answer = 0
numbers = collections.Counter(A)

for i in numbers.values():
    answer += i % 2

print(answer)
### BUGGY CODE ###

import math
N = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
st_n = a[0]
st_r = a[1]
m = math.factorial(st_r)*math.factorial(st_n-st_r)
for r in range(1,N):
    cn = math.factorial(a[r])*math.factorial(st_n-a[r])
    if cn < m:
        st_r = a[r]
        m = cn
print(st_n,st_r)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
st_n = a[0]
st_r = a[1]
m = st_r*(st_n-st_r)
for r in range(2,N):
    cn = a[r]*(st_n-a[r])
    if m < cn:
        st_r = a[r]
        m = cn
print(st_n,st_r)
### BUGGY CODE ###

N = int(input())
S = list(input().strip())
Qcnt = int(input())

cidx = {}
for i in range(ord("a"), ord("z")+1):
    cidx[chr(i)] = set([])

import bisect

for idx, s in enumerate(S):
    cidx[s].add(idx)

for _ in range(Qcnt):
    Q = list(input().strip().split(" "))
    if Q[0] == "1":
        q_idx = int(Q[1]) - 1
        prev_c = S[q_idx]
        S[q_idx] = Q[2]
        cidx[prev_c].remove(q_idx)
        cidx[Q[2]].add(q_idx)
    else:
        l = int(Q[1])
        r = int(Q[2])
        l -= 1
        cnt = 0
        for alpha in range(ord("a"), ord("z")+1):
            tmp = sorted(list(cidx[chr(alpha)]))
            lid = bisect.bisect_left(tmp, l)
            rid = bisect.bisect_left(tmp, r)
            if lid < rid:
                cnt += 1
        print(cnt)

### FIXED CODE ###

class SegTree:
    def __init__(self, N, S):
        self.N = 2 ** ((N-1).bit_length())
        self.tree = [0 for i in range(self.N * 2 - 1)]
        for i in range(len(S)):
            self.tree[self.N - 1 + i] = 1 << (ord(S[i]) - ord("a"))

        for i in range(self.N - 2, -1, -1):
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

    def update(self, index, char):
        i = self.N - 1 + index
        # アルファベットがある = bitが立っている
        self.tree[i] = 1 << (ord(char) - ord("a"))
        while i > 0:
            i = (i-1) // 2
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

    def get(self, a, b):
        return self.query(a, b, 0, 0, self.N)

    # k : ノードの番号
    # l : ノードkの受け持つ区間
    # r : ノードkの受け持つ区間
    def query(self, a, b, k, l, r):
        if r <= a or b <= l: # 区間外
            return 0
        elif a <= l and r <= b: # 受け持ち区間は完全に含まれている
            return self.tree[k]
        else: # 一部含まれてる
            left = self.query(a, b, 2 * k + 1, l, (l+r)//2)
            right = self.query(a, b, 2 * k + 2, (l+r)//2, r)
            return left | right

def solve():
    N = int(input())
    S = list(input().strip())
    tree = SegTree(N, S)

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == "1":
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        else:
            l_q = int(in_1)
            r_q = int(in_2)
            print(bin(tree.get(l_q-1, r_q)).count("1"))

solve()