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

import sys                                                   
l1 = list(map(int, input().split()))                         
N = l1[0]                                                    
M = l1[1]                                                    
                                                             
dat = []                                                     
                                                             
per_dis = [ [] for n in range(N+1)]                          
                                                             
for n in range(M):                                           
    x = list(map(int, input().split()))                      
    dat.append(x)                                            
                                                             
def bfs(start, goal):                                        
    visited = []                                             
    unvisited = [(start, 0)]                                 
    while unvisited:                                         
        now = unvisited[0]                                   
        unvisited = unvisited[1:]                            
        for next in per_dis[now[0]]:                         
            if next[0] not in visited:                       
                if next[0] == goal:                          
                    return now[1] + next[1]                  
                unvisited.append((next[0], now[1] + next[1]))
                visited.append(next[0])                      
    return None                                              
                                                             
for x in dat:                                                
    if None == bfs(x[0], x[1]):                              
        per_dis[x[0]].append((x[1],x[2]))                    
        per_dis[x[1]].append((x[0],-x[2]))                   
    elif  x[2] != bfs(x[0], x[1]):                           
        print("No")                                          
        break;                                               
else:                                                        
    print("Yes")                                             

### FIXED CODE ###

from collections import deque

def bfs(x, graph, people):
    if people[x] is not None:
        return
    unvisited = deque([x])
    people[x] = 0
    while unvisited:
        now = unvisited.popleft()
        for next, d in graph[now]:
            if people[next] is None:
                people[next] =  people[now] + d
                unvisited.append(next)

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

    graph = [ [] for n in range(N+1)]
    people = [None] * (N+1)

    for n in range(M):
        L, R, D = list(map(int, input().split()))
        graph[L].append((R, D))
        graph[R].append((L, -D))
    for i in range(1, N+1):
        bfs(i, graph, people)

    for i in range(1, N+1):
        for j, d in graph[i]:
            if people[j] - people[i] != d:
                print("No")
                exit()
    else:
        print("Yes")


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

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])


### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

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

s = input()

cnt = 0
while 'BW' in s:
    cnt += s.count('BW')
    s = s.replace('BW', 'WB')

print(cnt)


### FIXED CODE ###

s = input()

w_cnt = 0
_b_cnt = 0
b_flag = False
cnt = 0
for si in list(s)[::-1]:
    if si == 'B':
        _b_cnt += 1
    if si == 'W':
        cnt += w_cnt * _b_cnt
        w_cnt += 1
        _b_cnt = 0
cnt += w_cnt * _b_cnt

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

import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def len_make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return len(divisors)

def main():
    n = i_input()

    count = 0

    for i in range(1, n+1):
        count += i * len_make_divisors(i)

    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()

    ans_list = [1] * n

    for i in range(2,n+1):
        for j in range(i,n+1,i):
            ans_list[j-1] += 1

    count = 0
    for i, ans in enumerate(ans_list):
        count += (i+1) * ans

    print(count)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# Iterative Binary Search Function 
# It returns location of x in given array arr if present, 
# else returns -1 
def bins(arr, l, r, x): 

	while l <= r: 

		mid = l + (r - l)//2; 
		
		# Check if x is present at mid 
		if arr[mid] == x: 
			return('yes')

		# If x is greater, ignore left half 
		elif arr[mid] < x: 
			l = mid + 1

		# If x is smaller, ignore right half 
		else: 
			r = mid - 1
n,m=map(int,input().split( ))
p=list(map(int,input().split( )))
q=[i for i in range(1,n+1)]
for iddd in range(m):
    i,j=map(int,input().split( ))
    if p[i-1]>p[j-1] and bins(q,0,len(q)-1,j)=='yes' :
        q.remove(j)
    elif p[j-1]>p[i-1] and bins(q,0,len(q)-1,i)=='yes':
        q.remove(i)
    elif p[j-1]==p[i-1]:
        if bins(q,0,len(q)-1,i)=='yes':
            q.remove(i)
        if bins(q,0,len(q)-1,j)=='yes':
            q.remove(j)
print(len(q))


### FIXED CODE ###

n,m=map(int,input().split( ))
p=list(map(int,input().split( )))
q=set()
for iddd in range(m):
    i,j=map(int,input().split( ))
    if p[i-1]>p[j-1] :
        q.add(j)
    elif p[j-1]>p[i-1] :
        q.add(i)
    elif p[j-1]==p[i-1]:
        q.add(i)
        q.add(j)
print(n-len(q))
### BUGGY CODE ###

import queue

def bfs(s1,s2):
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    s[s1][s2] = 0
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and (s[nextX][nextY] == '.' or s[nextX][nextY] > s[x][y] + 1):
                    s[nextX][nextY] = s[x][y] + 1
                    queueX.put(nextX)
                    queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

cnt = 0
cntlst = []
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            cntlst.append([i, j])
            cnt += 1
if cnt == (W * H):
    print(0)
    exit()

for i in cntlst:
    bfs(i[0], i[1])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])

print(ans)

### FIXED CODE ###

from collections import deque

def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[p[0]][p[1]] + 1
                que.append([nextX, nextY])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

que = deque()
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            que.append([i, j])
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)
### BUGGY CODE ###

from itertools import accumulate

mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = sorted([int(x) for x in input().split()])

table = [[1] * K]
for _ in range(N - K):
    tmp = accumulate(table[-1])
    table.append([x % mod for x in tmp])

comb = [table[i][K - 1] for i in range(N - K + 1)]
ans = 0
for i in range(N - K + 1):
    ans += comb[i] * (A[i + K - 1] - A[N - i - K])
    ans %= mod
print(ans)


### FIXED CODE ###

from itertools import accumulate

mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = sorted([int(x) for x in input().split()])

f = [1 for _ in range(N + 1)]
inv = [1 for _ in range(N + 1)]
finv = [1 for _ in range(N + 1)]

for i in range(2, N + 1):
    f[i] = f[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod
comb = [f[n] * (finv[K - 1] * finv[n - (K - 1)] % mod) % mod for n in range(K - 1, N)]

ans = 0
for i in range(N - K + 1):
    ans += comb[i] * (A[i + K - 1] - A[N - i - K])
    ans %= mod
print(ans)
### BUGGY CODE ###

# コンテスト時にトライしていたアルゴリズム
# その後の検証でアルゴリズムは正しそうなのでコードエラーを探す

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

# TLE対策 dist_listからmax_Dを求める
# nearest_city = getNearestValue(city_list, x)
# Dとなり最大値はXと最も近い都市との距離に等しい
# max_D = abs(nearest_city-x)

# TLE対策 都市との距離は事前に計算
dist_list = []
for city in city_list:
    dist_list.append(abs(city - x))

# TLE対策 mac_D対策
dist_list.sort()
max_D = dist_list.pop(0)

for xx in reversed(range(1, max_D+1)):
    flag = True
    for dist in dist_list:
        if (dist % xx) != 0:
            flag = False
            break
    if flag:
        break
print(xx)

### FIXED CODE ###

import fractions

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

city_list = list(map(int, input().split()))

dist_list = []
for city in city_list:
    dist_list.append(abs(city - x))

max_common_value = dist_list.pop(0)

for dist in dist_list:
    # 今までのDと次の都市の距離との最大公約数を見つける
    max_common_value = fractions.gcd(max_common_value, dist)

print(max_common_value)
### BUGGY CODE ###

L,R=map(int,input().split())

x=[]
a=1
for i in range(L,R):
    for j in range(L+1,R+1):
        y=((i*j)%2019)
        if y==0:
            a=0
            break
        x.append(y)

if a==0:
    print(a)
else:
    print(min(x))

### FIXED CODE ###

L,R=map(int,input().split())

x=[]
a=0
for i in range(L,R):
    for j in range(L+1,R+1):
        y=((i*j)%2019)
        x.append(y)
        if y==0:
            break
    if y==0:
            break

print(min(x))
### BUGGY CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        continue
    for b in range(len(B)):
        if b+1 > K:
            continue
        elif (a+1)*(b+1) > K:
            continue
        for c in range(len(C)):
            if c+1 > K:
                continue
            elif (a+1)*(c+1) > K:
                continue
            elif (b+1)*(c+1) > K:
                continue
            elif (a+1)*(b+1)*(c+1) > K:
                continue
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n, a = input(), set(map(int, raw_input().split()))
out = []
for i in a:
    for j in xrange(i / 2, -1, -1):
        if j in a:
            out.append((i, j))
            break
        elif i - j in a:
            out.append((i, i - j))
            break
print ' '.join(map(str, sorted(out, key = lambda x: x[0], reverse = True)[0]))


### FIXED CODE ###

def check(a, b, target):
    if abs(target - a) < abs(target - b):
        return a
    else:
        return b


n, a = int(input()), list(map(int, input().split()))
if n == 2:
    a.sort(reverse = True)
    print(a[0], a[1])
    exit()
a.sort()
l, r = 0, n
target = a[-1] >> 1
while l < r:
    mid = (l + r) >> 1
    if a[mid] > target:
        r = mid
    else:
        l = mid + 1
if a[l] <= target:  # check a[l] and a[l + 1]
    print(a[-1], check(a[l], a[l + 1], target))
else:  # check a[l] and [l - 1]
    print(a[-1], check(a[l - 1], a[l], target))
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in reversed(range(N)):
  for j in range(N // 2):
    if (j + i) <= N and S.count(S[j:j+i]) == 2:
      ans = i
      print(ans)
      exit()

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
i = j = ans = 0
while j < N:
  if S[i:j] in S[j:]:
    ans = max(ans, len(S[i:j]))
    j += 1
  else:
    i += 1

  if i == j:
    i += 1
    j += 2
print(ans)
### BUGGY CODE ###

from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

cnt = 0
for j in range(N):
  target = B[j]
  insert_indexA = bisect.bisect_left(A, target)
  insert_indexC = bisect.bisect_right(C, target)
  cnt = cnt + len(A[:insert_indexA]) * len(C[insert_indexC:])

print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

cnt = 0
for j in range(N):
  target = B[j]
  insert_indexA = bisect.bisect_left(A, target)
  insert_indexC = bisect.bisect_right(C, target)
  cnt = cnt + insert_indexA * (len(C)-insert_indexC)

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

N,M = input().split()
N = int(N)
M = int(M)

sum = 0

for i in range(N + 1):
    for j in range(N + 1):
        for k in range(N + 1):
            if i + j + k == M:
                sum += 1
            
print(sum)

### FIXED CODE ###

N,M = input().split()
N = int(N)
M = int(M)

sum = 0

for i in range(N + 1):
    for j in range(N + 1):
        if  0 <= M - i - j <= N:
            sum += 1
            
print(sum)
### BUGGY CODE ###

N = int(input())
S = [sorted(list(input())) for _ in range(N)]
count = 0
for i in range(N):
  for j in range(i+1,N):
    if S[i] == S[j]:
      count +=1

print(count)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
count = {}

for s in S:
  ls = str(sorted(list(s)))
  if ls in count:
    count[ls] +=1
  else:
    count[ls] = 1

for s in count:
  count[s] = count[s]*(count[s]-1)//2 
print(sum(count.values()))
### BUGGY CODE ###

# ABC154 D Dice in Line

n, k = map(int, input().split())
p_list = [int(x) for x in input().split()]
e_list = [None]*n

for i in range(n):
    e_list[i] = (1 + p_list[i])/2

ans = 0
for i in range(n-k+1):
    _ = sum(e_list[i:i+k])
    if ans < _:
        ans = _

print(ans)

### FIXED CODE ###

# ABC154 D Dice in Line

import itertools

n, k = map(int, input().split())
p_list = [int(x) for x in input().split()]
e_list = [None]*n

for i in range(n):
    e_list[i] = (1 + p_list[i])/2

cumsum = list(itertools.accumulate(e_list))
ans = cumsum[k-1]

for i in range(k,n):
    _ = cumsum[i] - cumsum[i-k]
    if ans < _:
        ans = _

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

import collections
n = int(input())
s = [''] + list(input())
cnt_1 = collections.Counter(s)

sub = 0
for j in range(1, (n+1)//2):
    for i in range(1, n-2*j+1):
        tmp = s[i] + s[i+j] + s[i+j*2]
        cnt_2 = collections.Counter(tmp)
        if max(cnt_2.values()) == 1:
            sub += 1

print((cnt_1['R']*cnt_1['G']*cnt_1['B'])-sub)

### FIXED CODE ###

import collections
n = int(input())
s = [''] + list(input())
cnt_1 = collections.Counter(s)

sub = 0
for j in range(1, (n+1)//2):
    for i in range(1, n-2*j+1):
        tmp = s[i] + s[i+j] + s[i+j*2]
        cnt_2 = collections.Counter(tmp)
        if cnt_2['R'] == 1 and cnt_2['G'] == 1 and cnt_2['B'] == 1:
            sub += 1

print((cnt_1['R']*cnt_1['G']*cnt_1['B'])-sub)
### BUGGY CODE ###

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

ans = 10 ** 10
for i in range(n - k + 1):
    temp = x[i:i + k]
    left = temp[0]
    right = temp[-1]
    ans = min(ans, abs(left) + abs(right - left), abs(right) + abs(right - left))

print(ans)


### FIXED CODE ###

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

ans = 10 ** 10
for i in range(n - k + 1):
    left = x[i]
    right = x[i + k - 1]
    ans = min(ans, abs(left) + abs(right - left), abs(right) + abs(right - left))

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

import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    x = [tuple(map(int, input().split())) for _ in range(N)] 
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, W + 1):
            dpi = dp[i]
            dpim = dp[i-1]
            if x[i - 1][0] <= j:
                dpi[j] = max(dpim[j], dpim[j - x[i - 1][0]] + x[i - 1][1])
            else:
                dpi[j] = dpim[j]

    print(dp[-1][W])

if __name__ == "__main__":
    main()


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

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

N = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(N):
  if(0 in a):
    ans = 0
    break
  ans *= a[i]
  if(ans>10**18):
    ans = -1
print(ans)


### FIXED CODE ###

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

n,k = map(int,input().split())
list = input().split()
expectation = []
for i in range(len(list)):
  expectation.append((1+int(list[i]))/2)
max = 0
for i in range(n-k+1):
  tmp = sum(expectation[i:i+k])
  if tmp > max:
    max = tmp
print(max)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
ave=[0]*(N-K+1)
tmp=0
for i in range(K):
    tmp+=(p[i]+1)/2
ave[0]=tmp
for i in range(1,N-K+1):
    ave[i]=ave[i-1]-(p[i-1]+1)/2 + (p[i+K-1]+1)/2
print(max(ave))
### BUGGY CODE ###

N = int(input())
si = [list(input()) for i in range(N)]

si2 = []
for i in range(len(si)):
    s = []
    for k in list(set(si[i])):
        a = si[i].count(k)
        s.append([k,a])
    si2.append(s)
 
si3 = [] 
for i in range(len(si2)):
    si3.append(sorted(si2[i], key = lambda val : val[0]))

result = []
for i in range(len(si3)):
    result.append(si3.count(si3[i])-1)

print(int(sum(result)/2))

### FIXED CODE ###

from collections import Counter

N = int(input())
si = [''.join(sorted(list(input()))) for i in range(N)]

count = Counter(si)

ans = 0
for s in set(si):
    n = count[s]
    ans += n * (n-1) // 2

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

import math
import collections
n, m = map(int, input().split())

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
c = collections.Counter(factor)
num = list(c.values())

ans = 1
for i in range(len(num)):
    ans *= (math.factorial(num[i] + n - 1) // (math.factorial(n - 1) * math.factorial(num[i])) % 1000000007)
    ans %= 1000000007
print(ans)

### FIXED CODE ###

import collections
n, m = map(int, input().split())

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
num = list(collections.Counter(factor).most_common())

def comb(n, r):
    tmp = 1
    for i in range(r):
        tmp *= n - i
    for i in range(r):
        tmp //= r - i
    return tmp

ans = 1
for x in num:
    ans *= (comb(x[1] + n - 1, x[1]) % 1000000007)
    ans %= 1000000007
print(ans)