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

N = int(input())
A = [0]
B = list(map(int, input().split()))
A += B
#print(A)

sig = [0] * N

for i in range(N):
  sig[i] = A.count(i+1)

#print(sig)
for i in sig:
  print(i)

### FIXED CODE ###

N = int(input())
A = [0]
B = list(map(int, input().split()))
A += B
#print(A)

sig = [0] * N

for i in range(N-1):
  sig[A[i+1]-1] += 1
#print(sig)

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


import numpy as np
X, Y, A, B, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

A = A[0:X]
B = B[0:Y]
#C = np.array(C)

arr = A+B

flag = 1

while(flag):
  tmp = 0
  _min = min(arr)
  _max = max(C)
  if _min <= _max:
    arr[arr.index(_min)] = _max
  else:
    flag = 0
"""
_min = min(arr)
C = C[C>_min]

for c in C:
  _min = min(arr)
  if c >= _min:
    arr[arr.index(_min)] = c


"""
print(sum(arr))

### FIXED CODE ###

import numpy as np
X, Y, A, B, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

A = A[0:X]
B = B[0:Y]
D = A+B+C

D.sort(reverse=True)

D = D[0:X+Y]
print(sum(D))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())

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

'''
考え方
各リストをソートして、前からk個分のみの要素にする
'''

'''
import math

cnt_num = math.ceil(pow(k, 1/3))

A = sorted(A,reverse=True)[:cnt_num]
B = sorted(B,reverse=True)[:cnt_num]
C = sorted(C,reverse=True)[:cnt_num]
'''
A = sorted(A,reverse=True)[:k]
B = sorted(B,reverse=True)[:k]
C = sorted(C,reverse=True)[:k]


ans_list = []
for a in A:
  for b in B:
    for c in C:
      ans_list.append(a+b+c)

ans_list.sort(reverse=True)
for ans in ans_list[:k]:
  print(ans)

### FIXED CODE ###

x,y,z,k = map(int,input().split())

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

A = sorted(A,reverse=True)[:k]
B = sorted(B,reverse=True)[:k]
C = sorted(C,reverse=True)[:k]

list_ans = []
for index_a,a in enumerate(A):
  for index_b,b in enumerate(B):
    for index_c,c in enumerate(C):
      if (index_a + 1) * (index_b + 1) * (index_c + 1) > k:
        break
      list_ans.append(a+b+c)


list_ans.sort(reverse=True)
for i in list_ans[:k]:
  print(i)
### BUGGY CODE ###

import math

n = int(input())
L = []
dict = {}
ans = 0
for i in range(n):
    s = list(input())
    s.sort()
    s = str(s)
    if s in L:
        if s in dict:
            dict[s] += 1
        else:
            dict[s] = 1
    L.append(s)
for i in dict.values():
    ans += (math.factorial(i + 1) // (math.factorial(2))) // (math.factorial(i - 1))
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
SET = set()
dict = {}
ans = 0
for i in range(n):
    s = list(input())
    s.sort()
    s = str(s)
    if s in SET:
        if s in dict:
            dict[s] += 1
        else:
            dict[s] = 1
    SET.add(s)

for i in dict.values():
    ans += i * (i + 1) // 2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
tmp=0
for i in range(N):
  L=A[i+1:N]
  ##print(L)
  ##print(sum(L))
  ##print(A[i])
  tmp=A[i]*sum(L)+tmp
tmp=tmp%(10**9+7)
print(tmp)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
##print(S)
tmp=0
T=0
for i in range(N-1):
  T=T+A[i]
  ##print(T)
  ##print(A[i])
  tmp=(A[i]*(S-T)+tmp)
tmp=tmp%(10**9+7)
print(tmp)
### BUGGY CODE ###

from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    # 多分正解だけどpythonではTLEする。
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dist[nId] > cost:
                dist[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dist = [inf]*(h*w*4)
        dist[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dist[Id]:
                continue
            
            for nv in range(4):
                nx = x + dx[nv]
                ny = y + dy[nv]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: continue
                if field[nx][ny] == '@': continue
                if v == nv:
                    push(nx, ny, nv, cost+1)
                else:
                    push(nx, ny, nv, modCeil(cost)+ 1)
            
        ans = min([dist[toId(xg, yg, v)] for v in range(4)])
        if ans == inf:
            print(-1)
        else:
            print(modCeil(ans)//k)
        

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    dijkstra()


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split(' '))
h = list(map(int, input().split(' ')))
dp = [float('inf')]*(len(h))
dp[0] = 0
for i in range(1, len(h)):
    dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), 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.zeros(len(h), dtype=int)
for i in range(1, len(h)):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[-1])
### BUGGY CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])
b=[-1,n]
ans=0
for i,j in a:
    c=bisect.bisect(b,i)
    ans+=(i-b[c-1])*(b[c]-i)*j
    bisect.insort(b,i)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

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

def main():
    N=int(input())
    S=input()
    ans=0
    for i in range(N-2):
        for j in range(i+1,N-1):
            lis=["R","G","B"]
            if S[i]!=S[j]:
                lis=["R","G","B"]
                lis.remove(S[i])
                lis.remove(S[j])
                k=S[j+1:].count(lis[0])
                ans=ans+k
            if j+(j-i)<N and S[i]!=S[j]:
                if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                    ans-=1
    print(ans)
main()

### FIXED CODE ###

def main():
    N=int(input())
    S=input()
    k1=S.count("R")
    k2=S.count("B")
    ans=k1*k2*(len(S)-k1-k2)
    for i in range(N-2):
        for j in range(i+1,N-1):
            if j+(j-i)<N and S[i]!=S[j]:
                if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                    ans-=1
    print(ans)
main()
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=1
for i in li:
    ans=ans*i

if ans<=10**18:
    print(ans)
elif 0 in li:
    print(0)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n,*a = map(int,open(0).read().split())
mod = 10**9+7
ans = 0
for i in range(61):
  b = sum(map(lambda x:x>>i&1,a))
  ans += b*(n-b)*1<<i
print(ans%mod)

### FIXED CODE ###

import numpy as np
n,*a = map(int,open(0).read().split())
a = np.array(a)
mod = 10**9+7
ans = 0
for i in range(61):
  b = np.count_nonzero(a>>i&1)
  ans += b*(n-b)*1<<i
print(ans%mod)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
ans=[]
for _ in range(Q):
    l,r=map(int,input().split())
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0,0]
for i in range(2,N+1):
    t.append(t[-1]+(S[i-2:i]=='AC'))
for _ in range(Q):
    l,r=map(int,input().split())
    print(t[r]-t[l])
### BUGGY CODE ###

n,h=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[l[i][0] for i in range(n)]
maxA=max(a)
b=[l[i][1] for i in range(n)]
b.sort()
b.reverse()
damage=0
count=0
f=0
for i in range(n):
  if damage>=h:
    f=1
    break
  else:
    if b[i]>max(a):
      damage+=b[i]
      count+=1
    else:
      break
if f==1:
  print(count)
else:
  count+=((h-damage-1)//maxA)+1
  print(count)

### FIXED CODE ###

n,h=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=set()
for i in range(n):
  a.add(l[i][0])
maxA=max(a)
b=[]
for i in range(n):
  if l[i][1]>maxA:
    b.append(l[i][1])
b.sort()
b.reverse()
damage=0
count=0
f=0
for i in range(len(b)):
  if damage>=h:
    f=1
    break
  else:
    if b[i]>maxA:
      damage+=b[i]
      count+=1
    else:
      break
if f==1:
  print(count)
else:
  count+=((h-damage-1)//maxA)+1
  print(count)
### BUGGY CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M)]
    A[0] = X

    start = N
    end = N

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    # print(A)

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]


    for i in range(L):
        if start == N:
            break
        loop[i] = loop[i-1] + A[start+i]

    # print(straight)
    # print(loop)

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0


    if start != N:
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M+2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M+2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()
### BUGGY CODE ###

import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
N = int(input())
A = np.array(list(map(int, input().split())))
l = 0
r = 0
c = 0

while (l < len(A)):
    x = np.bitwise_xor.reduce(A[l:r])
    s = np.add.reduce(A[l:r])
    while (x == s):
        r += 1
        if (r > len(A)):
            break
        x = np.bitwise_xor.reduce(A[l:r])
        s = np.add.reduce(A[l:r])
    r -= 1
    c += (r - l)
    #print((l,r,r))
    l += 1

print(c)

### FIXED CODE ###

import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
N = int(input())
A = np.array(list(map(int, input().split())))
l = 0
r = 0
c = 0

x = 0
s = 0

while (l < len(A)):
    while (x == s):
        r += 1
        if (r > len(A)):
            break
        x = x ^ A[r-1]
        s += A[r-1]
    if (r <= len(A)):
        x = x ^ A[r-1]
        s -= A[r-1]
    r -= 1
    c += (r - l)
    x = x ^ A[l]
    s -= A[l]
    l += 1

print(c)
### BUGGY CODE ###


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

for i in range(M):
    B, C = list(map(int,input().split()))
    li = [C]*B
    A_li.extend(li)

A_li.sort()
A_li.reverse()
ans = sum(A_li[:N])
    
print(str(ans))

### FIXED CODE ###

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

CB_li.sort()
CB_li.reverse()

counter = 0
for i in range(M):
    li = [CB_li[i][0]]*CB_li[i][1]
    A_li.extend(li)
    counter += CB_li[i][1]
    if counter > N:
        break

A_li.sort()
ans = sum(A_li[-N:])
    
print(str(ans))
### BUGGY CODE ###

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

num = []
cnt = []

for a in A:
    if a not in num:
        num.append(a)
        cnt.append(1)
    else:
        cnt[-1] += 1
cnt.sort()
#print(num,cnt)

res = 0
M = len(cnt)
if M <= K:
    res = 0
else:
    for i in range(M-K):
        res += cnt[i]
print(res)

### FIXED CODE ###

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

num = []
cnt = []

for i in range(N):
    if i == 0:
        num.append(A[i])
        cnt.append(1)
    else:
        if A[i-1] != A[i]:
            num.append(A[i])
            cnt.append(1)
        else:
            cnt[-1] += 1
cnt.sort()
#print(num,cnt)

res = 0
M = len(cnt)
if M <= K:
    res = 0
else:
    for i in range(M-K):
        res += cnt[i]
print(res)
### BUGGY CODE ###

from operator import itemgetter
n,k = map(int,input().split())
li=[]
s=[]
t=[]
g=0
ans=[]
retu=[0]*n
p=0
for _ in range(n):
    a,b=map(int,input().split())
    li.append([a,b])
li=sorted(li,key=itemgetter(1),reverse=True)
for i in range(k):
    g+=li[i][1]
    if retu[li[i][0]-1]==0:
        retu[li[i][0]-1]+=1
        p+=1
    else:
        t.append(li[i][1])
g+=p**2
ans.append(g)
for i in range(k,n):
    if len(t)==0:
        break
    if retu[li[i][0]-1]==0:
        g=g-t[-1]+li[i][1]+2*p+1
        p+=1
        t=t[:-1]
        ans.append(g)
        retu[li[i][0]-1]+=1
print(max(ans))

### FIXED CODE ###

from operator import itemgetter
n,k = map(int,input().split())
li=[]
s=[]
t=[]
g=0
ans=[]
retu=[0]*n
p=0
q=0
for _ in range(n):
    a,b=map(int,input().split())
    li.append([a,b])
li=sorted(li,key=itemgetter(1),reverse=True)
for i in range(k):
    g+=li[i][1]
    if retu[li[i][0]-1]==0:
        retu[li[i][0]-1]+=1
        p+=1
    else:
        t.append(li[i][1])
        q+=1
g+=p**2
ans.append(g)
for i in range(k,n):
    if q==0:
        break
    if retu[li[i][0]-1]==0:
        g=g-t[q-1]+li[i][1]+2*p+1
        p+=1
        q-=1
        ans.append(g)
        retu[li[i][0]-1]+=1
print(max(ans))
### BUGGY CODE ###

N=int(input())
s=[]
for i in range(N):
    s.append(list(input()))
    s[i].sort()
    s[i]="".join(s[i])

sn=[x for x in set(s) if s.count(x) > 1]

c=0
for i in sn:
    n=s.count(i)
    c += (n*(n-1)//2)

print(c)


### FIXED CODE ###

N=int(input())
dic={}
for i in range(N):
    k="".join(sorted(list(input())))
    if k in dic:
        dic[k]+=1
    else:
        dic[k]=1
c=0
for i in dic.values():
    c += i*(i-1)

print(c//2)
### BUGGY CODE ###

N=int(input())
D=sorted(map(int,input().split()))
maximum=max(D)
medium=0
for threshold in range(1,maximum+1):
    count=0
    for d in D:
        if d<threshold:
            count+=1
    if count==len(D)//2:
        medium+=1
print(medium)

### FIXED CODE ###

N=int(input())
d=sorted(map(int,input().split()))
print(d[N//2]-d[N//2-1])
### BUGGY CODE ###

X = int(input())

A = X // 100

for i_100 in range(A + 1):
    for i_101 in range(A + 1):
        for i_102 in range(A + 1):
            for i_103 in range(A + 1):
                for i_104 in range(A + 1):
                    for i_105 in range(A + 1):
                        if i_100 + i_101 + i_102 + i_103 + i_104 + i_105 == A:
                            if i_100 * 100 + i_101 * 101 + i_102 * 102 + i_103 * 103 + i_104 * 104 + i_105 * 105 == X:
                                print("1")
                                exit()

print("0")




### FIXED CODE ###

X = int(input())

A100 = 0
A105 = 0
for i in range(1001):
    A100 += 100
    A105 += 105
    if A100 <= X <= A105:
        print("1")
        exit()

print("0")
### BUGGY CODE ###

n,y = map(int,input().split())
for i in range(0,n+1):
  for j in range(0,n+1):
    for k in range(0,n+1):
      sum_y = 10000*i + 5000*j + 1000*k
      sum_n = i + j + k
      if sum_y == y and sum_n == n:
        print(i, j ,k)
        break
    else:
      continue
    break
  else:
    continue
  break
if sum_y !=y and sum_n:
  print(-1,-1,-1)


### FIXED CODE ###

import itertools
n,y = map(int,input().split())
for i,j in itertools.product(range(0,n+1),range(0,n+1)):
  c = n-i-j
  sum_y = 10000*i + 5000*j + 1000*c
  if sum_y == y and c>=0:     
    print(i,j,c)
    break
else:
  print(-1,-1,-1)
### BUGGY CODE ###

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

dp = [float("inf")]*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], dp[i]+abs(hs[i]-hs[i+j]))
print(dp[-1])

### FIXED CODE ###

INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

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

n = int(input())
ans = 0
for i in range(1,n):
    ans +=i
print(ans)

### FIXED CODE ###

n = int(input())
if n%2:
    p = ((n-1)//2)*n
    print(int(p))
else:
    p = (n//2)*(n-1)
    print(int(p))
### BUGGY CODE ###

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

for i in range(N):
  a.append(a[i]+1)
  a.append(a[i]-1)

ans=[]

for i in range(min(a), max(a)+1):
  ans.append(a.count(i))

print(max(ans))

### FIXED CODE ###

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

d = [0]*(10**5+1)
for i in range(N):
  d[a[i]]+=1

ans=0
for i in range(10**5):
  ans = max(ans, d[i-1]+d[i]+d[i+1])

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

from collections import Counter

N = int(input())

s = [''.join(sorted(str(input()))) for _ in range(N)]
#print(s)
count = 0
for i in range(N):
    for j in range(i+1,N):
        #diff = Counter(s[i])-Counter(s[j])
        diff = s[i].replace(s[j],'')
        if len(diff) == 0:
            count += 1
        
print(count)

### FIXED CODE ###

from collections import Counter
 
n = int(input())
s = [list(input()) for _ in range(n)]
for i in range(n):
    s[i].sort()
    s[i] = ''.join(s[i])
counter = Counter(s)
#print(counter)
ans = 0
for val in counter.values():
    #countC2
    ans += val*(val-1)//2
    
print(ans)