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

N, K = map(int, input().split())
MOD = 998244353

l = [0] * K
r = [0] * K

for i in range(K):
	l[i], r[i] = map(int, input().split())
	
dp = [0] * (N+1)
dp[1] = 1

dpsum = [0] * (N+1)
dpsum[1] = 1

for i in range(2, N+1):
	for j in range(K):
		li = i - r[j]
		ri = i - l[j]
		if li <= 0:
			dp[i] = dp[i] + dpsum[ri]
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	
print(dp[N] % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

l = [0] * K
r = [0] * K

for i in range(K):
	l[i], r[i] = map(int, input().split())
	
dp = [0] * (N+1)
dp[1] = 1

dpsum = [0] * (N+1)
dpsum[1] = 1

for i in range(2, N+1):
	for j in range(K):
		li = i - r[j]
		ri = i - l[j]
		if li <= 0:
			dp[i] = dp[i] + dpsum[ri]
			dp[i] %= MOD
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			dp[i] %= MOD
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	dpsum[i] %= MOD
	
print(dp[N] % MOD)
### BUGGY CODE ###

#n = int(input())
n,m,k = [int(z) for z in input().split()]
a = [int(z) for z in input().split()]
b = [int(z) for z in input().split()]
time = 0
x=[0]
y=[0]
#maX = -100000
num = 0
for i in range(n):
      x.append(x[i]+a[i])
for j in range(m):
      y.append(y[j]+b[j])

for i in range(n+1):
      for j in range(m+1):
            z = x[i]+y[j]
            if (z<=k):
                  num = max(num,i+j)
                  
print(num)


### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, M, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))


    nowtime = 0

    Asum = [0]
    Bsum = [0]
    tmp = 0
    for a in A:
        tmp += a
        Asum.append(tmp)
    tmp = 0
    for b in B:
        tmp += b
        Bsum.append(tmp)

    maxbooks = 0
    before = M
    bcount = M
    for acount in range(N+1):
        if Asum[acount] > K:
            continue
        while K < Asum[acount] + Bsum[bcount]:
            bcount -= 1
        maxbooks = max(maxbooks, acount+bcount)

    print(maxbooks)

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

from itertools import combinations
n = int(input())
s = input()
ans = set()
for i in combinations(s, 3):
    a = ''.join(i)
    if not a in ans:
        ans.add(a) 
print(len(ans))


### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

for i in range(0, 1000):
    count = 0
    val = list(str(i).zfill(3))
    k = val[count]
    for j in s:
        if j == k:
            count += 1
            if count <= 2:
                k = val[count]
            elif count == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import collections


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

route = np.array([[0 for _ in range(n)]for _ in range(n)])
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)


ans = [0 for _ in range(n)]
for i in range(n):
	for j in range(i,n):
		ans[int(res[i][j])] += 1

for i in range(1,n):
	print(ans[i])


### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

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

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = tuple(dijkstra(route, directed=False))

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

dic={}

for i in range(1,N+1):
    a=Ai.index(i)+1
    dic[i]=a

ans=''
for i in range(1,N+1):
    ans+=str(dic[i])+' '
print(ans)

### FIXED CODE ###

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

# ans=[]
ans=[0]*N

# for i in range(1,N+1):
    # a=Ai.index(i)+1
    # ans.append(str(a))
for i in range (N):
    ans[Ai[i]-1]=str(i+1)

print(' '.join(ans))
### BUGGY CODE ###

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

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


D = {}
parent = [-1] * N
visited = [False] * N
for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    stack = [root]
    while stack:
        n = stack.pop()
        visited[n] = True
        parent[n] = root

        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    group = D[parent[iam]]
    tmp_ans = len(group) - len(F[iam]) - 1
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')


### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    N, M, K = map(int, sys.stdin.readline().split())

    F = [set() for _ in range(N)]
    B = [set() for _ in range(N)]
    for m in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        F[a].add(b)
        F[b].add(a)

    for k in range(K):
        c, d = map(int, sys.stdin.readline().split())
        c, d = c - 1, d - 1
        B[c].add(d)
        B[d].add(c)

    D = defaultdict(set)
    parents = [-1] * N
    visited = set()
    for s in range(N):
        if s in visited:
            continue

        stack = [s]
        D[s].add(s)
        while stack:
            n = stack.pop()
            visited.add(n)
            parents[n] = s
            for to in F[n]:
                if to in visited:
                    continue
                D[s].add(to)
                stack.append(to)

    ans = [0] * N
    for i in range(N):
        X = D[parents[i]]
        tmp_ans = 0
        tmp_ans += len(X)
        tmp_ans -= len(F[i])
        tmp_ans -= 1
        for b in B[i]:
            if b in X:
                tmp_ans -= 1
        ans[i] = tmp_ans

    print(*ans, sep=' ')


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

import sys
sys.setrecursionlimit(200000)

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    global b, w

    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W:
            if S[i][j] != S[ni][nj] and not visited[ni][nj]:
                dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)



### FIXED CODE ###

from collections import deque


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


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '#':
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


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

N, C = map(int, input().split())
#D[X][Y] = (X+1)→(Y+1)に塗り替えたときの違和感
D = [list(map(int, input().split())) for i in range(C)]
#C[i][j] = (i+1,j+1)の色
c = [list(map(int, input().split())) for i in range(N)]
#import pdb; pdb.set_trace()
ans = float('inf')

def mult3(x):
    if x % 3 == 0:
        return 1
    else:
        return 0

for x in range(C):
    for y in range(C):
        for z in range(C):
            if (x-y)*(y-z)*(z-x) != 0:
                new_grid = [[mult3(i+j) * x + mult3(i+j-1) * y + mult3(i + j -2) * z + 1 for j in range(N)]for i in range(N)]
                iwakan = 0
                for i in range(N):
                    for j in range(N):
                        iwakan += D[c[i][j] - 1][new_grid[i][j] - 1]
                ans = min(ans, iwakan)
print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
#D[X][Y] = (X+1)→(Y+1)に塗り替えたときの違和感
D = [list(map(int, input().split())) for i in range(C)]
#C[i][j] = (i+1,j+1)の色
c = [list(map(int, input().split())) for i in range(N)]
#import pdb; pdb.set_trace()
ans = float('inf')
#c0: (i+1)+(j+1) \equiv 0 なるマスに色1, 色2, ..., 色Cがそれぞれ何個書かれているか
c0 = [0] * C
c1 = [0] * C
c2 = [0] * C
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            c0[c[i][j] - 1] += 1
        if (i + j) % 3 == 1:
            c1[c[i][j] - 1] += 1
        if (i + j) % 3 == 2:
            c2[c[i][j] - 1] += 1


for x in range(C):
    for y in range(C):
        for z in range(C):
            if (x-y)*(y-z)*(z-x) != 0:
                iwakan = sum(D[i][x] * c0[i] for i in range(C)) + sum(D[j][y] * c1[j] for j in range(C))+sum(D[k][z] * c2[k] for k in range(C))                
                ans = min(ans, iwakan)
print(ans)
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
    temp = 0
    for j in range(i,N):
        temp += A[j]
        if j-i+1 >= K:
            break;
        if temp%K == j-i+1:
            cnt += 1
print (cnt)

### FIXED CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for i in range(N+1)]
for i in range(1,N+1):
    S[i] = S[i-1] + A[i-1]
cnt = 0
dict1 = {}
        
dict1[0] = 1

for j in range(1,N+1):
    if j-K >= 0:
        dict1[(S[j-K]-j+K)%K] -= 1
    if (S[j]-j)%K in dict1:
        cnt += dict1[(S[j]-j)%K]
        dict1[(S[j]-j)%K] += 1
    else:
        dict1[(S[j]-j)%K] = 1
print (cnt)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

row = []
col = []
for u, v in uv:
    for i in range(3):
        uu = u + i * n
        vv = v + ((i + 1) % 3) * n
        row.append(uu)
        col.append(vv)

cost = [1] * len(row)
N = 3 * (n + 1)

g = csr_matrix((cost, (row, col)), shape=(N, N))
dist = dijkstra(g, indices=s).astype(int)
ans = dist[t]
if ans < 0:
    ans = -1
else:
    ans //= 3
print(ans)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

adj = [[] for _ in range(3 * n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v + n)
    adj[u + n].append(v + 2 * n)
    adj[u + 2 * n].append(v)


def bfs(s):
    q = deque([s])
    d = [-1] * (3 * n)
    d[s] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                q.append(v)

    return d


dist = bfs(s - 1)
ans = dist[t - 1]
print(ans // 3)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
l = sorted(map(int, input().split()))
ans = 0
for i1 in range(n - 2):
    for i2 in range(i1 + 1, n - 1):
        a = l[i1]
        b = l[i2]
        i3s = max(bisect_right(l, b - a), i2 + 1)
        i3e = bisect_left(l, a + b)
        ans += i3e - i3s
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
l = sorted(map(int, input().split()))
ans = 0
for i1 in range(n - 2):
    for i2 in range(i1 + 1, n - 1):
        a = l[i1]
        b = l[i2]
        i3s = max(bisect_right(l, b - a), i2 + 1)
        i3e = bisect_left(l, a + b)
        ans += i3e - i3s
print(ans)
### BUGGY CODE ###

x = int(input())
a = 1
b = 0
A = []

while True:
    if a ** 5 - 10 ** 9 > 0:
        A.append(a ** 5 - 10 ** 9)
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)

### FIXED CODE ###

x = int(input())
a = 2
b = 0
A = []
A.append(1 ** 5 - x)

while True:
    if (a + 1) ** 5 - a ** 5 > 10 ** 10:
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)
### BUGGY CODE ###


N=int(input())
X=input()
Zero="0"*N

H=X.count("1")
Z=int(X,2)
G=1<<N

A=[]
for i in range(N):
    G>>=1
    
    if X[i]=="0":
        J=H+1
    else:
        J=H-1
        
    Y=Z^G

    if Y==0:
        A.append(0)
        continue
    
    I=1
    Y=Y%J
    
    while Y!=0:
        Y=Y%bin(Y).count("1")
        I+=1
    A.append(I)

print("\n".join(map(str,A)))


### FIXED CODE ###

N=int(input())
X=input()
Y=int(X,2)

J=X.count("1")

A=[0]*N
A[-1]=1
for i in range(2,N+1):
    A[-i]=(A[-(i-1)]*2)%(J+1)

B=[0]*N
if J>1:
    B[-1]=1
    for j in range(2,N+1):
        B[-j]=(B[-(j-1)]*2)%(J-1)


H=[0]*N

Q,R=divmod(Y,J+1)
if J>1:
    S,T=divmod(Y,J-1)
else:
    S=T=0

for i in range(N):
    if X[i]=="0":
        U=(R+A[i])%(J+1)
    else:
        if J==1:
            continue
        U=(T-B[i])%(J-1)
        
        
    I=1
    while U>0:
        U=U%bin(U).count("1")
        I+=1
    H[i]=I

print("\n".join(map(str,H)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb % MOD, tw % MOD
    return sum(dp(0)) % MOD


print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0)) % (10 ** 9 + 7)


print(main())
### BUGGY CODE ###

from collections import deque

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

cost = [[float("inf")] * w for _ in range(h)]

if s[0][0] == "#":
    cost[0][0] = 1
else:
    cost[0][0] = 0

q = deque([[0, 0]])
moves = [[1, 0], [0, 1]]

while q:
    curr = q.popleft()
    curr_cost = cost[curr[0]][curr[1]]

    for m in moves:
        if curr[0] + m[0] < h and curr[1] + m[1] < w:
            if s[curr[0] + m[0]][curr[1] + m[1]] == "#":
                cost[curr[0] + m[0]][curr[1] + m[1]] = min(curr_cost + 1, cost[curr[0] + m[0]][curr[1] + m[1]])
            else:
                cost[curr[0] + m[0]][curr[1] + m[1]] = min(curr_cost, cost[curr[0] + m[0]][curr[1] + m[1]])
            q.append([curr[0] + m[0], curr[1] + m[1]])
        else:
            continue

print(cost[-1][-1])

### FIXED CODE ###

from collections import deque

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

dp = [[10001] * w for _ in range(h)]

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

moves = [[1, 0], [0, 1]]

for y in range(h):
    for x in range(w):
        for m in moves:
            ny, nx = y + m[0], x + m[1]
            if ny >= h or nx >= w:
                continue
            add = 0
            # .から#に突入する時だけカウントが増える
            if s[y][x] == "." and s[ny][nx] == "#":
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[y][x] + add)

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

def main():  
  import sys
  input = sys.stdin.readline
  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  ab = [x+y for x,y in zip(chk_0,chk_1)]
  ab = tuple(ab)
  chk_1 = tuple(chk_1)
  #print(chk_0,chk_1,ab)
  ans = 0
  for i in range(len(chk_0)-k+1):
    chk = sum(ab[i:i+k])
    if i >= 1:
      chk += chk_1[i-1]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  import numpy as np

  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  chk_1 = tuple(chk_1)
  chk_0 = tuple(chk_0)
  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)
  ab = tuple(ab)
  #print(ab)
  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if x+y+z == s:
                if x == y and y == z:
                    count += 1
                elif x == y or y == z or x == z:
                    count += 3
                else:
                    count += 6
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
seen_list = []
n = 1
ans = 0
while True:
    if n in seen_list:
        print(-1)
        exit()
    else:
        if n == 2:
            print(ans)
            exit()
        else:
            seen_list.append(n)
            n = a[n - 1]
            ans += 1


### FIXED CODE ###

from collections import defaultdict

N = int(input())
a = [int(input()) for _ in range(N)]
seen_list = defaultdict(int)
n = 1
ans = 0
while True:
    if seen_list[n] == 1:
        print(-1)
        exit()
    else:
        if n == 2:
            print(ans)
            exit()
        else:
            seen_list[n] = 1
            n = a[n - 1]
            ans += 1
### BUGGY CODE ###

import math
class SegmentTree():
    def __init__(self, list):
        n = len(list)
        self.depth = math.ceil(math.log(n,2))
        num = 2**self.depth
        self.num = num
        self.seg = [0] * (num*2-1)
       
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = 2**(ord(x)-97)
        while k > 0:
            k = (k-1)//2
            self.seg[k] = self.seg[2*k+1]|self.seg[2*k+2]
    
    def query(self, l, r):
        l += self.num-1
        r += self.num-1
        res = self.seg[l]|self.seg[r]
        while r - l > 1:
            if l&1 == 1:
                res = res|self.seg[l+1]
            if r&1 == 0:
                res = res|self.seg[r-1]
            r = (r-1)//2
            l = (l-1)//2
        return bin(res).count('1')
    
N = int(input())
S = input()
s = SegmentTree(list(S))
for i in range(N):
    s.update(i, S[i])
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        i = int(q[1]) - 1
        s.update(i, q[2])
    else:
        l, r = int(q[1])-1, int(q[2])-1
        print(s.query(l,r))

### FIXED CODE ###

class SegmentTree():
    def segfunc(self, x, y):
        return x|y #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, s):
        x = 1<<(ord(s)-97)
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
    

N = int(input())
S = list(input())
for i in range(N):
    S[i] = 1<<(ord(S[i])-97)
Seg = SegmentTree(S)
Q = int(input())
for i in range(Q):
    x, y, z = input().split()
    if int(x) == 1:
        Seg.update(int(y)-1, z)
    else:
        print(popcount(Seg.query(int(y)-1, int(z))))
### BUGGY CODE ###

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

def main(i):
  a = A.count(i)
  print(a)


for i in range(1,n+1):
  main(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int,input().split()))

mycounter = Counter(A)

for i in range(1,n+1):
  print(mycounter[i])