Harryxun/stf_run huggingface dataset:
def cut(d, w, s):
    s %= 2 * (d + w)
    sq = []
    if 0 < s < w:
        sq = [(d, s), (d, w - s)]
    elif w < s < w + d:
        s -= w
        sq = [(s, w), (d - s, w)]
    elif w + d < s < 2 * w + d:
        s -= w + d
        sq = [(d, s), (d, w - s)]
    elif 2 * w + d < s < 2 * (w + d):
        s -= 2 * w + d
        sq = [(s, w), (d - s, w)]
    else:
        assert(False)
    p1, p2 = sq
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return [p1, p2]


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        square.extend(cut(*square.pop(p - 1), s))
    print(*sorted(d * w for d, w in square))

### FIXED CODE ###

def cut(d, w, s):
    s %= d + w
    if 0 < s < w:
        p1, p2 = (d, s), (d, w - s)
    else:
        s -= w
        p1, p2 = (s, w), (d - s, w)
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return [p1, p2]


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        d, w = square.pop(p - 1)
        square.extend(cut(d, w, s))
    print(*sorted(d * w for d, w in square))
import math

n=int(input())

sum=0
for i in range(1,n):
  for j in range(1,n):
    for k in range(1,n):
      y=[[i,j,k]]
      for h in range(z):
        x=math.gcd(h[0],h[1],h[2])
        sum=sum+x
print(sum)

### FIXED CODE ###

import math

n=int(input())

sum=0
for i in range(1,n+1):
  for j in range(1,n+1):
      x=math.gcd(i,j)
      for h in range(1,n+1):
        p=math.gcd(x,h)
        sum=sum+p
print(sum)
O = list(input())
E = list(input())
ans =[]
for i in range(len(O)):
  ans.append(O[i])
  ans.append(E[i])
print("".join(ans))

### FIXED CODE ###

O = list(input())
E = list(input())
ans =[]

if len(O)>len(E):
  for i in range(len(E)):
    ans.append(O[i])
    ans.append(E[i])
  ans.append(O[-1])
  print("".join(ans))
else:
  for i in range(len(E)):
    ans.append(O[i])
    ans.append(E[i])
  print("".join(ans))
sec = input().split(' ')
#sec = ['0','75','25','100']
#sec = ['0','33','66','99']
#print(sec[0],sec[1],sec[2],sec[3])
#開始時間選定
start = max(sec[0],sec[2])
#print('開始:' + start)
#終了時間選定
end = min(sec[1],sec[3])
#print('終了:' + end)
kekka =(int(end) - int(start))
if kekka < 1:
	kekka = 0
	print(kekka)
else:
	print(kekka)

### FIXED CODE ###

kaibun = str(input())
#print(kaibun)
#print(kaibun[::-1])
if kaibun == kaibun[::-1]:
	print('Yes')
else:
	print('No')
a = int(input())
b = int(input())


list = [1,2,3]

list.pop(a)
list.pop(b)

print(list[0])


### FIXED CODE ###

a = int(input())
b = int(input())

list = [1,2,3]

list.remove(a)
list.remove(b)

print(list[0])
i = 0;
mod = 0;
while True:
    mod = (mod*10 + 7) % k;
    if mod == 0:
        break;
    i += 1;
    if i == k:
        j = -2
        break;

print(i+1)

### FIXED CODE ###

k = int(input())


i = 0;
mod = 0;
while True:
    mod = (mod*10 + 7) % k;
    if mod == 0:
        break;
    i += 1;
    if i == k:
        i = -2
        break;

print(i+1)
h, a = input().split;
h = int(h);
a = int(a);

if h % a == 0:
  ans = int(h // a);
else:
  ans = int(h // a + 1);
  
print(ans);

### FIXED CODE ###

h, a = input().split();
h = int(h);
a = int(a);

if h % a == 0:
  ans = int(h // a);
else:
  ans = int(h // a + 1);
  
print(ans);
n = int(input())
nums = list(map(int, input().split()))
nums.sort()
if nums[n] < sum(nums[:n]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
if nums[n-1] < sum(nums[:n-1]):
    print("Yes")
else:
    print("No")
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

ans=[]

for i in range(len(N)//2+1):
  if i*2<=k and k-i*2<=len(P):
    ans.append(N2[i*2]*P2[k-i*2])

if len(ans)!=0:
  print(max(ans)%mod)
  exit()

for i in range(k+1):
  if k-i<=len(P):
    ans.append(N3[i]*P3[k-i])

print(-min(ans)%mod)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if n==k:
  ans=1
  for i in range(n):
    ans*=a[i]
    ans%=mod
  print(ans%mod)
  exit()

if k==1:
  print(max(a)%mod)
  exit()

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k]%mod)
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<=xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans%mod)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<=xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans%mod)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<=xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)
def gcd(a,b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a %b)

def gcdlist(l):
    if len(l) == 2:
        return gcd(l[0], l[1])
    f = l.pop()
    s = l.pop()
    m = gcd(f, s)
    l.append(m)
    return gcdlist(l)


def main():
    n, x = map(int, input().split())
    a = [int(v) for v in input().split(' ')]
    a.append(x)
    a.sort()
    dis = [x2 - x1 for x1, x2 in zip(a, a[1:])]
    max_ = 0
    for i in range(n):
        if len(dis) == 1:
            max_ = dis[0]
            break
        max_ = gcdlist(dis)
    print(max_)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a %b)

def gcdlist(l):
    if len(l) == 2:
        return gcd(l[0], l[1])
    f = l.pop()
    s = l.pop()
    m = gcd(f, s)
    l.append(m)
    return gcdlist(l)


def main():
    n, x = map(int, input().split())
    a = [int(v) for v in input().split(' ')]
    a.append(x)
    a.sort()
    dis = [x2 - x1 for x1, x2 in zip(a, a[1:])]
    max_ = 0
    for i in range(n):
        if len(dis) == 1:
            max_ = dis[0]
            break
        try:
            max_ = gcdlist(dis)
        except:
            max_ = 1
    print(max_)

if __name__ == '__main__':
    main()
n = int(input())
s = input()
x = m = 0
for i range(n): x += [-1,1][s[i] == I]; m = max(m,x)
print(m)

### FIXED CODE ###

n = int(input())
s = input()
x = m = 0
for i in range(n): x += [-1,1][s[i] == "I"]; m = max(m,x)
print(m)
a=input()
if a="A":
  print("T")
elif a="T":
  print("A")
elif a="G":
  print("C")
else:
  print("G")

### FIXED CODE ###

a=input()
if a=="A":
	print("T")
elif a=="T":
    print("A")
elif a=="G":
	print("C")
else:
	print("G")
from collections import deque

n,m=map(int,input().split())
graph=[[] for _ in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)#aにはbがつながってる
    graph[b-1].append(a-1)#bにはaがつながってる
#print(graph)

res=[-1]*n
que=deque()
que.append(0)

while len(que)>0:
    i=que.popleft();
    for j in graph[i]:
        if res[j]==-1:
            res[j]=i
            que.append(j)
    #print(que)

print("Yes")
for l in res[1:]:
    print(l+1)

### FIXED CODE ###

n=input()
if n[-1]=="3":
    print("bon")
elif (n[-1]=="0")|(n[-1]=="1")|(n[-1]=="6")|(n[-1]=="8"):
    print("pon")
else:
    print("hon")
n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n)
while n > 26:
    r = n % 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
for i in range(1, l):
    rev[i] += 1
name = []

for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i] - 1]
    name.append(d)
dogname = ''.join(name)
print(dogname)

### FIXED CODE ###

n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n) - 1
while n > 25:
    r = n % 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
name = []
for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i]]
    name.append(d)
dogname = ''.join(name)
print(dogname)
if __name__=="__main__":
    n = int(input())
    s=[]
    for i in range(n):
        s.append(input())
        
    s_most = s.most_common()

    print(s_most[0])

    for i in range(1,len(s_most)):
        if s_most[i]==s_most[0]:
            print(s_most[i])
        else:
            break

### FIXED CODE ###

from collections import Counter

if __name__=="__main__":
    n = int(input())
    s=[]
    for i in range(n):
        s.append(input())
        
    s_most = Counter(s).most_common()

    ans_list = [s_most[0][0]]
    for i in range(1,len(s_most)):
        if s_most[i][1]==s_most[0][1]:
            ans_list.append(s_most[i][0])
        else:
            break

    ans_list.sort()

    for i in range(len(ans_list)):
        print(ans_list[i])
import numpy as np

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            if bool_list[s]:
                input_list[s] = serial
                bool_list[s] = False

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

D = getD(max(A))
record = np.zeros((N, max(A)+1), np.uint8)

for i, a in enumerate(A):
    while a > 1:
        record[i, D[a]] = 1
        a = a // D[a]

flag = True

for i in range(2, max(A) + 1):
    s = np.sum(record[:, i])
    if s == 1:
        continue
    elif s == N:
        print('not coprime')
        exit()
    if s > 1:
        flag = False

if flag:
    print('pairwise coprime')
else:
    print('setwise coprime')



### FIXED CODE ###

import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for i in range(N):
    k = A[i]
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = A[0]
for i in range(N):
    gcd_of_a = gcd(gcd_of_a, A[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")
S=input()
n=len(S)
def T(i):
    if i == 0:
        return 0
    else:
        i-=1
        return T(i)+(10**i)*int(S[n-1-i])
s=[0]*2019
for j in range(1,n+1):

    m=T(j)%2019

    s[m]+=1

c=s[0]

for m in s:
    c += m*(m-1)/2

print(int(c))

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(combinations_with_replacement(range(1,M+1),N))
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)

### FIXED CODE ###

#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(itertools.combinations_with_replacement(range(1,M+1),N))
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)
mod=10**9+7

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

if A.count(0)==1: # 1色のみ
    ans=3
elif A.count(0)==2: # 2色のみ
    ans=1
    c1=c2=0
    for Ai in A:
        if Ai==0:
            if c1==0:
                c1+=1
                ans=ans*3%mod
            elif c2==0:
                c2+=1
                ans=ans*2%mod
        else:
            if c1==c2==Ai:
                c1+=1
                ans=ans*2%mod
            else:
                if c1==Ai:
                    c1+=1
                elif c2==Ai:
                    c2+=1
elif A.count(0)==3: # 3色全部
    ans=1
    c1=c2=c3=0
    for Ai in A:
        if Ai==0:
            if c1==0:
                c1+=1
                ans=ans*3%mod
            elif c2==0:
                c2+=1
                ans=ans*2%mod
            elif c3==0:
                c3+=1
        else:
            if c1==c2==c3==Ai:
                c1+=1
                ans=ans*3%mod
            elif c1==c2==Ai or c1==c3==Ai:
                c1+=1
                ans=ans*2%mod
            elif c2==c3==Ai:
                c2+=1
                ans=ans*2%mod
            else:
                if c1==Ai:
                    c1+=1
                elif c2==Ai:
                    c2+=1
                elif c3==Ai:
                    c3+=1

print(ans)

### FIXED CODE ###

mod=1000000007

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

ans=1
c1=c2=c3=0
for Ai in A:
    if c1==c2==c3==Ai:
        c1+=1
        ans=ans*3%mod
    elif c1==c2==Ai:
        c1+=1
        ans=ans*2%mod
    elif c2==c3==Ai:
        c2+=1
        ans=ans*2%mod
    elif c1==Ai:
        c1+=1
    elif c2==Ai:
        c2+=1
    elif c3==Ai:
        c3+=1
    else:
        ans=0
        break

print(ans)
import math

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

def get_num(a, lcm):
    return lcm // a


N_str = input()
a_str = input()
a_str_list = a_str.split(" ")
a_list = mapped_list = map(lambda x: int(x), a_str_list)
lcm = 1
for a in a_list:
    lcm = get_lcm(lcm, a)

sum_a = 0
for a in a_list:
    sum_a = a * get_num(a, lcm)

result = lcm // sum_a
input(result)

### FIXED CODE ###

import fractions

def get_lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def get_num(a, lcm):
    return lcm // a


N_str = input()
a_str = input()
a_str_list = a_str.split(" ")
a_list = list(map(lambda x: int(x), a_str_list))
lcm = 1
for a in a_list:
    lcm = get_lcm(lcm, a)

sum_a = 0
for a in a_list:
    sum_a += get_num(a, lcm)

result = lcm / sum_a
print(result)
h, a = map(int, input().split())
  print(h//a + h%a != 0)

### FIXED CODE ###

h, a = map(int, input().split())
print((h+a-1)//a)
N,M=map(int,input().split())
A=[int(input()) for __ in range(M)]
ans=[0]*N

if 0 in A:
    ans[1]=1
elif 1 in A:
    ans[0]=1
else:
    ans[0]=1
    ans[1]=2

for n in range(N):
    if n>1:
        if n+1 in A and n in A:
            print(0)
            break
        elif n+1 in A:
            ans[n]=0
        else:
            ans[n]=ans[n-1]+ans[n-2]
            ans[n] %= 1000000007
else:
    print(ans[N-1])


### FIXED CODE ###

N,M=map(int,input().split())
A=set([int(input()) for __ in range(M)])
ans=[0]*(N+1)
ans[0] = 1

if 1 in A:
    ans[1]=0
else:
    ans[1]=1

for n in range(N+1):
    if n>1:
        if n-1 in A and n in A:
            print(0)
            break
        elif n in A:
            ans[n]=0
        else:
            ans[n]=(ans[n-1]+ans[n-2]) % 1000000007
else:
    print(ans[N])
n,q=map(int,input().split())
s=input()
count=[0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1]=="AC":
        count[i]+=1
for i in range(n):
    l,r=map(int,input().split())
    print(count[r-1] - count[l-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count=[0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1]=="AC":
        count[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(count[r-1] - count[l-1])
N, K = map(int, input().split())
cnt = 0

for b in range(K+1, N+1):
    u = ((N - b)//b) + 1
    v =  (N - K)//b

    cnt += (b-K)*u + (v-u+1)*(-b*(u+v)+2*N-2*K+2)*(1/2)

print(cnt)





### FIXED CODE ###

row1 = input()[0]
row2 = input()[1]
row3 = input()[2]

print(row1 + row2 + row3)
a, b = map(int, imput().split())
seki = a*b
if seki % 2 == 0:
	print('Even')
else:
	print('Odd')


### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
from itertools import groupby

def count(s):
    l = []
    c = 0
    for key,value in groupby(s):
        l.append(list(value))
    for i in l:
        c += len(i)//2
    return c
s = list(input())
k =int(input())
print(count(s*k))



### FIXED CODE ###

from itertools import groupby

def count(s):
    l = []
    c = 0
    for key,value in groupby(s):
        l.append(list(value))
    for i in l:
        c += len(i)//2
    return c
s = list(input())
k =int(input())
if k <= 10**5:
    print(count(s*k))
else:
    d2 = count(s*3)-count(s*2)
    d3 = count(s*4)-count(s*3)
    if d2 != d3:
        if k%2 == 1:
            print(d2*((k-2)//2+1) + count(s*2) + d3*((k-2)//2))
        else:
            print(d2*((k-2)//2) + count(s*2) + d3((k-2)//2))
    else:
        print(d2*(k-2) + count(s*2))
N=int(input("enter number")) 
Counter1=0
Counter2=0
for i in range(N) :
    if i%2==0:
        Counter1+=1 
    if i%2==1:
        Counter2+=1 
Print(Counter1*Counter2)

### FIXED CODE ###

n=int(input())
e=int(n/2)
if n%2:
	o=int(n/2+1)
else:
	o=int(n/2)
	
print (o*e)
#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i))
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()