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

s = input()
length = len(s)
k = length
mid = length//2

while k>mid:
    overlap = s[length-k:k]
    pure = len(set(list(overlap))) == 1
    if pure:
        print(k)
        exit()
    k -= 1

print(mid)

### FIXED CODE ###

# D 3424320
S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2
l = r = center_i
if N%2==0:
    l -= 1
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

n=int(input())
S=deque()
A=deque()

for i in range(n):
	cnt=-1
	str=input().split()
	if str[0][0]=="i":
		S.append(str[1])
	else:
		'''for i in range(len(S)):
			if S[i]==str[1]:
				cnt+=1
				break
		'''
		try:
			cnt=S.index(str[1])
		except:
			pass
		if cnt!=-1:
			print("yes")
		else:
			print("no")



### FIXED CODE ###

n=int(input())
dict={}
for i in range(n):
    str=input()
    if str[0]=="i":
        dict.update({str[7:]:1})
    else:
        if str[5:] in dict:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import math
from collections import Counter
n=int(input())
l=[int(x) for x in input().split()]
f1=[]
f2=[]
for i in range(1,len(l)+1):
	f1.append(i-l[i-1])
	f2.append(l[i-1]+i)

c=0
for i in range(len(l)):
	c+=f1.count(f2[i])
print(c)




### FIXED CODE ###

n=int(input())
l=[int(x) for x in input().split()]
f1={}
f2={}
for i in range(1,len(l)+1):
	if i-l[i-1] in f1:
		f1[i-l[i-1]]+=1
	else:
		f1[i-l[i-1]]=1
	if l[i-1]+i in f2:
		f2[l[i-1]+i]+=1
	else:
		f2[l[i-1]+i]=1

c=0
#print(f1)
#print(f2)
for u,v in f1.items():
	c+=f2.get(u,0)*v
print(c)
### BUGGY CODE ###

N = int(input())
A = input().split()
A = list(map(int,A))
sa = 0
useds = []
min_value = 10000000000000000000

for j in range(1,len(A)+1):
	sa = A[j-1]-j
	if((sa not in useds)==True):
		useds.append(sa)
		b = int(sa)
		sum_As = 0
		for p in range(1,len(A)+1):
			sum_As += abs(A[p-1]-(b+p))

		if(sum_As<min_value):
			min_value = int(sum_As)

print(min_value)

### FIXED CODE ###

import statistics

N = int(input())
A = input().split()
A = list(map(int,A))
sa = 0
sa_list = []

for i in range(1,N+1):
	sa = A[i-1]-i
	sa_list.append(sa)

sa_list.sort()
if(len(sa_list)%2 != 0):
	b = statistics.median(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	print(sum_As)
else:
	b = statistics.median_low(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	
	b2 = statistics.median_high(sa_list)
	sum_As2 = 0
	for p in range(1,len(A)+1):
		sum_As2 += abs(A[p-1]-(b2+p))
	
	print(max(sum_As,sum_As2))
### BUGGY CODE ###

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

total = sum(A)
ans = 10**9
if n > 2:
    for i in range(1,n-1):
        res = abs(total - 2*sum(A[:i]))
        ans = min(ans, res)
else:
    ans = (A[0] - A[1])
print(ans)


### FIXED CODE ###

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

total = sum(A)
ans = 10**10
res = 0

for i in range(n-1):
    res += A[i]
    ans = min(ans, abs(total -2*res))

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

A, B, K = map(int, input().split())
l = range(A, B+1)
  
for i in range(len(l)):
  if l[i] <= A + K - 1 or B - K + 1 <= l[i]:
    print(l[i])

### FIXED CODE ###

A, B, K = map(int, input().split())
l = []

if B - A + 1 > 2 * K:
  for i in range(K):
    l.append(A + i)
    l.append(B - i)
else:
  l = list(range(A, B+1))
  
l.sort()

for i in l:
  print(i)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ set() for i in range(n) ]

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].add(v - 1)
    nbs[v - 1].add(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

memo = [{} for i in range(M+1)]
def dfs(rest, i):
    if i == M:
        return ([] if rest == 0 else None), 0
    mi = memo[i]
    if rest in mi:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
        k += 1
    if r is None:
        mi[rest] = r = None, 0
    else:
        mi[rest] = r = [kc] + r, cnt
    return r
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

N, M = map(int, readline().split())
*A, = map(int, readline().split())

A.sort(reverse=1)
CS = [0,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M+1)]
mM = memo[M]
mM[0] = EMP
for i in range(1, N+1):
    mM[i] = INV
def dfs(rest, i):
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
writelines(ans)
write("\n")
### BUGGY CODE ###

from collections import defaultdict,Counter
import queue

N, X, Y = map(int, input().split())
d = defaultdict(list)
d[X].append(Y)
d[Y].append(X)
for i in range(1,N):
    d[i].append(i+1)
    d[i+1].append(i)

ans=defaultdict(int)

for i in range(N):
    dist = [None]*N
    s=i+1
    q=queue.Queue()
    q.put(s)
    dist[i]=0

    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    c=Counter(dist)
    for i,m in c.items():
        ans[i]+=m


for i in range(1,N):
    print(ans[i]//2)


### FIXED CODE ###

from collections import Counter, deque


def bfs(d, s, N):
    dist = [-1]*N
    q = deque()
    q.append(s)
    dist[i] = 0
    while len(q) != 0:
        From = q.popleft()
        for To in d[From]:
            if dist[To-1] == -1:
                q.append(To)
                dist[To-1] = dist[From-1]+1
    return dist


N, X, Y = map(int, input().split())
d = [[] for _ in range(N+1)]
d[X].append(Y)
d[Y].append(X)
for i in range(1, N):
    d[i].append(i+1)
    d[i+1].append(i)

ans = [0]*(N+1)

for i in range(N):
    s = i+1
    c = Counter(bfs(d, i+1, N))
    for i, m in c.items():
        ans[i] += m

for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

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

import queue

h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = queue.Queue()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.put( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while not q.empty():
    # queue の先頭を取り出す
    x, y, dist = q.get()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.put( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

### FIXED CODE ###

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

from collections import deque

# input
h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False for _ in range(w)] for __ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

while q:
    # queue の先頭を取り出す
    x, y, cnt = q.popleft()
    # 4方向にループ
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny or is_visited[ny][nx]:
            continue

        q.append( (nx, ny, cnt+1) )
        is_visited[ny][nx] = True

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

N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

color_num = 0

while A != []:
    base = A[0]
    A.pop(0)

    looking = 0

    while looking < len(A):
        if base < A[looking] :
            base = A[looking]
            A.pop(looking)
        else:
            looking += 1

    color_num += 1

print(color_num)


### FIXED CODE ###

import bisect

N = int(input())

A = [int(input()) for _ in range(N)]

colors = []

for i in range(N-1, -1, -1):
    target = bisect.bisect_right(colors, A[i])

    if target == len(colors):
        colors.append(A[i])
    else:
        colors[target] = A[i]

print(len(colors))
### BUGGY CODE ###

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

mx = 10**18

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

print(ans) if ans <= mx else print(-1)

### FIXED CODE ###

n = int(input())
alist = list(map(int,input().split()))
alist.sort()
mx = 10**18

ans = 1
for a in alist:
    ans *= a
    if ans > mx:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n, k =map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
roop = []
seen = [0 for  _ in range(n)]
count = 0
for i in range(n):
    if seen[i]>0:
        continue
    else:
        count+=1
        seen[i] = count
        roop.append([c[i]])
        t = i
        while i!=p[t]-1:
            seen[p[t]-1]=count
            roop[-1].append(c[p[t]-1])
            t = p[t]-1
#print(seen)
#print(roop)
ans = max(c)
for i in roop:
    ii = i+i
    if len(i)>=k:
        for j in range(1, k+1):
            for l in range(len(i)):
                temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
    else:
        for j in range(1, len(i)+1):
            for l in range(len(i)):
                if sum(i)>0:
                    temp = sum(ii[l:l+j])+(sum(i)*((k-j)//len(i)))
                else:
                    temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
            
print(ans)

        

### FIXED CODE ###

n, k =map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
roop = []
seen = [0 for  _ in range(n)]
count = 0
for i in range(n):
    if seen[i]>0:
        continue
    else:
        count+=1
        seen[i] = count
        roop.append([c[i]])
        t = i
        while i!=p[t]-1:
            seen[p[t]-1]=count
            roop[-1].append(c[p[t]-1])
            t = p[t]-1
#print(seen)
#print(roop)
ans = max(c)

for i in roop:
    #print(ans)
    
    s = sum(i)
    ii = i+i
    #print(ii)
    if len(i)>=k:
        for j in range(1, k+1):
            temp = sum(ii[:j])
            for l in range(len(i)):
                if l!=0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                    #temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
    else:
        for j in range(1, len(i)+1):
            temp=  sum(ii[:j])
            for l in range(len(i)):
                if l != 0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                #print(temp)
                if s>0:
                    temp1 = temp+s*((k-j)//len(i))
                else:
                    temp1 = temp
                
                #print(i, j, l, temp)
                ans  = max(ans, temp)
                ans  = max(ans, temp1)
            
print(ans)
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())
a = []
b = []
for i in range(m):
    a_ , b_ = map(int,input().split())
    a.append(a_)
    b.append(b_)

broken_bridge = [0 for i in range(n-1)]
comp_task = [0 for i in range(m)]

a = np.array(a) - 1
b = np.array(b) - 1 
cnt = 0
comp_task = np.zeros(m).astype(np.bool)
in_task = np.zeros(m).astype(np.bool)

for i in range(n-1):
    if(np.any(a == i)):
        in_task += (a == i).astype(np.bool)
    if(np.any(b*in_task == i+1)):
        cnt += 1
        comp_task += in_task
        a[comp_task] = -1
        b[comp_task] = -1
        in_task = np.zeros(m).astype(np.bool)

print(cnt)

### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ac_l = []
ans = []
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_l.append(i)
for i in range(q):
    l, r = map(int, input().split())
    print(len([j for j in ac_l if j>=l-1 and j+1<=r-1]))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])
### BUGGY CODE ###

import bisect
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=bisect.bisect_left(ans,num)
    if index==0:
        tmp=[num]
        tmp.extend(ans)
        ans=tmp
    else:
        ans[index-1]=num
print(len(ans))

### FIXED CODE ###

#import bisect
def desc_bin(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=desc_bin(ans,num)
    if index==len(ans):
        ans.append(num)
    else:
        ans[index]=num
    #print(ans)
print(len(ans))
### BUGGY CODE ###

N,M = map(int,input().split())
xs,ys,zs =[],[],[]
comps1 = []
comps2 = []
comps3 = []
comps4 = []
comps5 = []
comps6 = []
comps7 = []
comps8 = []
for i in range(N):
    x,y,z = map(int,input().split())
    raw = [x+y+z,x+y-z,x-y+z,x-y-z,-x+y+z,-x+y-z,-x-y+z,-x-y-z,]
    comps1.append(raw[0])
    comps2.append(raw[1])
    comps3.append(raw[2])
    comps4.append(raw[3])
    comps5.append(raw[4])
    comps6.append(raw[5])
    comps7.append(raw[6])
    comps8.append(raw[7])

ans = 0
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps1[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps2[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps3[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps4[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps5[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps6[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps7[i-1])
cand = dp[N][M]
ans = max(ans,cand)
###
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+comps8[i-1])
cand = dp[N][M]
ans = max(ans,cand)

print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
comp = [[] for _ in range(8)]
for i in range(N):
    x,y,z = map(int,input().split())
    raw = [x+y+z,x+y-z,x-y+z,x-y-z,-x+y+z,-x+y-z,-x-y+z,-x-y-z]
    for j in range(8):
        comp[j].append(raw[j])
ans = 0
for k in range(8):
    comp[k].sort(reverse=True)
    sum = 0
    for l in range(M):
        sum += comp[k][l]
    ans = max(ans,sum)


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

def sort_list():
    _ = input()
    K = [int(x) for x in input().split()]
    ans = 0
    n_lst = tuple(sorted(K, reverse=True))
    for idx in range(len(K)-2):
        for diff_idx in range(idx+1, len(K)-1):
            diff = n_lst[idx] - n_lst[diff_idx]
            for search in range(diff_idx+1, len(K)):
                if n_lst[search] <= diff:
                    search -= 1
                    break
            ans += search - diff_idx
    print(ans)


if __name__ == "__main__":
    sort_list()


### FIXED CODE ###

import bisect


def sort_list():
    _ = input()
    K = [int(x) for x in input().split()]
    ans = 0

    len_k = len(K)
    n_lst = sorted(K)

    for idx in reversed(range(2, len_k)):
        for diff_idx in range(1, idx):
            diff = n_lst[idx] - n_lst[diff_idx]
            insert_index = bisect.bisect_right(n_lst, diff)
            if insert_index < diff_idx:
                # print(n_lst, diff, idx, diff_idx, insert_index)
                ans += diff_idx - insert_index
    print(ans)


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

N = int(input())

c = list()
for n in range(1, N+1):
    c.append(n)

d = c[:]
del d[0]
d.append(1)

cont = 0
for e, f in zip(c, d):
    mod = e % f
    cont += mod


print(cont)

### FIXED CODE ###

N = int(input())
print((N*(N-1))//2)
### BUGGY CODE ###

n=int(input())
flag=0
nums=list(map(int,input().split()))
cnt=0

while flag==0:
    for i in range(n):
        num=nums[0]/2
        key=nums[0]%2
        if key==1:
            flag==1
            break
        else:
            del nums[0]
            nums.append(num)
    if flag==0:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
nums=list(map(int,input().split()))
cnt=0
flag=0
while flag is 0:
    for i in range(n):
        num=nums[0]/2
        key=nums[0]%2
        if key==1:
            flag=1
            break
        else:
            del nums[0]
            nums.append(num)
    if flag==0:
        cnt+=1

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

from bisect import insort_left, bisect_left
n = int(input())
s = input()
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)


### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
### BUGGY CODE ###

import sys;input=sys.stdin.readline
from bisect import*

n,q=map(int,input().split())
event=[]
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        if l[2] in stopped:
            stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]+[float("inf")]
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1


### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n,m=map(int,input().split())
a="AC"
s=input()
for _ in range(m):
    x,y=map(int,input().split())
    print(s[x-1:y].count(a))

### FIXED CODE ###

n,m=map(int,input().split())
a="AC"
arr=[0]*(n+1)
s=input()
for i in range(1,n+1):
    arr[i]=arr[i-1]+s[i-1:i+1].count(a)
for _ in range(m):
    x,y=map(int,input().split())
    print(arr[y-1]-arr[x-1])