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

data_num = int(input())
price = list([0 for i in range(data_num)])
cnt = 0
deff_price = -999999999
tmp_price = 0
for i in range(data_num):
    price[i] = int(input())

for i in range(data_num-1):
    tmp_price = max(price[i+1:])-price[i]
    if tmp_price>deff_price:
            deff_price = tmp_price

print(str(deff_price))

### FIXED CODE ###

data_num = int(input())
cnt = 0
deff_price = -999999999
min_price = 0
tmp_price = 0

for i in range(data_num):
    price = int(input())
 
    if i ==0:
        min_price = price
    elif price - min_price > deff_price:
        deff_price = price - min_price
    
    if price < min_price:
        min_price = price

print(str(deff_price))
### BUGGY CODE ###

import math
import copy

neko = 0
n = int(input())
p = [int(x) for x in input().split()]
for i in range(n):
    if p[i] <= min(p[:i+1]):
        neko += 1
print(neko)

### FIXED CODE ###

import math
import copy

neko = 0
low = 10**6
n = int(input())
p = [int(x) for x in input().split()]
for i in range(n):
    if p[i]<low:
        neko += 1
    if p[i]<low:
        low = p[i]
print(neko)
### BUGGY CODE ###

N = int(input())
treedic = {}
for i in range(1, N+1):
    treedic[i] = {}
for i in range(N-1):
    a, b, c = map(int, input().split())
    treedic[a][b] = c
    treedic[b][a] = c

Q, K = map(int, input().split())
checked = set([K])
length = [0]*(N+1)
check = set([K])

while len(checked) < N:
    nextcheck = set()
    for i in check:
        for j in treedic[i].keys():
            if j not in checked:
                length[j] = length[i] + treedic[i][j]
                checked.add(j)
                nextcheck.add(j)
    check = nextcheck

for i in range(Q):
    x, y = map(int, input().split())
    print(length[x] + length[y])


### FIXED CODE ###

def main():
    N = int(input())
    treedic = {}
    for i in range(1, N+1):
        treedic[i] = {}
    for i in range(N-1):
        a, b, c = map(int, input().split())
        treedic[a][b] = c
        treedic[b][a] = c

    Q, K = map(int, input().split())
    checked = set([K])
    length = [0]*(N+1)
    check = set([K])

    while len(checked) < N:
        nextcheck = set()
        for i in check:
            for j in treedic[i].keys():
                if j not in checked:
                    length[j] = length[i] + treedic[i][j]
                    checked.add(j)
                    nextcheck.add(j)
        check = nextcheck

    for i in range(Q):
        x, y = map(int, input().split())
        print(length[x] + length[y])


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

# -*- coding: utf-8 -*-

def main(N,A):
    zenbu = sum(A)
    ans = float("INF")
    for i in range(1,N):
        part_sum = 0
        part_sum = sum(A[:i])
        ans = min(ans, abs(zenbu-2*part_sum))
    print(ans)
    
if __name__ == '__main__':
    N = int(input())
    A = [int(a) for a in input().split()]
    main(N,A)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main(N,A):
    zenbu = sum(A)
    part_sum = [A[0]]
    ans = float("INF")
    for i in range(1,N): 
        ans = min(ans, abs(zenbu-2*part_sum[-1]))
        part_sum.append(part_sum[-1]+A[i])

    print(ans)
    
if __name__ == '__main__':
    N = int(input())
    A = [int(a) for a in input().split()]
    main(N,A)
### BUGGY CODE ###

import sys

def is_prime(n):
        if n <= 1:
            return 0
        elif n <= 3:
            return 1
        elif (n % 2 == 0 or n % 3 == 0):
            return 0
        i = 5
        while ((i * i) <= n):
            if (n % i == 0 or n % (i + 2) == 0):
                return 0
            i += 6
        return 1

def count_prime(x):
    temp = 0
    if(x > 2):
        temp += 1
    for i in range(3,x+1,2):
        if(is_prime(i) == 1):
            temp += 1
    return temp

l = []
for input in sys.stdin:
    l.append(input)
print l
for input in l:
    print count_prime(int(input))


### FIXED CODE ###

import sys

def is_prime(x):
    if(x <= 3 and x > 1):
        return 1
    elif(x == 5):
        return 1
    elif(x % 2 == 0 or x < 2):
        return 0
    a = 3
    while(a * a <= x):
        if(x % a == 0):
            return 0
        a += 2
    return 1

def generate_prime(x):
    list = []
    list.append(2)
    for i in range(3,x+1,2):
        if(is_prime(i) == 1):
            list.append(i)
    return list

def count_list(x,list):
    count = 0
    for i in range(0,len(list)):
        if(list[i] > x):
            break
        elif(list[i] <= x):
            count += 1
    return count

l = []
for input in sys.stdin:
    l.append(int(input))

prime = generate_prime(max(l))
for i in range(0,len(l)):
    print count_list(l[i],prime)
### BUGGY CODE ###

n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
q=int(input())
st=[list(map(int,input().split())) for i in range(q)]
inf=float("inf")
dp=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    dp[i][i]=0
for u in abc:
    a,b,c=u
    dp[a][b]=c
    dp[b][a]=c
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
data=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if dp[i][j]<=l:
            data[i][j]=1
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            data[i][j]=min(data[i][j],data[i][k]+data[k][j])
for u in st:
    s,t=u
    if data[s][t]!=inf:
        print(data[s][t]-1)
    else:
        print(-1)

### FIXED CODE ###

def warshal(d):
    n=len(d)
    for k in range(1,n):
        for i in range(1,n):
            for j in range(1,n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
q=int(input())
st=[list(map(int,input().split())) for i in range(q)]
inf=float("inf")
dp=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    dp[i][i]=0
for u in abc:
    a,b,c=u
    dp[a][b]=c
    dp[b][a]=c
dp=warshal(dp)
data=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if 0<dp[i][j]<=l:
            data[i][j]=1
        elif dp[i][j]==0:
            data[i][j]=0
data=warshal(data)
for u in st:
    s,t=u
    if data[s][t]!=inf:
        print(data[s][t]-1)
    else:
        print(-1)
### BUGGY CODE ###

def main():
    s = input()
    mod = 2019

    R = [0] * mod
    R[0] += 1
    for i in range(len(s)):
        R[int(s[-i - 1:]) % mod] += 1

    print(sum([r * (r - 1) // 2 for r in R]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    mod = 2019

    n = 0
    R = [0] * mod
    R[0] += 1
    for i in range(len(s)):
        n += int(s[-i - 1]) * pow(10, i, mod)
        R[n % mod] += 1

    print(sum([r * (r - 1) // 2 for r in R]))


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

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i, j, 0))

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1] and A[i][j-1] == '.':
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1] and A[i][j+1] == '.':
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W] and A[i-1][j] == '.':
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W] and A[i+1][j] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

def solve():
    R,G,B,N=map(int,input().split())
    ans=0
    for i in range(N+1):
        for j in range(N+1):
            if (N-(R*i+G*j))%B==0 and N-(R*i+G*j) >=0:
                ans+=1
    print(ans)

solve()

### FIXED CODE ###

def solve():
    R,G,B,N=map(int,input().split())
    ans=0
    for i in range(N+1):
        for j in range(N+1):
            tmp=N-(R*i+G*j)
            if tmp>=0 and tmp%B==0:
                ans+=1
    print(ans)

solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Aug  8 14:35:24 2018

@author: sugawara
"""

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    #N = 6
    #A = [-679, -2409, -3258, 3095, -3291, -4462]
    # iからi+1への移動距離
    delta_A = [abs(A[0])] + [abs(A[i] - A[i-1]) for i in range(1, N)]
    
    #i番目を抜かしたときの
    delta_A_1skip = [abs(A[1])] + [abs(A[i+1] - A[i-1]) for i in range(1, N-1)] + [abs(A[N-2])]
    
    res = []
    for i in range(N):
        # i番目を抜いた場合を考える
        tmp_delta_A = delta_A[:i] + [delta_A_1skip[i]] + delta_A[i+2:]
        if i != N-1:
            tmp_delta_A.append(abs(A[-1]))
        res.append(sum(tmp_delta_A))
    #    break
        
    for i in range(N):
        print(res[i])
if __name__=='__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Aug  8 14:35:24 2018

@author: sugawara
"""


N = int(input())
A = [int(i) for i in input().split()]
#N = 6
#A = [-679, -2409, -3258, 3095, -3291, -4462]
#N = 3
#A = [3, 5, -1]

# iからi+1への移動距離
delta_A = [abs(A[0])] + [abs(A[i] - A[i-1]) for i in range(1, N)] + [abs(A[-1])]
sum_of_all = sum(delta_A)

A = [0] + A + [0]
res = []
for i in range(N):
    res.append(sum_of_all - abs(A[i+1] - A[i]) - abs(A[i+2] - A[i+1]) + abs(A[i+2] - A[i]))
    
    
for i in range(N):
    print(res[i])
### BUGGY CODE ###

import math

X = int(input())

B = 1
while True:
    B_5 = B**5

    diff = X - B_5
    A = diff**(1 / 5)
    if type(A) != complex and math.floor(A) == A:
        B = -B
        A = int(A)
        break

    diff = X + B_5
    A = diff**(1 / 5)
    if type(A) != complex and math.floor(A) == A:
        A = int(A)
        break

    B += 1

print(A, B)


### FIXED CODE ###

import sys

X = int(input())

# X = 33

for a in range(-118, 120):
    for b in range(-119, 119):
        if a**5 - b**5 == X:
            print(a, b)
            sys.exit(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def rec(v, p, color, graph, memo):
    if memo[v][color] != -1:
        return memo[v][color]
    ret = 1
    for c in graph[v]:
        if c == p:
            continue
        if color == 0:
            ret *= rec(c, v, 0, graph, memo) + rec(c, v, 1, graph, memo)
        else:
            ret *= rec(c, v, 0, graph, memo)
        ret %= mod
    memo[v][color] = ret
    return ret


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        graph[x].append(y)
        graph[y].append(x)
    memo = [[-1, -1] for _ in range(N)]
    print((rec(0, -1, 0, graph, memo) + rec(0, -1, 1, graph, memo)) % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def rec(v, p, color, graph, memo):
    if memo[v][color] != -1:
        return memo[v][color]
    ret = 1
    for c in graph[v]:
        if c == p:
            continue
        if color == 0:
            ret *= rec(c, v, 0, graph, memo) + rec(c, v, 1, graph, memo)
        else:
            ret *= rec(c, v, 0, graph, memo)
        ret %= mod
    memo[v][color] = ret
    return ret


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        graph[x].append(y)
        graph[y].append(x)
    memo = [[-1, -1] for _ in range(N)]
    print((rec(0, -1, 0, graph, memo) + rec(0, -1, 1, graph, memo)) % mod)


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

from collections import Counter
 
n = int(input())
c=list(map(int,input().split()))
 
s = Counter(c)
t = list(s.items())
 
nag = len(t)
x = 0
rt = [0 for i in range(nag)]
 
for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
for f in range(nag):
    rt[f] = x - (t[f][1] -1)
  
for j in range(n):
    for k in range(nag):
        if c[j] == t[k][0]:
            print(rt[k])
            break

### FIXED CODE ###

from collections import Counter

n = int(input())
c = list(map(int,input().split()))
s = Counter(c)
t = list(s.items())
nag = len(t)
x = 0
ans = 0

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
    
for j in range(n):
    ans = x - s[c[j]] + 1 
    print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] + [1000000000] * (N-1)

h = np.array(h)
dp = np.array(dp)

for i in range(N-1):
	for j in range(1, min(K+1, N-i)):
		if dp[i] + abs(h[i+j] - h[i]) < dp[i+j]:
			dp[i+j] = dp[i] + abs(h[i+j] - h[i])			

print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)
#candi = np.array([0] * N)

for i in range(1, N):
	j = max(0, i-K)
	#print()
	#candi[j:i] = dp[j:i] + np.abs(h[i] - h[j:i])
	dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()
	#print('j,i=',j,i)
	#print('dp[j:i]=',dp[j:i])
	#print('np.abs(h[i] - h[j:i]) = ', np.abs(h[i] - h[j:i]) )		
	#print('candi[j:i]=',candi[j:i])
	#dp[i] = candi[j:i].min()
	#print('dp=',dp)
				
print(dp[-1])
### BUGGY CODE ###

N, M = map(int, input().split())
abl = []
for i in range(M):
    abl.append(list(map(int,input().split())))

island = 0
ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1:
        island = i[1]
    if [island,N] in abl:
        ans = 'POSSIBLE'
        print(ans)
        exit()
print(ans)


### FIXED CODE ###

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

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
a=1
for i in range(1,n+1):
    a=a*i
print(a%(10**9+7))


### FIXED CODE ###

n=int(input())

import math
print(math.factorial(n)%(10**9+7))
### BUGGY CODE ###

import math
K=int(input())

n=K**3
ABC=[0]*3
ans=0
for i in range(n):
    for j in range(3):
        ABC[j]=i%K+1
        i//=K
    val=math.gcd(ABC[0],ABC[1])
    val=math.gcd(val,ABC[2])
    ans+=val
print(ans)

### FIXED CODE ###

import math
K=int(input())

ans=0
for i in range(1,K+1):
    ans+=i

for i in range(1,K):
    for j in range(i+1,K+1):
        ans+=math.gcd(i,j)*6

for i in range(1,K-1):
    for j in range(i+1,K):
        for k in range(j+1,K+1):
            val=math.gcd(i,j)
            val=math.gcd(val,k)
            ans+=val*6

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

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

a, b, k = map(int, input().split())

for i in range(a, b+1):
    if i - a < k or b - i < k:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if b - a < 2 * k:
    for i in range(a, b+1):
        print(i)
else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)
### BUGGY CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(["#"] + list(sys.stdin.readline().strip()) + ["#"])
grid.append(["#"] * (W+2))
# print(grid)

q = deque()
for j in range(1, H+1):
    for i in range(1, W+1):
        if grid[j][i] == "#":
            q.append((i, j, 0))

visited = set()
ans = 0
while q:
    x, y, count = q.popleft()
    if (x, y) in visited:
        continue
    visited.add((x, y))
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[y+dy][x+dx] != ".":
            continue
        grid[y+dy][x+dx] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)

### FIXED CODE ###

import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))
field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))

# pprint(field)

q = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            q.append((0, i, j))

while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            # print(y+dy, x+dx, field[y+dy][x+dx])
            if field[y+dy][x+dx] == "#":
                continue
            else:
                field[y+dy][x+dx] = "#"
                q.append((count+1, y+dy, x+dx))

# pprint(field)
print(count)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.dat[i*2] | self.dat[i*2+1]

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = lres | self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                rres = self.dat[r] | rres # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = lres | rres
        return len(res)

N = ir()
S = sr()
seg = SegmentTree(N, default=set())
for i in range(N):
    seg.update(i, set(S[i]))
    
Q = ir()
for _ in range(Q):
    a, b, c = sr().split()
    if a == '1':
        seg.update(int(b)-1, set(c))
    else:
        print(seg.query(int(b)-1, int(c)))

# 03

### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17