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

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

import fractions

def segfunc(x, y):
    return fractions.gcd(x, y)

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = 0

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(A)

ans = -1
for i in range(n):
    ans =max(ans, fractions.gcd(query(0, i), query(i+1, n)))
print(ans)

### FIXED CODE ###

import fractions

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

gcd_l = [0]
gcd_r = [0]

for i in range(n):
  gcd_l.append(fractions.gcd(gcd_l[i], l[i]))
  gcd_r.append(fractions.gcd(gcd_r[i], l[-(i+1)]))
gcd_r = gcd_r[::-1]
# print(gcd_l)
# print(gcd_r)

ans = [0]*n
for i in range(n):
  ans[i] = fractions.gcd(gcd_l[i], gcd_r[i+1])
print(max(ans))
### BUGGY CODE ###

import numpy as np
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l2=np.zeros(N-1)
import sys
l_l=[i.rsplit() for i in sys.stdin.readlines()]
l_l = [list(map(int,i)) for i in l_l]
for i in l_l:
   l[i[0]-1].append(i[1])
   l[i[1]-1].append(i[0])
from collections import deque
que=deque([1])
after=deque()
que_append=que.append
after_append=after.append
while que != deque([]):
   X=que.popleft()
   after_append(X)
   for i in l[X-1]:
      if i in after:
         continue
      if i in que:
         continue
      que_append(i)
      np.put(l2,[i-2],X)
if len(after) == N:
   print("Yes")
   for i in l2:
      print(int(i))
else:
   print("No")

### FIXED CODE ###

from collections import deque
def bfs(graph,N):
   que=deque([0])
   visited=[0]*N
   visited[0]=1
   while que:
      node=que.popleft()
      for i in graph[node]:
         if not visited[i]:
            visited[i]=node+1
            que.append(i)
   return visited
N,M= list(map(int,input().split()))
l=[[] for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
ans=bfs(l,N)[1:]
if all(ans):
   print("Yes")
   print(*ans,sep="\n")
else:
   print("No")
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))

    #output
    answer = 0
    for a in A:
        if N - np.count_nonzero(a % A) > 1:
            answer += 1
    answer = N - answer
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        m = max(dp[:h[i]])
        dp[h[i]] = m + a[i]
    return(max(dp))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f3(n, h, a))


### FIXED CODE ###

# coding: utf-8

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

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        i1 = 2 * i + 1
        i2 = i1 + 1
        lr = (l + r) // 2
        lmax = getmax(a, b, i1, l, lr)
        rmax = getmax(a, b, i2, lr, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f2(n, h, a))
### BUGGY CODE ###

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

for i in M:
  if i in N:
    N.remove(i)
  else:
    print("NO")
    exit()
print("YES")

### FIXED CODE ###

from collections import Counter
n = int(input())
d= Counter(list(map(int, input().split())))
m = int(input())
t= Counter(list(map(int, input().split())))
if t-d=={}:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)

colors = [-1]*(N+1)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
def dfs(n,c):
    if colors[n] == -1:
        colors[n] = c
        for nx in edges[n]:
            dfs(nx,(c+1)%2)
    else:
        if colors[n] != c:
            print(choose(N,2)-M)
            exit()
dfs(1,0)
white = colors.count(0)
black = N - white
print(white*black-M)

### FIXED CODE ###

"""
グラフが二部グラフかどうかを判定する。
二部グラフであれば、AグループのノードとBグループのノード同士をそれぞれ結ぶことができる。
二部グラフでない場合、すべてのノード同士を結ぶことができる。
"""
import math
from collections import Counter
import sys
sys.setrecursionlimit(200000)
def choose(n):
    return math.factorial(n)//(math.factorial(n-2)*math.factorial(2))
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)

colors = [-1]*(N+1)
def f(n,p):
    c = colors[n]
    for v in edges[n]:
        if v != p:
            if colors[v] == -1:
                colors[v] = 1 if c==0 else 0
                f(v,n)
            elif colors[v] == c:
                print(choose(N)-M)
                exit()
colors[1]=0
f(1,0)
count1 = colors.count(0)
count2 = colors.count(1)
print(count1*count2-M)
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
N = int(input())
A = prod(list(map(int,input().split())))

if A <= 10**18:
    print(A)
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)
            exit()
    print(ans)
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    if visited[y][x] != -1 and visited[y][x] < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if grid[ny][nx] != pre and grid[ny][nx] == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
        else:
            if count == nc:
                q.appendleft((nx, ny, nc, grid[ny][nx]))
            else:
                q.append((nx, ny, nc, grid[ny][nx]))

# print(visited)
print(ans)

### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    v_score = visited[y][x]
    if v_score != -1 and v_score <= count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        n_color = grid[ny][nx]
        if n_color != pre and n_color == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
            print(ans)
            sys.exit()
        else:
            if visited[ny][nx] != -1 and visited[ny][nx] <= nc:
                continue
            if count == nc:
                q.appendleft((nx, ny, nc, n_color))
            else:
                q.append((nx, ny, nc, n_color))

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



def binsearch(x,value):
    left=0; right=len(x)-1
    if x[right] == value:
        return right
    elif x[left] == value:
        return left
    while True:
        m = (right+left)//2
        if x[m] == value:
            return m
        elif x[m] > value:
            right = m
        else:
            left = m


def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    newx = sorted(x)
    for i in x:
        index = binsearch(newx,i)
        del newx[index]
        print(newx[(n-1)//2])
        newx.insert(index,i)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    newx = sorted(x)
    ans = dict()
    for i,xx in enumerate(newx):
        if i+1 <= n//2:
            ans[xx] = newx[n//2]
        else:
            ans[xx] = newx[n//2-1]
    for xx in x:
        print(ans[xx])

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

n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = [sum([x ^ an for an in a]) for x in range(0, k+1)]
print(max(b))


### FIXED CODE ###

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

bits_k = len(bin(k)) - 2
forma = '0%db' % bits_k
data = [0 for i in range(bits_k)]

for an in a:
    anb = format(an, forma)
    #print(anb)
    for i in range(bits_k):
        if anb[-i-1] == '0':
            data[i] += 1
        else:
            data[i] -= 1

#print(data)
ans = 0
for i in range(bits_k - 1, -1, -1):
    if data[i] > 0:
        ans |= (1 << i)
        if ans > k:
            ans &= ~(1 << i)

#print(ans)
b = sum([ans ^ an for an in a])
print(b)
### BUGGY CODE ###

import math

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

ans = 1
for num in range(N):
    ans *= A[num]
    if 0 in A:
        ans = 0
        break
    elif ans > math.pow(10, 18):
        ans = -1
        break

print(ans)

### FIXED CODE ###

import math

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

ans = 1
for num in range(N):
    ans *= A[num]
    if ans > math.pow(10, 18):
        ans = -1
        break

if 0 in A:
    ans = 0

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

import queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, V):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK and d[v] == INFTY:
                d[v] = d[u] + 1
                color[v] = GRAY
                q.put(v)

    return d

def rec(s, i, depth):
    if depth == 3:
        kkpgraph[s].append(i)
        return
    if not graph[i]:
        return
    for node in graph[i]:
        rec(s, node, depth+1)
    return

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
kkpgraph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
for i in range(1, N+1):
    rec(i, i, 0)
    kkpgraph[i] = list(set(kkpgraph[i]))
d = dijkstra(S, kkpgraph)
if d[T] == INFTY:
    print(-1)
else:
    print(d[T])


### FIXED CODE ###

import queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def bfs(s, V):
    color = [[WHITE for i in range(N+1)] for j in range(3)]
    d = [[INFTY for i in range(N+1)] for j in range(3)]
    d[0][s] = 0
    q = queue.Queue()
    q.put((0, s))
    
    while not q.empty():
        dv, u = q.get()
        color[dv%3][u] = BLACK

        for v in V[u]:
            if color[(dv+1)%3][v] != BLACK and d[(dv+1)%3][v] == INFTY:
                d[(dv+1)%3][v] = d[dv%3][u] + 1
                q.put((d[(dv+1)%3][v], v))

    return d

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
d = bfs(S, graph)
if d[0][T] == INFTY:
    print(-1)
else:
    print(d[0][T]//3)
### BUGGY CODE ###

N = int(input())
max_keys = []
max_cnt = 1
c = {}
for _ in range(N):
    s = input()
    if s in set(c.keys()):
        c[s] += 1
    else:
        c[s] = 1

    if max_cnt == c[s]:
        max_keys.append(s)
    elif max_cnt < c[s]:
        max_keys = [s]
        max_cnt = c[s]

for x in sorted(max_keys):
    print(x)

### FIXED CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]
C = collections.Counter(S)
max_cnt = C.most_common()[0][1]
tmp = sorted([k for k,v in C.items() if v == max_cnt])
for ans in tmp:
    print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
ls = []
cnt = 0
for i in range(m):
    l, r = map(int, input().split())
    ln = l
    while r >= ln:
        ls.append(ln)
        ln += 1
for i in range(ln):
    if ls.count(i) == m:
        cnt += 1
print(cnt) 


### FIXED CODE ###

n, m = map(int, input().split())
snum = 0
bnum = 100000
for i in range(m):
    l, r = map(int, input().split())
    if l >= snum:
        snum = l
    if r <= bnum:
        bnum = r
if snum > bnum:
    print(0) 
else:
    print(bnum - snum + 1)
### BUGGY CODE ###

def main():
	import sys
	input=sys.stdin.readline
	all,rolls=map(int,input().split())
	List=list(map(int,input().split()))

	sum = 0
	sumList =[]

	for i in range(all - rolls + 1):
		sum = 0
		for j in range(rolls):
			sum = sum + (List[i + j] + 1) / 2
		sumList.append(sum)

	sumList.sort(reverse=True)
	print(sumList[0])

if __name__ == '__main__':
	main()


### FIXED CODE ###

all,rolls=map(int,input().split())
inputList=list(map(int,input().split()))

sum = 0
sumList =[]

# 初めに全期待値計算
for i in range(all):
	inputList[i] = (inputList[i] + 1) / 2

# 最初の組み合わせの期待値計算
for i in range(rolls):
	sum = sum + inputList[i]
sumList.append(sum)

# 2番目以降の期待値計算
for i in range(all - rolls):
	sum = sum + inputList[i + rolls] - inputList[i]
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])
### BUGGY CODE ###

N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = sorted(list(map(int, input().split(" "))))
bottoms = sorted(list(map(int, input().split(" "))))


def binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] > num:
        return binary_search(check_list, num, left, mid - 1)
    elif check_list[mid] == num:
        return mid
    else:
        return binary_search(check_list, num, mid + 1, right)


total_count = 0
for bottom in bottoms:
    mid_insert_index = binary_search(mids, bottom, 0, N - 1)

    for mid in mids[0:mid_insert_index]:
        top_insert_index = binary_search(tops, mid, 0, N - 1)
        total_count += len(tops[0:top_insert_index])
print(total_count)


### FIXED CODE ###

import bisect
N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = list(map(int, input().split(" ")))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


# def left_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] >= num:
#         return left_binary_search(check_list, num, left, mid - 1)
#     else:
#         return left_binary_search(check_list, num, mid + 1, right)


# def right_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] > num:
#         return right_binary_search(check_list, num, left, mid - 1)
#     else:
#         return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    # bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    bottom_start_index = bisect.bisect_right(bottoms, mid)
    # top_end_index = left_binary_search(tops, mid, 0, N - 1)
    top_end_index = bisect.bisect_left(tops, mid)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)
### BUGGY CODE ###

from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.8:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        if t2 - t1 > 0.8:
            flag = 0
            break
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
        ans %= mod
    print(ans%mod)


### FIXED CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])


### FIXED CODE ###

rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])
### BUGGY CODE ###

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

expected_list = [(x+1)/2 for x in p_list]

maximum = 0
for i in range(n-(k-1)):
    maximum = max(maximum, sum(expected_list[i:i+k]))
print(maximum)

### FIXED CODE ###

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

expected_list = [(x+1)/2 for x in p_list]

partsum = sum(expected_list[0:k])
maximum = partsum
for i in range(1, n-(k-1)):
    partsum = partsum + expected_list[i+k-1] - expected_list[i-1]
    maximum = max(maximum, partsum)
print(maximum)
### BUGGY CODE ###

x=int(input())

def enum_div(n):
    ir=int(n**(0.5))+1
#    ret=[]
    ret=set()
    for i in range(1,ir):
        if n%i == 0:
            ret.add(i)
#            ret.append(i)
            if (i!= 1) & (i*i != n):
#                ret.append(n//i)
                ret.add(n//i)
    return ret

ret=enum_div(x)

y=100000
for ai in range(-y,y):
    yn=""
    for r in ret:
        bi=ai-r
        if ai**5-bi**5==x:
            yn="YES"
            break
        bi=ai+r
        if ai**5-bi**5==x:
            yn="YES"
            break
    if yn=="YES":
        break

if yn=="YES":
    print(ai,bi)


### FIXED CODE ###


x=int(input())

def enum_div(n):
    ir=int(n**(0.5))+1
#    ret=[]
    ret=set()
    for i in range(1,ir):
        if n%i == 0:
            ret.add(i)
#            ret.append(i)
            if (i!= 1) & (i*i != n):
#                ret.append(n//i)
                ret.add(n//i)
    return ret

ret=enum_div(x)

y=20000
for ai in range(-y,y):
    yn=""
    for r in ret:
        bi=ai-r
        if ai**5-bi**5==x:
            yn="YES"
            break
        bi=ai+r
        if ai**5-bi**5==x:
            yn="YES"
            break
    if yn=="YES":
        break

if yn=="YES":
    print(ai,bi)
### BUGGY CODE ###

n=int(input())

S=[]
for i in range(n):
    s=input()
    if s not in S:
        S.append(s)
print(len(S))


### FIXED CODE ###

n=int(input())
S=[]
for i in range(n):
    S.append(input())
print(len(list(set(S))))
### BUGGY CODE ###

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

frends = []

for i in range(m):
  a,b = map(int, input().split())
  ainclude = set()
  binclude = set()
  flag = False
  for j in frends:
    if a in j and b in j:
      flag = 'M'
      continue
    elif a in j:
      ainclude = j
      frends.remove(j)
      flag = True
    elif b in j:
      binclude = j
      frends.remove(j)
      flag = True
  if flag == False:
    frends.append({a,b})
  elif flag == 'Y':
    continue
  else:
    c = {a,b}
    frends.append(ainclude|binclude|c)

cnt = 1

for i in frends:
  num = len(i)
  if cnt < num:
    cnt = num


print(cnt)

### FIXED CODE ###

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x


N, M = map(int, input().split())
par = [-1 for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)

print(-min(par))
### BUGGY CODE ###

import itertools

N = int(input())
S = []
for i in range(N):
    s = list(input())
    s.sort()
    S.append(s)

S.sort()
A = []
cnt = 1

for i in range(N-1):
    if S[i] == S[i+1]:
        cnt += 1
    elif cnt > 1:
        A.append(cnt)
        cnt = 1
A.append(cnt)
        
ans = 0
for i in A:
    iL = [j for j in range(i)]
    ans += len(list(itertools.combinations(iL, 2)))

print(ans)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
    S = list(input())
    S.sort()
    S = ''.join(S)
    A[S] = A.get(S, 0) + 1

ans = 0
for i in A.values():
    if i > 1:
        iL = [j for j in range(i)]
        ans += sum(iL)
    
print(ans)