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

X, K, D = map(int, input().split())
X=abs(X)
if X==0 and K%2==0:
    ans=0
elif X==0 and K%2==1:
    ans=D
elif D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif X>0 and D<X and K*D<X:
    ans=X-K*D
else:
    ans=X
    for i in range(0,K):
        ans=ans-D
        if ans<0 and (K-i)%2==0:
            ans=ans+D
            break
        elif ans<0 and (K-i)%2==1:
            ans=-ans
            break
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)
### BUGGY CODE ###

N=int(input())
li=[]

for n in range(N):
  a=int(input())
  li.append(a)

check=[]
s=0
count=0

while s!=1:
  if s in check:
    break
  else:
    check.append(s)
    s=li[s]-1
    count+=1

if s==1:
  print(count)
else:
  print(-1)

### FIXED CODE ###

N=int(input())
li=[]

for n in range(N):
  a=int(input())
  li.append(a)

s=0
count=0

while s!=1:
  if count==N:
    break
  else:
    s=li[s]-1
    count+=1

if s==1:
  print(count)
else:
  print(-1)
### BUGGY CODE ###

def sigma(n):
    return (n+1) * n//2 if n % 2 == 0 else sigma(n-1)+n

n = int(input())
Ss = [sorted(input()) for _ in range(n)]
Ss.sort()
src = []
ans = 0
for i in range(n):
    if(src == Ss[i]):
        continue
    else:
        src = [] 
    if not src:
        ans += sigma(Ss.count(Ss[i])-1)
        src = Ss[i]
print(ans)

### FIXED CODE ###

n = int(input())
S = ["".join(sorted(input())) for _ in range(n)]
ans = 0
dict = {}
for s in S:
    tmp = dict.get(s, 0)
    ans += tmp
    dict[s] = tmp + 1
print(ans)
### BUGGY CODE ###

N, K=map(int, input().split())
Pn=list(map(int, input().split()))
V = [0] * N
for n in range(N):
    for p in range(1, Pn[n]+1):
        V[n] += p/Pn[n]
ans = 0
for n in range(N):
    ans = max(ans, sum(V[n:n+K]))
print(ans)

### FIXED CODE ###

N, K=map(int, input().split())
Pn=list(map(int, input().split()))
V = [0] * N
ans = [0] * K
max_v = 0
sum_v = 0
for n in range(N):
    V[n] = (0.5*Pn[n]*(Pn[n]+1))/Pn[n]
    if n < K:
        sum_v += V[n]
        max_v = sum_v
    else:
        sum_v = sum_v - V[n-K] + V[n]
        max_v = max(max_v, sum_v)
print(max_v)
### BUGGY CODE ###

S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

for i in reversed(range(N)):
    for j in reversed(range(4)):
        if j == 3:
            m = 3 if S[i] == '?' else 1
            dp[i][j] = m * dp[i + 1][j] % MOD
        else:
            m1 = 3 if S[i] == '?' else 1
            m2 = 1 if S[i] == '?' or S[i] == 'ABC'[j] else 0
            dp[i][j] = m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1] % MOD
            
print(dp[0][0] % MOD)


### FIXED CODE ###

S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

for i in reversed(range(N)):
    m = 3 if S[i] == '?' else 1
    for j in reversed(range(3)):
        dp[i][j] = m * dp[i + 1][j]
        if S[i] == '?' or S[i] == 'ABC'[j]:
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= MOD
    
    # j == 3
    dp[i][3] = m * dp[i + 1][3] % MOD
            
print(dp[0][0] % MOD)
### BUGGY CODE ###

H, W=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]

G=[[[0]*(80*162) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
sumi=[[0]*W for i in range(H)]
  
from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  owari=(i+j+1)*80+1
  if i<H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i>=H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i<H-1 and j>=W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    
q=deque()
q.append([0, 0])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)

### FIXED CODE ###

H, W=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]

G=[[[0]*(80*162) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
sumi=[[0]*W for i in range(H)]
  
from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  owari=(i+j+1)*80+1
  if i<H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i>=H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i<H-1 and j>=W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    
q=deque()
q.append([0, 0])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)
### BUGGY CODE ###

A, B, C, X, Y = map(int, input().split())

min_sum = 9999999999
for a in range(X+1):
    for b in range(Y+1):
        c = max(X-a, Y-b)
        sum = A*a + B*b + 2*C*c
        if sum<min_sum:
            min_sum=sum
print(min_sum)

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())

res = a*x + b*y # 条件を満たす買い方のうちABピザの枚数(*2)を全探索する。ABピザを一切買わない場合を一旦答えにする（これを大きい値にして、for ループを0からにしてもよい）
for i in range(1, max(x, y)+1): # 全部ABピザでまかなう時は x,yの内多い方分買うことになる
    ab = i*2 # ABピザを買う枚数奇数枚買うことはないので2倍
    cand = ab*c + a*max(0, x-i) + b*max(0, y-i) # i枚分はABピザになるので-i 負の値にはならない（あまりになる）ので0とのmaxをとる

    res = min(res, cand) # 候補との最小値を保持

print(res)
### BUGGY CODE ###

N = int(input())
ints = [int(x) for x in input().split()]

bitarrays = []
for i in ints:
    bitarrays.append([int(x) == 1 for x in reversed(bin(i)[2:])])

ans = 0

for i in range(N):
    total_barr = bitarrays[i]
    for j in range(i + 1, N):
        barr = bitarrays[j]
        for ind in range(max(len(total_barr), len(barr))):
            exit = False
            b1 = total_barr[ind] if len(total_barr) > ind else False
            b2 = barr[ind] if len(barr) > ind else False
            if b1 and b2:
                exit = True
                break
            else:
                if len(total_barr) <= ind:
                    total_barr.append(b1 or b2)
                else:
                    total_barr[ind] = b1 or b2
        if exit:
            break
        else:
            ans += 1

print(ans + N)


### FIXED CODE ###

N = int(input())
ints = [int(x) for x in input().split()]

ans = 0
r = 0
s = 0
xs = 0
for l in range(N):
    while r < N and s + ints[r] == xs ^ ints[r]:
        s += ints[r]
        xs ^= ints[r]
        r += 1
    ans += (r - l)
    s -= ints[l]
    xs ^= ints[l]

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

import itertools
import sys
from typing import Callable, NoReturn, Tuple


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline
    n, k = map(int, readline().rstrip().split())  # type: int,...
    p: Tuple[int] = tuple(int(_) for _ in readline().rstrip().split())

    answer: int = 10 ** 6
    for combinations in itertools.combinations(p, k):
        sum_of_comb: int = sum(combinations)
        if sum_of_comb < answer:
            answer = sum_of_comb

    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys
from typing import Callable, List, NoReturn


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline
    n, k = map(int, readline().rstrip().split())  # type: int,...
    p: List[int] = [int(_) for _ in readline().rstrip().split()]
    p.sort()
    print(sum(p[:k]))


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

N = int(input())
from collections import Counter
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
h = []
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    heappush(h,(-ca[i]-cb[i])*mod+i)
lis = [[] for _ in range(N+1)]
while len(h):
  cntn = heappop(h)
  cnt2n2 = heappop(h)
  cnt,n = divmod(cntn,mod)
  cnt2,n2 = divmod(cnt2n2,mod)
  if ca[n]>0:
    ca[n] -= 1
    cntn += mod
    lists = []
    while cb[n2]==0:
      lists.append(cnt2n2)
      cnt2n2 = heappop(h)
      cnt2,n2 = divmod(cnt2n2,mod)
    for cnt3n3 in lists:
      heappush(h,cnt3n3)
    cb[n2] -= 1
    cnt2n2 += mod
    lis[n].append(n2)
    if cntn<0:
      heappush(h,cntn)
    if cnt2n2<0:
      heappush(h,cnt2n2)
  else:
    cb[n] -= 1
    cntn += mod
    lists = []
    while ca[n2]==0:
      lists.append(cnt2n2)
      cnt2n2 = heappop(h)
      cnt2,n2 = divmod(cnt2n2,mod)
    for cnt3n3 in lists:
      heappush(h,cnt3n3)
    ca[n2] -= 1
    cnt2n2 += mod
    lis[n2].append(n)
    if cntn<0:
      heappush(h,cntn)
    if cnt2n2<0:
      heappush(h,cnt2n2)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)


### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

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

t_list = [[0] * (n + 1) for i in range(n + 1)]
c_list = [[0] * (n + 1) for i in range(n + 1)]

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    t_list[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        c_list[i][j] = t_list[i][j] + c_list[i][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    ans = 0
    for j in range(l, r + 1):
        ans += c_list[j][r] - c_list[j][l - 1]
    print(ans)

### FIXED CODE ###

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

t_list = [[0] * (n + 1) for i in range(n + 1)]
c_list = [[0] * (n + 1) for i in range(n + 1)]

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    t_list[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        c_list[i][j] = t_list[i][j] + c_list[i][j - 1] + c_list[i - 1][j] - c_list[i - 1][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    print(c_list[r][r] - c_list[l - 1][r] - c_list[r][l - 1] + c_list[l - 1][l - 1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
x=0
b_brick=0
for i in range(N):
    try:
        x+=A[x:].index(i+1)
        b_brick+=1
    except:
        break
if b_brick<=0:
    print(-1)
else:
    print(N-b_brick)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
x=1
for a in A:
    if a==x:
        x+=1
    else:
        pass
if x==1:
    print(-1)
else:
    print(N-x+1)
### BUGGY CODE ###

n = int(input())

d = list(map(int,input().split()))
ans = 0
k_m = max(d)

for i in range(1, k_m+1):
    abc = []
    arc = []
    arc = [j for j in d if j >= i]  
    abc = [k for k in d if k < i]
    if len(arc) == len(abc):
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())

d = sorted(list(map(int,input().split())))

print(d[n//2] - d[n//2-1])
### BUGGY CODE ###

d, g = list(map(int, input().split()))
ps, cs = [], []
for i in range(d):
	p, c = list(map(int, input().split()))
	ps.append(p)
	cs.append(c)

def solve(sum_score, cnt, i, ans):
	if sum_score >= g:
		return min(ans, cnt)
	elif i < d:
		for j in range(ps[i]):
			ans = solve(sum_score + 100 * (i + 1) * j, cnt + j, i + 1, ans)
		ans = solve(sum_score + 100 * (i + 1) * ps[i] + cs[i], cnt + ps[i], i + 1, ans)
	return ans

print(solve(0, 0, 0, 10 ** 10))


### FIXED CODE ###

import itertools

def main():
	d, g = list(map(int, input().split()))
	problems = [list(map(int, input().split())) for _ in range(d)]

	ptns = list(itertools.product([0, 1], repeat = d))

	ans = 10 ** 10

	for pt in ptns:
		rest = g - sum([((i + 1) * 100 * problems[i][0] + problems[i][1]) * pt[i] for i in range(d)])
		tmp = sum([problems[i][0] * pt[i] for i in range(d)])
		
		if rest > 0:
			if 0 in pt:
				rest_max_idx = d - pt[::-1].index(0) - 1
				#print(pt, tmp, rest_max_idx, rest)
				for i in range(problems[rest_max_idx][0]):
					rest -= (rest_max_idx + 1) * 100
					tmp += 1
					if rest <= 0:
						break

		if rest <= 0:
			ans = min(ans, tmp)

	print(ans)


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

n,p=map(int,input().split())
s=input()
if p==2:
  ans=0
  for i in range(n):
    if int(s[i])%2==0:
      ans=ans+i+1
  print(ans)
elif p==5:
  ans=0
  for i in range(n):
    if int(s[i])%5==0:
      ans=ans+i+1
  print(ans)
else:
  G=[[0]*p for i in range(2)]
  G[0]=[i for i in range(p)]
  for i in range(p):
    G[1][i]=G[0][i]*10%p
  R=[[0]*p for i in range(3)]
  a=0
  b=1
  c=2
  for i in range(n):
    x=int(s[i])
    for j in range(p):
      y=(G[1][j]+x)%p
      R[a][y]=R[c][j]+R[c][y]-R[b][j]
    R[a][x%p]+=1
    a=b
    b=c
    c=(c+1)%3
  print(R[c][0])

### FIXED CODE ###

n,p=map(int,input().split())
s=input()
if p==2:
  ans=0
  for i in range(n):
    if int(s[i])%2==0:
      ans=ans+i+1
  print(ans)
elif p==5:
  ans=0
  for i in range(n):
    if int(s[i])%5==0:
      ans=ans+i+1
  print(ans)
else:
  R=[0]*p
  x=0
  y=1
  for i in range(n-1,-1,-1):
    a=int(s[i])
    b=(a*y+x)%p
    R[b]=R[b]+1
    y=y*10%p
    x=b
  ans=R[0]*(R[0]+1)//2
  for i in range(1,p):
    ans=ans+(R[i]*(R[i]-1))//2
  print(ans)
### BUGGY CODE ###

r,c,k = map(int,input().split())
t = [[0 for i in range(c)] for i in range(r)]
for i in range(k):
    a,b,z = map(int,input().split())
    t[a-1][b-1] = z
dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = t[0][0]
dp[2][0][0] = t[0][0]
dp[3][0][0] = t[0][0]
for i in range(r-1):
    dp[0][i+1][0] = dp[1][i][0]
    for j in range(1,4):
        dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
for i in range(c-1):
    dp[0][0][i+1] = 0
    for j in range(1,4):
        dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
    for j in range(2,4):
        dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
    dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
for i in range(r-1):
    for j in range(c-1):
        for s in range(0,4):
            dp[s][i+1][j+1] =  max(dp[0][i+1][j],dp[3][i][j+1])
        for s in range(1,4):
            dp[s][i+1][j+1] = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
        for s in range(2,4):
            dp[s][i+1][j+1] = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
        dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
print(dp[3][r-1][c-1])

### FIXED CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

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

n = int(input())

for i in range(n):
    cnt = 0
    for x in range(1,int(n**0.5)):
        for y in range(1,int(n**0.5)):
            for z in range(1,int(n**0.5)):
                a = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if a == i+1:
                    cnt += 1
    print(cnt)


### FIXED CODE ###

n = int(input())
ans = [0] * n

for x in range(1,int(n**0.5)):
    for y in range(1,int(n**0.5)):
        for z in range(1,int(n**0.5)):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a <= n:
                ans[a-1] += 1
[print(x) for x in ans]
### BUGGY CODE ###

from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(n):
    al[ord(s[i])-ord("a")].append(i)

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

### FIXED CODE ###

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

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

L, R = map(int, input().split())
ans = 2018
for i in range(L, R):
    for j in range(L+1, R+1):
        if ans > (i*j) % 2019:
            ans = (i*j) % 2019
    if ans == 0:
        break
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())
R = min(R, L+4038)
ans = 2018
for i in range(L, R):
    for j in range(L+1, R+1):
        ans = min((i*j) % 2019, ans)
print(ans)
### BUGGY CODE ###

N,K=(int(i) for i in input().split())
h=[int(input()) for i in range(N)]
h.sort()
m = max(h[0:K]) - min(h[0:K])
for i in range(N-K+1):
    d = max(h[i:i+K]) - min(h[i:i+K])
    if m>d:
        m = d
print(m)

### FIXED CODE ###

N,K=(int(i) for i in input().split())
h=[int(input()) for i in range(N)]
h.sort()
m = h[K-1] - h[0] 
for i in range(N-K+1):
    d = h[i+K-1] -h[i]
    if m>d:
        m = d
print(m)
### BUGGY CODE ###

import sys
def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))


N, K = IL()
h_i = IL()
dp = [sys.maxsize for _ in range(N)]
dp[0] = 0
for i in range(N):
	for j in range(1, K+1):
		if i+j < N:
			dp[i+j] = min(dp[i+j], abs(h_i[i] - h_i[i+j]) + dp[i])
	
print(dp[-1])

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
inf = 10**9
s = list()
for i in range(H):
  s.append(input())

dist = [[inf]*W for i in range(H)]
q = deque()
dist[si][sj] = 0
q.append([si,sj])

while len(q) > 0:
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  if dist[i][j] != d:
    continue
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
  
  for ei in range(-2,3,1):
    for ej in range(-2,3,1):
      ni = i+ei
      nj = j+ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "#":
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d + 1
      q.append([ni,nj])
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)


### FIXED CODE ###

from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
inf = 10**9
s = list()
for i in range(H):
  s.append(input())

dist = [[inf]*W for i in range(H)]
q = deque()
dist[si][sj] = 0
q.append([si,sj])

while len(q) > 0:
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  if dist[i][j] != d:
    continue
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
  
  for ei in range(-2,3,1):
    for ej in range(-2,3,1):
      ni = i+ei
      nj = j+ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "#":
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d + 1
      q.append([ni,nj])
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)