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

#!/usr/bin/env python3
import sys
import bisect as bi


def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    for _ in range(M):
        Max = A.pop()
        bi.insort(A, Max//2)
    print(sum(A))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq as q
import math

def solve(N: int, M: int, A: "List[int]"):
    q.heapify(A)
    for _ in range(M):
        Max = q.heappop(A)
        q.heappush(A, math.ceil(Max/2))
    print(-sum(A))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [-int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

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

import sys
import math

input = lambda: sys.stdin.readline().rstrip()


def erastosthenes(num):

    if num <= 1:
        return []
    if num == 2:
        return [2]

    input_list = [False if i % 2 == 0 else True for i in range(num)]
    input_list[0] = False
    input_list[1] = False
    input_list[2] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            prime_list = [i for i, b in enumerate(input_list) if b]
            return prime_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def solve():
    A, B = map(int, input().split())
    prime_list = erastosthenes(min(A, B))
    ans = 1
    for pl in prime_list:
        if A % pl == 0 and B % pl == 0:
            ans += 1

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import math
input = lambda: sys.stdin.readline().rstrip()


def factorize(n):
    b = 2
    fct = set()
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct |= set([b])
        b = b + 1
    if n > 1:
        fct |= set([n])
    return fct


def solve():
    A, B = map(int, input().split())
    ap = factorize(A)
    bp = factorize(B)
    ans = 1 + len(ap & bp)
    print(ans)


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

import sys
input = sys.stdin.readline
N = int(input())
A_array = [list(map(int, input().split())) for _ in range(N)]

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
while(1):
    flag = 0
    match_array = [0] * N
    for i in range(N):
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
print(ans_date)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A_array = [list(map(int, input().split())) for _ in range(N)]

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
first_flag = 1
while(1):
    flag = 0
    match_array = [0] * N
    if first_flag:
        match_candidate = [i for i in range(N)]
        first_flag = 0
    next_match = []
    for i in match_candidate:
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
            next_match.append(i)
            next_match.append(vs)
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
    match_candidate = next_match
print(ans_date)
### BUGGY CODE ###

S = input()
B = [0]*2019
B[0]+=1

for i in range(len(S)):
    B[int(S[-i-1:])%2019]+=1

ans=0

for j in range(2019):
    ans+=(B[j]-1)*B[j]/2

print(int(ans))

### FIXED CODE ###

from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

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

import bisect
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort()
idx=0
for i in range(M):
	b,c=map(int,input().split())
	t=bisect.bisect_left(A,c)
	if t>0:
		[bisect.insort_left(A,c) for i in range(min(t,b))]
		A=A[min(t,b):]

print(sum(A))

### FIXED CODE ###

N,M=map(int,input().split())
A=[]
[A.append([int(i),1]) for i in input().split()]
for i in range(M):
	A.append(list(map(int,input().split()))[::-1])
A.sort(reverse=True)
cnt=0
ans=0
for a in A:
	if N<=(cnt+a[1]):
		ans+=(N-cnt)*a[0]
		break
	else:
		ans+=a[0]*a[1]
		cnt+=a[1]
print(ans)
### BUGGY CODE ###

K = int(input())

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
    
def solution(K):
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):

                ans += euclid(euclid(i,j), euclid(j,k))
    
    print(ans)

solution(K)


### FIXED CODE ###

K = int(input())

import functools

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def gcd(nums):
    return functools.reduce(euclid, nums)

def solution(K):
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                num = (i,j,k)
                ans += gcd(num)
    print(ans)

solution(K)
### BUGGY CODE ###

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(i8(b1[:,:],i8,i8,i8,i8),cache=True)
def solve(road_map,ch,cw,dh,dw):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    max_l = 2<<30
    used_map = np.full(h*w,max_l,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        tl,n = heapq.heappop(queue)
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    heapq.heappush(queue,(loop,next_n))

    ans = used_map[goal]
    if ans == max_l:
        return -1
    else:
        return ans

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(road_map,ch,cw,dh,dw))



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

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

for i in range(0,M):
    b,c = map(int,input().split())
    for j in range(0,b):
        A.append(c)

A.sort()

result = 0
start = len(A)-1
for k in range(start,start-N,-1):
    result += A[k]
print(result)


### FIXED CODE ###

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

for i in range(0,M):
    b,c = map(int,input().split())
    cards.append((c,b))

cards.sort()
cards.reverse()

result = 0
total = N
for num, cnt in cards:
    total -= cnt
    result += num*cnt
    if total < 0:
        result += num * total
        break
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a = int(input())
numlist = []
for i in range(a):
	b = int(input())
	if b in numlist:
		numlist.remove(b)
	else:
		numlist.append(b)
print(len(numlist))

### FIXED CODE ###

# -*- coding: utf-8 -*-
a = int(input())
b = set()
for i in range(a):
	b ^= {input()}
print(len(b))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = [0] * N
for i,a in enumerate(A):
    for n in range(N):
        if i == n:
            pass
        else:
            ans[n] = ans[n]^a
print(*ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
xorsum = 0
for a in A:
    xorsum = xorsum^a
ans = [xorsum] * N
for i,a in enumerate(A):
    ans[i] = ans[i] ^ a
print(*ans)
### BUGGY CODE ###

import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))


    res = 0

    for i in range(1,30):
        tank = []
        for eb in b:
            tank.append(eb - ((eb>>i)<<i))
        tank.sort()

        cnt = 0

        for elt in a:
            e = elt - ((elt >> i) << i)

            cnt += bisect.bisect_left(tank, (1<<i)-e ) - bisect.bisect_left(tank, (1<<(i-1))-e)
            cnt += bisect.bisect_left(tank, (1<<(i+1))-e ) - bisect.bisect_left(tank, 3*pow(2,i-1)-e)
        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    res = 0
    p = 0

    for i in range(1,30):
        p += 1<<(i-1)
        A = []
        B = []

        for j in range(n):
            A.append(a[j]&p)
            B.append(b[j]&p)
        A.sort()
        B.sort()

        cnt = 0

        q2 = p+1
        q1 = q2>>1
        q3 = q2<<1

        k1,k2,k3,k4 = 0,0,0,0

        for j in range(n-1,-1,-1):
            while k1 < n and A[j]+B[k1] < q1:
                k1 += 1
            while k2 < n and A[j]+B[k2] < q2:
                k2 += 1
            while k3 < n and A[j]+B[k3] < 3*q1:
                k3 += 1
            while k4 < n and A[j]+B[k4] < q3:
                k4 += 1
            cnt += k4 + k2 - k1 - k3

        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


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

import sys
n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:
  print(-1)
  sys.exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(a,reverse=True)

ans=1
if b[-1]==0:
    print(0) 
else:
    for i in a:
        ans=ans*i
        if ans>10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

S=list(input())
Q=int(input())
T=[]
for i in range(Q):
  T.append(input().split())
for i in range(Q):
  if T[i][0]=="1":
    S.reverse()
  else:
    if T[i][1]=="1":
      S.insert(0,T[i][2])
    else:
      S.append(T[i][2])
print("".join(S))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
T=[]
m=0
for i in range(Q):
  T.append(input().split())
for i in range(Q):
  if T[i][0]=="1":
    if len(S)>1:
      if m==0:
        m=1
      else:
        m=0
        
  else:
    if T[i][1]=="1":
      if m==0:
        S.appendleft(T[i][2])
      else:
        S.append(T[i][2])
   
    else:
      if m==0:
        S.append(T[i][2])
      else:
        S.appendleft(T[i][2])
if m==0:
  print("".join(S))
else:
  S.reverse()
  print("".join(S))
### BUGGY CODE ###

import numpy as np


def func(x):
    if x == '.':
        return 2000
    else:
        return 0


H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append(list(map(func, input())))
a = np.array(b)

for i in range(H - 1):
    a[1:, :] = np.minimum(a[1:, :], a[:-1, :] + 1)
for i in range(H - 1):
    a[:-1, :] = np.minimum(a[:-1, :], a[1:, :] + 1)
for j in range(W - 1):
    a[:, 1:] = np.minimum(a[:,1:], a[:, :-1] + 1)
for j in range(W - 1):
    a[:, :-1] = np.minimum(a[:, :-1], a[:, 1:] + 1)

print(np.max(a))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break
### BUGGY CODE ###

a, b = map(int, input().split())

x = []

for i in range(a, b+1):
    x.append(format(i, "b"))

l = len(x[b - a])

ans = ""

for i in range(1, l+1):
    sum = 0
    for j in range(b-a+1):
        if len(x[j]) >= i:
            sum = sum + int(x[j][-i])
    if sum % 2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans

print(int(ans, 2))

### FIXED CODE ###

a, b = map(int, input().split())

N = b - a + 1

if a%2 == 0:
    if N%4 == 0:
        print(0)
    elif N%4 == 1:
        print(b)
    elif N%4 == 2:
        print(1)
    else:
        print(b + 1)
else:
    if N%4 == 0:
        print(a ^ b ^ 1)
    elif N%4 == 1:
        print(a)
    elif N%4 == 2:
        print(a ^ b)
    else:
        print(a ^ 1)
### BUGGY CODE ###

H, N = map(int, input().split())
dp = [0] * (H+1)
A, B = map(int, input().split())
for j in range(1, H+1):
    if j>A:
        dp[j] = max(dp[j-A] + B, dp[j])
    else:
        dp[j] = max(dp[0] + B, dp[j])
for i in range(1,N):
    A, B = map(int, input().split())
    for j in range(1, H+1):
        if j>A:
            dp[j] = min(dp[j-A] + B, dp[j])
        else:
            dp[j] = min(dp[0] + B, dp[j])
print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
dp = [0] * (H+1)
A, B = map(int, input().split())
for j in range(1, H+1):
    dp[j] = max(dp[max(j-A,0)] + B, dp[j])
for i in range(1,N):
    A, B = map(int, input().split())
    for j in range(1, H+1):
        dp[j] = min(dp[max(j-A,0)] + B, dp[j])
print(dp[H])
### BUGGY CODE ###

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
for i in range(1,n):
    A[i],B[i] = [int(j) for j in input().split()]
for i in range(1,q+1):
    P[i],X[i] = [int(j) for j in input().split()]

NIL = -1

class node:
    def __init__(self):
        self.value = 0
        self.child = []
        self.parent = NIL

def childadd(T,x):
    for i in range(len(T[x].child)):
        T[T[x].child[i]].value += T[x].value
        if T[T[x].child[i]].child != []:
            childadd(T,T[x].child[i])

for i in range(1,n+1):
    T[i] = node()
T[1] = node()
T[1].parent = 0
for i in range(1,n):
    if T[A[i]].parent != NIL:
        T[A[i]].child.append(B[i])
        T[B[i]].parent = T[A[i]]
    else:
        T[B[i]].child.append(A[i])
        T[A[i]].parent = T[B[i]]

for i in range(1,q+1):
    T[P[i]].value += X[i]

childadd(T,1)

for i in range(1,n+1):
    print(T[i].value,end = " ")


### FIXED CODE ###

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)

to = [[] for i in range(n+1)]
cnt = [0] * (n)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p-1] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
print(*cnt)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
al = "abcdefghijklmnopqrstuvwxyz"
al = {al[i]: i for i in range(26)}


def get(i):
    a = [0] * 26
    a[al[i]] = 1
    return a


def add(i, j):
    k = []
    for l, m in zip(i, j):
        k.append(l + m)
    return k


def sub(i, j):
    k = []
    for l, m in zip(i, j):
        k.append(l - m)
    return k


bit = [[0]*26 for _ in range(n+1)]


def ko(i, j):
    global bit
    while i <= n:
        bit[i] = add(bit[i], j)
        i += i & (-i)


def su(i):
    s = [0]*26
    while i != 0:
        s = add(s, bit[i])
        i -= i & (-i)
    return s


a = []
for i in range(n):
    ko(i + 1, get(s[i]))
    a.append(get(s[i]))
for _ in range(q):
    kind, i, j = [k for k in input().split()]
    i = int(i)
    if int(kind) == 1:
        ko(i, sub(get(j),a[i-1]))
        a[i-1] = get(j)
    else:
        j = int(j)
        b = sub(su(j), su(i-1))
        k = 0
        for i in b:
            if i != 0:
                k += 1
        print(k)


### FIXED CODE ###

n = int(input())
s = input()
q = int(input())


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


def get_int(s):
    abc = "abcdefghijklmnopqrstuvwxyz"
    return 1<<abc.index(s)


seg = SegmentTree([get_int(i) for i in s], int.__or__, 0)

for _ in range(q):
    q, i, j = input().split()
    if q == "1":
        seg.update(int(i) - 1, get_int(j))
    else:
        aa = seg.get_segment(int(i) - 1, int(j))
        ans = 0
        for i in range(26):
            if (aa >> i) & 1 == 1:
                ans += 1
        print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
d=0
for a in range(1,n+1):
 for b in range(1,n+1):
  for c in range(1,n+1):
   if (a+b)%k==0 and (b+c)%k==0 and (c+a)%k==0:d+=1
print(d)

### FIXED CODE ###

n,k=map(int,input().split())
if k%2==0:
 if n%k<k/2:print((n//k)**3+(n//k)**3)
 else:print((n//k)**3+((n//k)+1)**3)
else:print((n//k)**3)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
s = []
for i in range(n):
    m = list(input())
    m.sort()
    s.append(m)
# print(s)
count = 0
for i in range(n):
    for j in range(n):
        # if i != j:
        if i < j:
        #     print(s[i])
        # print(s[j])
            if s[i] == s[j]:
                count += 1
# for i in range(n):
    
print(count)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
s = []
for i in range(n):
    m = list(input())
    m.sort()
    s.append(m)
s.sort()
# print(s)
# print(s)
count = 0
ren = 1
r = []
rsum = [0] * n
for i in range(n-1):
    if s[i] == s[i+1]:
        count += 1
        ren += 1
        # print(ren)
        rsum[i+1] +=rsum[i]+1
    else:
        r.append(ren)
        ren = 1
        # print(ren)
r.append(ren)
        
for i in range(n):
    rsum[i] = rsum[i] + 1
    

def P(n, r):
    return factorial(n)//factorial(n-r)

def C(n, r):
    return P(n, r)//factorial(r)
# print(r)

# print(count)
# print("rsum:", rsum)
b = []
rsum.append(1)

for i in range(n):
    if rsum[i]>rsum[i+1]:
        b.append(rsum[i])
    #     continue
    # else:
    #     print(rsum[i+1])
    #     b.append(rsum[i+1])
# print("b", b)
count2 = 0
for i in b:
    # print(i)
    # print(C(i,2))
    count2 += C(i, 2)
print(count2)
    # if b[i]>=3:


# for i in range(n):
#     for j in range(n):
#         # if i != j:
#         if i < j:
#         #     print(s[i])
#         # print(s[j])
#             if s[i] == s[j]:
#                 count += 1
# # for i in range(n):
    
# print(count)