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

import queue

H, W = map(int, input().split())
A = []
dist = []
black = []
for i in range(H):
    A.append(list(input()))
    dist.append([])
    for j in range(W):
        dist[i].append([1000000, False])
        if A[i][j] == '#':
            black.append([i, j])

q = queue.Queue(maxsize=-1)
for b in black:
    q.put(b)

max_dist = 0
while not q.empty():
    item = q.get()
    if i < 0 or j < 0 or i > H - 1 or j > W - 1:
        continue
    if A[item[0]][item[1]] == '#':
        dist[item[0]][item[1]][0] = 0
    else:
        a = dist[item[0] - 1][item[1]][0] if item[0] > 0 else 1000000
        b = dist[item[0]][item[1] - 1][0] if item[1] > 0 else 1000000
        c = dist[item[0] + 1][item[1]][0] if item[0] < H - 1 else 1000000
        d = dist[item[0]][item[1] + 1][0] if item[1] < W - 1 else 1000000
        dist[item[0]][item[1]][0] = min(a, b, c, d) + 1
        if dist[item[0]][item[1]][0] > max_dist:
            max_dist = dist[item[0]][item[1]][0]

    if item[0] > 0 and not dist[item[0] - 1][item[1]][1]:
        q.put([item[0] - 1, item[1]])
        dist[item[0] - 1][item[1]][1] = True
    if item[1] > 0 and not dist[item[0]][item[1] - 1][1]:
        q.put([item[0], item[1] - 1])
        dist[item[0]][item[1] - 1][1] = True
    if item[0] < H - 1 and not dist[item[0] + 1][item[1]][1]:
        q.put([item[0] + 1, item[1]])
        dist[item[0] + 1][item[1]][1] = True
    if item[1] < W - 1 and not dist[item[0]][item[1] + 1][1]:
        q.put([item[0], item[1] + 1])
        dist[item[0]][item[1] + 1][1] = True

print(max_dist)

### FIXED CODE ###

H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) for s in A]

	BC = []
	for i in range(M):
		b, c = map(int, input().split(" "))
		BC.append((c, b))

	BC.sort(reverse=True)
	A.sort()

	for i in BC:
		c, b = i
		if A[0] >= c:
			continue

		tmp = bisect_left(A, c)
		if tmp <= b:
			A[:tmp] = [c] * tmp
		elif tmp > b:
			A[:b] = [c] * b

		A.sort()

	print(sum(A))


if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


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

import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
S = [0]*Q

for i, bc in enumerate(BC):
  b = bc[0]
  c = bc[1]
  s = 0
  a[a == b] = c
  S[i] = a.sum()

[print(i) for i in S]

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
s_old = 0
for k, v in a_c.items():
    s_old += k*v
for bc in BC:
  b = bc[0]
  c = bc[1]
  s = s_old
  if b in a_c:
    n = a_c.pop(b)
    a_c[c]+=n
    s-=n*b
    s+=n*c
  print(s)
  s_old = s
### BUGGY CODE ###

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

p = [((1+int(i))*int(i)/2)/int(i) for i in input().split()]


res = 0
for j in range(N-K+1):
  res = max(res,sum(p[j:j+K]))
  
print(res) 

### FIXED CODE ###

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

p = [((1+int(i))*int(i)/2)/int(i) for i in input().split()]

m = check = sum(p[0:K])
for i in range(K,N):
  check = check+p[i]-p[i-K]
  m = max(m,check)
print(m)
### BUGGY CODE ###

from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    result = ""
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(x):
        if (i-1)%num_s==0 and (i-1)%num_t==0:
            if s[(i-1)//num_s] == t[(i-1)//num_t]:
                result = result+s[(i-1)//num_s]
            else:
                print(-1)
                sys.exit()
        elif (i-1)%num_s==0:
            result = result+s[(i-1)//num_s]
        elif (i-1)%num_t==0:
            result = result+t[(i-1)//num_t]
        else:
            result = result+"a"
    print(x)
else:
    print(-1)

### FIXED CODE ###

from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(0, x, num_s):
        if i%num_t==0 and s[i//num_s]!=t[i//num_t]:
            print(-1)
            sys.exit()
    print(x)
else:
    print(-1)
### BUGGY CODE ###

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)
### BUGGY CODE ###

N = input()
A = list(map(int, input().split()))
num = 1
for i in A:
  if 0 in A:
    num = 0
    break
  elif num > 1000000000000000000:
    break
  num = num*int(i)
if num > 1000000000000000000:
  print(-1)
else:
  print(num)


### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
newA = sorted(A,reverse=True)
num = 1
if 0 in A:
  num = 0
else:
  for i in newA:
    if num > 1000000000000000000:
      break
    num = num*int(i)
if num > 1000000000000000000:
  print(-1)
else:
  print(num)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
b={i:0 for i in range(1,n+1)}

for i in a:
    b[i]+=1

for i in b.values():
    print(i)
### BUGGY CODE ###

import math
 
K = int(input())
 
sum = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            sum += math.gcd(math.gcd(i+1, j+1), k+1)
            
print(sum)

### FIXED CODE ###

import math
 
K = int(input())
 
sum = 0
for i in range(K):
    for j in range(K):
        r = math.gcd(i+1, j+1)
        for k in range(K):
            sum += math.gcd(r, k+1)
            
print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
line = []
 
for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)
 
start = 1
end = N
second = []
 
for l in line:
    if l[0] == start:
        second.append(l[1])
    elif l[1] == start:
        second.append(l[0])
 
for l in line:
    if l[0] in second:
        if l[1] == end:
            print('POSSIBLE')
            exit()
    if l[1] in second:
        if l[0] == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
line = []

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
first = set()
second = set()

for l in line:
    if end in l:
        second.add(l[0])
        second.add(l[1])
    elif start in l:
        first.add(l[1])
        first.add(l[0])


for f in first:
    if f in second:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = []
for _ in range(n):
    s.append(list(input()))
count = 0
for i in range(n-1):
    for j in range(i+1, n):
        if Counter(s[i]) == Counter(s[j]):
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    if s in d:
        d[s] += 1
        ans += d[s]
    else:
        d[s] = 0
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
  l, r = map(int, input().split())
  deleted = S[l-1:r]
  print(len(deleted.split('AC'))-1)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

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

import math
N, P = list(map(int, input().split()))

now_max = 1

for i in range(int(math.pow(P, 1/N))+1, 0, -1):
    if P % (i ** N) == 0:
        now_max = i
        break

print(now_max)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

import numpy as np

N, k = list(map(int, input().split()))
if k > N:
    k = N
hs = list(map(int, input().split()))
hs = [0] + hs

# init
dp = np.zeros(N + 1).astype(int)
dp[2] = abs(hs[2] - hs[1])

# loop
if N > 2:
    for i in range(3, N + 1):
        for j in range(1, k + 1):
            if i <= j:
                continue
            if dp[i] == 0:
                dp[i] = dp[i-j] + abs(hs[i] - hs[i-j])
            else:
                dp[i] = min(dp[i-j] + abs(hs[i] - hs[i-j]), dp[i])

# output
print(dp[N])

### FIXED CODE ###

import numpy as np

N, k = list(map(int, input().split()))
if k > N:
    k = N
hs = list(map(int, input().split()))
hs = np.array([0] + hs)

# init
dp = np.zeros(N + 1).astype(int)
dp[2] = abs(hs[2] - hs[1])

# loop
if N > 2:
    for i in range(3, N + 1):
        """
        for j in range(1, k + 1):
            if i <= j:
                continue
            if dp[i] == 0:
                dp[i] = dp[i-j] + abs(hs[i] - hs[i-j])
            else:
                dp[i] = min(dp[i-j] + abs(hs[i] - hs[i-j]), dp[i])
        """
        x = max(1, i - k)
        dp[i] = np.min(dp[x:i] + np.abs(hs[i] - hs[x:i]))

# output
print(dp[N])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ma = max(a)
maketa = len(bin(ma))-2
#print(maketa)
res = 0
dic = {}
for i in range(maketa):
    dic[i] = 0
for j in range(N):
    count = 0
    while a[j] >= 1:
        dic[count] += a[j] % 2
        a[j] = a[j] // 2
        count += 1
for i in range(maketa):
    num = dic[i]
    res += num*(N-num)*(2**(i))
print(res%(10**9+7))


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ma = max(a)
maketa = len(bin(ma))-2
#print(maketa)
res = 0
dic = {}
for i in range(maketa):
    dic[i] = 0
for i in range(0,maketa):
    num = 0
    for j in range(N):
        #print(a[j] & (2**i))
        dic[i] += int((a[j] & (2**i))>>i)
        #count += 1
for i in range(maketa):
    num = dic[i]
    res += num*(N-num)*(2**(i))
print(res%(10**9+7))
### BUGGY CODE ###

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

ok = False
found = False
while not ok:
    money_digits = [int(mon) for mon in str(money)]

    for digit in money_digits:
        for dis_digit in dislike_digits:
            if digit == dis_digit:
                found = True
                break
        if found:
            money += 1
            break

    if not found:
        ok = True

print(money)


### FIXED CODE ###

price, size = map(int, input().split())
dislikes = list(map(int, input().split()))
likes = list(set(range(10)) - set(dislikes))
digits = [int(digit) for digit in str(price)]
r_digits = list(reversed(digits))
res = []
for i in range(len(r_digits)):
    if r_digits[i] in likes:
        res.append(r_digits[i])
    elif max(likes) > r_digits[i]:
        res = [min(likes) for i in range(i)] + [min(x for x in likes if x > r_digits[i])]
    else:
        res = [min(likes) for i in range(i+1)]
        if i == len(r_digits)-1:
            res.append(min(x for x in likes if x > 0))
            
        else:
            r_digits[i+1] += 1

ans = "".join([str(num) for num in list(reversed(res))])
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
if m <= n:
  print(0)
else:
  Dif_X = []
  for i in range(m-1):
    Dif_X += [X[i+1]-X[i]]
  count = 0  
  while count < n-1:
    Dif_X[Dif_X.index(max(Dif_X))] = 0
    count += 1
  print(sum(Dif_X))

### FIXED CODE ###

n,m = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
if m <= n:
  print(0)
else:
  Dif_X = []
  for i in range(m-1):
    Dif_X += [X[i+1]-X[i]]
  Sum_Dif_X = sum(Dif_X)  
  Sorted_Dif_X = sorted(Dif_X, reverse = True)
  count = 0  
  while count < n-1:
    Sum_Dif_X -= Sorted_Dif_X[count]
    count += 1
  print(Sum_Dif_X)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=k-q

for i in range(n):
    print("Yes" if a.count(i)+point>0 else "No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=[k-q for i in range(n)]
for i in a:
    point[i]+=1

for i in point:
    print("Yes" if i>0 else "No")
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    aa=[]
    for _ in range(n):
        a = readline().strip()
        if a in aa:
            aa.remove(a)
        else:
            aa.append(a)
    print(len(aa))
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    d={}
    for _ in range(n):
        a = readline().strip()
        if a in d:
            d[a]+=1
        else:
            d[a]=1
    cnt=0
    for key in d:
        if d[key]%2==1:
            cnt+=1
    print(cnt)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
s = input()
a = []
ans = 0
def dfs(st, num):
    if num == n:
        global ans, a
        a.append(st)
        ans += 1
        return        
    if s[num] not in st:
        dfs(st + s[num], num+1)
        dfs(st, num+1)
    else:
        dfs(st, num+1)


dfs("", 0)
print(ans-1)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = list(input())
c = Counter(s)
ans = 1
for i in c.values():
    ans =  (ans * (i+1)) % 1000000007
print(ans-1)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
#xR+yG+zB=Nの自然数解の個数
ans=0
for x in range(int(N/R)+1):
    for y in range(int(N/G)+1):
        nokori=N-x*R-y*G
        if nokori>=0 and nokori%B==0:
            ans+=1
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
#xR+yG+zB=Nの自然数解の個数
ans=0
for x in range(int(N/R)+1):
    for y in range(int(N/G)+1):
        nokori=N-x*R-y*G
        if nokori>=0 and nokori%B==0:
            ans+=1
print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
for i in range(1,N+1):
  print(L.count(i))

### FIXED CODE ###

import collections
S=0
N=int(input())
L=list(map(int,input().split()))
c = collections.Counter(L)
for i in range(1,N+1):
  print(c[i])
### BUGGY CODE ###

from collections import defaultdict
dd = defaultdict(lambda:[])
N, M = map(int, input().split())
temp = list(map(int, input().split()))
li_h = [0]
li_h.extend(temp)
for i in range(M):
    a, b= map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
#print(dd)
ans = 0
d = defaultdict(lambda:True)
for i in range(1, N+1):
    d[i] = True
li_dd = []
for i in dd:
    li_dd.append(i)
#print(li_dd)
for i in range(1, N+1):
    if i not in li_dd:
        ans += 1
    else:
        if not d:
            continue
        else:
            for k in dd[i]:
                if li_h[k] < li_h[i]:
                    d[k] = False
                elif li_h[k] == li_h[i]:
                    d[k] = False
                    d[i] = False
                else:
                    d[i] = False
            if d[i]:
                ans += 1
                #print(i)
            else:
                continue
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
dd = {}
for i in range(1, N+1):
    dd[i] = []
temp = list(map(int, input().split()))
li_h = [0]
li_h.extend(temp)
for i in range(M):
    a, b= map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
#print(dd)
ans = 0
d = {}
for i in range(1, N+1):
    d[i] = True
for i in range(1, N+1):
        if not d:
            continue
        else:
            for k in dd[i]:
                if li_h[k] < li_h[i]:
                    d[k] = False
                elif li_h[k] == li_h[i]:
                    d[k] = False
                    d[i] = False
                    break
                else:
                    d[i] = False
                    break
            if d[i]:
                ans += 1
                #print(i)
            else:
                continue
print(ans)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    for i in range(0, N):
        U[int(S[i:N])%P] += 1
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    t, s = 0, 1
    for i in range(N-1, -1, -1):
        t = (int(S[i])*s+t)%P
        U[t] += 1
        s = s*10%P
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)
### BUGGY CODE ###

import numpy as np
h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

a = np.zeros((h, w), dtype=np.int64)
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for i in range(h):
    k = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in range(h):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in reversed(range(h)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
a = np.where(a == 0, 0, a-3)
print(np.max(a))


### FIXED CODE ###

h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

a = [[0]*w for _ in range(h)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for i in range(h):
    k = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in range(h):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in reversed(range(h)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
b = max([max(i) for i in a])
print(0 if b == 0 else b-3)
### BUGGY CODE ###

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

x = [0]*N

for i in range(N):
    for j in range(N):
        if j % 2 == 0:
            x[i] += A[i-(j+1)]
        else:
            x[i] -= A[i-(j+1)]

for i in range(N):
    print(str(x[i]), end="")
    if i != N-1:
        print(" ", end="")


### FIXED CODE ###

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

x = [0]*N

for i in range(N):
    if i % 2 == 0:
        x[0] += A[i]
    else:
        x[0] -= A[i]

for i in range(1,N):
    x[i] = int( 2 * ( A[i-1] - x[i-1] / 2 ) )

for i in range(N):
    print(str(x[i]), end="")
    if i != N-1:
        print(" ", end="")
### BUGGY CODE ###

from collections import deque

def main():
    n = int(input())
    s = deque(sorted(["".join(sorted(input())) for i in range(n)]))
    ans = 0
    while len(s) != 0:
        cnt = s.count(s[0])
        for i in range(cnt):
            s.popleft()
        if cnt == 1:
            continue
        ans += (cnt * (cnt - 1)) // 2
    print(int(ans))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    s = collections.Counter(s)
    ans = 0
    for i in s.values():
        ans += (i*(i-1))//2
    print(ans)

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

import collections
import copy

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

x = int(input())
master_c = prime_factorize(x)
if len(master_c) == 1:
    print(x-1)
else:
    min_num = x-1
    for i in range(2,int(x/2)):
        if x % i == 0:
            num = int(i+(x/i)-2)
            if num < min_num:
                min_num = num
    print(min_num)

### FIXED CODE ###

import math
x = int(input())
x_sqrt = int(math.sqrt(x))

min_num = x-1
for i in range(2,x_sqrt+2):
    if x % i == 0:
        num = i+int(x/i)-2
        if num < min_num:
            min_num = num
print(min_num)
### BUGGY CODE ###

def change_dict(string):
	dic = {}
	for ch in set(string):
		dic[ch] = string.count(ch)
	return dic

n = int(input())
st = []
for i in range(n):
	st.append(change_dict(input()))
cnt = 0

for i in range(n-1):
	for j in range(i+1,n):
		if st[i]==st[j]:
			cnt+=1

print(cnt)

### FIXED CODE ###

n = int(input())
dic = {}
ans = 0
for i in range(n):
	tmp = list(input())
	sorted_str = "".join(sorted(tmp))
	if not(sorted_str in dic):
		dic[sorted_str] = 0
	else:
		dic[sorted_str] += 1
		ans += dic[sorted_str]

print(ans)