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

from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
sj = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
			sj.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

if len(ans)!=n*(n-1)//2:
	print(-1)
	exit()

mac=0
for edge in sj:
	x=edge[0]
	y=edge[1]
	q=deque([[x,y,1]])
	while(q):
		tmp=q.popleft()
		f1=tmp[0]
		f2=tmp[1]
		c=tmp[2]
		mac=max(c,mac)
		for nn in g[f1][f2]:
			q.append([nn[0],nn[1],c+1])
print(mac)

### FIXED CODE ###

n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
m_load = [[] for i in range(n)]
for j in range(m):
  a,b = map(int,input().split())
  a = a-1
  b = b-1
  m_load[a].append(b)
  m_load[b].append(a)

import heapq

def dijkstra(edges,num_v,start,goal):
      dist = [float("inf")] * num_v
      dist[start] = 0
      q = []
      heapq.heappush(q,[0,[start]])#[0,0]とは1番目に頂点のインデックス、0番目に頂点までのコストを格納する
    
      while len(q) >0:
        #ヒープから取り出し
        _,u = heapq.heappop(q)
        last = u[-1]
        if last == goal:
          return u
        for i in edges[last]:
            if dist[i] > dist[last] + 1:
                #頂点までのコストが更新できれば更新してヒープに登録
                dist[i] = dist[last] + 1
                heapq.heappush(q,[dist[last] + 1,u + [i]])
      return []

result = []
check = True
for i in range(1,n):
  r = dijkstra(m_load,n,i,0)
  if len(r) >= 2:
    
    result.append(r[1] + 1)
  else:
    check = False
if check == False:
  print("No")
else:
  print("Yes")
  for _ in result:
    print(_)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
edge_list = [[] for i in range(n)]
depth_list = [-1 for i in range(n)]
ans_list = [-1 for i in range(n)]
depth_list[0] = 0
ans_list[0] = 0
for m in range(m):
  a,b = map(int,input().split())
  a = a-1
  b = b-1
  edge_list[a].append(b)
  edge_list[b].append(a)
q = deque()
q.append(0)

while len(q) > 0:
  node = q.popleft()
  connects = edge_list[node]
  for c in connects:
    if depth_list[c] == -1:
      depth_list[c] = depth_list[node] + 1
      q.append(c)
      ans_list[c] = node
      
if -1 in ans_list:
  print("No")
else:
  print("Yes")
  for _ in ans_list[1:]:
    print(_ + 1)
### BUGGY CODE ###

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

for i in range(K+1):
  for j in range(S+1-i):
    if 0<=i<=K and 0<=S-i-j<=K and 0<=j<=K:
      ans += 1

print(ans)


### FIXED CODE ###

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

for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j<=K:
      ans += 1
#    print(i, j, S-i-j, ans)
      

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

n = int(input())
l = list(map(int,input().split()))
cnt = 0
for i in range(n-2):
    for j in range(i,n-1):
        for k in range(j,n):
            if i != j != k and l[i] < l[j]+l[k] and l[j] < l[i]+l[k] and l[k] < l[i]+l[j]:
                cnt += 1
                
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
cnt = 0
l.sort()

for i in range(n):
    for j in range(i+1,n):
        k = bisect.bisect_left(l,l[i]+l[j])
        if k > j:
            cnt += k - j - 1
        else:
            pass
            
print(cnt)
### BUGGY CODE ###

import heapq
import sys
input=sys.stdin.readline

N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (START,s,x) )
    querys.append( (GOAL,t,x) )

for _ in range(Q):

    querys.append( (GO,int(input()),-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys = sorted(querys,key = lambda x: (x[1],x[2])  )
for query in querys:
    qtype,time,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    elif qtype == GO:
        while koji_place and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])





### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

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

from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
c = 1
B = [1]
ans = []
append = ans.append
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, readline().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v + (N - 2)) // N
        w = (w + (N - 2)) // N
    append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")


### FIXED CODE ###

from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")
### BUGGY CODE ###

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

C = set([])
for x in range(min(K+1,S+1)):
    for y in range(min(K+1,S-x+1)):
        if 0 <= S-x-y and S-x-y <= K:
            C.add((x,y,S-x-y))

print(len(C))


### FIXED CODE ###

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

count = 0
if S % 3 == 0:
    count += 1
for x in range(K):
    if 0 <= S-2*x and S-2*x <= K and x != S-2*x:
        count += 3
for x in range(K):
    for y in range(x+1,K):
        if y >= S-x-y:
            break
        elif 0 <= S-x-y and S-x-y <= K:
            count += 6

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

import re
s=input()
m=0
for i in range(len(s)//2):
  dst = re.sub(r'01|10', "", s)
  dst = re.sub(r'000000111111', "", dst)
  if dst == s:
    break
  m += len(s) - len(dst)
  s=dst
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY CODE ###

n = int(input())
def fib(n):
    if (n == 0 or n == 1):
        return 1
    else:
        return fib(n-1) + fib(n-2)
print(fib(n))


### FIXED CODE ###

n = int(input())
f = [1,1]
for i in range(n-1):
    fib = f[-1] + f[-2]
    f.append(fib)
print(f[n])
### BUGGY CODE ###

import numpy as np

n, max_weight = map(int, input().split())
WV = np.array([input().split() for _ in range(n)], np.int64)

W, V = zip(*WV)
dp = np.zeros((n + 1, max_weight + 1), np.int64)

# O(NW)
for i in range(n):
    for w in range(1, max_weight + 1):
        if w >= W[i]:
            dp[i + 1, w] = max(dp[i, w], dp[i, w - W[i]] + V[i])
        else:
            dp[i + 1, w] = dp[i, w]

print(dp[n, max_weight])


### FIXED CODE ###

n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
dp = list([0] * (max_weight + 1) for _ in range(n + 1))
for i in range(n):
    for w in range(1, max_weight + 1):
        if w >= W[i]:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - W[i]] + V[i])
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[n][max_weight])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
table = [[None] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    table[r][c] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp[r - 1][c])
        for n in range(4):
            dp[r][c][n] = max(m,
                              dp[r][c - 1][n])
        if table[r][c] is not None:
            for n in range(3):
                dp[r][c][n + 1] = max(dp[r][c][n + 1],
                                      m + table[r][c],
                                      dp[r][c - 1][n] + table[r][c])
print(max(dp[-1][-1]))


### FIXED CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

# coding:utf-8
import math
import fractions

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

if K==0:
    print("N")
elif N==0 or N%K==0:
    print("0")
else:
    a=fractions.gcd(N,K)
    N=N%K
    N=int(N/a)
    K=int(K/a)
    mi=N
    t=N
    for i in range(N):
        t=abs(t-K)
        mi=min(mi,t)
    print(mi*a)

### FIXED CODE ###

# coding:utf-8
import math
import fractions

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

if K==0:
    print("N")
elif N==0 or N%K==0:
    print("0")
else:
    N=N%K
    print(min(N, K-N))
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [val % m for val in d]

        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = sum(_d[:n_rest])
            d0_rest = _d[:n_rest].count(0)

        a_last = x + n_d * sum(_d) + _d_rest
        n_step = a_last // m
        # n_same

        n_same = n_d * _d.count(0) + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
import numpy as np
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))
    d = np.array(d, dtype=np.uint64)

    def check(n ,x, m):
        _d = d % m
        d0 = d % m == 0
        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[:n_rest].sum()
            d0_rest = d0[:n_rest].sum()

        a_last = x + n_d * _d.sum() + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0.sum() + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(int(check(n, x, m)))

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

N=int(input())
A=list(map(int,input().split()))
flg=1
count=0
while(0==0):
    for i in A:
        if i%2!=0:
            flg=0
    if flg==1:
        for i in A:
            i=i%2
        count+=1
    else:
        break
print(count)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            flg=0
            break

    if flg==1:
        for i in range(N):
            A[i]=A[i]//2
        count+=1
    else:
        break
print(count)
### BUGGY CODE ###

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

sum = a[0]
count = 0

if a[0] == 0:
    if a[1] > 0:
        sum -= 1
        count += 1
    elif a[1] < 0:
        sum += 1
        count += 1

for i in range(1, n):
    tmp = sum
    sum += a[i]
    while tmp > 0 and sum >= 0:
        sum -= 1
        count += 1
    while tmp < 0 and sum <= 0:
        sum += 1
        count += 1

print(count)


### FIXED CODE ###

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

# +, -, +, -, ...
sum = 0
count = 0
for i in range(n):
    sum += a[i]
    if i % 2 == 0:
        if sum <= 0:
            count += abs(sum) + 1
            sum = 1
    else:
        if sum >= 0:
            count += abs(sum) + 1
            sum = -1

# -, +, -, +, ...
sum2 = 0
count2 = 0
for i in range(n):
    sum2 += a[i]
    if i % 2 == 0:
        if sum2 >= 0:
            count2 += abs(sum2) + 1
            sum2 = -1
    else:
        if sum2 <= 0:
            count2 += abs(sum2) + 1
            sum2 = 1

print(min(count, count2))
### BUGGY CODE ###

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

for i in range(1,N+1):
    print(A.count(i))
    if i in A:
        A.remove(i)
    else:pass


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))#N-1
list=[]
for i in range(N):
    list.append(0)

for i in range(0,N-1):
    list[A[i]-1]+=1

for i in range(0,N):
    print(list[i])
### BUGGY CODE ###

import copy
from scipy.misc import comb
from collections import Counter

N=int(input())
A=list(map(int,input().split() ))
B=[-1]*N   #メモ化。iの時の方法の総数

f_cnt=Counter(A)
f_dic=dict(f_cnt)
#print("first",f_dic)
#f_dic[1] += -1 
#print(f_dic)

for i,item in enumerate(A):
  if B[item-1]>-1:
    #print(i,item,"は計算済み！")
    #print(i,B[item-1],"done")
    print(B[item-1])
  else:
    #C=A[0:i]+A[i+1:] #仮で作るリスト
    #cnt = Counter(C)
    #D=dict(cnt)
    D=copy.deepcopy(f_dic)
    D[item] -= 1
    E=[]
    for item2 in D:
      if D[item2]>=2:
        E.append(D[item2])
    #print(i,f_dic,D,E)
    opt=0
    for item3 in E:
      opt += comb(item3,2,exact=True)
    B[item-1]=opt
    #print(i,opt)
    print(opt)
    #print(i,E,opt)
    #print(C,cnt)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split() ))
from collections import Counter
d=dict(Counter(A))
#print(d)
cnt=0
for item in d:
    cnt += (d[item])*(d[item]-1)//2

#print("cnt",cnt)
   
for num in A:
    new = max(0, (d[num]-1)*(d[num]-2)//2)
    print(cnt- d[num]*(d[num]-1)//2 + new)
### BUGGY CODE ###

import itertools
N,M,Q = map(int,input().split())

num_all = [i+1 for i in range(M)]
#print(num_all)
Comb = list(itertools.combinations_with_replacement(num_all,N))

num_l = []         
for i in range(Q):
  a,b,c,d = map(int,input().split())
  num_l.append([a,b,c,d])
#print(num_l)  
  
#print(len(Comb))
d_sum_max = 0  
for A in Comb:
  d_sum = 0
  #print(A)
  #print()
  
  for i in range(Q):
    a,b,c,d = num_l[i][0],num_l[i][1],num_l[i][2],num_l[i][3]
    #print(a,b,c,d)
    #print(A[b-1],A[a-1],':',A[b-1]-A[a-1],c)
    if(A[b-1]-A[a-1] == c):
      d_sum += d
      
  #print(A,d_sum)
  d_sum_max = max(d_sum_max,d_sum)

print(d_sum_max)    

### FIXED CODE ###

import itertools
N,M,Q = map(int,input().split())

num_all = [i+1 for i in range(M)]
#print(num_all)
Comb = list(itertools.combinations_with_replacement(num_all,N))

num_l = []         
for i in range(Q):
  a,b,c,d = map(int,input().split())
  num_l.append([a,b,c,d])
#print(num_l)  
  
#print(len(Comb))
d_sum_max = 0  
for A in Comb:
  d_sum = 0
  #print(A)
  #print()
  
  for x in num_l:
    a,b,c,d = x[0],x[1],x[2],x[3]
    #print(a,b,c,d)
    #print(A[b-1],A[a-1],':',A[b-1]-A[a-1],c)
    if(A[b-1]-A[a-1] == c):
      d_sum += d
      
  #print(A,d_sum)
  d_sum_max = max(d_sum_max,d_sum)

print(d_sum_max)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

rest = 0
for i in range(n-1):
  for j in range(i+1, n):
    rest = (rest + (a[i] ^ a[j])) % mod
    
print(rest)

### FIXED CODE ###

n = int(input())
str_a = ''.join(['{:060b}'.format(a) for a in map(int, input().split())])
mod = 10**9 + 7

rest = 0
for d in range(60):
  ones = str_a[59-d::60].count('1')
  rest = (rest + 2**d * ones * (n - ones)) % mod
    
print(rest)
### BUGGY CODE ###

import math
num_limit = int(input())
s_limit_1 = int(num_limit**0.5)
s_limit_2 = int((num_limit/2)**0.5)
s_limit_3 = int((num_limit/3)**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    j = 0
    k = 0
    l = 0
    for j in range(1,s_limit_1+1):
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j == k and k == l:
                        xyz_count += 1
                    elif j == k and k > l or j > k and k == l:
                        xyz_count += 3
                    else:
                        xyz_count += 6
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

def II(): return int(input())
def LI(): return [int(i) for i in input().split()]

N, K = LI()
H = LI()

cost = list()
cost.append(0)
for n in range(1, N):
  MIN = min(
  	[ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, K+1) if n-k>=0 ]
  )
  cost.append(MIN)

print(cost[-1])

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    s = [SS() for _ in range(N)]

    cnt = [collections.Counter(i) for i in s]
    
    ans = 0
    for i, j in itertools.combinations(cnt, 2):
        if i == j:
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    s = [''.join(sorted(list(SS()))) for _ in range(N)]

    cnt = collections.Counter(s)
    ans = sum([i * (i - 1) // 2 for i in cnt.values()])

    print(ans)

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

N, M = map(int, input().split())
path = set([n for n in range(1, N + 1)])
for _ in range(M):
    l, r = map(int, input().split())
    pi = set([n for n in range(l, r + 1)])
    path &= pi
print(len(path))

### FIXED CODE ###

N, M = map(int, input().split())
l, r = 1, 10 ** 5

for _ in range(M):
    li, ri = map(int, input().split())
    l = max(l, li)
    r = min(r, ri)

ans = r - l + 1 if r >= l else 0
print(ans)
### BUGGY CODE ###

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

cnt = 0
flg = True
while flg:
  flg = False
  for i in range(0, n):
    if not a[i]%2:
      a[i] = a[i] / 2
      flg = True
      cnt += 1
      break

print(cnt)

### FIXED CODE ###

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

cnt = 0
flg = True
while flg:
  flg = False
  minus = 0
  for i in range(0, len(a)):
    if not a[i+minus]%2:
      a[i+minus] = a[i+minus] / 2
      flg = True
      cnt += 1
      break
    else:
      a.pop(i+minus)
      minus -= 1

print(cnt)
### BUGGY CODE ###

a = input()
a = str(a)
l = len(a)
blk = a
i = 0
rem = 0
while i < (l - 1):
    if(int(blk[i]) + int(blk[i+1]) == 1):
        blk = blk[:i] + blk[i+2:]
        l -= 2
        rem += 2
        i = 0
    else:
        i += 1
    
print(rem)

### FIXED CODE ###

a = input()
l = len(a)
blk = a
i = 0
rem = 0
num0 = 0
num1 = 0
while i < l:
    if blk[i] == "0":
        num0 += 1
    else:
        num1 += 1
    i += 1
rem = min(num0, num1)
print(rem * 2)