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

from collections import *
from itertools import *
import copy

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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[0 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        nagasalst=[]

        stack=[[r1,set([r1]),0]]
        while stack:
            a,visited,m=stack.pop()
            for b in data[a]:
                if not b in visited:
                    tempvisited=copy.copy(visited)
                    tempvisited.add(b)
                    A,B=min(a,b),max(a,b)
                    tempm=m+nagasa[str(A)+" "+str(B)]
                    if b==r2:
                        nagasalst.append(tempm)
                    else:

                        stack.append([b,tempvisited,tempm])
        nagasalst=min(nagasalst)
        mokutekiti[r1i][r2i]=nagasalst
        mokutekiti[r2i][r1i]=nagasalst

value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))


### FIXED CODE ###

from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))
### BUGGY CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e.sort(reverse=True)

for i in range(k):
  print(e[i])

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

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


### FIXED CODE ###

N = int(input())
emp = list(map(int,input().split()))
ans_l = [0]*(N+1)
for i in range(N-1):
    a = emp[i]
    ans_l[a] +=1
for i in range(1,N+1):
    print(ans_l[i])
### BUGGY CODE ###

import math
import collections
def main():

    N = int(input())

    d = collections.defaultdict(int)

    v = int(math.sqrt(N))
    for i in range(1, v+1):
        p = i
        while p <= N:
            d[p] += 1
            if p//i > v and p//i > i:
                d[p] += 1
            p += i
    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

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

Swap=[None]*M
for i in range(M):
    Swap[i]=set(map(int,input().split()))
 

i=1
finish=M
judge=1
judge_2=0
Matome=[]

for i in range(1,N+1):
    for j in range(finish):
        if i in Swap[j]:
            k=j
            break
    j+=1
    while j<finish:
        if i in Swap[j]:
            Swap[k]=Swap[k]|Swap[j]
            del Swap[j]
            finish-=1
            j-=1
        j+=1

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)
        


### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

from collections import deque


def bfs(si, sj):
    q = deque()
    used = set()
    if grids[sj][si] == '#':
        q.append([si, sj, 1])
    else:
        q.append([si, sj, 0])

    ans = float('inf')
    while len(q) > 0:
        prv_si, prv_sj, num_b = q.popleft()
        if [prv_si, prv_sj] == [W - 1, H - 1]:
            ans = min(ans, num_b)

        else:
            if prv_si < W - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj][prv_si + 1] == '#':
                    q.append([prv_si + 1, prv_sj, num_b + 1])
                else:
                    q.append([prv_si + 1, prv_sj, num_b])

            if prv_sj < H - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj + 1][prv_si] == '#':
                    q.append([prv_si, prv_sj + 1, num_b + 1])
                else:
                    q.append([prv_si, prv_sj + 1, num_b])

    return ans


H, W = map(int, input().split())
grids = [input() for _ in range(H)]
print(bfs(0, 0))


### FIXED CODE ###

H, W = map(int, input().split())
grids = [input() for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]
if grids[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(W):
    for j in range(H):
        if i == 0 and j == 0:
            continue

        if i - 1 < 0:
            val1 = float('inf')
        elif grids[j][i - 1] == '.' and grids[j][i] == '#':
            val1 = dp[j][i - 1] + 1
        else:
            val1 = dp[j][i - 1]

        if j - 1 < 0:
            val2 = float('inf')
        elif grids[j - 1][i] == '.' and grids[j][i] == '#':
            val2 = dp[j - 1][i] + 1
        else:
            val2 = dp[j - 1][i]

        dp[j][i] = min(val1, val2)
        #print(i,j,dp)

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

import sys
input = sys.stdin.readline

s=input()
s=s.strip("\n")
n=len(s)
res=0
d={}
t=[0]*(n+1)
d[0]=1
for i in range(1,n+1):
    t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
    if t[n-i] not in d:
        d[t[n-i]]=1
    else:
        d[t[n-i]]+=1
for i in d.values():
    if i<2:
      continue
    res+=int(i*(i-1)/2)
print(res)


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

N = int(input())
P = list(map(int,input().split()))
ans_count=[True]*N
for i in range(1,N):
    if(P[i]>=min(P[:i])):
        ans_count[i]=False
print(ans_count.count(True))



### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
minP = P[0]
ans = 1
for i in P[1:]:
    if(i<=minP):
        minP = i
        ans += 1
print(ans)
### BUGGY CODE ###

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


tab_h = [[0] * W for _ in range(H)]
tab_v = [[0] * W for _ in range(H)]

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp

# for i in range(H): print("#", tab_h[i])
# for i in range(H): print("#", tab_v[i])

ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

print(ans)

### FIXED CODE ###

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


tab_h = [[0] * W for _ in range(H)]
tab_v = [[0] * W for _ in range(H)]

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp

# for i in range(H): print("#", tab_h[i])
# for i in range(H): print("#", tab_v[i])

ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

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

from collections import defaultdict

def paint(v, d, c):
    if (v, d) in memo:
        return
    else:
        memo[(v, d)] = True
    if d == 0:
        color[v] = c
    elif d > 0:
        paint(v, d-1, c)
        for nb in graph[v]:
            paint(nb, d-1, c)

memo = {}
N, M = map(int, input().split())
color = [0] * N
graph = defaultdict(set)
for _ in range(M):
    i, j = map(int, input().split())
    graph[i-1].add(j-1)
    graph[j-1].add(i-1)
Q = int(input())
vdcs = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    vdcs.append((v-1, d, c))
vdcs.reverse()

for v, d, c in vdcs:
    paint(v, d, c)

for c in color:
    print(c)

### FIXED CODE ###

from collections import defaultdict

def paint(v, d, c):
    if color[v] == 0:
        color[v] = c
    if dp[v] >= d or d == 0:
        return
    dp[v] = d
    for nb in graph[v]:
        paint(nb, d-1, c)

N, M = map(int, input().split())
dp = [0] * N
color = [0] * N
graph = defaultdict(set)
for _ in range(M):
    i, j = map(int, input().split())
    graph[i-1].add(j-1)
    graph[j-1].add(i-1)
Q = int(input())
vdcs = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    vdcs.append((v-1, d, c))
vdcs.reverse()

for v, d, c in vdcs:
    paint(v, d, c)

for c in color:
    print(c)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
sum = 0
cnt = []
for i in range(N-1):
    if A[i] in cnt:
        sum += a
    else:
        for j in range(i+1, N):
            a = A[i] ^ A[j]
            sum += a
print(sum%1000000007)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

ans = 0
twopow = 1
for n in range(60):
    tmp = A & 1
    one = np.count_nonzero(tmp)
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    A >>= 1
    twopow = twopow << 1 % MOD

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

n = int(input())
inp_ls = input().split(" ")
a_ls = [int(e) for e in inp_ls[:n]]

i_dic = {}
for i,a in enumerate(a_ls):
	val = -a+(i+1)
	if val not in i_dic: i_dic[val] = []
	i_dic[val].append(i+1)

cnt = 0
for i in range(len(a_ls)):
	val = a_ls[i] + (i+1)
	cand_ls = i_dic.get(val, [])
	ok_ls = [j for j in cand_ls if j>(i+1)]
	cnt += len(ok_ls)

print(cnt)

### FIXED CODE ###

def count_j(arg_ls, th, b_idx, e_idx):
	if b_idx-1 == e_idx: return 0
	if b_idx == e_idx: return int(arg_ls[b_idx] > th)
	cent_idx = (e_idx+1 - b_idx) // 2 + b_idx
	cent_j = arg_ls[cent_idx]
	if cent_j > th:
		return count_j(arg_ls, th, b_idx, cent_idx-1) + (e_idx+1 - cent_idx)
	else:
		return count_j(arg_ls, th, cent_idx, e_idx)

n = int(input())
inp_ls = input().split(" ")
a_ls = [int(e) for e in inp_ls[:n]]

i_dic = {}
for i,a in enumerate(a_ls):
	val = -a+(i+1)
	if val not in i_dic: i_dic[val] = []
	i_dic[val].append(i+1)

cnt = 0
for i in range(len(a_ls)):
	val = a_ls[i] + (i+1)
	cand_ls = i_dic.get(val, [])
	result = count_j(cand_ls, (i+1), 0, len(cand_ls)-1)
	cnt += result

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

n = int(input())
res = 0
for i in range(n):
    res += i
print(res)

### FIXED CODE ###

n = int(input())
print((n*(n-1)//2))
### BUGGY CODE ###

def main():
    n=int(input())
    if n==1:
        print("Yes")
        print(2)
        print(1,1)
        print(1,1)
        exit()
    a=1
    while True:
        t=a*(a-1)//2
        if t>n:
            print("No")
            exit()
        if t==n:
            print("Yes")
            break
        a+=1
    print(a)
    s=set(range(1,1+n))
    l=[0]*(n+1)
    ans=[set()]

    for i in range(a):
        ll=set()
        for j in ans[:i+1]:
            for p in s&j:
                if p not in ll:
                    ll.add(p)
                    if l[p]==1:
                        s.remove(p)
                    else:
                        l[p]+=1
                    break

        for p in s:
            if len(ll)>=n*2//a:
                break
            else:
                if l[p]==0:
                    ll.add(p)
                    l[p]+=1

        ans.append(ll)
        q=[n*2//a]+list(ll)
        print(*q)


if __name__ == '__main__':
    main()








### FIXED CODE ###

def main():
    n=int(input())
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        print("Yes")
        m+=1
        print(m)
    else:
        print("No")
        exit()
    
    ans=[[m-1] for i in range(m)]
    c=1
    for i in range(m):
        for j in range(i+1,m):
            ans[i].append(c)
            ans[j].append(c)
            c+=1
    for i in ans:
        print(*i)


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

XKD=input().split(" ")
X=int(XKD[0])
K=int(XKD[1])
D=int(XKD[2])

X=abs(X)

ans=pow(10,15)+1
for i in range(K):
    minus_X=abs(X-D)
    plus_X=abs(X+D)
    if(minus_X<plus_X):
        X=minus_X
        ans=minus_X
    else:
        X=plus_X
        ans=plus_X

print(ans)    

### FIXED CODE ###


XKD=input().split(" ")
X=int(XKD[0])
K=int(XKD[1])
D=int(XKD[2])

X=abs(X)

if(X>=K*D):
    print(X-K*D)
else:
    k=int((X-X%D)/D)
    if((K-k)%2==0):
        print(X%D)
    else:
        print(abs(X%D-D))
### BUGGY CODE ###

N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
ans=sum(P[0:K])
flag=0
for i in range(len(P)-K+1):
  ans=max(ans,sum(P[i:i+K]))
print((ans+K)*0.5)

### FIXED CODE ###

N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
ans=[0]
ans[0]=sum(P[0:K])
for i in range(K,len(P)):
  ans.append(ans[-1]-P[i-K]+P[i])
print((max(ans)+K)*0.5)
### BUGGY CODE ###

N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(S+1)]for j in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        if j-A[i]>=0:
            dp[i+1][j]+=dp[i][j-A[i]]+dp[i][j]+dp[i][j]
        else:
            dp[i+1][j]+=dp[i][j]+dp[i][j]
print(dp[N][S]%998244353)

### FIXED CODE ###

from copy import copy
import numpy as np
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=np.zeros(S+100,np.int64)
dp[0]=1
for i in range(N):
    buf=copy(dp)
    dp=2*dp
    dp[A[i]:]+=buf[:-A[i]]
    dp%=998244353
print(dp[S]%998244353)
### BUGGY CODE ###

s = str(input())
q = int(input())
quer = [input().split() for i in range(q)]


for i in range(q):
    if quer[i][0] == '1':
        s = ''.join(list(reversed(s)))
    else:
        if quer[i][1] == '1':
            s = quer[i][2] + s
        else:
            s = s + quer[i][2]

print(s)


### FIXED CODE ###

s = str(input())
q = int(input())
quer = [input().split() for i in range(q)]

k = 0
fo = ''
re = ''
for i in range(q):
    if quer[i][0] == '1':
        k += 1
    else:
        if quer[i][1] == '1':
            if k % 2 == 0:
                re = re + quer[i][2]
            else:
                fo = fo + quer[i][2]
        else:
            if k % 2 == 0:
                fo = fo + quer[i][2]
            else:
                re = re + quer[i][2]

if k % 2 ==0:
    print( ''.join(list(reversed(re))) + s + fo)
else:
    print(''.join(list(reversed(fo))) + ''.join(list(reversed(s))) + re)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
heapq.heapify(A)
BC = []
for _ in range(M):
    BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
for b, c in BC:
    for _ in range(b):
         my_min = heapq.heappop(A)
         if c > my_min:
             heapq.heappush(A, c)
         else:
              heapq.heappush(A, my_min)

print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
heapq.heapify(A)
BC = []
for _ in range(M):
    BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x: x[1], reverse=True)

card = []
for b, c in BC:
    for _ in range(b):
         my_min = heapq.heappop(A)
         if c > my_min:
             heapq.heappush(A, c)
         else:
              heapq.heappush(A, my_min)
              break

print(sum(A))
### BUGGY CODE ###

from fractions import gcd

K = int(input())

res = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            res += gcd(gcd(a, b), c)

print(res)

### FIXED CODE ###

from math import gcd

K = int(input())

res = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            res += gcd(gcd(a, b), c)

print(res)
### BUGGY CODE ###

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

a_max = max(a)
# dp[i] : モンスターのHPをi減らすのに必要な魔力の最小値
dp = [0] * (h + a_max + 1)
dp[0] = 0

for i in range(1, h + a_max + 1):
    m = 10 ** 9
    for j in range(n):
        tmp = dp[i - a[j]] + b[j]
        if (m > tmp):
            m = tmp

    dp[i] = m

print(min(dp[h:]))


### FIXED CODE ###

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

a_max = max(a)
# dp[i] : モンスターのHPをi減らすのに必要な魔力の最小値
dp = [0] * (h + a_max + 1)
dp[0] = 0

for i in range(1, h + a_max + 1):
    m = 10 ** 9
    for j in range(n):
        tmp = dp[i - a[j]] + b[j]
        if (m > tmp):
            m = tmp

    dp[i] = m

print(min(dp[h:]))
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    if n == 1:
        print(a[0])
        return
    ok = 0
    ng = 10**9+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        b = [0]+list(ac([(i >= mid)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    def value(v):
        if n == 1:
            if v <= a[0]:
                return True
            else:
                return False
        b = [0]+list(ac([(i >= v)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            return True
        else:
            return False

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(b_search(0, 10**9+1, value))


main()
### BUGGY CODE ###

from math import factorial

num=int(input())
count=0

#for i in range(num):
#    str=input()
#    str=''.join(sorted(str))
#    str = ''.join(sorted(input()))
#    stl.append(str)
stl =[(''.join(sorted(input()))) for i in range(num)]

duplicate=[x for x in set(stl) if stl.count(x) > 1]
if duplicate:
    for dup in duplicate:
        n=stl.count(dup)
        count += factorial(n) // 2 // factorial(n - 2)
    
print(count)

### FIXED CODE ###

num=int(input())
stl =[''.join(sorted(input())) for i in range(num)]

#duplicate=[x for x in set(stl) if stl.count(x) > 1]

t = {}
for i in range(num):
  if stl[i] in t:
    t[stl[i]] += 1
  else:
    t[stl[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))