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

n = int(input())
s = input()
q = int(input())
for query in range(q):
    x,y,z = list(input().split())
    if x=='1':
        y = int(y)
        s = s[:y-1] + z + s[y:]
    else:
        y,z = int(y), int(z)
        print(len(set(list(s[y-1:z]))))

### FIXED CODE ###

class BIT:
    def __init__(self, n):
        """
            data : BIT木データ
            el : 元配列
        """
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    
    """A1 ~ Aiまでの累積和"""
    def Sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (-i)   #LSB(Least Significant Bit)の獲得:i&(-i)
        return s
    
    """Ai += x"""
    def Add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    """Ai ~ Ajまでの累積和"""
    def Get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.Sum(j) - self.Sum(i)

def ctoi(c):
    return ord(c) - 97

n = int(input())
s = list(input())
q = int(input())

bits = [BIT(n) for _ in range(26)]
ans = []
for i in range(n):
    bits[ctoi(s[i])].Add(i+1, 1)
for _ in range(q):
    line = list(input().split())
    if line[0] == '1':
        idx = int(line[1])
        bits[ctoi(s[idx-1])].Add(idx, -1)
        s[idx-1] = line[2]
        bits[ctoi(line[2])].Add(idx, 1) 
    else:
        l,r = int(line[1]), int(line[2])
        cnt = 0
        for i in range(26):
            if bits[i].Get(l-1,r)!=0:
                cnt += 1
        ans.append(cnt)
for a in ans:
    print(a)
### BUGGY CODE ###

def main():
	A,B,C,D=map(int,input().split())
	mod=998244353
	dp=[[0]*(C-A+1) for _ in range(D-B+1)]
	dp[0][0]=1
	for i in range(1,D-B+1):
		dp[i][0]=dp[i-1][0]*A%mod
	for j in range(1,C-A+1):
		dp[0][j]=dp[0][j-1]*B%mod
	for i in range(1,D-B+1):
		for j in range(1,C-A+1):
			dp[i][j]+=(dp[i-1][j]*(A+j)+dp[i][j-1]*(B+i)-((B+i-1)*(A+j-1))*dp[i-1][j-1]+mod)%mod
	print(dp[-1][-1])

if __name__=='__main__':
	main()

### FIXED CODE ###

A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0]*(C-A+1) for _ in range(D-B+1)]
dp[0][0]=1
for i in range(1,D-B+1):
	dp[i][0]=dp[i-1][0]*A%mod
for j in range(1,C-A+1):
	dp[0][j]=dp[0][j-1]*B%mod
for i in range(1,D-B+1):
	for j in range(1,C-A+1):
		dp[i][j]+=(dp[i-1][j]*(A+j)+dp[i][j-1]*(B+i)-((B+i-1)*(A+j-1))*dp[i-1][j-1]+mod)%mod
print(dp[-1][-1])
### BUGGY CODE ###

from collections import deque
def main():
    n = int(input())
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a-1, b-1])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0]=0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

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

n, c = list(map(int, input().split()))
x, v = [], []
for i in range(n):
    x_, v_ = list(map(int, input().split()))
    x.append(x_)
    v.append(v_)
sushi1 = list((sum(v[:i+1]) - x[i]) for i in range(n))
sushi2 = list((sum(v[n-i:]) - (c - x[n-i])) for i in range(1, n+1))
max1, max2 = [0]*(n+1), [0]*(n+1)
for i in range(n):
    max1[i+1] = max(sushi1[i] - x[i], max1[i])
    max2[i+1] = max(sushi2[i] - (c - x[n-i-1]), max2[i])
sushi1.reverse()
sushi2.reverse()
sushi1.append(0)
sushi2.append(0)
ans = 0 
for i in range(n+1):
    a1 = max1[i] + sushi2[i]
    a2 = max2[i] + sushi1[i]
    ans = max(ans, a1, a2)
print(ans)

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
for i in range(n):
    sum = sum * a[i]

if sum > 10**18:
    print(-1)
else:
    print(sum)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
if 0 in a:
    sum = 0
else:
    for i in a:
        sum = sum * i
        if sum > 10**18:
            sum = -1
            break
print(sum)
### BUGGY CODE ###

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

ave = [(p[i]+1)/2 for i in range(N)]

ans = 0

for i in range(N-K+1):
	ans = max(ans,sum(ave[i:K+i]))
	#print(ave[i:K+i])
print(ans)


### FIXED CODE ###

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

ave = [(p[i]+1)/2 for i in range(N)]

ans = 0
cumlative = []
for i in range(N):
	if i == 0:
		cumlative.append(ave[i])
	else:
		cumlative.append(cumlative[i-1]+ave[i])
	#print(ave[i:K+i])
if N == K:
	ans = cumlative[N-1]
else:
	for i in range(N-K):
		ans = max(cumlative[i+K] - cumlative[i],ans)

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

s=input()
q=int(input())
l = [list(input().split()) for i in range(q)]
c=0
for i in range(q):
  if l[i][0]=="1":
    c+=1
  elif c%2==0 and l[i][1]=="1":
    s=l[i][2]+s
  elif c%2==0:
    s=s+l[i][2]
  elif c%2==1 and l[i][1]=="1":
    s=s+l[i][2]
  else:
    s=l[i][2]+s
if c%2==1:
  s=s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
l = [list(input().split()) for i in range(q)]
c=0
for i in range(q):
  if l[i][0]=="1":
    c+=1
  elif c%2==0 and l[i][1]=="1":
    s.appendleft(l[i][2])
  elif c%2==0:
    s.append(l[i][2])
  elif c%2==1 and l[i][1]=="1":
    s.append(l[i][2])
  else:
    s.appendleft(l[i][2])
s=list(s)
if c%2==1:
  s=s[::-1]
print(*s, sep="")
### BUGGY CODE ###

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

inf = float("inf")
dp = [inf] * N

dp[0] = 0

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

print(dp[N - 1])


### FIXED CODE ###

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

dp=[100000 for i in range(N)]
dp[0]=0

for i,h_now in enumerate(h):
    if i==0:
        continue
    x=max(0,i-K)
    dp[i]=min([dp_i+abs(h_now-h_i) for dp_i,h_i in zip(dp[x:i],h[x:i])])

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

import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, -1)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 10**9+1, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, X, f in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, 1, X)
    L[2 * i + 1] = (T-X, -1, X)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 2, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, f, X in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")
### BUGGY CODE ###

import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i+1], b)
  #print(i,a,b,r)
  if r <= i and A[r] == b:
    if a == A[r]:
      ans += C[a]//2
      C[a] -= C[a]//2*2
    else:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)


### FIXED CODE ###

import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A, b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)
### BUGGY CODE ###

from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.appendleft((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.pop()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.appendleft((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

K, S = map(int, input().split())

count = [1 for x in range(K + 1) for y in range(K + 1)
         for z in range(K + 1) if x + y + z == S]

print(len(count))


### FIXED CODE ###

K, S = map(int, input().split())

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        if 0 <= S - x - y <= K:
            count += 1

print(count)
### BUGGY CODE ###

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

if N >= 24:
    print(0)

else:
    res = 0
    for bit in range(2**N):
        d = [0 for _ in range(24)]
        for i in range(N):
            if (bit >> i) & 1:
                d[D[i]] += 1
            else:
                d[(24 - D[i]) % 24] += 1
        md = 25
        tmp = 0
        for i in range(24):
            if d[i] > 1:
                md = 0
                break
            elif d[i] == 1:
                md = min(md, i - tmp)
                tmp = i
        md = min(24 - tmp, md)
        res = max(res, md)
    print(res)

### FIXED CODE ###

from copy import deepcopy

N = int(input())
D = list(map(int,input().split()))
T = [0 for _ in range(13)]
ans = 0

for i in range(N):
    if D[i]==0:
        print(0)
        break
    T[D[i]] += 1
    if T[D[i]] >=3:
        print(0)
        break
        
else:
    C = [0]
    S = []
    for j in range(13):
        if T[j]==2:
            C.append(j)
            C.append(-j)
        elif T[j]==1:
            S.append(j)

    for j in range(2**len(S)):
        CC = deepcopy(C)
        for k in range(len(S)):
            if ((j >> k) & 1):
                CC.append(S[k])
            else:
                CC.append(-S[k])
                
        mind = 25
        for p in range(N):
            for q in range(p+1,N+1):
                mind = min(mind,min(abs(CC[p]-CC[q]),24-abs(CC[p]-CC[q])))
        ans = max(ans,mind)
        
    print(ans)
### BUGGY CODE ###

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]

  def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

li = [[0]*n for i in range(n)]  
for i in range(n):
  li[uf_rail.find(i)][uf_road.find(i)] +=1

for i in range(n):
  print(li[uf_rail.find(i)][uf_road.find(i)],end=" ")
print()

### FIXED CODE ###

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]

  def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

memo = {}
for i in range(n):
  if str(uf_rail.find(i))+" "+str(uf_road.find(i)) not in memo:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] = 1
  else:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] += 1

for i in range(n):
  print(memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))])
### BUGGY CODE ###

n, k = map(int, input().split())
x = list(map(int, input().split()))

ans = 10 ** 9

for i in range(n-k+1):
    temp = x[i:i+k]
    dif = temp[-1] - temp[0]
    from_s = min(abs(temp[-1]), abs(temp[0]))

    ans = min(dif + from_s, ans)

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
x = list(map(int, input().split()))

ans = 10 ** 9

for i in range(n-k+1):

    l = abs(x[i]) + abs(x[i+k-1] - x[i])
    r = abs(x[i+k-1]) + abs(x[i+k-1] - x[i])

    if l < r:
        ans = min(ans, l)
    else:
        ans = min(ans, r)

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

n,a,b=map(int,input().split())
ncpre=1
MOD=1000000007
ans=0
for i in range(1,n+1):
    nci=ncpre*(n-(i-1))//i
    ncpre=nci
    if(i!=a and i!=b):
        ans = (ans + nci)%MOD
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
MOD  = 1000000007

def comb(N,x):
    numerator = 1
    for i in range(N-x+1,N+1):
        numerator = numerator *i%MOD
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator *j%MOD
    d = pow(denominator,MOD-2,MOD)
    return (numerator*d)%MOD


#実際に使うときは、MOD=10000007 などの剰余計算を組み込んで使うこと！
def repeated_square(x,n):
    #nを2進数で表して順序反転
    bit_n=bin(n)[2:][::-1]

    ans=1
    ni=x

    if(bit_n[0]=="1"):
        ans*=ni

    for i in range(1,len(bit_n)):
        ni=((ni%MOD)*(ni%MOD))%MOD

        #i桁目が1なら、x^(2^i)を加える
        if(bit_n[i]=="1"):
            ans=((ans%MOD)*(ni%MOD))%MOD

    return ans

alln=(repeated_square(2, n)-1)%MOD
print((alln-comb(n, a)-comb(n, b))%MOD)
### BUGGY CODE ###

N=int(input())
s=0
L=[i for i in range(N)]
A=list(map(int,input().split()))
dic1={i:i+a for i,a in zip(L,A)}
dic2={i:i-a for i,a in zip(L,A)}
for p in range(N):
    z=[k for k,v in dic1.items() if v==p ]
    w=[k for k,v in dic2.items() if v==p ]
    s+=len(z)*len(w)
print(s)

### FIXED CODE ###

def count(dic,x):
    if x in dic:
        dic[x]+=1
    else:
        dic[x]=1

N=int(input())
A=list(map(int,input().split()))
dic1={}
dic2={}
s=0
for i in range(N):
    count(dic1,i-A[i])
    count(dic2,i+A[i])
for x in dic1:
    if x in dic2:
        s+=dic1[x]*dic2[x]
print(s)
### BUGGY CODE ###

import collections
import math

#****************************************************************
def comb(n):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
#****************************************************************

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

c = collections.Counter(A)
full_ans = sum(list(map(comb, c.values())))
dict_ans = {}

for i in c.keys():
    target = c.copy()
    target[i] -= 1
    if target[i] == 0:
        dict_ans[i] = full_ans
    else:
        dict_ans[i] = sum(list(map(comb, target.values())))

for i in A:
    print(dict_ans[i])


### FIXED CODE ###

import collections
import math

#****************************************************************
def comb(n):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
#****************************************************************

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

c = collections.Counter(A)
full_ans = sum(list(map(comb, c.values())))

for a in A:
    print(full_ans - c[a] + 1)
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=int(input())
a=sorted(list(map(int,input().split())))
b=a[n-1]
a.pop(n-1)
ans=[0,comb(b,a[0])]
for i in range(n-1):
    #print(a[i])
    if ans[1]<comb(b,a[i]):
        ans=[i,comb(b,a[i])]
print(str(b)+" "+str(a[ans[0]]))


### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

k=int(input())
a=sorted([int(i) for i in input().split()])
ma=a[-1]/2
#print(a)
eps=10**(-7)

m=a[-1]-ma
for i in range(k):
    m=min(abs(a[i]-ma),m)
print(a[-1],end=" ")
for i in range(k):
    if abs(abs(a[i]-ma)-m)<eps:
        print(a[i])
        break
### BUGGY CODE ###

N,X,Y = map(int,input().split())
li = [0]*(N-1)
for i in range(0,N-1):
    for j in range(i+1,N):
        dis = min(j-i,abs(j-(X-1))+1+abs(i-(Y-1)),abs(i-(X-1))+1+abs(j-(Y-1)))
        li[dis-1] += 1
for ans in li:
    print(ans)

### FIXED CODE ###

N,X,Y = map(int,input().split())
li = [0]*(N-1)
for i in range(0,N-1):
    for j in range(i+1,N):
        dis = min(j-i,abs(i-(X-1))+1+abs(j-(Y-1)))
        li[dis-1] += 1
for ans in li:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())

s = inp_str()
t = inp_str()
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = ans[i][j]+s[i]#"".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])


### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  s=set()
  while d:
    x,y=d.popleft()
    if (x,y) in s:
      s.discard((x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      if b[x-i][y]!=0:
        s.add((x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append((x+i,y))
      if b[x+i][y]!=0:
        s.add((x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      if b[x][y-j]!=0:
        s.add((x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0

for i in range(N-1):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        ans += bisect.bisect_left(L, a+b) - bisect.bisect_right(L, max(a,b))

print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

print(ans)