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

"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()

    cnt = [0] * 2019
    # print(cnt)
    cnt[0] = 1
    ans = 0
    b = 0
    t = 1
    for i in range(len(s)):
        b = b + int(s[len(s)-i-1]) * t
        amari = b % 2019
        cnt[amari] += 1
        t *= 10 % 2019

    for i in range(2019):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

N = int(input())
sl = []
cnt = 0
for i in range(N):
    str = input()
    if sorted(str) in sl:
        cnt += sl.count(sorted(str))
    sl.append(sorted(str))


print(cnt)

### FIXED CODE ###

N = int(input())
sd = {}
cnt = 0
for i in range(N):
    str = ','.join(sorted(input()))
    if str in sd:
        sd[str] += 1
        cnt += sd[str]
    else:
        sd[str] = 0
print(cnt)
### BUGGY CODE ###

N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
cnt2 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
# G4.sort()
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += sum(L[1] for L in G3)

if cnt2 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

if cnt2 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = int(input())
    A = LII()
    A.sort()

    B = A.copy()

    for a in A:
        c = B.count(a)
        B = list(filter(lambda x: x % a != 0, B))
        if c == 1:
            B.append(c)

    print(len(B))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import numpy as np
from collections import Counter

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))


def main():
    N = int(input())
    A = LII()
    A.sort() 
    
    if N == 1:
        print(1)
        return

    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2

    print(sum(filter(lambda x: x == 1, dp)))


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

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


num = 2 ** ((n - 1).bit_length())
SEG = [0] * (2 * num)


def func(a, b):
    return a | b


for idx, val in enumerate(C):
    idx += num
    SEG[idx] = 1 << (val - 1)
for idx in range(num - 1, 0, -1):
    while idx > 0:
        SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])
        idx //= 2


def query(left, right):
    resleft = 0
    resright = 0
    left += num
    right += num
    while right - left > 0:
        if left % 2 == 1:
            resleft = func(resleft, SEG[left])
            left += 1
        if right % 2 == 1:
            right -= 1
            resright = func(resright, SEG[right])
        left //= 2
        right //= 2
    return func(resleft, resright)


for _ in range(q):
    l, r = map(int, input().split())
    temp = query(l - 1, r)
    print(popcnt(temp))


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")
### BUGGY CODE ###

import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###


""""
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""

N, M = map(int, raw_input().split())

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

h = [0]*(N+1)

for eg in G:
    h[eg[1]]+=1

que = []

for i in xrange(1, N+1):
    if h[i] == 0: que.append(i)

dp = [0]*(N+1)

while len(que)>0:
    now = que.pop(0)
    for eg in G:
        if eg[0]==now:
            h[eg[1]]-=1
            if h[eg[1]]==0:
                que.append(eg[1])
                dp[eg[1]] = max(dp[eg[0]] + 1, dp[eg[1]])

print max(dp)

### FIXED CODE ###


""""
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""

N, M = map(int, raw_input().split())

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

h = [0]*(N+1)

dest = [[] for _ in xrange(N+1)]

for eg in G:
    h[eg[1]]+=1
    dest[eg[0]].append(eg[1])

que = []

for i in xrange(1, N+1):
    if h[i] == 0: que.append(i)

dp = [0]*(N+1)

while len(que)>0:
    now = que.pop(0)
    for edest in dest[now]:
        h[edest]-=1
        if h[edest]==0:
            que.append(edest)
            dp[edest] = max(dp[now] + 1, dp[edest])

print max(dp)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
a = list(map(int, input().split()))
a.sort()
ans=1
b=10**18
for i in a:
    ans*=i
    if ans > b:
        ans=-1
        break
print(ans)
### BUGGY CODE ###

from pprint import pprint

n,w = map(int,input().split())

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

#pprint(dp_table)



### FIXED CODE ###

from pprint import pprint

n,w = map(int,input().split())

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)
### BUGGY CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = csr_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.dijkstra(A,0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

### FIXED CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))
### BUGGY CODE ###

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

Z = []
for i in range(N):
    Z.append(min(T[i], A[i]))
s = 1
if max(Z) < max(T[-1], A[0]):
    print(0)
else:
    for i in range(1, N - 1):
        if not (Z[i] > Z[i - 1] or Z[i] > Z[i + 1]):
            s *= Z[i] % (1000000000 + 7)
    print(sum % (1000000000 + 7))

### FIXED CODE ###

import sys

MOD = 1000000007

def union(x,y):
    if len(x)==1:
        if len(y)==1:
            return (1 if x[0]==y[0] else 0)
        else:
            return (1 if y[-1]>=x[0] else 0)
    if len(x)>1:
        if len(y)==1:
            return (1 if x[-1]>=y[0] else 0)
        else:
            return min(len(x),len(y))

n = int(input())
a = list(map(lambda x: int(x) % MOD, input().split()))
b = list(map(lambda x: int(x) % MOD, input().split()))
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
x[0] = 1
y[-1] = 1
z = 1

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] = 1
    else:
        x[i] = 0

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += 1
    else:
        y[j-1] += 0

for i in range(n):
    if x[i] == 1 and y[i] == 0:
        if a[i] > b[i]:
            print(0)
            sys.exit()
    elif x[i] == 0 and y[i] == 1:
        if a[i] < b[i]:
            print(0)
            sys.exit()
    elif x[i] == 1 and y[i] == 1:
        if a[i] != b[i]:
            print(0)
            sys.exit()
    else:
        z *= min(a[i],b[i])
        z = z % MOD

print(z)
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int, input().split()))
lst = list(itertools.combinations(L, 3))
cnt = 0
for i in lst:
    if i[0]+i[1] > i[2] and i[1]+i[2] > i[0] and i[0]+i[2] > i[1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
lst = list(map(int, input().split()))
lst.sort()
total = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        x = bisect.bisect_left(lst, lst[i]+lst[j])
        total += x-j-1
print(total)
### BUGGY CODE ###

s = input()

for _ in range(100000):
    s = s.replace('ST', '', 1)
print(len(s))



### FIXED CODE ###

s = list(input())
l = []
for i in range(len(s)):
    if s[i] == 'S':
        l.append('S')
    elif not l:
        l.append('T')
    elif l[-1] == 'T':
        l.append('T')
    else:
        l.pop()
print(len(l))
### BUGGY CODE ###

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

for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

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

b=[0]*N
for c in A:
    b[c-1]+=1

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

def solve():
    maxD = 30

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = 0
    for d in range(maxD):
        m1 = 1 << d
        mask = m1 - 1
        B0s, B1s = [], []
        for B in Bs:
            if B & m1:
                B1s.append(B & mask)
            else:
                B0s.append(B & mask)
        B0s.sort()
        B1s.sort()
        lenB0, lenB1 = len(B0s), len(B1s)

        A2s = [(A & mask, A & m1) for A in As]
        A2s.sort()

        num1 = 0
        iB0, iB1 = lenB0, lenB1
        for A2, v in A2s:
            while iB0 > 0 and B0s[iB0-1] >= m1-A2:
                iB0 -= 1
            while iB1 > 0 and B1s[iB1-1] >= m1-A2:
                iB1 -= 1
            if v:
                num1 += iB0
                num1 += lenB1 - iB1
            else:
                num1 += lenB0 - iB0
                num1 += iB1

        if num1 % 2:
            ans |= m1

    print(ans)


solve()


### FIXED CODE ###

from bisect import bisect_left, bisect_right

def solve():
    maxD = 30

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    As.sort()
    Bs.sort()

    ans = 0
    for d in reversed(range(maxD)):
        m1 = 1 << d

        iA = bisect_left(As, m1)
        iB = bisect_left(Bs, m1)

        num1 = N * (N-iA + N-iB)

        As = As[:iA] + [A-m1 for A in As[iA:]]
        Bs = Bs[:iB] + [B-m1 for B in Bs[iB:]]

        As.sort()
        Bs.sort(reverse=True)

        iB = 0
        for A in As:
            while iB < N and A + Bs[iB] >= m1:
                iB += 1
            num1 += iB

        Bs.reverse()

        if num1 % 2:
            ans |= m1

    print(ans)


solve()
### BUGGY CODE ###

import heapq
import math
x1, y1, x2, y2 = [int(i) for i in input().split()]
n = int(input())

xy = [[x1, y1,0]]
for _ in range(n):
    xy.append([int(i) for i in input().split()])
xy.append([x2, y2,0])

def dif(x, y):
    return max(0, math.sqrt((x[0] - y[0])** 2 + (x[1] - y[1])** 2) - x[2] - y[2])


que = [[0, 0]]
heapq.heapify(que)
mi = [10 ** 16] * (n + 2)
mi[0] = 0
used = [False]*(n+2)

while que:
    w, x = heapq.heappop(que)
    used[x]=True
    for i in range(n + 2):
        if used[i]:
            continue
        cost = dif(xy[x], xy[i])
        if w + cost < mi[i]:
            mi[i] = w + cost
            heapq.heappush(que,[w + cost, i])
print(mi[-1])

    

### FIXED CODE ###

import math
x1, y1, x2, y2 = [int(i) for i in input().split()]
n = int(input())

xy = [[x1, y1, 0]]
for _ in range(n):
    xy.append([int(i) for i in input().split()])
xy.append([x2, y2, 0])


def dif(x, y):
    return max(0, math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) - x[2] - y[2])




q = set([i for i in range(n + 2)])
mi = [10 ** 16] * (n + 2)
mi[0] = 0

while q:
    u = -1
    mm = 10**16
    for i in q:
        if mm > mi[i]:
            mm = mi[i]
            u = i
    
    q.remove(u)
    for i in q:
        mi[i] = min(mi[i], mi[u] + dif(xy[i], xy[u]))

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

import sys

change = True
debug = False


def print_err(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    """
    0 と 1 からなる文字列 S が与えられます。
    以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。
    S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r−l+1≥K が満たされる必要がある)。
    l≤i≤r なるすべての整数 i に対し、Si が 0 なら Si を 1 に、Si が 1 なら Si を 0 に置き換える。
    制約
    1≤|S|≤105
    Si(1≤i≤N) は 0 または 1 である
    """
    S = input()

    f(S)


def f(S):
    """
    最大となるKより、1つずつ変えるのは最後の手段
    ※K以上の反転可能であるため

    000: OK
    001, 110:  -> 100, 011
    010, 101:
      11を最終的に反転するように修正していく
        101: 1-3 all
        011: 1-2
        000: 2-3
    011, 100: 11を反転でOK

    0001 となっているとき
    K=3とすれば
    000 をまず反転、その後K+1まで反転すれば、初期状態からK+1番目のみ反転できる
    """
    n = len(S)
    ans = n

    # 反転確認
    table = str.maketrans('01', '10')
    for k in range(1, n):
        if S[k] == S[k - 1]:
            continue

        t = max(k, n - k)
        ans = min(ans, t)

        # 反転を利用して異なる部分を変更
        # 要素数の多い方を対称の異なる文字含めて反転

        # CPython3: TLE
        if change:
            if t == k:
                S = S[:t].translate(table) + S[t:]
            else:
                S = S[:k] + S[k:].translate(table)

            if debug:
                print_err("t:", t, "k:", k, "S:", S, sep="\t")

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

change = False
debug = False


def print_err(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    """
    0 と 1 からなる文字列 S が与えられます。
    以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。
    S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r−l+1≥K が満たされる必要がある)。
    l≤i≤r なるすべての整数 i に対し、Si が 0 なら Si を 1 に、Si が 1 なら Si を 0 に置き換える。
    制約
    1≤|S|≤105
    Si(1≤i≤N) は 0 または 1 である
    """
    S = input()

    f(S)


def f(S):
    """
    最大となるKより、1つずつ変えるのは最後の手段
    ※K以上の反転可能であるため

    000: OK
    001, 110:  -> 100, 011
    010, 101:
      11を最終的に反転するように修正していく
        101: 1-3 all
        011: 1-2
        000: 2-3
    011, 100: 11を反転でOK

    0001 となっているとき
    K=3とすれば
    000 をまず反転、その後K+1まで反転すれば、初期状態からK+1番目のみ反転できる
    """
    n = len(S)
    ans = n

    # 反転確認
    table = str.maketrans('01', '10')
    for k in range(1, n):
        if S[k] == S[k - 1]:
            continue

        t = max(k, n - k)
        ans = min(ans, t)

        # 反転を利用して異なる部分を変更
        # 要素数の多い方を対称の異なる文字含めて反転

        # CPython3, PyPy: TLE
        if change:
            if t == k:
                S = S[:t].translate(table) + S[t:]
            else:
                S = S[:k] + S[k:].translate(table)

            if debug:
                print_err("t:", t, "k:", k, "S:", S, sep="\t")

    print(ans)

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

import collections
n = int(input())
s = [input() for l in range(n)]
word = collections.Counter(s)
z = [kv for kv in word.items() if kv[1] == max(word.values())]
z = sorted(z)
for c in z:
  print(c[0])


### FIXED CODE ###

import collections
n = int(input())
s = [input() for l in range(n)]
word = collections.Counter(s)
ma = max(word.values())
z = [kv for kv in word.items() if kv[1] == ma]
z = sorted(z)
for c in z:
  print(c[0])
### BUGGY CODE ###

n=int(input())
ans=[]
for i in range(n):
    qw=input()
    ans.append([0,0,0,0,0,0,0,0,0,0])
    for j in range(10):
        ans[i][j]=qw[j]
    ans[i].sort()

ans.sort()
a=0
for i in range(n-1):
    for j in range(n-1-i):
        if ans[i]==ans[i+j+1]:
            a+=1
        else:
            break

print(int(a))


### FIXED CODE ###

n=int(input())
ans=[]
for i in range(n):
    qw=input()
    ans.append([0,0,0,0,0,0,0,0,0,0])
    for j in range(10):
        ans[i][j]=qw[j]
    ans[i].sort()

lis=[]
for i in range(n):
    lis.append(ans[i][0])
    for j in range(9):
        lis[i]+=ans[i][j+1]

a=0
#print(lis)

dic={lis[0]:1}
for i in range(n-1):
    if lis[i+1] in dic.keys():
        a+=dic[lis[i+1]]
        dic[lis[i+1]]+=1
    else:
        dic[lis[i+1]]=1

print(int(a))