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

def int_cards(cards, operations):
    cards = sorted(cards)
    operations.sort(reverse=True)
    changed = False
    for i in range(len(operations)):
        if changed:
            cards = sorted(cards)
            changed = False
        for j in range(operations[i][1]):
            if cards[j] < operations[i][0]:
                cards[j] = operations[i][0]
                changed = True
            else:
                break
            
    print(sum(cards))
    
N, M = map(int, input().split())
A = list(map(int,input().split()))
operations = []
for i in range(M):
    B, C = map(int, input().split())
    operations.append([C, B])
    
int_cards(A, operations)

### FIXED CODE ###

import collections

def int_cards(N, cards, operations):
    col_cards = collections.deque(sorted(cards), N)
    operations.sort(reverse=True)
    for c, b in operations:
        for _ in range(b):
            if col_cards[0] >= c:
                break
            col_cards.popleft()
            col_cards.append(c)
            
    print(sum(col_cards))
    
N, M = map(int, input().split())
A = list(map(int,input().split()))
operations = []
for i in range(M):
    B, C = map(int, input().split())
    operations.append([C, B])
    
int_cards(N, A, operations)
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(N):
    p = p*(i+1)
print(p%(10**9+7))

### FIXED CODE ###

N = int(input())
p = 1
for i in range(N):
    p = (p*(i+1))%(10**9+7)
print(p)
### BUGGY CODE ###

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

K, S = map(int, input().split())

r = 0
for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                r += 1

print(r)


### FIXED CODE ###

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

K, S = map(int, input().split())

r = 0
for i in range(K + 1):
    for j in range(K + 1):
        k = S - i - j
        if k >= 0 and k <= K:
            r += 1

print(r)
### BUGGY CODE ###

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

hs = [0] * H
ws = [0] * W
s = list()
for i in range(M):
  h,w = map(int, input().split())
  hs[h-1] += 1
  ws[w-1] += 1
  s.append([h-1,w-1])
  
mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])
  
i_s = list()
j_s = list()
for i in range(H):
  if mh == hs[i]:
    i_s.append(i)
for j in range(W):
  if mw == ws[j]:
    j_s.append(j)

ans = mh + mw
for i in i_s:
  for j in j_s:
    if [i,j] in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
hs = [0] * H
ws = [0] * W
s = set()

for i in range(M):
  r,c = map(int,input().split())
  r -= 1
  c -= 1
  hs[r] += 1
  ws[c] += 1
  s.add((r,c))
mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])

i_s = list()
j_s = list()
for i in range(H):
  if mh == hs[i]:
    i_s.append(i)
for j in range(W):
  if mw == ws[j]:
    j_s.append(j)
ans = mh + mw
for i in i_s:
  for j in j_s:
    if (i,j) in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
tree=[[]for i in range(N)]
bridge=[]
for i in range(M):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)
    bridge.append((A,B))
ans=[]
All=N*(N-1)//2
for a,b in bridge:
    ischecked=[0]*N
    tree[a-1].pop(0)
    tree[b-1].pop(0)
    x=0
    for i in range(N):
        if ischecked[i]==1:
            continue
        count=0
        q=[i]
        while q:
            now=q.pop()
            if ischecked[now]==1:
                continue
            ischecked[now]=1
            q.extend(tree[now])
            count+=1
        x+=count*(count-1)//2
    ans.append(All-x)
for i in ans:
    print(i)

### FIXED CODE ###

N,M=map(int,input().split())
bridge=[]
size=[1]*(N+1)
tree=list(range(N+1))
def find(a):
    x=tree[a]
    if a==x:
        return a
    y=find(x)
    tree[a]=y
    return y
for i in range(M):
    A,B=map(int,input().split())
    bridge.append((A,B))
Ans=N*(N-1)//2
ans=[]
for a,b in bridge[::-1]:
    aroot=find(a)
    broot=find(b)
    if aroot==broot:
        ans.append(Ans)
        continue
    ans.append(Ans)
    sa=size[aroot]
    sb=size[broot]
    Ans-=sa*sb
    if sa>sb:
        tree[broot]=aroot
        size[aroot]+=sb
    else:
        tree[aroot]=broot
        size[broot]+=sa
for i in ans[::-1]:
    print(i)
### BUGGY CODE ###

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

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

class Group:
    id = 0
    def __init__(self):
        self.id = Group.id
        Group.id += 1
        self.count = 1
        self.root = None

    def top(self):
        w = self
        while not w.root is None:
            w = w.root
        return w

    def addMember(self):
        self.count += 1

    def union(self, g):
        self.top().count += g.top().count
        g.top().root = self.top()

    def __repr__(self):
        w = self.top()
        return str(("Gropup", w.id, w.count))

pt = []
G = [Group() for x in range(N+1)]
idx = 0
cnt = 0
while len(B):
    x, y = B.pop()
    wx = G[x].top()
    wy = G[y].top()
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx.count * wy.count)
        wx.union(wy)

    #print(G)

cnt = 0
while len(pt):
    cnt += pt.pop()
    print(cnt)


### FIXED CODE ###

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

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)
### BUGGY CODE ###

n = int(input())

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

sorted_a = sorted(a)

aa = []
for i in range(n):
    sorted_a.pop(-1)
    sorted_a.pop(0)
    aa.append(sorted_a.pop(-1))

print(sum(aa))

### FIXED CODE ###

import sys 
n = int(input())

a = list(map(int, sys.stdin.readline().split()))

sorted_a = sorted(a)
reversed_a = sorted(a, reverse=True)

aa = []
for i in range(n):
    sorted_a.pop(-1)
    reversed_a.pop(-1)
    aa.append(sorted_a.pop(-1))

print(sum(aa))
### BUGGY CODE ###

# a,b,q=map(int,input().split())
# s=[]
# t=[]
# x=[]
# for i in range(a):
#     s.append(int(input()))
# for i in range(b):
#     t.append(int(input()))
# for i in range(q):
#     x.append(int(input()))

# tmp_s=10000000001
# arg_s=0
# tmp_t=10000000001
# arg_t=0
# lis_s=[]
# lis_t=[]
# lis_tmp_s_0=[]
# lis_tmp_s_1=[]
# lis_tmp_t_0=[]
# lis_tmp_t_1=[]
# for i in range(q):
#     min_1=10000000001
#     min_2=10000000001
#     for j in range(a):
#         lis_s.append(abs(x[i]-s[j]))
#     aa=lis_s.index(min(lis_s))
#     lis_s.pop(lis_s.index(min(lis_s)))
#     ii=lis_s.index(min(lis_s))
#     for k in range(b):
#         lis_tmp_s_0.append(abs(s[aa]-t[k]))
#     lis_tmp_s_0.sort()
#     for k in range(b):
#         lis_tmp_s_1.append(abs(lis_s[ii]-t[k]))
#     min_1=min(lis_s[0]+lis_tmp_s_0[0],lis_s[1]+lis_tmp_s_1[0])

#     for j in range(b):
#         lis_t.append(abs(x[i]-t[j]))
#     lis_t.sort()
#     aa=lis_t.index(min(lis_t))
#     lis_t.pop(lis_t.index(min(lis_t)))
#     ii=lis_t.index(min(lis_t))
#     for k in range(a):
#         lis_tmp_t_0.append(abs(lis_t[aa]-s[k]))
#     lis_tmp_t_0.sort()
#     for k in range(a):
#         lis_tmp_t_1.append(abs(lis_t[ii]-s[k]))
#     min_2=min(lis_t[0]+lis_tmp_t_0[0],lis_t[1]+lis_tmp_t_1[0])
#     print(min(min_1,min_2))

import bisect
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
s.sort()
t.sort()
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect.bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[bisect.bisect_left(t,s[tmp_s_1])-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[bisect.bisect_left(t,s[tmp_s_1])]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[bisect.bisect_left(t,s[tmp_s_2])-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[bisect.bisect_left(t,s[tmp_s_2])]))
    tmp_t_1=bisect.bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[bisect.bisect_left(s,t[tmp_t_1])-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[bisect.bisect_left(s,t[tmp_t_1])]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[bisect.bisect_left(s,t[tmp_t_2])-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[bisect.bisect_left(s,t[tmp_t_2])]))
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-10**12)
t.append(-10**12)
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(10**12)
t.append(10**12)
for i in range(q):
    x=int(input())
    tmp_s=bisect_left(s,x)-1
    tmp_s_1=s[tmp_s]
    tmp_s_2=s[tmp_s+1]
    tmp_t=bisect_left(t,x)-1
    tmp_t_1=t[tmp_t]
    tmp_t_2=t[tmp_t+1]
    print(min(abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_1),
    abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_2),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_1),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_2),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_1),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_2),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_1),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_2)))
### BUGGY CODE ###

X,Y,A,B,C=map(int, input().split())
AA=list(map(int, input().split()))
BB=list(map(int, input().split()))
CC=list(map(int, input().split()))
AA=sorted(AA,reverse=True)
BB=sorted(BB,reverse=True)
CC=sorted(CC,reverse=True)
AAA=AA[0:X]
BBB=BB[0:Y]
for i in CC:
    if i>min(AAA)or i>min(BBB):
        if min(AAA)>min(BBB):
            BBB[-1]=i
            BBB=sorted(BBB,reverse=True)
        else:
            AAA[-1]=i
            AAA=sorted(AAA,reverse=True)
    else:
        break
print(sum(AAA)+sum(BBB))

### FIXED CODE ###

X,Y,A,B,C=map(int, input().split())
AA=list(map(int, input().split()))
BB=list(map(int, input().split()))
CC=list(map(int, input().split()))
AA=sorted(AA,reverse=True)
BB=sorted(BB,reverse=True)
CC=sorted(CC,reverse=True)
XX=sorted(AA[0:X]+BB[0:Y]+CC,reverse=True)
XX=XX[0:X+Y]
print(sum(XX))
### BUGGY CODE ###

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

pro = 1

for i in a:
    pro = pro * i

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

### FIXED CODE ###

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

pro = 1

if 0 in a:
    pro = 0
else:
    for i in a:
        if pro > 10 ** 18:
            pro = -1
            break
        else:
            pro = pro * i

if pro > 10 ** 18:
    print(-1)
else:
    print(pro)
### BUGGY CODE ###

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[input() for i in range(n)]
    maxInt=-100000
    for i in range(n-k):
        maxInt=max(maxInt,sum(L[i:i+k]))
    print maxInt

### FIXED CODE ###

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[input() for i in range(n)]
    maxInt=-10000000
    temp=sum(L[:k])
    for i in range(k,n):
        maxInt=max(maxInt,temp)
        temp=temp+L[i]-L[i-k]
    print maxInt
### BUGGY CODE ###

import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    #print(a,A[a-1],idx,B[idx].sum())
    B[a-1] = (A[a-1] - B[idx].sum())
B=B.astype('int') % 2
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    for i in range(1,N+1):
        j = math.ceil(i**0.5)
        ans = 0
        for x in range(1,j+1):
            for y in range(1,j+1):
                A=x**2+y**2+x*y
                B=x+y
                D = B**2-4*(A-i)
                if D < 0: continue

                d = D**0.5
                if d.is_integer():
                    for z in [(-B+d)/2,(-B-d)/2]:
                        # print(i,d,z)
                        if z.is_integer() and 1<=z:
                            ans += 1
                
        
        print(ans)
                


if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    j = math.ceil((N+1)**0.5)

    ans = [0] * (N+1)
    for x in range(1,j+1):
        for y in range(1,j+1):
            for z in range(1,j+1):
                n = x**2+y**2+z**2+x*y+y*z+z*x
                if 1<=n<=N:
                    ans[n] += 1
            
        
    print(*ans[1:],sep="\n")

                


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

import itertools

N = input()
l = ['3', '5', '7']
d = len(N)
N = int(N)

if N - 357 < 0:
    print(0)
    exit()

#d-1桁以下の753数
aa = 0
for i in range(3, d):
    aa += 3 ** i - 3 * (2 ** i - 2) - 3

#N以下のd桁の753数
a = [i for i in itertools.combinations_with_replacement(l, d)]
b = [i for i in a if len(set(i)) == 3]
c = []
count = 0
for k in b:
    temp = [i for i in itertools.permutations(k)]
    temp = list(set(temp))
    for j in temp:
        if int(''.join(j)) <= N:
            count += 1

print(aa + count)

### FIXED CODE ###

N = input()
l = ['3', '5', '7']
L = ['3', '5', '7']
temp = []
d = len(N)
N = int(N)


if N - 357 < 0:
    print(0)
    exit()

#d-1桁以下の753数
a = 0
for i in range(3, d):
    a += 3 ** i - 3 * (2 ** i - 2) - 3

#d桁の753数
for k in range(d - 1):
    for i in L:
        for j in l:
            temp.append(i + j)
    L.clear()
    L.extend(temp)
    temp.clear()
L = [i for i in L if '3' in i and '5' in i and '7' in i]

count = 0
for i in L:
    if int(i) <= N:
        count += 1
print(a + count)
### BUGGY CODE ###

a, b, k = map(int, input().split())
print(*[i for i in range(a, b+1) if i < a+k or i > b-k], sep="\n")

### FIXED CODE ###

a, b, k = map(int, input().split())
print(*[i for i in range(a, b+1) if i < a+k or i > b-k], sep="\n")
### BUGGY CODE ###

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

for i in range(len(x)):
    b=list()
    for j in range(len(x)):
        if j!=i:b.append(x[j])
    b.sort()
    print(b[int(n/2)-1])



### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
 
xs = list(sorted(x))
b1 = xs[n//2-1]
b2 = xs[n//2]
for xi in x:
    if xi<=b1:print(b2)
    else:print(b1)
### BUGGY CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if sum([r*i,j*g,abs(b*k)]) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] = H[i]%M
SumH = [0]
for i in range(N):
    SumH.append((SumH[i]+H[i])%M)
Ctr = []
Ans = []
for i in range(N+1):
    if SumH[i] not in Ctr:
        Ctr.append(SumH[i])
        Ans.append(int((SumH.count(SumH[i]))*(SumH.count(SumH[i])-1)/2))
print(sum(Ans))

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]

N,M = inpl()
H = {0: 1}
k = 0
ans = 0
for i in inpl():
    k += i
    t = k % M
    if t not in H:
        H[t] = 0
    H[t] += 1
    
for i in H.values():
   ans += i * (i - 1) // 2

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

N = int(input())
arr = list(map(int, input().split()))
i_arr =[]
j_arr =[]

for i in range(N):
    i_arr.append(i+arr[i])
    j_arr.append(-1*arr[i]+i)

ans = 0
for i in range(N):
    for j in range(i,N):
        if i_arr[i] == j_arr[j]:
            ans += 1

print(ans)


### FIXED CODE ###

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

dic = {}
j_arr =[]

ans = 0
for i in range(N):
    if i+arr[i] not in dic:
        dic[i+arr[i]] = 0
    dic[i+arr[i]] += 1
    j_arr.append(-1*arr[i]+i)
    if -1*arr[i]+i in dic:
        ans += dic[-1*arr[i]+i]

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

N=int(input())
l=[]
val=[]
for i in range(N):
  s=list(str(input()))
  s.sort()
  if s not in l:
    l.append(s)
    val.append(1)
  else:
    num=l.index(s)
    val[num]+=1
ans=0
for i in range(len(val)):
  ans+=val[i]*(val[i]-1)//2
print(ans)

### FIXED CODE ###

N=int(input())
l=[]
d={}
ans=0
for i in range(N):
  s=list(str(input()))
  s.sort()
  l.append(s) 
for s in l:
  s=''.join(s)
  if s in d:
    ans+=d[s]
    d[s]+=1
  else:
    d[s]=1
print(ans)
### BUGGY CODE ###

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

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


def checkAllLess(tgt):
    for id in range(tgt):
        # print("id=" + str(id) + ", pn[]=" + str(pn[id]) + ", tgt=" + str(tgt))
        if(pn[id] < pn[tgt]):
            # print('False')
            return False
    # print('True')
    return True


cnt = 0
for i in range(n):
    if (checkAllLess(i)):
        cnt += 1
    # print(str(i) + ":" + str(cnt))

print(cnt)

### FIXED CODE ###

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

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

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

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

import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [''] + list(input())
Q, *query = map(str, read().split())
bit = BIT(N)
for idx, i in enumerate(S[1:], 1):
    bit.update(ord(i) - 97, idx, 1)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        bit.update(ord(c) - 97, b, 1)
        bit.update(ord(S[b]) - 97, b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [i - 97 for i in map(ord, list(input()))]
S = [-1] + S
Q, *query = map(str, read().split())
bit = BIT(N)
for idx, i in enumerate(S[1:], 1):
    bit.update(i, idx, 1)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        c = ord(c) - 97
        if S[b] == c:
            continue
        bit.update(c, b, 1)
        bit.update(S[b], b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))
### BUGGY CODE ###

from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

a = [[False]*(w+2)]
for y in _in[1:]:
    a += [[False] + [x!='#' for x in y.replace('\n','')] + [False]]
a += [[False]*(w+2)]

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

import sys
n = int(input())
a = []
for i in range(n):
    k = [int(x) for x in input().split()]
    j = []
    for i in range(1, len(k)+1):
        j.append(k[-i])
    a.append(j)
ans = 0
while a:
    todaylist = []
    s = 1
    for i in range(n):
        if a[i]:
            p = [min([i+1, a[i][-1]]), max([i+1, a[i][-1]])]
            if p in todaylist:
                a[p[0]-1].pop()
                a[p[1]-1].pop()
                s = 0
            else:
                todaylist.append([min([i+1,a[i][-1]]),max([i+1,a[i][-1]])])
    ans += 1
    if s:
        print(-1)
        sys.exit()
    if not any(a):
        break
print(ans)

### FIXED CODE ###

import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import re

def cal():
    x = input()
    while True:
        pre = len(x)
        x = re.sub('ST', '', x)
        if len(x) == pre:
            break
    print(len(x))

cal()


### FIXED CODE ###

x = input()
ans = []

for i in x:
    if i == 'S':
        ans.append(i)
    else:
        if len(ans) == 0 or ans[-1] == 'T':
            ans.append(i)
        else:
            ans.pop()
print(len(ans))