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

import copy
def solve():
    INF = float('inf')
    N = int(input())
    a = []
    for i in range(N):
        a.append(list(map(int, input().split())))
        flag = 0
        length = 0
        

    for i in range(N):
        for j in range(i+1, N):
            muda = 0
            for k in range(N):
                if k == i or k == j:
                    continue
                mix = a[i][k] + a[k][j]
                if a[i][j] > mix:
                    flag = 1
                    continue
                elif a[i][j] == mix:
                    muda = 1
                    continue
            if muda == 1:
                continue
            length += a[i][j]

    if (flag == 0):
        length = int(length)
    else:
        length = -1
    print(length)

solve()

                

               

### FIXED CODE ###

import numpy as np
import scipy.sparse.csgraph as graph

N = int(input())
G = np.array([list(map(int, input().split())) for i in range(N)])

G2 = graph.floyd_warshall(G, directed=False)

if np.any(G != G2):
    print(-1)
    exit()
else:
    c = [2*10**9]*N
    d = np.diag(c)
    G += d
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            two = np.min(G[i]+G[j])
            if two != G[i,j]:
                ans += G[i,j]

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



N,M=map(int,input().split())
A=[0]*M
B=[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())

uf=UnionFind(N+1)
for i in range(M):
    uf.union(A[i],B[i])
    #print(uf.find(1))
#print()
a=[0]*N
#print(uf)
print(len(list(uf.all_group_members().values()))-2)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N,M=map(int,input().split())
A=[0]*M
B=[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())

uf=UnionFind(N+1)
for i in range(M):
    uf.union(A[i],B[i])
a=[0]*(N+1)
con=0

for i in uf.parents:
    if(i<0):
        con=con+1

print(con-2)
### BUGGY CODE ###

import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
#print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = a[np.argmin(np.abs(a-t))]
    b_dis = b[np.argmin(np.abs(b-t))]
    a_d = np.abs(a_dis-t)
    b_d = np.abs(b_dis-t)
    cand1 = b_d + np.min(np.abs(a-b_dis))
    cand2 = a_d + np.min(np.abs(b-a_dis))
    print(np.min([cand1, cand2]))

### FIXED CODE ###

import bisect
import numpy as np
 
hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

def search_min_pos(arr, target):
  index = bisect.bisect_left(arr, target)
  if 0 == index:
    dist = arr[index]
  else:
    dist = arr[index-1:index+1]
  if not isinstance(dist, list):
    dist = [dist]
  return dist

a_arr = s[:hint[0]]
b_arr = s[hint[0]:-hint[2]]
sum = 0
for t in s[-hint[2]:]:
  a_pos = search_min_pos(a_arr, t)
  b_pos = search_min_pos(b_arr, t)
  #print(t, a_pos, b_pos)
  min_dist = 10 ** 11
  for a in a_pos:
    b_against_a = search_min_pos(b_arr, a)
    for ba in b_against_a:
      min_dist = min([min_dist, abs(t-a)+abs(ba-a)])
  for b in b_pos:
    a_against_b = search_min_pos(a_arr, b)
    for ab in a_against_b:
      min_dist = min([min_dist, abs(t-b)+abs(ab-b)])
  print(min_dist)
### BUGGY CODE ###

import math
import calendar
import fractions
import itertools

n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(1, n + 1):
        a = str(i)
        b = str(j)
        if a[0] == b[-1] and a[-1] == b[0]:
            ans += 1

print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n = int(input())
cnt = [[0] * 9 for i in range(9)]
# print(len(cnt), len(cnt[0]))
# print(cnt)
for i in range(1, n + 1):
    prefix = int(str(i)[0])
    suffix = int(str(i)[-1])
    if suffix != 0:
        cnt[prefix - 1][suffix - 1] += 1
ans = 0
for i in range(9):
    for j in range(9):
       ans += cnt[i][j] * cnt[j][i]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3


s = int(input())

#2以下だったら0で決まり
if s <= 2:
    print(0)


else:
    #結果
    result = 0
    #項数でループ
    for i in range(1, s // 3 + 1):
        # #あまり
        r = s - i * 3

        if r == 0:
            result += 1
        else:
            h = 1
            # for j in range(1, r + 1):
            #     h *= ((j + i - 1) / j)

            for j in range(1, r + 1):
                h *= (j + i - 1)

            for j in range(1, r + 1):
                h //= j

            result += h
        result %= int(1e9 + 7)

    print(int(result))







### FIXED CODE ###

#!/usr/bin/env python3

s = int(input())



if s <= 2:
    print(0)
else:
    a = [0] * (s + 1)
    a[0] = 1
    for i in range(3, s + 1):
        a[i] = int((a[i - 1] + a[i - 3]) % (1e9 + 7))

    print(a[s])
### BUGGY CODE ###

S = input()
ans = 0
while "01" in S:
    ind = S.find("01")
    S = S[:ind]+S[ind+2:]
    ans += 2
while "10" in S:
    ind = S.find("10")
    S = S[:ind]+S[ind+2:]
    ans += 2
print(ans)

### FIXED CODE ###

import collections
S = input()
c = collections.Counter(S)
if len(c.values()) == 2:
    print(min(c.values())*2)
else:
    print(0)
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]

dp = [0] * (n+1)
dp[0] = 1

for i in range( 1, n+1):
    if i in a:
        dp[i]= 0
    else:
        dp[i]= (dp[i-1] + dp[i-2])

print(dp[n] % 1000000007)

### FIXED CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
dp = [0] * (n+1)
dp[0] = 1

for i in range( 1, n+1):
    if i in a:
        dp[i]= 0
    else:
        dp[i]= (dp[i-1] + dp[i-2])

print(dp[n] % 1000000007)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + abs(p[j][0]-p[j-D][0]) + abs(p[j][1] - p[j-D][1]) 

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

d = [0]*(H*W)
for i in range(D, H*W):
    d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(d[R]-d[L])
### BUGGY CODE ###

# C - 高橋君とカード / Tak and Cards

import numpy as np
import math

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

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = x - np.array(A) # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-x for x in x_diff if x < 0]
x_diff_positive = [x for x in x_diff if x > 0]

ans = 0
for i in range(1, sum(x)):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

    
# 0の選び方
n_pattern_0 = 0
n_0 = np.count_nonzero(x_diff == 0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)

### FIXED CODE ###

# C - 高橋君とカード / Tak and Cards

#import numpy as np
import math

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

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = [a - A for a in x] # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, min(sum(x_diff_negative), sum(x_diff_positive)) + 1):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

# 0の選び方
n_pattern_0 = 0
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)
### BUGGY CODE ###

import sys
import collections

def main():
    N,*S = map(int, open(0).read().split())

    S = sorted(S)

    g = [S.pop(-1)]

    for gen in range(N):
        for p in g[:2**gen]:
            for si, s in enumerate(S[::-1]):
                if p > s:
                    g.append(s)
                    del S[-(si+1)]
                    break
            else:
                print('No')
                sys.exit()
    print('Yes')

if __name__=='__main__':
    main()

### FIXED CODE ###

## 他の方と処理内容がほぼ同じなのに何でTLEになるか分からないので、他の方のコードでテスト
N = int(input())
a = list(map(int,input().split(' ')))
a.sort()
    

fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()
    
    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    
    
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
b = list(map(int, input().split()))
MOD = 1000000007
sum_n = 0
a = []
for i in b:
  a.append(i%MOD)
sum_sum = []
for i in range(N):
  s = 0
  for j in range(i+1,N):
    s = (s + a[j]) % MOD
  sum_sum.append(s)
for i in range(1,N):
  sum_n = (sum_n + (a[i-1] * sum_sum[i-1]) % MOD) % MOD
print(sum_n % MOD)

### FIXED CODE ###

N = int(input())
b = list(map(int, input().split()))
MOD = 1000000007
sum_n = 0
a = []
for i in b:
  a.append(i%MOD)
sum_sum = sum(a[1:])
for i in range(N):

  sum_n = (sum_n + (a[i] * sum_sum) % MOD) % MOD
  if i+1 < N:
  	sum_sum = sum_sum - a[i+1]
print(sum_n % MOD)
### BUGGY CODE ###

from queue import Queue
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
black_num = sum([map_list[i].count("#") for i in range(h)])
ans = 0
q = Queue()
q1 = Queue()
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.put([y, x])
while (black_num < (h*w)):
    q_list = []
    for j in range(q.qsize()):
        y, x = q.get()
        if map_list[y][x] == "#":
            for i in range(4):
                new_y = y + y_list[i]
                new_x = x + x_list[i]
                if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                    if map_list[new_y][new_x] == ".":
                        map_list[new_y][new_x] = "#"
                        black_num += 1
                        q_list.append([new_y, new_x])
    q = Queue()
    for qq in q_list:
        q.put(qq)
    ans += 1
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n
d = [[inf] * j + [abs(h[i+j] - h[i]) for i in range(n-j)] for j in range(1, k+1)]

# calc
for i in range(1, n):
    d_i = [dp[i-j+k] + d[j-1][i] for j in range(1, k+1)]
    dp[i+k] = min(d_i)

print(dp[-1])


"""
"""


### FIXED CODE ###

import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for i in range(1, k+1, 1):
    for l in range(1, k+1, 1):
        for m in range(1, k+1, 1):
            ans += gcd(i,l,m)

print(ans)


### FIXED CODE ###

import math

k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1,k+1):
        tmp = math.gcd(i,j)
        for m in range (1,k+1):
            ans += math.gcd(tmp,m)

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

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

earn = 0
for day in reversed(range(M)):
    maxearn = -1
    maxindex = -1
    for i, ab in enumerate(AB):
        if ab[0] + day <= M:
            if ab[1] > maxearn:
                maxearn = ab[1]
                maxindex = i
    if maxindex == -1:
        continue
    earn += maxearn
    del AB[maxindex]

print(earn)


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[0])
pos=0
cando=[]
for remain in range(M+1):
    for i in range(pos,len(AB)):
        if AB[i][0] <= remain:
            heapq.heappush(cando, -AB[i][1])
            pos=i+1
        else:
            pos=i
            break
    if cando:
        earn-=heapq.heappop(cando)
print(earn)
### BUGGY CODE ###

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

cur_m = 1000
cur_s = 0

state = -1 # 1:up 0:down
prev = 0
for ai in a:
  if state == -1:
    prev = ai
    state = 0
  elif state == 1:
    if prev > ai: # peak
      # sell at prev
      cur_m += (prev * cur_s)
      cur_s = 0
      state = 0
  else:
    if prev <= ai:
      # buy at prev
      while cur_m >= prev:
        cur_s += 1
        cur_m -= prev
      state = 1
  prev = ai

if cur_s > 0:
  cur_m += (a[-1] * cur_s)

print(cur_m)





### FIXED CODE ###

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

cur_m = 1000
cur_s = 0

state = -1 # 1:up 0:down
prev = 0
for ai in a:
  if state == -1:
    prev = ai
    state = 0
  elif state == 1:
    if prev > ai: # peak
      # sell at prev
      cur_m += (prev * cur_s)
      cur_s = 0
      state = 0
  else:
    if prev < ai:
      # buy at prev
      buy_num = cur_m // prev
      cur_s += buy_num
      cur_m -= prev * buy_num
      state = 1
  prev = ai

if cur_s > 0:
  cur_m += (a[-1] * cur_s)

print(cur_m)
### BUGGY CODE ###

if __name__ == '__main__':
    N, A = map(int, input().split())
    x = list(map(int, input().split()))

    # x.insert(0, 0)

    dp = [[[0 for _ in range(N * A + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0][0] = 1

    for i in range(1, N + 1):
        for j in range(1, i + 1):
            for k in range(1, N * A + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if k >= x[i - 1]:
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i - 1]]

    ans = 0
    for j in range(1, N + 1):
        ans += dp[N][j][A * j]

    print(ans)


### FIXED CODE ###

if __name__ == '__main__':
    N, A = map(int, input().split())
    x = list(map(int, input().split()))

    x.insert(0, 0)

    dp = [[[0 for _ in range(N * A + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0][0] = 1

    for i in range(1, N + 1):
        for j in range(1, i + 1):
            for k in range(1, N * A + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if k >= x[i]:
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i]]

    ans = 0
    for j in range(1, N + 1):
        ans += dp[N][j][A * j]

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

from collections import Counter
S = input()
mod = 2019
p = [0] * len(S)
r = 0
for i,s in enumerate(S[::-1]):
  r += (int(s) * (10**i))%mod
  p[i] = r%mod

p.append(0)
ans = 0
c = Counter(p)
for k in c:
  if c[k] > 1:
    ans += 1
print(ans)

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
ans = 0
for a in range(1,n+1):
    for b in range(1,n+1):
        if a % b >= k:
            ans += 1

print(ans)

### FIXED CODE ###

def max(a,b):
    if a > b:
        return a
    else:
        return b
n, k = [int(i) for i in input().split()]
ans = 0


for b in range(1,n+1):
    p = n // b
    r = n % b
    ans += p * max(0,b-k)+max(0,r-k+1)
if k == 0:
    ans -= n
    
print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[(2**i)%mod for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)
### BUGGY CODE ###

from collections import Counter

N=int(input())
L=[]
V=[]
LV=[]

for i in range(N):
    si=input()
    # ci=Counter(si)
    # c=sorted(ci.elements())
    c=sorted(Counter(si).elements())
    if c in L:
        ind=L.index(c)
        V[ind]+=1
    else:
        L.append(c)
        V.append(1)

ans=0

for v in V:
    ans+=v*(v-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

N=int(input())
dic={}

ans=0

for i in range(N):
    si=input()
    # ci=Counter(si)
    # c=sorted(ci.elements())
    # c=sorted(Counter(si).elements())
    sorted_s=''.join(sorted(Counter(si).elements()))
    if sorted_s in dic:
        ans+=dic[sorted_s]
        dic[sorted_s]+=1
    else:
        dic[sorted_s]=1
print(ans)
### BUGGY CODE ###

K=int(input())
ans=float("Inf")
for i in range(1,6*10**6):
    a=list(str(K*i))
    a2=list(map(int,a))
 
    ans=min(ans,sum(a2))
 
print(ans)

### FIXED CODE ###

from collections import deque

def BFS01(d,K):
    d[1] = 1
    q = deque([1])
    while q:
        n = q.popleft()
        l, r = map(lambda x: (x) % K, [n * 10, n + 1])
        if d[l] > d[n]:
            d[l] = d[n]
            q.appendleft(l)

        if d[r] > d[n] + 1:
            d[r] = d[n] + 1
            q.append(r)
    return d[0]

K = int(input())
d = [float('inf')] * K

print(BFS01(d,K))
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod
print(count)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])
### BUGGY CODE ###

from bisect import *
n=int(input())
r=[]
for _ in range(n):
    a=int(input())
    if not r:
        r.append(a)
        continue
    i=bisect_left(r,a)
    if i:
        r.insert(i,a)
        del r[i-1]
    else:
        r=[a]+r
print(len(r))

### FIXED CODE ###

import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(input())
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print(mi+1)

n = int(input())
inf=10**10
f(n)
### BUGGY CODE ###

n,k = map(int, input().split())
lst = list(map(int, input().split()))
ans = 0
koho = 0

for i in range(n-k+1):
    koho = sum(lst[i:i+k])
    if koho > ans:
        ans = koho

print((ans+k)/2)


### FIXED CODE ###

from itertools import accumulate


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

# 累積和
B = [0] + A
B = list(accumulate(B))

ans = []
for i in range(N-K+1):
    ans.append(B[i+K]-B[i])

print((max(ans)+K)/2)