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

# -*- coding: utf-8 -*-
from math import factorial
from scipy.misc import comb
def inpl(): return tuple(map(int, input().split()))

def combination(n, r):
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))

n = int(input())
A = inpl()
C = ["" for i in range(n+1)]

for l, a in enumerate(A):
    if type(C[a]) == int:
        i, j = C[a], l
        break
    else:
        C[a] = l

print(n)

for k in range(2, n+2):
    total = comb(n+1, k, 1)
    b = comb(n+i-j, k-1, 1)
    res = (total-b)%(10**9 + 7)
    print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

n = int(input())
A = inpl()
mod = 10**9 + 7

fct = [1]
inv = [1]

for i in range(1, n+2):
    fct.append((fct[-1]*i)%mod)
    inv.append((pow(fct[i], mod-2, mod)))

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return (fct[n] * inv[n - k] * inv[k]) % mod    

C = ["" for i in range(n+1)]

for l, a in enumerate(A):
    if type(C[a]) == int:
        i, j = C[a], l
        break
    else:
        C[a] = l

print(n)

for k in range(2, n+2):
    total = comb(n+1, k)
    b = comb(n+i-j, k-1)
    res = (total-b)%(mod)
    print(res)
### BUGGY CODE ###

def main():
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

### FIXED CODE ###

def main():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()
### BUGGY CODE ###

import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def routes_from_zero(r,c, factorial):
    ret = 0
    for i in range(r + 1):
        tmp = 1
        tmp *= factorial[i+c+1]
        tmp %= MOD
        tmp *= pow(factorial[c], MOD - 2, MOD)
        tmp %= MOD
        tmp *= pow(factorial[i + 1], MOD - 2, MOD)
        tmp %= MOD

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    factorial = [1]
    tmp = 1
    for i in range(1, r2 + c2 + 5):
        tmp *= i
        tmp %= MOD
        factorial.append(tmp)

    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial) - routes_from_zero(r1 - 1, c2, factorial)\
          - routes_from_zero(r2, c1 - 1, factorial) + routes_from_zero(r1 - 1, c1 - 1, factorial)
    print(ans % MOD)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import time
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def routes_from_zero(r,c, factorial, gyaku):
    ret = 0
    for i in range(r + 1):
        tmp = 1
        tmp *= factorial[i+c+1]
        # tmp %= MOD
        tmp *= gyaku[c]
        # tmp %= MOD
        tmp *= gyaku[i+1]
        # tmp %= MOD

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    # factorial = [1]
    # tmp = 1
    # t1 = time.time()
    # for i in range(1, r2 + c2 + 5):
    #     tmp *= i
    #     tmp %= MOD
    #     factorial.append(tmp)
    # print(time.time() - t1)
    # gyaku = [pow(i, MOD - 2, MOD) for i in factorial]
    # print(time.time() - t1)
    SIZE = 2 * 10 ** 6 + 10 ** 5
    SIZE += 1
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    factorial = fac
    gyaku = finv
    # print(time.time() - t1)
    # return
    # gyaku = [1 for i in range(2000000)]
    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial, gyaku) - routes_from_zero(r1 - 1, c2, factorial, gyaku)\
          - routes_from_zero(r2, c1 - 1, factorial, gyaku) + routes_from_zero(r1 - 1, c1 - 1, factorial, gyaku)
    print(ans % MOD)

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

N = int(input())
P = [int(n) for n in input().split()]
c = 0
o = sorted([i for i in range(1, N+1)], reverse=True)
if o==P:
    print(N)
else:
    while P:
        r = min(P)
        P = P[:P.index(r)]
        c += 1
    print(c)


### FIXED CODE ###

N = int(input())
P = [int(n) for n in input().split()]
c = 0
curr = 2*10**5+1
for p in P:
    if p < curr:
        curr = p
        c += 1
print(c)
### BUGGY CODE ###

#python3
import sys
sys.setrecursionlimit(10**6)

def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        to[a-1].append(b-1)
        to[b-1].append(a-1)

    node = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1] += x  

    def dfs(v=0, p=-1):
        for u in to[v]:
            if u == p:
                continue
            else:
                node[u] = node[u] + node[v]
                dfs(u, v)

    dfs()
    for i in range(n):
        if i == n-1:
            print(node[i])
        else:
            print(node[i], end=' ')
main()

### FIXED CODE ###

#python3
from collections import deque 
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]

    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1] += x

    dq = deque() 
    dq.append(0)
    done = [0 for _ in range(n)]
    done[0] = 1
    while len(dq) > 0:
        x = dq.popleft()
        for i in to[x]:
            if done[i] == 1:
                continue
            node[i] += node[x]
            done[i] = 1 
            dq.append(i)

    for i in range(n):
        print(node[i]) if i == n-1 else print(node[i], end=' ')
main()
### BUGGY CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s = []
        
    for i in range(N):

        if i == 0:
            sorted_s.append(sorted(s[i]))

        for j in range(i + 1, len(s)):

                if i == 0:
                    sorted_s.append(sorted(s[j]))

                if sorted_s[i] == sorted_s[j]:
                    anagram_num += 1

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))


### FIXED CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s_sub = []
    sorted_s = []
        
    for i in range(N):
        sorted_si = sorted(s[i])
        sorted_s_sub.append(''.join(sorted_si))

    sorted_s = sorted(sorted_s_sub)

    i = 0
    item_count = []
    while i < N:
        item = sorted_s[i]
        j = i + 1
        count = 1
        while j < N:
            if item == sorted_s[j]:
                count += 1
                j += 1
            else:
                break
        item_count.append(count)
        i += count  # count だけ進める
    
    for count in item_count:
        
        anagram_num += int(count * (count - 1) / 2)

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))
### BUGGY CODE ###

N, W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int,input().split())
  dp[n][:] = dp[n-1][:]
  for w in range(W+1):
    if w + wn > W: break
    dp[n][w+wn] = max(dp[n][w+wn],dp[n-1][w]+vn)
print(max(dp[N]))

### FIXED CODE ###

N, W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int,input().split())
  dp[n][:] = dp[n-1][:]
  for w in range(W+1):
    if w + wn > W: break
    dp[n][w+wn] = max(dp[n][w+wn],dp[n-1][w]+vn)
print(max(dp[N]))
### BUGGY CODE ###

class Node():
    def __init__(self, v):
        self.value = v
        self.friends = set()
        self.blocked = set()

n, m, k = list(map(int, input().split()))
link = {i: Node(i) for i in range(1, n+1)}
groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a].friends.add(b)
    link[b].friends.add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c].blocked.add(d)
    link[d].blocked.add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i].blocked - link[i].friends) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")


### FIXED CODE ###

class Tree:
    def __init__(self, v: int):
        self.value = v
        self.size = 1
        self.depth = 1
        self.parent = None
        self.friends = set()
        self.blocked = 0

    def get_root(self):
        t = self
        while(t.parent != None):
            t = t.parent
        return t

    def merge(self, t):
        p, c = (self, t) if self.depth > t.depth else (t, self)
        c.parent = p
        p.depth = max(p.size, c.size + 1)
        p.size += c.size

def main():
    n, m, k = [int(s) for s in input().split()]
    forest = [Tree(i+1) for i in range(n)]

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        ta, tb = forest[a-1], forest[b-1]
        ta.friends.add(b)
        tb.friends.add(a)
        ra = ta.get_root()
        rb = tb.get_root()
        if ra != rb:
            ra.merge(rb)

    roots = [t.get_root() for t in forest]
    for i in range(k):
        c, d = [int(s) for s in input().split()]
        tc, td = forest[c-1], forest[d-1]
        rc = roots[c-1]
        rd = roots[d-1]
        if rc == rd:
            tc.blocked +=1
            td.blocked +=1

    cands = []
    for t in forest:
        root = roots[t.value - 1]
        cand = root.size - len(t.friends) - t.blocked - 1
        cands.append(str(cand))
    print(" ".join(cands))

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

N = int(input())
S = []
for i in range(N):
    S.append(int(input()))
    
ans = 0
for bits in range(1 << N):
    check = 0
    for i in range(N):
        if (bits >> i & 1) == 1:
            check += S[i]
    if check % 10 != 0:
        ans = max(check,ans)
print(ans)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(int(input()))
    
S = sorted(S)
# print(S)

sum_S = sum(S)

if sum_S % 10 != 0:
    print(sum_S)
else:
    for i in range(N):
        if S[i] % 10 != 0:
            sum_S -= S[i]
            break
    if sum_S % 10 != 0:
        print(sum_S)
    else:
        print(0)
### BUGGY CODE ###

# N, D = [int(i) for i in input().split()]
def pow_(x, n):
  if n == 0:
    return 1

  k = 1
  while n > 1:
    if n % 2 != 0:
      k *= x
    x *= x
    n //= 2

  return k * x

K = int(input())
count = 0
for i in range(1, 10**6):
  count += 1
  if (7 * (pow_(10, i) - 1) // 9) % K == 0:
    print(count)
    break
else:
  print(-1)



### FIXED CODE ###

# N, D = [int(i) for i in input().split()]
K = int(input())
if K % 7 == 0:
  K = K // 7
K = 9 * K
remain = 1
for i in range(10**6):
  remain = (remain*10) % K
  if remain == 1:
    print(i+1)
    break
else:
  print(-1)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

if reduce(mul, k) <= 10**18:
    print(reduce(mul, k))
else:
    print(-1)

### FIXED CODE ###

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

def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int32).T
    a = csr_matrix(([1] * m, (edge - 1)), shape=(n, n))
    s, p = shortest_path(a, return_predecessors=True,
                         indices=0, directed=False, unweighted=True)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, n, edge, inf=float("inf")):
        import heapq
        d = [inf] * n
        used = [False] * n
        d[s] = 0
        used[s] = True
        queue = []
        path = [-9999] * n
        for e in edge[s]:
            heapq.heappush(queue, e + [s])
        while len(queue):
            dist, point, before = heapq.heappop(queue)
            if used[point]:
                continue
            d[point] = dist
            used[point] = True
            path[point] = before
            for nextdist, nextp in edge[point]:
                if not used[nextp]:
                    heapq.heappush(queue, [dist + nextdist, nextp, point])
        return d, path
    n, m = map(int, input().split())
    inf = 10 ** 10
    edge = [[] for _ in range(n)]
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        edge[x].append([1, y])
        edge[y].append([1, x])
    l, p = Dijkstra(0, n, edge, inf)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


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

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

result=1

if 0 in A:
    result=0
else:
    for i in range(N):
        result = result*A[i]

    if result > 10**18:
        result=-1
print(result)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
### BUGGY CODE ###

import numpy as np


def check_value(before_key, values):
    if before_key == 0:
        k, v = np.argmax(values[1:])+1, np.max(values[1:])
    elif before_key == 1:
        k, v = np.argmax(values[::2])*2, np.max(values[::2])
    else:
        k, v = np.argmax(values[:-1]), np.max(values[:-1])
    return k, v


if __name__ == '__main__':
    n = int(input())
    happy_list = []
    for _ in range(n):
        happy_list.append(list(map(int, input().split())))
    a_key, b_key, c_key = 0, 1, 2
    a_sum, b_sum, c_sum = happy_list[0][0], happy_list[0][1], happy_list[0][2]
    for happy in happy_list[1:]:
        key, value = check_value(a_key, happy)
        a_key = key
        a_sum += value
        key, value = check_value(b_key, happy)
        b_key = key
        b_sum += value
        key, value = check_value(c_key, happy)
        c_key = key
        c_sum += value
    print(max(a_sum, b_sum, c_sum))


### FIXED CODE ###

n = int(input())
ha, hb, hc = 0, 0, 0
for _ in range(n):
    a, b, c = map(int, input().split())
    ha, hb, hc = max(hb, hc) + a, max(hc, ha) + b, max(ha, hb) + c
print(max(ha, hb, hc))
### BUGGY CODE ###

m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		if R.count(R[r]) == 1: continue
		for c in range(m):
			if S[r][c] == 0: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
				break
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

### FIXED CODE ###

def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i
### BUGGY CODE ###

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
  ans%=(10**9+7)
print(ans)


### FIXED CODE ###

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
print(ans%(10**9+7))
### BUGGY CODE ###

import numpy as np
input1 = input()

door_num = int(input1.split()[1])
max_left = 1
min_right = int(input1.split()[0])

for i in range(door_num):
    a = input()
    new_inputs = [int(i) for i in a.split()]
    max_left = np.max([new_inputs[0], max_left])
    min_right = np.min([new_inputs[1], min_right])
    if not min_right >= max_left:
        break

if min_right >= max_left:
    print(min_right - max_left + 1)
else:
    print(0)

### FIXED CODE ###

import numpy as np
input1 = input()

door_num = int(input1.split()[1])
lefts = []
rights = []
for i in range(door_num):
    a = input()
    new_inputs = [int(i) for i in a.split()]
    lefts.append(new_inputs[0])
    rights.append(new_inputs[1])
    #max_left = np.max([new_inputs[0], max_left])
    #min_right = np.min([new_inputs[1], min_right])
    #if not min_right >= max_left:
    #    break
min_right = np.min(rights)
max_left = np.max(lefts)

if min_right >= max_left:
    print(min_right - max_left + 1)
else:
    print(0)
### BUGGY CODE ###

Machine_list = []
N = int(input())

for _ in range(N):
  X, L = map(int, input().split())
  Machine_list.append([X,L])

Machine_list = sorted(Machine_list)
  
def MachineArrangementCheck():
  length = len(Machine_list)
  # 配列の上限エラー対策
  for i in range(length):
    if i != length - 1:
      M1 = Machine_list[i]
      M2 = Machine_list[i+1]

      # 上限下限を確認
      m1max = M1[0] + M1[1]
      m2min = M2[0] - M2[1]
      
      # m1の上限とm２の下限が接するかを確認
      if (m2min - m1max) < 0:
        del Machine_list[i+1]
        return False
  return True

while MachineArrangementCheck() == False:
  continue
  
print(len(Machine_list))

### FIXED CODE ###

n = int(input())
m_list = []
for i in range(n):
    x,l = map(int, input().split())
    m_list.append([x-l, x+l])

m_list = sorted(m_list,key= lambda x:x[1])

result = 0
cur_pos = -1000000000

for min,max in m_list:
    if cur_pos <= min:
        result += 1
        cur_pos = max
print(result)
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    dh, dw = 0,1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 0,-1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = -1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = [sorted(input()) for _ in range(N)]

print(sum(1 if s1 == s2 else 0 for s1, s2 in combinations(S, 2)))


### FIXED CODE ###

from collections import Counter

N = int(input())
S = ["".join(sorted(list(input()))) for _ in range(N)]

cnt = Counter(S)
print(sum(v*(v-1)//2 for v in cnt.values()))