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

from collections import deque
n,m = map(int,input().split())
ans = []
data1 = deque([1])
data2 = deque([])
hantei = [0]*(10**5+2)
hantei[1] = 1
for i in range(m):
    data2.append(list(map(int,input().split())))
while data1 and data2:
    i = data1.popleft()
    for k in range(len(data2)):
        a,b = map(int,data2.popleft())
        if a == i and hantei[b] == 0:
            ans.append([b,a])
            data1.append(b)
            hantei[b] = 1
        elif hantei[a] == 0 and b == i:
            ans.append([a,b])
            data1.append(a)
            hantei[a] = 1
        else:
            if hantei[a]*hantei[b] == 1:
                continue
            else:
                data2.append([a,b])
else:
    if data2:
        print("No")
    else:
        print("Yes")
        ans.sort()
        for i in ans:
            print(i[-1])

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
data = [[] for i in range(n)]
ans = [0]*n
for i in range(m):
    a,b =map(int,input().split())
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)
hantei = [False]*n
hantei[0] = True
deq = deque([0])
while deq:
    k = deq.popleft()
    for i in data[k]:
        if hantei[i]:
            continue
        hantei[i] = True
        ans[i] = k
        deq.append(i)
print("Yes")
for i in range(1,n):
    print(ans[i]+1)
### BUGGY CODE ###

N,M=map(int,input().split()) #N個の商品、M枚の割引券
A=list(map(int,input().split())) #i番目に買う値段はA[i]円

for i in range(M):
    A[A.index(max(A))]//=2
print(sum(A))

### FIXED CODE ###

import heapq

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

for i in range(N):
    A[i]*=-1
#print(A)
heapq.heapify(A)
for i in range(M):
    temp=heapq.heappop(A)
#    print(temp)
    heapq.heappush(A,temp//2+temp%2)
    
print(-sum(A))
### BUGGY CODE ###

import bisect

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

ind = [[] for _ in range(2*10**5 + 1)]
for i,num in enumerate(a):
    ind[num].append(i)

for i in range(1,2*10**5 + 1):
    if(ind[i]):
        ind[i].append(ind[i][0] + n)

cnt = 0
now = a[0]
while(True):
    right = bisect.bisect_right(ind[now], cnt%n)
    cnt += ind[now][right] - ind[now][right-1] + 1
    now = a[cnt%n]
    if(cnt%n == 0):
        break

cyc = k%(cnt//n)
cnt = 0
now =a[0]
while(True):
    right = bisect.bisect_right(ind[now], cnt%n)
    cnt += ind[now][right] - ind[now][right-1] + 1
    if(cnt//n == cyc):
        cnt -= ind[now][right] - ind[now][right-1] + 1
        break
    now = a[cnt%n]

cnt %= n
ans = []
while(cnt < n):
    now = a[cnt]
    right = bisect.bisect_right(ind[now],cnt)
    if(ind[now][right] >= n):
        ans.append(now)
        cnt += 1
    else:
        cnt = ind[now][right] + 1

print(' '.join(map(str,ans)))

### FIXED CODE ###

import bisect

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

ind = [[] for _ in range(2*10**5 + 1)]
for i,num in enumerate(a):
    ind[num].append(i)

for i in range(1,2*10**5 + 1):
    if(ind[i]):
        ind[i].append(ind[i][0] + n)

before = []
cnt = 0
now = a[0]
while(True):
    right = bisect.bisect_right(ind[now], cnt%n)
    cnt += ind[now][right] - ind[now][right-1] + 1
    if(ind[now][right] >= n):
        before.append(ind[now][right-1])
    now = a[cnt%n]
    if(cnt%n == 0):
        break

if(cnt//n==1):
    print('')
    exit()

cyc = k%(cnt//n)

cnt = before[cyc-1]
ans = []
while(cnt < n):
    now = a[cnt]
    right = bisect.bisect_right(ind[now],cnt)
    if(ind[now][right] >= n):
        ans.append(now)
        cnt += 1
    else:
        cnt = ind[now][right] + 1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

def main():
    N = int(input())
    S = []
    for i in range(N):
        s = input()
        if s not in S:
            S.append(s)
    print(len(S))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = {}
    for i in range(N):
        s = input()
        if s not in S:
            S.update({s:0})
    print(len(S))

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

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input().rstrip()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

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

def readinput():
    n,m=list(map(int,input().split()))
    rooms = [
        [[],-1,-1] for _ in range(n)
        ]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        rooms[a-1][0].append(b)
        rooms[b-1][0].append(a)
    return n,m,rooms

def labelNext(target, rooms, nokori, cost):
    oitaList=[]
    for i, room in enumerate(rooms):
        if (target in room[0]) and (room[1] == -1):
            room[1] = target
            room[2] = cost
            oitaList.append(i+1) # 道しるべをおいた部屋番号のリストにするので+1
    nokori -= set(oitaList)  #　道しるべを置いた部屋番号を削除
    return oitaList

def main(n,m,rooms):
    nokori=set(range(2,n+1))  # 道しるべを置いてない部屋番号の集合 (1を除くすべて)
    target=1
    cost=1
    nextList=labelNext(target,rooms, nokori, cost)
    while(len(nokori)>0):
        cost+=1
        nl=[]
        for n in nextList:
            nl.append(labelNext(n,rooms,nokori,cost))
            if(len(nokori)==0):
                break
        nextList=nl
    labelList=[]
    for room in rooms:
        labelList.append(room[1])   
    labelList.pop(0)     
    return labelList

if __name__=='__main__':
    n,m,rooms=readinput()
    labelList=main(n,m,rooms)
    print('Yes')
    for l in labelList:
        print(l)


### FIXED CODE ###

from collections import deque

WHITE=0
GRAY=1
BLACK=2

nList = []
labelList = []
color = []
Q = deque([])

def readinput():
    global nList
    global color
    global Q
    global labelList

    n,m=list(map(int,input().split()))
    nList = []
    for _ in range(n+1):
        nList.append([])  # 1-オリジンの隣接リスト

    for _ in range(m):
        a,b = list(map(int,input().split()))
        nList[a].append(b)
        nList[b].append(a)

    labelList = [0]*(n+1)
    color = [WHITE]*(n+1)
    Q = deque([])

    #print(nList)

def bfs(p):
    global Q
    global nList
    global color
    global labelList

    Q.append(p)
    color[p]=GRAY
    #print(Q)
    #print(color)
    while(len(Q)>0):
        current=Q.popleft()
        for next in nList[current]:
            if(color[next]==WHITE):
                Q.append(next)
                color[next]=GRAY
                labelList[next]=current
                #print(Q)
                #print(color)
                #print(labelList)
        color[current]=BLACK

def main():

    bfs(1)


if __name__=='__main__':
    readinput()

    main()
    print('Yes')
    for l in labelList[2:]:
        print(l)
### BUGGY CODE ###

from bisect import bisect_right

H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for _ in range(N)]
M.sort()
A = [0] * N
B = [0] * N
for i, (a, b) in enumerate(M):
    A[i] = a
    B[i] = b


INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + A[j])
        b = B[j]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])


### FIXED CODE ###

import sys

H, N = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
# A = [0] * N
# B = [0] * N
# for i, (a, b) in enumerate(M):
#     A[i] = a
#     B[i] = b


INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + M[j][0])
        b = M[j][1]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])
### BUGGY CODE ###

N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + ((2**(N-1-i)) % (pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (2**(N-1-i) % (pop_c - 1))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

### FIXED CODE ###

N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)
### BUGGY CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


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

import itertools

N = int(input())
S = list(input())

ans = 0
for comb in list(itertools.combinations(range(N), 3)):
  i, j, k = comb
  
  if (S[i] != S[j]) & (S[j] != S[k]) & (S[k] != S[i]) :
    if (j + j - i - k) != 0 :
      ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = list(input())

cnt = Counter(S)

ans = cnt['R'] * cnt['G'] * cnt['B']

for i in range(N):
  for j in range(i+1, N):
    k = j + j - i
    if k < N :
      if (S[i] == S[j]) or (S[j] == S[k]) or (S[k] == S[i]) :
        continue
      ans -= 1

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

S = input()
n = len(S)
mod = 10**9+7
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(k*10**i+j)%13] += dp[i][j]
                dp[i+1][(k*10**i+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(k*10**i+j)%13] += dp[i][j]
            dp[i+1][(k*10**i+j)%13] %= mod
print (dp[n][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

n = int(input())
prime = 0
for i in range(n):
    m = int(input())
    cout = 0
    for j in range(m):
        if m % (j+1) == 0:
            cout += 1
    if cout == 2:
         prime += 1
print(prime)

### FIXED CODE ###

n = int(input())
prime = 0

def is_prime(q):
    if q == 2:
        return True
    if q < 2:
        return False
    return pow(2, q-1, q) == 1


prime = 0
for i in range(n):
    m = int(input())
    if is_prime(m):
        prime += 1
print(prime)
### BUGGY CODE ###

n = int(input())
s = input()
result = 0

r = s.count('R')
g = s.count('G')
b = s.count('B')

result = r * g * b
count = 0

for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if j < k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                count += 1

print(result-count)


### FIXED CODE ###

n = int(input())
s = input()
result = 0

r = s.count('R')
g = s.count('G')
b = s.count('B')

result = r * g * b
count = 0

for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if j < k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                count += 1

print(result-count)
### BUGGY CODE ###

import re

N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for n in range(Q)]

pattern = "AC"

for i in li:
  s = S[i[0]-1:i[1]]
  result = re.findall(pattern, s, re.S)
  print(len(result))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for n in range(Q)]

t = [0] * len(S)

for index, s in enumerate(S):
  if index+1 > len(S)-1:
    break

  if s == 'A' and S[index+1] == 'C':
    t[index+1] = t[index] + 1
    
  else:
    t[index+1] = t[index]

for i in li:
  print(t[i[1]-1] - t[i[0] - 1])
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
  for j in range(i,n+1,i):ans+=j
print(ans)


### FIXED CODE ###

n=int(input())
c=[0]*(n+1)
for i in range(1,n+1):
  for j in range(i,n+1,i):c[j]+=1
ans=0
for i in range(1,n+1):ans+=i*c[i]
print(ans)
### BUGGY CODE ###

N = int(input())

A = []
for _ in range(N):
  A.append(int(input())-1)

count = []
n = 0
ans = 1
for _ in range(N+1):
  if A[n] == 1:
    break
 
  elif A[n] in count:
    ans = -1
    break
  
  else:
    count.append(A[n])
    ans += 1
    n = A[n]
 
print(ans)

### FIXED CODE ###

n = int(input())
al = []
for i in range(n):
    a = int(input())
    al.append(a)
 
al.insert(0, 0)
ans = -1
push = 1
for i in range(1, n+2):
    light = al[push]
    push = light
    if light == 2:
        ans = i
        break
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N):
    for j in range(i+1, N):
        Lij = L[i] + L[j]
        for k in range(j+1, N):
            if Lij <= L[k]:
                break
            ans += 1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N):
    for j in range(i+1, N):
        Lij = L[i] + L[j]
        k = bisect.bisect_left(L, Lij)
        ans += max(k - j - 1, 0)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    count = len([x for x in filter(lambda n: n<0, a)])
b = [x for x in map(abs, a)]

p = min(b)
q = sum(b)
if count % 2 != 0:
    ans = q - 2 * p
else:
    ans = q
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
count = len([x for x in filter(lambda n: n<0, a)])
b = [x for x in map(abs, a)]

p = min(b)
q = sum(b)
if count % 2 != 0:
    ans = q - 2 * p
else:
    ans = q
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    N = H*W

    def pos(h,w):
        return h*W+w

    G = []
    for h in range(H):
        G.append(list(input()))

    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw] == "#": continue
                    dp[pos(h,w)][pos(h+dh,w+dw)] = 1
                    dp[pos(h+dh,w+dw)][pos(h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    print(ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

@njit(cache=True)
def pos(W,h,w):
    return h*W+w

def solve(H,W,G):
    N = H*W+W
    INF=10**18

    dp = np.full((N,N),INF)
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w]: continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw]: continue
                    dp[pos(W,h,w)][pos(W,h+dh,w+dw)] = 1
                    dp[pos(W,h+dh,w+dw)][pos(W,h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    return ans





def main():
    H,W=mi()
    G = [[0] * W for _ in range(H)]
    for h in range(H):
        S = list(input())
        for w in range(W):
            G[h][w] = S[w] == "#"

    print(solve(H,W,np.array(G,bool)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,b1[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
A = [R,G,B]
A.sort()
R = A[0]
G = A[1]
B = A[2]
rmax = N//R
gmax = N//G
bmax = N//B

cnt = 0

for i in range(rmax+1):
    for j in range(gmax+1):
        if R*i + G*j > N:
            continue
        if ((N-R*i-G*j)%B == 0) and ((N-R*i-G*j)//B <= bmax):
            cnt += 1
print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
A = [R,G,B]
A.sort()
R = A[2]
G = A[1]
B = A[0]
rmax = N//R
gmax = N//G
bmax = N//B

cnt = 0

if R == 1:
    print((N+1)*(N+2)//2)
    exit()

for i in range(rmax+1):
    for j in range(gmax+1):
        if R*i + G*j > N:
            continue
        if ((N-R*i-G*j)%B == 0) and ((N-R*i-G*j)//B <= bmax):
            cnt += 1
print(cnt)
### BUGGY CODE ###

import collections
import itertools

cnt = 0

N = int(input())
string_counters = [collections.Counter(input()) for i in range(N)]
for pair in list(itertools.combinations(string_counters, 2)):
    if pair[0] == pair[1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = dict()
output = 0

for i in range(N):
    string = ''.join(sorted(input()))
    cnt.setdefault(string, 0)
    output += cnt[string]
    cnt[string] += 1

print(output)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


H, W, D = map(int, input().split())

A = [False] * (H*W+1)

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        A[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)


### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

ans = 0
for i in range(n-1):
  ans += a[i]*sum(a[i+1:])
  ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))

sum_a = sum(a)
ans = 0
for i in range(n-1):
  sum_a-=a[i]
  ans += a[i]*sum_a
  ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

from itertools import groupby
S = input()
A = [len(list(it)) for s, it in groupby(S)]
B = [[0]*(n1-1)+[(n1+1)//2+n2//2]+[n1//2+(n2+1)//2]+[0]*(n2-1)
     for n1, n2 in zip(A[::2], A[1::2])]
print(*sum(B, []))

### FIXED CODE ###

from itertools import groupby
S = input()
A = [len(list(it)) for s, it in groupby(S)]
for n1, n2 in zip(A[::2], A[1::2]):
    print(*([0]*(n1-1)+[(n1+1)//2+n2//2]+[n1//2+(n2+1)//2]+[0]*(n2-1)), end=" ")
### BUGGY CODE ###

N = int(input())
L = [""]*N
for i in range(N) :
    L[i] = "".join(sorted(list(input())))

ans = 0

for i in range(N-1) :
    a = L[i]
    for j in range(i+1,N) :
        b = L[j]
        if a == b :
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
L = ["".join(sorted(list(input()))) for i in range(N)]
D = {}
for s in L :
    if s not in D :
        D[s] = 1
    else :
        D[s] +=  1
ans = 0
for k in D :
    n = D[k]
    ans += n*(n-1)//2
print(ans)