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

from heapq import heappush, heappop, heapify
from collections import deque
def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    isRoot = [True] * n
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        isRoot[b] = False

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    que = deque()
    que.append((0, root, -1))
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = que.popleft()
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                que.append((score - 1, to, node))

    while que:
        search(que)

    for i in range(n):
        print(parent[i] + 1)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = -1
    index = -1
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = index

for i in range(n):
    print(parent[i] + 1)
### BUGGY CODE ###

N = int(input())
a = map(int,input().split())
A = sorted([(b,a) for a, b in enumerate(a)])[::-1]
dp = [[-1 for _ in range(N+10)]for _ in range(N+10)]
#dp[x][y]: 活発度順でx+y人詰めた時,左にx人右にy人詰めたときの最大値
dp[0][0] = 0
import sys
sys.setrecursionlimit(100000000)

def memo(x, y):
    if x < 0 or y < 0: return -1000000000000 #ありえん
    if dp[x][y] != -1: return dp[x][y]
    val, pre = A[x+y-1][0], A[x+y-1][1]
    dp[x][y] = max(
            #x-1からくるパターン
            memo(x - 1,y) + abs(pre - (x - 1)) * val,
            #y-1からくるパターン
            memo(x, y - 1) + abs(pre - (N - y )) *val,
            )
    return dp[x][y]
ans = 0
for i in range(N): ans = max(ans, memo(i,N - i))
print(ans)


### FIXED CODE ###

N = int(input())
a = map(int,input().split())
A = sorted([(b,a) for a, b in enumerate(a)])[::-1]
dp = [[-1 for _ in range(N+10)]for _ in range(N+10)]
#dp[x][y]: 活発度順でx+y人詰めた時,左にx人右にy人詰めたときの最大値
dp[0][0] = 0
import sys
sys.setrecursionlimit(100000000)

def memo(x, y):
    if x < 0 or y < 0: return -1000000000000 #ありえん
    if dp[x][y] != -1: return dp[x][y]
    val, pre = A[x+y-1][0], A[x+y-1][1]
    dp[x][y] = max(
            #x-1からくるパターン
            memo(x - 1,y) + abs(pre - (x - 1)) * val,
            #y-1からくるパターン
            memo(x, y - 1) + abs(pre - (N - y )) *val,
            )
    return dp[x][y]
ans = 0
for i in range(N): ans = max(ans, memo(i,N - i))
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())

res = 0

for k in range(1,n//2+1):
    d = [0]*n
    for i in range(n):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

### FIXED CODE ###

n = int(input())
s = list(input())

res = 0

for k in range(1,n):
    d = [0]*n
    for i in range(n-k):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
tmp=[-1]*n
ans=0
for i in range(n):
  for j in range(n):
    if tmp[j]<a[i]:
      if tmp[j]==-1:ans+=1
      tmp[j]=a[i]
      break
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**9+1
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
t = input()
*c, = map(int, t.replace(*"W1").replace(*"R0"))

"""
1100 -> 0101 -> 0011
00
10110100 -> 00111100 -> 00011110 -> 00001111
"""

a = 0
i, j = 0, 1
while i + j < n:
    if c[i] == 1 and c[-j] == 0:
        a += 1
        i += 1
        j += 1
    elif c[i] == c[-j] == 0:
        i += 1
    elif c[i] == c[-j] == 1:
        j += 1
print(a)

### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
t = input()
*c, = map(int, t.replace(*"W1").replace(*"R0"))

"""
1100 -> 0101 -> 0011
00
10110100 -> 00111100 -> 00011110 -> 00001111
"""

a = 0
i, j = 0, 1
while i + j < n:
    if c[i] == 1 and c[-j] == 0:
        a += 1
        i += 1
        j += 1
    elif c[i] == c[-j] == 0:
        i += 1
    elif c[i] == c[-j] == 1:
        j += 1
    else:
        i += 1
        j += 1
print(a)
### BUGGY CODE ###

#import numpy as np
import math
import collections
import bisect


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


dp = [[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)]
for k in range(2):
    for i in range(c + 1):
        for j in range(d + 1):
            dp[i][j][1] = 0
            if j < b or i < a:
                dp[i][j][k] = 0

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = ((i * dp[i][j - 1][0]) % 998244353 + dp[i][j - 1][1]) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1]) % 998244353) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)


### FIXED CODE ###

#import numpy as np
import math
import collections
import bisect


def main():
    a, b, c, d = map(int, input().split())

    dp0 = [[1 for i in range(d + 1)] for j in range(c + 1)]
    dp1 = [[0 for i in range(d + 1)] for j in range(c + 1)]
    for i in range(c + 1):
        for j in range(d + 1):
            if j < b or i < a:
                dp0[i][j] = 0
                dp1[i][j] = 0
    for i in range(a, c + 1):
        for j in range(b, d + 1):
            # print(i, j, dp[i][j])
            if a == i and b == j:
                continue
            dp0[i][j] = ((i * dp0[i][j - 1]) % 998244353 + dp1[i][j - 1]) % 998244353
            dp1[i][j] = (j * (dp0[i - 1][j] + dp1[i - 1][j]) % 998244353) % 998244353

    print((dp0[c][d] + dp1[c][d]) % 998244353)


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

def prime(n,a,b):
    num=[i for i in range(n,1,-1) if n%i ==0 and a%i == 0 and b%i == 0]
    prime=[]
    p = 2
    while p <=n**0.5 and len(num) != 0:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

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

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2),a,b)
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import *
def gcd(n,m):
    while m != 0:
        n,m=m,n%m
    return n
def main():
    a,b=map(int,input().split(' '))
    g=gcd(a,b)
    cnt = 1
    g2 = int(sqrt(g))
    for i in range(2,g2+1):
        if g%i ==0:
            while g%i ==0:
                g //= i
            cnt += 1
    if g > 1:
        cnt += 1
    print(cnt)

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

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

def list_seki(l):
    S = 1
    for i in range(0, len(l)):
        S *= l[i]
    return S

for x in range(K, N):
    before = list_seki(A[x-K:x])
    after = list_seki(A[x-K+1:x+1])
    if after > before:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for x in range(K-1, N-1):
    if A[x-K+1] < A[x+1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from math import sqrt

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)] 
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False
    return(prime)
def f(n):
    ans = 0
    for i in range(1, int(sqrt(n)+1)):
        if n%i == 0:
            if i**2 == n:ans+=1
            else:ans += 2
    return(ans)
prime = SieveOfEratosthenes(10**6)
n = int(input())
ans = 0
for i in range(1, n):
    tem = n-i
    if not prime[tem]:
        ans += f(tem)
    else:
        ans += 2
#     print(tem ,ans)
print(ans)

### FIXED CODE ###

from math import *
MAX = 1000001; 
factor = [0]*(MAX + 1); 
  
def generatePrimeFactors(): 
    factor[1] = 1; 
   
    for i in range(2,MAX): 
        factor[i] = i; 
  
    for i in range(4,MAX,2): 
        factor[i] = 2; 
    i = 3; 
    while(i * i < MAX): 
        if (factor[i] == i): 
            j = i * i; 
            while(j < MAX):  
                if (factor[j] == j): 
                    factor[j] = i; 
                j += i; 
        i+=1
  
def calculateNoOFactors(n): 
    if (n == 1): 
        return 1; 
    ans = 1; 
    dup = factor[n]; 
    c = 1; 
    j = int(n / factor[n]); 
    while (j > 1): 
        if (factor[j] == dup): 
            c += 1; 
        else: 
            dup = factor[j]; 
            ans = ans * (c + 1); 
            c = 1; 
        j = int(j / factor[j]); 
    ans = ans * (c + 1); 
  
    return ans;
generatePrimeFactors()
# n = int(input())
# print(calculateNoOFactors(n))

n = int(input())
ans = 0
for i in range(1, n):
    tem = n-i
    ans += calculateNoOFactors(i)
#     print(tem ,ans)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
a = []
b = []
ans = 0
for i in range(N):
    a.append(i+1+A[i])
    b.append(i+1-A[i])
for i in a:
    ans += b.count(i)
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = []
b = []
ans = 0
for i in range(N):
    a.append(i+1+A[i])
    b.append(i+1-A[i])
b = Counter(b)
for i in a:
    ans += b[i]
print(ans)
### BUGGY CODE ###

N = int(input()) - 1

LARGE = 10**9+7

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0
# precompute
fac_list = [1]*(N+1)
fac = 1
for i in range(1, N+1):
    fac = (fac * i) % LARGE
    fac_list[i] = fac
    
fac_inv_list = [1]*(N+1)
for i in range(N+1):
    fac_inv_list[i] =  pow(fac_list[i], LARGE-2, LARGE)
    
def nCr(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE

def pat(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE


pat = 0
score = 0

for k in range(N+1):
    if k-1 >= N-k:
        res = (((fac_list[k-1]*fac_list[k]) % LARGE) * fac_inv_list[k-1-N+k]) % LARGE
        score = (score + (res - pat) * k) % LARGE
        # print(k, pat, res)
        pat = res
print(score)

### FIXED CODE ###

N = int(input()) - 1

LARGE = 10**9+7

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0
# precompute
fac_list = [1]*(N+1)
fac = 1
for i in range(1, N+1):
    fac = (fac * i) % LARGE
    fac_list[i] = fac
    
fac_inv_list = [1]*(N+1)
for i in range(N+1):
    fac_inv_list[i] =  pow(fac_list[i], LARGE-2, LARGE)
    
def nCr(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE

def pat(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE


pat = 0
score = 0

for k in range(N+1):
    if k-1 >= N-k:
        res = (((fac_list[k-1]*fac_list[k]) % LARGE) * fac_inv_list[k-1-N+k]) % LARGE
        score = (score + (res - pat) * k) % LARGE
        # print(k, pat, res)
        pat = res
print(score)
### BUGGY CODE ###

import sys
import numpy as np
stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())

B = []
for a in A:
    B.extend(A + a)
B.sort(reverse=True)

answer = sum(B[:M])
print(answer)


### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A,x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0 #握手するのがM人以上
while right > left + 1:
    mid = (left+right) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

X = np.searchsorted(A, right-A) #握手しない人数
Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()

shake = N*N - X.sum()
happy = (Acum[-1] - Acum[X]).sum() + (A * (N-X)).sum()
happy += (M-shake) * left
print(happy)
### BUGGY CODE ###

n = int(input())
ans = []
for i,a in enumerate([int(i) for i in input().split()]):
    if (n%2 == 0 and (i+1)%2 == 0) or (n%2 == 1 and (i+1)%2 == 1):
        ans.insert(0,str(a))
    else:
        ans.append(str(a))
print(' '.join(ans))


### FIXED CODE ###

n = int(input())
l,r = [],[]
for i,a in enumerate([int(i) for i in input().split()]):
    if (n%2 == 0 and (i+1)%2 == 0) or (n%2 == 1 and (i+1)%2 == 1):
        l.append(str(a))
    else:
        r.append(str(a))
for a in l[::-1]:
    print(a,end=' ')
for b in r:
    print(b,end=' ')
print()
### BUGGY CODE ###

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

cnt = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S - X - Y
    if 0 <= X <= K and 0 <= Y <= K and 0 <= Z <= K and X + Y + Z == S:
      cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
for x in range(K + 1):
  for y in range(K + 1):
    z = S - x - y
    if 0 <= z <= K:
      cnt += 1
      
print(cnt)
### BUGGY CODE ###

def solve(K, N):
    mod = 10**9 + 7
    T = [0] * (N + 1)
    T[0] = 1
    for i in range(K + N):
        T[N] = (T[N - 1] + T[N] * 26) % mod
        for j in reversed(range(1, N)):
            T[j] = (T[j - 1]  + T[j] * 25) % mod
        T[0] = (T[0] * 25) % mod
    return T[-1] % mod

def main():
    K = int(input())
    S = input()
    return solve(K, len(S))
        
print(main())


### FIXED CODE ###

def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    r = 0
    t = pow(26, K, mod)
    s = 1
    inv26 = pow(26, mod - 2, mod)
    inv = [0] * (K + 2)
    inv[1] = 1
    for i in range(2, K + 2):
        inv[i] = -inv[mod % i] * (mod // i) % mod
    for i in range(K + 1):
        r = (r + t * s) % mod
        t = (t * 25 * inv26) % mod
        s = (s * (N + i) * inv[i + 1]) % mod
    return r

        
print(main())
### BUGGY CODE ###

import queue
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
q = queue.Queue()
for i in range(H):
  for j in range(W):
    if L[i][j] == "#":
      q.put((i, j))
      
cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
count = 0
q_size = q.qsize()
result = -1
while q.qsize() > 0:
  now = q.get()
  for cand in cands:
    i = now[0] + cand[0]
    j = now[1] + cand[1]
    if i < 0 or i >= H or j < 0 or j >= W:
      continue
    if L[i][j] == ".":
      L[i][j] = "#"
      q.put((i, j))
  count += 1
  if count == q_size:
    count = 0
    q_size = q.qsize()
    result += 1

print(result)


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

def main():
    n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    max = 0

    while True:
        i = 0
        max += l[i]
        if max < x:
            ans += 1

        i += 1

    print(ans)

main()


### FIXED CODE ###

def main():
    n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    max = 0

    #while True:
        #i = 0
        #max += l[i]
        #if max < x:
            #ans += 1
        #i += 1

    for i in range(len(l)):
        max += l[i]
        if max <= x:
            ans += 1
    print(ans)

main()
### BUGGY CODE ###

n, m = list(map(int, input().rstrip().split(" ")))
members = [1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  while members[a-1] < 0:
    a = -members[a-1]
  while members[b-1] < 0:
    b = -members[b-1]
  if a != b:
    members[a-1] += members[b-1]
    members[b-1] = -a
    if members[a-1] > members[max_idx]:
      max_idx = a-1
print(members[max_idx])

### FIXED CODE ###

def root(x, root_ls):
  if root_ls[x] < 0:
    return x
  else:
    root_ls[x] = root(root_ls[x], root_ls)
    return root_ls[x]

def unite(a, b, root_ls):
  a = root(a, root_ls)
  b = root(b, root_ls)
  if a != b:
    root_ls[a] += root_ls[b]
    root_ls[b] = a
  
n, m = list(map(int, input().rstrip().split(" ")))
members = [-1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  unite(a-1, b-1, members)
print(max([-m for m in members]))
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
#input=sys.stdin.readline

def dfs(u,s):
  visited[u]=True
  ans_list[u]=s+dic_score[u]
  
  for v in tree_list[u]:
    if not visited[v]:
      dfs(v,ans_list[u])    
  return s

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

tree_list=[[] for _ in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  tree_list[a].append(b)
  tree_list[b].append(a)
#print(tree_list)

dic_score=defaultdict(int)
for i in range(Q):
  p,x=map(int,input().split())
  dic_score[p]+=x

ans_list=[0]*(N+1)
visited=[False]*(N+1)
dfs(1,0)

print(*ans_list[1:])

### FIXED CODE ###

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

def dfs(u,par):
  ans_list[u]+=ans_list[par]  
  for v in tree_list[u]:
    if v!=par:
      dfs(v,u)      
  return

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

tree_list=[[] for _ in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  tree_list[a].append(b)
  tree_list[b].append(a)
#print(tree_list)

ans_list=[0]*(N+1)
for i in range(Q):
  p,x=map(int,input().split())
  ans_list[p]+=x

dfs(1,0)

print(*ans_list[1:])
### BUGGY CODE ###

N,K = map( int, input().split() )
h_list = list( map( int, input().split() ) )
h_list.append(0)
result_list = [10**10]*N
result_list[0] = 0
for i in range(N):
    for j in range(1,min(K+1,N-i)):
        result_list[i+j] = min(result_list[i+j], result_list[i] + abs( ( h_list[i+j] - h_list[i]) ) )
print(result_list[N-1])

### FIXED CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i,Hi in enumerate(H[1:],1):
    s = max(0,i-K)
    dp[i] = min( [ t + abs( Hi - hl ) for hl,t in zip(H[s:i], dp[s:i]) ] )
print(dp[N-1])
### BUGGY CODE ###

def str_order(str):
    temp_ls = []
    for _s in str:
        temp_ls.append(_s)

    temp_ls.sort()

    temp_val = ""
    for _st in temp_ls:
        temp_val += _st

    return(temp_val)

def pair_cal(int):
    cnt = 0
    for _i in range(1, int):
        cnt += _i

    return cnt

N = int(input())

str_ls = []
for _n in range(0, N):
    str_ls.append(str_order(str(input())))

uniq_ls = list(set(str_ls))
# print(uniq_ls)

str_ls.sort()
# print(str_ls)

total_cnt = 0

for _u in uniq_ls:
    count_num = str_ls.count(_u)
    if count_num != 1:
        total_cnt += pair_cal(count_num)

print(total_cnt)

### FIXED CODE ###

n = int(input())
s = [sorted(input()) for i in range(n)]

count = 0
dic1 = {}
# print(s)
for i in range(n):
    # print(s[i])
    so = ''.join(s[i])
    # print(so)
    if so in dic1:
        count += dic1[so]
        dic1[so] += 1
    else:
        dic1[so] = 1
    # print(count, dic1)
print(count)
### BUGGY CODE ###

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

def solve():
    x = 1
    for i in range(N):
        x = x * l[i]

    if x > (1000000000000000000):
        x = -1
        return str(x)
    else:
        return str(x)

print(solve())

### FIXED CODE ###

import sys

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

def solve():
    if 0 in l:
        return (0)
        sys.exit()

    x = 1
    for i in range(N):
        x = x * l[i]
        if x > (1000000000000000000):
            x = -1
            break

    return str(x)

print(solve())
### BUGGY CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    bin_list = [[0, 0] for _ in range(60)]

    for num in a:
        for j in range(60):
            b = (num >> j) & 1
            bin_list[j][b] += 1

    sum_ = 0
    for j in range(60):
        sum_ += bin_list[j][0] * bin_list[j][1] * (2 ** j) % mod
        sum_ %= mod

    print(sum_)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ret = 0
    magni = 1
    for j in range(60):
        bin_cnt = [0, 0]
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_cnt[b] += 1
        x, y = bin_cnt
        ret += x * y * magni % mod
        magni = magni * 2 % mod

    ret %= mod

    print(ret)


if __name__ == '__main__':
    main()