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

#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

adj = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = (a - 1, b - 1)
    adj[a].append(b)
    adj[b].append(a)
    
values = [0 for _ in range(N)]
    
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

print(" ".join(map(str, values)))
    

### FIXED CODE ###

#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()

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

adj = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = (a - 1, b - 1)
    adj[a].append(b)
    adj[b].append(a)
    
values = [0 for _ in range(N)]
    
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

print(" ".join(map(str, values)))
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
S = [int(i) for i in input().split()]

def solve() :
    S.sort()
    T = [S.pop()]
    for i in range(N) :
        T.sort(reverse=True)
        for j in range(2**i) :
            if S[0] >= T[j] :
                return 'No'
            
            pos = bisect_left(S, T[j])
            T.append(S.pop(pos-1))
            
    return 'Yes'
    
print(solve())

### FIXED CODE ###

N = int(input())
S = [int(i) for i in input().split()]

def solve() :
    S.sort()
    par = [S.pop()]
    rst = S
    for _ in range(N) :
        n_par = []
        n_rst = []
        
        for p in par[::-1] :
            flg = True
            while rst :
                if rst[-1] < p :
                    n_par.append(rst.pop())
                    flg = False
                    break
                else :
                    n_rst.append(rst.pop())
            if flg :
                return 'No'
                
        par += n_par
        par.sort()
        rst += n_rst
        rst.sort()
            
    return 'Yes'
    
print(solve())
### BUGGY CODE ###

from collections import defaultdict

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]
    checked = defaultdict(lambda: 0)

    while queue:
        qsn = queue.pop()

        if checked[qsn]: continue

        checked[qsn] = 1
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

S = input()
T = input()
DP = [[""]*(len(T)+1) for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j] + S[i]
        else:
            if len(DP[i+1][j]) > len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i+1][j]
            else:
                DP[i+1][j+1] = DP[i][j+1]
print(DP[-1][-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline

S = input().rstrip()
T = input().rstrip()
DP = [[0]*(len(T)+1) for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j]+1
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])

m,n = len(S),len(T)
ans = ''
while m>0 and n>0:
    if DP[m][n] == DP[m][n-1]:
        n-=1
    elif DP[m][n] == DP[m-1][n]:
        m -= 1
    else:
        m,n = m-1,n-1
        ans = T[n]+ans
print(ans)
### BUGGY CODE ###

# 約数の個数を出力
def divisor_counter(n):
    # if n < 1: return -1
    if n < 1: return 0
    if n == 1: return 1
    count = 0
    for i in range(1, n):
        if i*i > n: break
        if n % i == 0:
            count += 1 if n == i*i else 2
    return count

n = int(input())

s = 0
for i in range(1, n+1):
    s += i*divisor_counter(i)
print(s)


### FIXED CODE ###

n = int(input())
s = 0
for m in range(1, n+1):
    k = n // m
    s += k * (k+1) * m // 2
print(s)
### BUGGY CODE ###

from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    while len(C):
        d = max(C.keys())
        n = (2 ** d.bit_length()) - d
        if d != n:
            dc = C[d]
            dn = C[n] if n in C else 1
            mn = min(dc, dn)
            C[d] -= mn
            if n in C:
                C[n] -= mn
                ans += mn
        else:
            if C[d] >= 2:
                ans += C[d]//2
                C[d] -= 2 * C[d]//2
            elif C[d] >= 1:
                C[d] -= 1

        if C[d] == 0:
            del C[d]
        if n in C and C[n] == 0:
            del C[n]
    return ans


if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))


### FIXED CODE ###

from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in reversed(sorted(As)):
        n = (2 ** d.bit_length()) - d
        if d != n:
            if C[d] > 0 and C.get(n, 0) > 0:
                C[d] -= 1
                C[n] -= 1
                ans += 1
        else:
            ans += C[d]//2
            C[d] = 0
    return ans
 
 
if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))
### BUGGY CODE ###


from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs():
    
    label = 1
    while False in seen:
        i = seen.index(False)
        seen[i] = label
        que = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    que.append(nec)
        label += 1


dfs()
for i in range(N):
    count = seen.count(seen[i]) -1 -len(graph[i])
    if bgraph[i]:
        for j in bgraph[i]:
            if seen[i] == seen[j]:
                count -= 1
    cnt.append(count)

print(*cnt)


### FIXED CODE ###

#計算時間が足りない　何がダメなのか　工夫が足りない　研究が必要
from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = [0]*N
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]
seenb = [False for _ in range(N)]
def dfs():
    labelb = 1
    #while False in seen:
    for i in range(N):
        if seen[i] != False: continue
        label = 1
        #i = seen.index(False)
        seen[i] = label
        seenb[i] = labelb
        que = deque([i])
        seg = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    seenb[nec]=labelb
                    que.append(nec)
                    seg.append(nec)
                    label += 1
        for iii in seg:
            seen[iii] = label

        labelb += 1

dfs()
for i in range(N):
    count = seen[i] - 1 -len(graph[i])
    if bgraph[i] and seen[i]>=2:
          for j in bgraph[i]:
                if seenb[i] == seenb[j]:
                    count -= 1
    cnt[i]=count
print(*cnt)
### BUGGY CODE ###

def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if s[i:j] in s[j:] and ans < j-i+1:
                ans = j-i
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>=R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
        elif z[i-L]<R-i: # 過去の結果が全て使える
            z[i]=z[i-L]
        else: # 過去の結果が一部使える
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()
### BUGGY CODE ###

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

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] #X - Yの最大値
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] #X - Yの最小値

if N % 2 == 0: #偶数-->最後の一個はY
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        # print (dp2[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])



else: #奇数-->最後の一個はX
    for i in range(N):
        dp1[i][i + 1] = A[i]
        # print (dp1[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])


### FIXED CODE ###

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

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] #X - Yの最大値
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] #X - Yの最小値

if N % 2 == 0: #偶数-->最後の一個はY
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        # print (dp2[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])



else: #奇数-->最後の一個はX
    for i in range(N):
        dp1[i][i + 1] = A[i]
        # print (dp1[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])
### BUGGY CODE ###

#!/usr/bin/env pypy3


def div_ceil(a, b):
    return (a + b - 1) // b


def solve(n, xs, ys):
    ctr = 0
    for i in range(n)[::-1]:
        diff = div_ceil(xs[i], ys[i]) * ys[i] - xs[i]
        ctr += diff
        for j in range(i + 1):
            xs[j] += diff
    return ctr


def main():
    n = int(input())
    data = (tuple(int(x) for x in input().split()) for _ in range(n))
    xs, ys = (list(line) for line in zip(*data))
    print(solve(n, xs, ys))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3


def div_ceil(a, b):
    return (a + b - 1) // b


def solve(n, xs, ys):
    ctr = 0
    for i in range(n)[::-1]:
        xs[i] += ctr
        diff = div_ceil(xs[i], ys[i]) * ys[i] - xs[i]
        ctr += diff
    return ctr


def main():
    n = int(input())
    data = (tuple(int(x) for x in input().split()) for _ in range(n))
    xs, ys = (list(line) for line in zip(*data))
    print(solve(n, xs, ys))


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

h, w = map(int, input().split())
c = [input() for i in range(h)]
INF = 10 ** 9


ans = 0
for wi in range(w - 1):
    dq = [[0] * (h + 1) for i in range(h + 1)]
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            if c[i][wi] == c[i + diff][wi + 1]:
                cnt += 1
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1 + diff][i + 1] = dq[i + diff][i] - (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            if c[i + diff][wi] == c[i][wi + 1]:
                cnt += 1
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1][i + 1 + diff] = dq[i][i + diff] - (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])  
    
    dp = [[INF] * (h + 1) for i in range(h + 1)]
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)
    

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

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

max = 0

for i in range(n-k+1):
    sum = 0
    for j in range(k):
        sum += p[i+j]
    if sum > max:
        max = sum
        m = i


ave = 0
for i in range(m, m+k):
    ave += (p[i] + 1)/2

print(ave)


### FIXED CODE ###

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

s = []
sum = 0
for i in range(k):
    sum += p[i]

s.append(sum)

for i in range(1, n-k+1):
    sum = sum - p[i-1] + p[i+k-1]
    s.append(sum)

m = max(s)/2 + k/2

print(m)
### BUGGY CODE ###


N = int(input())

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

if D[0] != 0 or D.count(0) !=1:
    print("0")
    exit()

D.sort()
D = D[1:]
m = max(D)

#calc
result = 1
x = D.count(1)
D = D[x:]
for i in range(2,m+1):
    y = D.count(i)
    D = D[y:]
    if y!= 0:
        result = result * pow(x,y)
        x = y
print(result%998244353)





### FIXED CODE ###

import collections
N = int(input())

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

counted = collections.Counter(D)

if D[0] != 0 or counted[0] !=1:
    print("0")
    exit()

#calc
result = 1
x = counted[1]
for i in range(2,N+1):
    y = counted[i]
    result = result * pow(x,y) %998244353
    x = y
print(result)
### BUGGY CODE ###

def answer():
    n, p = map(int, input().split())
    s = input()
    m = [0] * p
    dp = [0]
    pre = [p - pow(10, i, p) for i in range(len(s))]
    for i, a in enumerate(s):
        m = amari(m, int(a), p)
        dp.append(dp[i] + m[0])
    print(dp[-1])

def amari(m, a, p):
    mm = [0] * p
    for i, b in enumerate(m):
        if b == 0:
            continue
        mm[(i * 10 + a) % p] += b
    mm[a%p] += 1
    return mm

answer()




### FIXED CODE ###

from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for i, ss in enumerate(s[::-1]):
        sss = (sss + pow(10, i, p) * int(ss)) % p
        m[sss] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(W + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= j - cw :
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - cw] + cv)
    return max(dp[-1])


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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(W + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= j - cw :
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - cw] + cv)
    return max(dp[-1])


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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    print(result)

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

x = int(input())
b = (-1)
for i in range(10**7):
    a = i
    if (a-b)*(a**4+(a**3)*b+(a**2)*(b**2)+a*(b**3)+b**4) == x:
        print(a,b)
        break

### FIXED CODE ###

import sys
x = int(input())
a = []
b = []
t = 0
for i in range(-1000,1000):
    t = i**5
    a.append([t,i])
    b.append([t,i])
    
for i in a:
    for j in b:
        if i[0]-j[0] == x:
            print(i[1],j[1])
            sys.exit()
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
Q = int(input())
rev = False

for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            S.appendleft(q[2])
        else:
            S.append(q[2])

for i in (range(len(S)) if rev is False else reversed(range(len(S)))):
    print(S[i], end="")
else:
    print("")

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

from subprocess import*
with open('A.py','w')as f:
    f.write('a,b=map(int,input().split())\n')
    for i in range(-100,101):
        f.write('if a==%d:\n'%i)
        for j in range(-100,101):
            f.write('    if b==%d:print(%d)\n'%(j,max(i+j,i-j,i*j)))
call(('pypy3','A.py'))

### FIXED CODE ###

from subprocess import*
with open('A.py','w')as f:
    f.write('a,b=map(int,input().split())\n')
    for i in range(-100,101):
        f.write('if a==%d:\n'%i)
        for j in range(-100,101):
            f.write('    if b==%d:print(%d)\n'%(j,max(i+j,i-j,i*j)))
call(('python3','A.py'))
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

N = int(input())
lis_all = []
lis_pat = []
lis_num = []

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

count = 0
for i in range(N):
    lis_S = list(str(input()))
    lis_S.sort()
    if lis_S not in lis_all:
        lis_pat.append(lis_S)
    lis_all.append(lis_S)

for i in lis_pat:
    lis_num.append(lis_all.count(i))

ans = 0
for i in lis_num:
    if i != 1:
        ans += comb(i,2)
   
print(ans)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)