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

n ,k= map(int,input().split())
h = list(map(int,input().split()))
#print(h)
inf = float("inf")
dp = [inf]*(n+1)
dp[0] = 0


for i in range(1,n):
    for j in range(1,k+1):
        if i-j >=0:
            dp[i] = min(dp[i],dp[i-j] + abs(h[i] - h[i-j]))
            #print(dp)
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
dp = [float("inf")]*(n)
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(L[i]-L[j]))
        
print(dp[n-1])
### BUGGY CODE ###

def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    max_total = 0

    for i in range(N-K+1):
        max_total = max(max_total, sum(P[i:i+K]))

    ans = (max_total + K) / 2
    print(ans)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

from itertools import accumulate

N, K = map(int, input().split())
P = map(int, input().split())
acc_P = list(accumulate(P))
ans = (acc_P[K-1] + K) / 2

for i in range(N-K):
    ans = max(ans, (acc_P[i+K] - acc_P[i] + K) / 2)

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

from itertools import combinations


N, K, *XY = map(int, open(0).read().split())
X = sorted(XY[::2])
Y = sorted(XY[1::2])

ans = 10 ** 20
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        in_rect = [
            (x, y) for x, y in zip(*[iter(XY)] * 2) if x1 <= x <= x2 and y1 <= y <= y2
        ]
        if len(in_rect) < K:
            continue
        ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)



### FIXED CODE ###

import numpy as np

N, K, *XY = map(int, open(0).read().split())

X = XY[::2]
comp_X = {}
decomp_X = {}
for i, x in enumerate(sorted(set(X))):
    comp_X[x] = i
    decomp_X[i] = x

Y = XY[1::2]
comp_Y = {}
decomp_Y = {}
for i, y in enumerate(sorted(set(Y))):
    comp_Y[y] = i
    decomp_Y[i] = y

I = len(comp_X)
J = len(comp_Y)
comp_XY = [(comp_X[x], comp_Y[y]) for x, y in zip(X, Y)]
acc = np.zeros((I + 1, J + 1), np.int32)
for c_x, c_y in comp_XY:
    acc[c_x + 1][c_y + 1] += 1
acc = np.add.accumulate(acc, axis=0)
acc = np.add.accumulate(acc, axis=1)

ans = float("inf")
for i in range(1, I + 1):
    for j in range(1, J + 1):
        cur = acc[i:, j:] + acc[:-i, :-j] - acc[:-i, j:] - acc[i:, :-j]
        for k, row in enumerate(cur):
            for l, val in enumerate(row):
                if val >= K:
                    ans = min(
                        ans,
                        (decomp_X[k + i - 1] - decomp_X[k])
                        * (decomp_Y[l + j - 1] - decomp_Y[l]),
                    )
print(ans)
### BUGGY CODE ###

import heapq

N = int(input())
a    = [ int(x) for x in input().split() ]
arev = [ -x for x in a[::-1] ]

Hl = a[:N]
heapq.heapify(Hl) #; print(Hl)

Hr = arev[:N]
heapq.heapify(Hr) #; print(Hr)

sumL = [sum(Hl)]
for i in range(N):
    x = heapq.heappushpop(Hl, a[N+i])
    #print(i, x, Hl, sum(Hl))
    sumL.append(sum(Hl))
    
sumR = [sum(Hr)]
for i in range(N):
    y = heapq.heappushpop(Hr, arev[N+i])
    #print(i, y, Hr, sum(Hr))
    sumR.append(sum(Hr))

#print(sumL, sumR)
dif = [ i+j for i, j in zip(sumL, sumR[::-1])]  #; print(dif)
print(max(dif))

### FIXED CODE ###

import heapq

N = int(input())
a    = [ int(x) for x in input().split() ]
arev = [ -x for x in a[::-1] ]

Hl = a[:N]
heapq.heapify(Hl) #; print(Hl)
suml = sum(Hl)
sumL = [suml]

Hr = arev[:N]
heapq.heapify(Hr) #; print(Hr)
sumr = sum(Hr)
sumR = [sumr]

for i in range(N):
    x = heapq.heappushpop(Hl, a[N+i])
    #print(i, x, Hl, sum(Hl))
    suml += -x + a[N+i]
    sumL.append(suml)
    
for i in range(N):
    x = heapq.heappushpop(Hr, arev[N+i])
    #print(i, x, Hr, sum(Hr))
    sumr += -x + arev[N+i]
    sumR.append(sumr)

#print(sumL, sumR)
dif = [ i+j for i, j in zip(sumL, sumR[::-1])]  #; print(dif)
print(max(dif))
### BUGGY CODE ###

N=int(input())

answer=1
# -*- coding:utf-8 -*-
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


def factorization(n):
    arr = []
    temp = n
    for i in get_sieve_of_eratosthenes(int(N**0.5)):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    number=1


    for a in arr:
        number*=(a[1]+1)
    return number



for n in range(2,N+1):
    answer+=n*factorization(n)

print(answer)



### FIXED CODE ###

N = int(input())

ans = 0
for x in range(1, N + 1):
    n = N // x
    ans += n * (2 * x + (n - 1) * x) // 2

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

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(-2,3):
            for y in range(-2,3):
                if 0<=i+x<h and 0<=j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

from collections import deque
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    sx = c[0]
    sy = c[1]
    gx = g[0]
    gy = g[1]

    # 周辺25マス移動
    dd = []
    for i in range(-2,3):
        for j in range(-2,3):
            dd.append([i,j])

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] > d[p[0]][p[1]]:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.appendleft((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]
        for i in range(25):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dd[i][0]
            ny = p[1] + dd[i][1]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]+1

    return d[gx][gy]

n, m = map(int, input().split())
c = list(map(lambda x:int(x)-1,input().split()))
g = list(map(lambda x:int(x)-1,input().split()))
maze = [list(input()) for i in range(n)]

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
a=0
for i in range(1,max(h)+1):
    s=0
    while s<n:
        if h[s]>=i:
            a+=1
            while s<n and h[s]>=i:
                s+=1
    s+=1
print(a)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
print(sum(max(0,h[i]-h[i+1]) for i in range(n-1)) +h[-1])
### BUGGY CODE ###

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

ans = 1
for i in A:
        ans = ans * i

if ans > 1000000000000000000:
        print(-1)
else:
        print(ans)

### FIXED CODE ###

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

if A[0] == 0:
        print(0)
        exit()

ans = 1
for i in A:
        ans = ans * i
        if ans > 1000000000000000000:
                print(-1)
                exit()

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

def paint(point, color):
    colors[point] = color

    # その点とつながる点で、まだ色が塗られていない点にルールに従い色を塗る
    for i in reration[point]:
        if not colors[i]:  # 塗られてない点
            # print(str(i)+"塗る")
            nextcolor = color*((-1)**hen[point][i])
            paint(i, nextcolor)


N = int(input())
hen = [[0 for _ in range(N)] for i in range(N)]
reration = [[] for i in range(N)]  # その点がつながる点
colors = ["" for i in range(N)]  # 色(作業中は簡単のため1,-1の2つに塗り分ける)
for i in range(N-1):
    U, V, W = map(int, input().split())
    hen[U-1][V-1] = W % 2
    hen[V-1][U-1] = W % 2
    reration[U-1].append(V-1)
    reration[V-1].append(U-1)

# print(hen)
# print(reration)
for i in range(N):
    if not colors[i]:
        paint(i, 1)
for co in colors:
    print((co+1)//2)


### FIXED CODE ###

import sys

sys.setrecursionlimit(2**31-1)#ループ回数

def paint(point, color):
    colors[point] = color

    # その点とつながる点で、まだ色が塗られていない点にルールに従い色を塗る
    for friend, w in reration[point]:
        if not colors[friend]:  # 塗られてない点
            # print(str(i)+"塗る")
            nextcolor = color*(-1)**w
            paint(friend, nextcolor)


N = int(input())
reration = [[] for i in range(N)]  # その点がつながる点
colors = ["" for i in range(N)]  # 色(作業中は簡単のため1,-1の2つに塗り分ける)
for i in range(N-1):
    U, V, W = map(int, input().split())
    reration[U-1].append((V-1, W % 2))
    reration[V-1].append((U-1, W % 2))

# print(hen)
# print(reration)
for i in range(N):
    if not colors[i]:
        paint(i, 1)
for co in colors:
    print((co+1)//2)
### BUGGY CODE ###

#codinng:utf-8

N = int(input())
count = 0

while N > 0:
    count += (N % 10000000) % 9
    N = N // 10000000

if count % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#codinng:utf-8

N = int(input())
count = 0

while N > 0:
    count += (N % (10 ** 100)) % 9
    N = N // (10 ** 100)

if count % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    res = ""
    i = S
    j = T
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            res = s[i-1]+res
            i -= 1
            j -= 1
    print(res)


main()


### FIXED CODE ###

def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    res = ""
    i = S
    j = T
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            res = s[i-1]+res
            i -= 1
            j -= 1
    print(res)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)


s = input()
t = input()

def z_algorithm(s):

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        break

def solve(i, li):
    ans = 0
    if i < 0 or len(li) <= i:
        return 0
    if visited[i]:
        return 0
    if li[i] >= len(t):
        visited[i] = True
        ans += 1 + solve(i+len(t), li)
    if li[i] < len(t):
        visited[i] = True
    return ans

s = new_s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = s
while True:
    if len(new_s) > len(t):
        s = new_s
        break
    new_s += new_s

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
### BUGGY CODE ###

iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
a=list(enumerate(a))
b=sorted(a, key=lambda x:x[1])
a.sort(key=lambda x:x[1][1])
c=0
while not all(done):
    j, (_, h) = a.pop(0)
    if(done[j]): continue
    d = filter(lambda x: x[1][0]<h and not done[x[0]], b)
    if d:
        c+=1
    for (i, l) in d:
        done[i]=1
print(c)

### FIXED CODE ###

import bisect
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
b=sorted(a, key=lambda x:x[1])
c=0
d=-1
for p, q in b:
    if not p<=d<q:
        c+=1
        d=q-1
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

cost=[-1]*(n+1)
cost[k]=0
c=0
while c<n-1:
    for i in range(n-1):
        if cost[l[i][0]]!=-1 and cost[l[i][1]]==-1:
            cost[l[i][1]]=cost[l[i][0]]+l[i][2]
            c+=1
        if cost[l[i][1]]!=-1 and cost[l[i][0]]==-1:
            cost[l[i][0]]=cost[l[i][1]]+l[i][2]
            c+=1
for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

neighbor=[[] for _ in range(n+1)]
for i in range(n-1):
    neighbor[l[i][0]].append([l[i][1],l[i][2]])
    neighbor[l[i][1]].append([l[i][0],l[i][2]])

cost=[-1]*(n+1)
cost[k]=0
c=0

def sol(i,p,d):
    global cost
    cost[i]=d
    for x in neighbor[i]:
        if x[0]!=p:
            sol(x[0],i,d+x[1])
sol(k,-1,0)

for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])
### BUGGY CODE ###

n, p = [int(_) for _ in input().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
    print(ans)
    exit()

t = [0 for i in range(n+1)]
P = [0 for i in range(p)]
P[0] += 1
for i in range(1, n+1):
    t[i] = (t[i-1]+int(s[n-i])*10**i) % p
    P[t[i]] += 1

ans = 0
for c in P:
    ans += c*(c-1)//2
# print(t)
print(ans)


### FIXED CODE ###

n, p = [int(_) for _ in input().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
    print(ans)
    exit()

t = [0 for i in range(n+1)]
P = [0 for i in range(p)]
P[0] += 1
d = 1
for i in range(1, n+1):
    t[i] = (t[i-1]+int(s[n-i])*d) % p
    P[t[i]] += 1
    d = d*10 % p
ans = 0
for c in P:
    ans += c*(c-1)//2
# print(t)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

def dfs(B,LEN,ANS):
    #print(B,LEN,ANS)
    if LEN==0:
        for a in ANS[::-1]:
            print(a)
        sys.exit()
    for i in range(LEN):
        if B[i]==i+1:
            C=B[:i]+B[i+1:]
            dfs(C,LEN-1,ANS+[i+1])

dfs(B,N,[])
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(N):
    if B[i]>i+1:
        print(-1)
        sys.exit()

def dfs(B,LEN,ANS):
    #print(B,LEN,ANS)
    if LEN==0:
        for a in ANS[::-1]:
            print(a)
        sys.exit()
    for i in range(LEN-1,-1,-1):
        if B[i]==i+1:
            C=B[:i]+B[i+1:]
            dfs(C,LEN-1,ANS+[i+1])

dfs(B,N,[])
print(-1)
### BUGGY CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for i in range(m)], key = itemgetter(1), reverse=True)

ans = 0
for i in range(n):
    now = a[i]
    for rep, con in enumerate(bc):
        if now < con[1] and bc[rep][0] != 0:
            ans += con[1]
            bc[rep][0] -= 1
            break

    else:
        ans += now + sum(a[i+1:])
        break

print(ans)

### FIXED CODE ###

from collections import Counter

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

abc = Counter(a).most_common()
for i in range(m):
    b, c = map(int, input().split())
    abc.append((c, b))

abc.sort(reverse=True)

ans = 0
count = n
for c, b in abc:
    rep = min(count, b)
    ans += c * rep
    count -= rep
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
l = [int(x) for x in list(s)]

count = 0
flag = True

while flag == True:
    flag = False
    for i in range(n-1):
        if l[i] != l[i+1]:
            l = l[:i] + l[i+2:]
            count += 2
            n -= 2
            flag = True
            break

print(count)



### FIXED CODE ###

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

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

mod = 1000000000+7

z=0
for x in range(K, N+2):
  zz = 1
  for y in range(0,x):
    zz += (N-y) - y
    zz %= mod
  z += zz
  z %= mod
#
print(z)


### FIXED CODE ###

N, K = map(int, input().split())
mod = 1000000000+7

z=0

zz = ((N-K+1)+N)*K//2 - (0+(K-1))*K//2 + 1
zz = zz % mod

for x in range(K+1, N+3):
#  print(zz)
  z = (z + zz) % mod
  zz += (N-x+1) - (x-1)
  zz = zz % mod
#
print(z)
### BUGGY CODE ###

from collections import Counter

N = int(input())

s = [str(input()) for _ in range(N)]
count = 0
for i in range(N):
    for j in range(i+1,N):
        diff = Counter(s[i])-Counter(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)
### BUGGY CODE ###

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))
cards.sort()

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    for _ in range(stock_count):
        minimum_index = cards.index(min(cards))

        if rewrite_number <= cards[minimum_index]:
            break

        cards[minimum_index] = rewrite_number

print(sum(cards))


### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

print(total)
### BUGGY CODE ###

from itertools import combinations

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

l = list(combinations(p, K))

ans = []

for i in l:
    ans.append(sum(i))

print(min(ans))

### FIXED CODE ###

import numpy as np

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

p = np.array(p)
p = np.sort(p)

ans = p[:K].sum()

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

n = int(input())
*a, = map(int, input().split())
print(*[a.index(i)+1 for i in range(1, n+1)])

### FIXED CODE ###

n = int(input())
*a, = map(int, input().split())
b = [(j, i) for i, j in enumerate(a)]
b.sort()
print(*[j+1 for i, j in b])
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[]
for _ in range(q):
   a.append(int(input()))
for i in range(1,n+1):
   if k-q+a.count(i)>0:
      print("Yes")
   else:
      print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
import sys
input = sys.stdin.readline
a=[int(input()) for _ in range(q)]
import collections
c=collections.Counter(a)
for _ in range(1,n+1):
   if k-q+c[_]>0:
      print("Yes")
   else:
      print("No")
### BUGGY CODE ###

def squaremod(A,p,mod):#A^pの計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

    

N,A,B,K=map(int,input().split())
mod=998244353

def Combi(n,r):
    UP=1
    DOWN=1
    DOWN_r=1
    for i in range(r):
        UP=UP*(n-i) %mod
        DOWN=DOWN*(i+1)
        if i==r-1:
            DOWN_r=DOWN_r*squaremod(DOWN,mod-2,mod) %mod
        elif DOWN>mod**2:
            DOWN_r=DOWN_r*squaremod(DOWN,mod-2,mod) %mod
            DOWN=1

    return UP*DOWN_r %mod

ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi(N,i)*Combi(N,q)))%mod

print(ANS)

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)
### BUGGY CODE ###

a,b = map(int,input().split())
count = [i for i in range(a,b+1) if i<0]
if 0 in [i for i in range(a,b+1)]:
    print("Zero")
elif len(count)%2==0:
    print("Positive")
else:
    print("Negative")

### FIXED CODE ###

a,b = map(int,input().split())
if 0 >=a and 0<=b:
    print("Zero")
elif a>0 and b>0:
    print("Positive")
else:
    if (b-a+1)%2==0:
        print("Positive")
    else:
        print("Negative")