Harryxun/stf_run huggingface dataset:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

s=input()
x,y=map(int,input().split())
lst=[[],[]]
cnt=0
tmp=0
for i in range(len(s)):
    if s[i]=="F":
        tmp+=1
    else:
        if cnt==0:
            x-=tmp
        else:
            lst[cnt%2].append(tmp)
        tmp=0
        cnt+=1
if tmp!=0:
    lst[cnt%2].append(tmp)
dpx=[[0]*16001 for i in range(len(lst[0])+1)]
dpy=[[0]*16001 for i in range(len(lst[1])+1)]
dpx[0][8000]=1
dpy[0][8000]=1

for i in range(len(lst[0])):
    for j in range(16001):
        if dpx[i][j]!=0:
            dpx[i+1][j+lst[0][i]]+=1
            dpx[i+1][j-lst[0][i]]+=1

for i in range(len(lst[1])):
    for j in range(16001):
        if dpy[i][j]!=0:
            dpy[i+1][j+lst[1][i]]+=1
            dpy[i+1][j-lst[1][i]]+=1

if dpx[len(lst[0])][8000+x]!=0 and dpy[len(lst[0])][8000+y]!=0:
    print("Yes")
else:
    print("No")
# print(x,lst)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

s=input()
x,y=map(int,input().split())
lst=[[],[]]
cnt=0
tmp=0
for i in range(len(s)):
    if s[i]=="F":
        tmp+=1
    else:
        if cnt==0:
            x-=tmp
        else:
            if tmp!=0:
                lst[cnt%2].append(tmp)
        tmp=0
        cnt+=1
if cnt==0:
    x-=tmp
elif tmp!=0:
    lst[cnt%2].append(tmp)

sumx=sum(lst[0])
sumy=sum(lst[1])
# print(x,sumx)
if sumx<x or x<-sumx:
    print("No")
    exit()
if sumy<y or y<-sumy:
    print("No")
    exit()
dpx=[[0]*(sumx*2+1) for i in range(len(lst[0])+1)]
dpy=[[0]*(sumy*2+1) for i in range(len(lst[1])+1)]
dpx[0][sumx]=1
dpy[0][sumy]=1

for i in range(len(lst[0])):
    for j in range(sumx*2+1):
        if dpx[i][j]!=0:
            dpx[i+1][j+lst[0][i]]+=1
            dpx[i+1][j-lst[0][i]]+=1

for i in range(len(lst[1])):
    for j in range(sumy*2+1):
        if dpy[i][j]!=0:
            dpy[i+1][j+lst[1][i]]+=1
            dpy[i+1][j-lst[1][i]]+=1

# print(dpx)
# print(dpy)
if dpx[len(lst[0])][sumx+x]!=0 and dpy[len(lst[1])][sumy+y]!=0:
    print("Yes")
else:
    print("No")
h, w = [int(n) for n in input().split()]
grid = [input() for _ in range(h)]
row_hashs = set()
column_hashs = set()

for i, row in enumerate(grid):
    for j, ch in enumerate(row):
        if ch == '#':
            row_hashs.add(i)
            column_hashs.add(j)

new_grid = []

for i, row in enumerate(grid):
    if i not in row_hashs:
        continue
    new_grid.append([])
    for j, ch in enumerate(row):
        if j not in column_hashs:
            continue
        new_grid[-1].append(ch)
    new_grid[-1] = "".join(new_grid[-1])


print("\n".join(new_grid))
# print(*new_grid, sep="\n")

### FIXED CODE ###

h, w = [int(n) for n in input().split()]
grid = [input() for _ in range(h)]
row_hashs = set()
column_hashs = set()

for i, row in enumerate(grid):
    for j, ch in enumerate(row):
        if ch == '#':
            row_hashs.add(i)
            column_hashs.add(j)

new_grid = []

for i, row in enumerate(grid):
    if i not in row_hashs:
        continue
    new_grid.append([])
    for j, ch in enumerate(row):
        if j not in column_hashs:
            continue
        new_grid[-1].append(ch)
    new_grid[-1] = "".join(new_grid[-1])

print("\n".join(new_grid))
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = min(L//N*i, len(X_S)-1)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = min(L//M*i, len(X_T)-1)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    main()


### FIXED CODE ###

import sys
import fractions
N, M = map(int, input().split())
S = input()
T = input()

g = fractions.gcd(N, M)
L = N * M // g

ss = L // N
ts = L // M
for i in range(N):
  if (i * ss) % ts == 0:
    j = (i * ss) // ts
    if S[i] != T[j]:
      print(-1)
      sys.exit()

for i in range(M):
  if (i * ts) % ss == 0:
    j = (i * ts) // ss
    if T[i] != S[j]:
      print(-1)
      sys.exit()

print(L)
def pair(n,count):
    l=[];su=0
    for i in range(0,len(n),2):
        sub=list()
        sub.append(n[i:i+2])
        su=su+sub[0][0]
        l.append(sub)
    return(su)
        

        
ip1=int(input())
ip2=[]
for i in range(ip1*2):
    ip2.append(int(input()))
ip2.sort()
print(pair(ip2,ip1))

### FIXED CODE ###

def pair(n,count):
    l=[];su=0
    for i in range(0,len(n),2):
        sub=list()
        sub.append(n[i:i+2])
        su=su+sub[0][0]
        l.append(sub)
    return(su)
        
def ip11(): return int(input())
def ip22(): return [int(_) for _ in input().split()]
        

def main():
    ip1=ip11()
    ip2=ip22()
    ip2.sort()
    print(pair(ip2,ip1))
    return
if __name__ == '__main__':
    main()
import math , sys

N  = int( input() )

A = list(map(int, input().split() ) )
M = max( [ i + A[i] for i in range(N) ])
B = [0] * (M + 2)
ans = 0
for i in range(N):
    if i - A[i] >=0:
        ans += B[i - A[i]]
    B[i + A[i]]+=1
print(ans)

### FIXED CODE ###

import math , sys

N  = int( input() )

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

def Prime(x):
    ub=int(math.sqrt(x))+2
    if x==2 or x==3 or x==5 or x==7:
        return True
    for i in range(2,ub):
        if x%i==0:
            return False
    return True

y = N
while not Prime(y):
    y+=1

def h1(x):
    return x % y
def h2(x):
    return 1+ x%(y-1)
def h(x,i):
    return (h1(x) + i*h2(x)) % y

def insert(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0]== -1:
            T[j][0]=x
            T[j][1]=1
            return j
        elif x ==T[j][0]:
            T[j][1]+=1
            return j
        else:
            i+=1

def search(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0] == x:
            return T[j][1]
        elif T[j][0] == -1:
            return -1
        else:
            i+=1

T = [[-1,0] for _ in range(y)]
for i in range(N):
    insert(T , i + A[i])
ans =0
        
for j in range(N):
    if j - A[j]>=0:
        s = search(T, j - A[j])
        if s >=0:
            ans+=s
print(ans)
import numpy as np
N, M=list(map(int(input().split()))
AC=[0]*(a+1)
WA=[0]*(a+1)
ac=0
wa=0
t=0
for i in range(M):
    x,y=map(str(input().split())
    if y=="WA":
        WA[int(x)]+=1   
    elif x=="AC" and AC[int(x)]==0:
        wa+=WA[int(x)]
        ac+=1     
        AC[int(x)]=1
print(ac, wa)             

### FIXED CODE ###

a,b = map(int,input().split())
AC = [0]*(a+1)
WA = [0]*(a+1)
ac = 0
wa = 0
wat = 0

for i in range(b):
  x,y = map(str,input().split())
  if y == "WA":
    WA[int(x)] += 1
  elif AC[int(x)] == 0 and y == "AC":
    wa += WA[int(x)]
    ac += 1
    AC[int(x)] = 1

print(ac,wa)
n = int(input())
s = input()

before = aaa
ans = 0
for char in s:
  if char != before:
    before = char
    ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
 
before = 'aaa'
ans = 0
for char in s:
  if char != before:
    before = char
    ans += 1
print(ans)
a=input().split()
N,A,B=int(a[0]),int(a[1]),int(a[2])
st_a='b'*A
st_b='r'*B

sum=0
b=''
d=st_a+st_b
e=A+B
while sum<=N:
  sum+=e
  b+=d
c=b[0:N]
print(c.count('b'))

### FIXED CODE ###

a=input().split()
N,A,B=int(a[0]),int(a[1]),int(a[2])
b=int(N/(A+B))
ans=int(A*b)
if(N-b*(A+B)<=A):
    ans=ans+N-b*(A+B)
else:
    ans+=A
print(int(ans))
def resolve():

    n = int(input())
    dataset = set(map(int, input().split()))

    li_dataset = list(dataset)
    xor = li_dataset[0] ^ li_dataset[1]

    flag = 0
    if xor in dataset:
        flag = 1

    if len(dataset) <= 3 and n % 3 == 0 and flag:
        print('Yes')

    else:
        print('No')
        
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    dataset = list(map(int, input().split()))

    xor = 0

    for i in range(n):
        xor ^= dataset[i]

    if xor == 0:
        print('Yes')
    else:
        print('No')
        
resolve()
#標準入力
N = int(input())
D, X = list(map(int, input().split()))

A = []
for i in range(N):
    A.append(input())
    
B=0
for i in range(N):
    B += 1 + (D-1)//A[i]

    
Total = X + B

print(Total)



### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())

if A < B:
  E = A
else:
  E = B
  
if C < D:
  F = C
else:
  F = D
  
print(E+F)
input(); print((lambda xs: max(xs) - min(xs))[int(x) for x in input().split()])

### FIXED CODE ###

n = int(input())
points = [int(x) for x in input().split()]
points.sort()
print(points[-1] - points[0])
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    l = lcm_list(a)

    i = l / 2

    if m < i:
        print("0")
    else:
        print(int(((m - i) // l) + 1))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    # for j in a:
    #     if j % 2 != 0:
    #         print("0")

    # a = [i/2 for i in a]
    l = lcm_list(a)

    # if l == 0:
    #     print(0)
    #     exit()

    if (2 * m) < l:
        print("0")
        exit()

    i = l / 2

    for j in a:
        if i // (j // 2) % 2 == 0:
            print(0)
            exit()

    # if m < i:
    #     print("0")
    else:
        # print("1")
        print(int(((m - i) // l) + 1))
        # print(int((m // i + 1) // 2))
import sys
X = list(sys.stdin.readline().strip())
N = len(X)

def solve():
    cnt = 0
    i = 0
    while True:
        while i < N and X[i] != 'S':
            i += 1
        j = i + 1
        while j < N and X[j] != 'T':
            j += 1
        if j == N:
            return N - 2*cnt
        cnt += 1
        X[i] = ' '
        X[j] = ' '
        i += 1
        j += 1

print(solve())

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())
from math import ceil
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    r = 1
    if nt<t:
        r *= ceil(t/nt)
    if na<a:
        r *= ceil(a/na)
    na = r*na
    nt = r*nt
    t,a = nt,na
    #print(t, a)
print(t+a)

### FIXED CODE ###

N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max((t-1)//nt+1, (a-1)//na+1)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)
t =[]
for n in range(2,10000):
  for x in range(2,n):
    if n % x == 0:
      break
  else:
    t.append(n)

while True:
  try:
    a = int(input())
    for b in range(100000):
      if t[b] >= a:
        break


    print len((t[0:b]))
  except EOFError:
    break

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env python
import sys
 
list=1000000*[1]
 
list[0] = 0
list[1] = 0
for i in range(1,1000000):
    if list[i] == 1:
        for j in range(i*i,1000000,i):
            list[j] = 0
 
for i in range(2,1000000):
    list[i] += list[i-1]
     
for line in sys.stdin:
    a = int(line)
    print list[a]
al = 'abcdefghijklmnopqrstuvwxyz'
N=int(input())
S=input()
Q=int(input())
from bisect import bisect_left, bisect_right
dic = {}
for i in range(N):
  if not S[i] in dic:
    dic[S[i]]=[i+1]
  else:
    dic[S[i]].append(i+1)
def fg1(l, r):
  l = int(l)
  dic[S[l-1]].remove(l)
  if not r in dic:
    dic[r]=[l]
  else:
    ins = bisect_left(dic[r], l)
    dicr = dic[r][:ins]
    dicr.append(l)
    dicr += dic[r][ins:]
    dic[r]=dicr
def fg2(l, r):
  l, r = int(l), int(r)
  ret = 0
  for d in list(dic.keys()):
    li = bisect_left(dic[d], l)
    if li<=len(dic[d])-1:
      ret += (dic[d][li]<=r)
  print(ret)
  
for i in range(Q):
  fg, l, r = input().split()
  if fg=='1':
    fg1(l, r)
  else:
    fg2(l, r)

### FIXED CODE ###

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

from bisect import bisect_left, bisect_right


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

al = 'abcdefghijklmnopqrstuvwxyz'
dicq = {i:[] for i in al}
for i, si in enumerate(s):
    dicq[si].append(i)

def q1(iq, cq):
    #print(iq,cq,s[iq],dicq[s[iq]],bisect_left(dicq[s[iq]], iq))
    dicq[s[iq]].pop(bisect_left(dicq[s[iq]], iq))   #更新前から削除
    s[iq] = cq
    dicq[cq].insert(bisect_left(dicq[cq], iq), iq)   #更新後に追加

def q2(l, r):
    ret = 0
    for ai in al:
        if len(dicq[ai])==0: continue
        li = bisect_left(dicq[ai], l)
        ri = bisect_right(dicq[ai], r)
        if li != ri:
            ret += 1
        elif li == len(dicq[ai]): continue
        elif dicq[ai][li] == l:
            ret += 1
    #    print(l,r,ai,dicq[ai],li,ri,ret)
    print(ret)

for i in range(q):
    fg, x, y = input().split()
    if fg == '1':
        q1(int(x)-1, y)
    else:
        q2(int(x)-1, int(y)-1)
N = int(input())
Hs = map(int, input().split())

"""
SEA H_1 H_2 H_3 H_4 ... H_N
"""

# 0 ~ i番目の旅館のうち最も高いもの
# max(Hs[0:i+1])

ret = 0
for i in range(N):
    if Hs[i] == max(0:i+1):
        ret += 1

print(ret)

### FIXED CODE ###

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

"""
SEA H_1 H_2 H_3 H_4 ... H_N
"""

# 0 ~ i番目の旅館のうち最も高いもの
# max(Hs[0:i+1])

ret = 0
for i in range(N):
    if Hs[i] == max(Hs[0:i+1]):
        ret += 1

print(ret)
a = list(map(int,input().split()))
print(0 if x<a else 10)

### FIXED CODE ###

a = list(map(int,input().split()))
print(0 if a[0]<a[1] else 10)
import itertools
n, m, q = list(map(input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
mx = 0
nums = list(range(1,11))
for h in itertools.combinations_with_replacement(nums,10):
    mxtemp = 0
    for j in range(q):
        a = sets[q][0]
        b = sets[q][1]
        if list(h)[b-1] - list(h)[a-1] == sets[q][2]:
            mxtemp += sets[q][3]
        if mxtemp > mx:
            mx = mxtemp
print(mx)

### FIXED CODE ###

import itertools
n, m, q = list(map(int,input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
#print(sets)
mx = 0
nums = list(range(1,m+1))
for h in itertools.combinations_with_replacement(nums,n):
    mxtemp = 0
    for j in range(q):
        a = sets[j][0]
        b = sets[j][1]
        if list(h)[b-1] - list(h)[a-1] == sets[j][2]:
            mxtemp += sets[j][3]
    if mxtemp > mx:
        mx = mxtemp
print(mx)
N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= sum(ar1):
                b = i+1
                break
        print(len(ar1)+b)


### FIXED CODE ###

l1  = input().split(" ")
ar = []
for i in l1:
  ar.append(int(i))
d = {1:0,9:0,7:0,4:0}
for i in ar:
  for j in d:
    if  i == j:
      d[j] = 1
con = True
for  i in d:
  if d[i] == 0:
    con = False
    print("NO")
    break
if con:
  print("YES")
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.parent[self.parent[x]] = self.root(self.parent[self.parent[x]]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

ans = [0]*(m+1)
a = n*(n-1)//2
ans[0] = a

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print(ans[m-i-1])
    
    
    
    
    
    





### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

ans = [0]*(m+1)
a = n*(n-1)//2
ans[0] = a

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print(ans[m-i-1])
a=int(input())

### FIXED CODE ###

s=input()
if s==s.upper():
  print('A')
else:
  print('a')
import sys
N, M = map(int, input().split())

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

### FIXED CODE ###

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

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N) % MOD)
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)
S = input()
i = 0
while i <= len(S)-5:
    if S[i:i+5] == "dream":
        i += 5
        if S[i:i+2] == "er" and S[i:i+5] != "erase":
            i += 2
    elif S[i:i+5] == "erase":
        i += 5
        if S[i] == "r":
            i += 1
    else:
        break
if i != len(S):
    print("NO")
else:
    print("YES")

### FIXED CODE ###

S = input()
i = 0
n = len(S)
while i <= n-5:
    if S[i:i+5] == "dream":
        i += 5
        if S[i:i+2] == "er" and S[i:i+5] != "erase":
            i += 2
    elif S[i:i+5] == "erase":
        i += 5
        if S[i:i+1] == "r":
            i += 1
    else:
        break
if i != len(S):
    print("NO")
else:
    print("YES")
from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(n):
    al[ord(s[i])-ord("a")].append(i)

for i in range(q):
    a , b , x = input().split()
    if a == "1":
        al[ord(s[int(b)-1])-ord("a")].pop(al[ord(s[int(b)-1])-ord("a")],int(b)-1)
        al[ord(x)-ord("a")].insert(bisect_left(al[ord(x)-ord("a")],int(b)-1),int(b)-1)
        s[int(b)-1] = x
    elif a == "2":
        b = int(b)-1
        x = int(x)-1
        cou = 0
        for j in range(26):
            l = bisect_left(al[j],b)
            r = bisect(al[j],x)
            if l != r:
                cou += 1
        print(cou)


### FIXED CODE ###

def main():
    from bisect import bisect_left,bisect
    n = int(input())
    s = list(input())
    q = int(input())
    al=[[] for i in range(26)]
    for i in range(n):
        al[ord(s[i])-97].append(i)
    ans = []
    for i in range(q):
        a , b , x = input().split()
        if a == "1":
            al[ord(s[int(b)-1])-97].pop(bisect_left(al[ord(s[int(b)-1])-97],int(b)-1))
            al[ord(x)-97].insert(bisect_left(al[ord(x)-97],int(b)-1),int(b)-1)
            s[int(b)-1] = x
        elif a == "2":
            b = int(b)-1
            x = int(x)-1
            cou = 0
            for j in range(26):
                l = bisect_left(al[j],b)
                r = bisect(al[j],x)
                if l != r:
                    cou += 1
            ans.append(cou)
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()