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

def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()


### FIXED CODE ###

def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(x+1)
            exit()
        if chk:
            print(-1)
            exit()

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

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

sum_num = 0
for i in range(N-1):
  sum_num += int_list[i] * sum(int_list[i+1:])
    
print(sum_num % (10 ** 9 + 7))

### FIXED CODE ###

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

sum_num = 0
sum_temp = sum(int_list[1:])

for i in range(N-1):
  sum_num += int_list[i] * sum_temp
  sum_temp -= int_list[i+1]
    
print(sum_num % (10 ** 9 + 7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(len(instr)+1):
		
		if i < j:
			str_list.append(instr[i:j])
		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(i, len(instr)+1):
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		if i < j:
			str_list.append(instr[i:j])

		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])
### BUGGY CODE ###

import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    B=np.array(B)
    B=np.cumsum(B)[:N]
    #print(B)
    A=B.copy()
print(*B)


### FIXED CODE ###

#import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
#K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    #B=np.array(B)
    A=[0]*N
    A[0]=B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

    if min(A)==N:
        break
    #print(B)
    
    
print(*A)
### BUGGY CODE ###

def e():
    n=int(input())
    s=input()
    ans=0

    for i in range(n):
        cnt = 0
        for j in range(n-i):
            if s[j] == s[i+j]:
                cnt+=1
            else:
                cnt = 0
            ans = max(ans, min(i, cnt))
    return ans


print(e())

### FIXED CODE ###

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

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

ans = 0

for j in range(N - 1, 0, -1):
    sj = S[j]
    for i in range(j-1, -1, -1):
        si = S[i]
        if j == N - 1:
            if si == sj:
                dp[j][i] = 1
                ans = 1
        else:
            if si == sj:
                dp[j][i] = min(j - i, dp[j + 1][i + 1] + 1)
                ans = max(ans, dp[j][i])

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

n = int(input())
li = list(map(int,input().split()))
ans = 0

for x in range(min(li), max(li)+1):
    if x == min(li):
        a = li.count(x-1)
        b = li.count(x)
        c = li.count(x+1)

    else:
        a = b
        b = c
        c = li.count(x+1)
    
    y = a+b+c
    if y > ans:
        ans = y
    
print(ans)


### FIXED CODE ###

import collections

n = int(input())
li = list(map(int,input().split()))
ans = []

for i in li:
    ans.append(i-1)
    ans.append(i)
    ans.append(i+1)

c = collections.Counter(ans)

print(c.most_common()[0][1])
### BUGGY CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  
  for a in A:
    prod *= a
    
  if prod > 1000000000000000000:
    print(-1)
    return
  
  else:
    print(prod) 

main()

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  A.sort()
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  
  print(prod) 
 
main()
### BUGGY CODE ###

import numpy as np

N = int(input())
l = list(map(int, input().split()))
nl = np.array(l)
X = nl.sum()
a = []
for i in range(N-1):
    x = nl[0:i+1]
    a.append(abs(2 * x.sum() - X))
print(min(a))

### FIXED CODE ###

import numpy as np

N = int(input())
l = list(map(int, input().split()))
nl = np.array(l)
X = nl.sum()
a = []
x = 0
for i in range(N-1):
    x = x + nl[i]
    a.append(abs(2 * x - X))
print(min(a))
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans = 0
for x in range(1, min(B-1, N)+1):
    now = (A*(x%B) - (A*x)%B)/B
    ans = max(now, ans)
print(int(ans))

### FIXED CODE ###

A, B, N = map(int, input().split())
x = min(B-1, N)

ans = int(A*x/B) - A*int(x/B)
print(ans)
### BUGGY CODE ###

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

score = 1
for i in range(K):
    score *= A[i]

for i in range(K, N):
    tmp = score
    score /= A[i - K]
    score *= A[i]
    if int(score) > tmp:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

score = 1
for i in range(N - K):
    if A[i] < A[i + K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
ans = 1
for a in A:
    ans*=a
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
else:
    prod = 1
    for a in A:
        prod*=a
        if prod > 10**18:
            print(-1)
            quit()
    print(prod)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
RGB = sorted([R,G,B],reverse=True)
R,G,B = RGB[0],RGB[1],RGB[2]
for r in range(int(N/R)+1):
    for g in range(int((N-R*r)/G)+1):
        for b in range(int((N-(R*r+G*g))/B)+1):
            if(R*r+G*g+B*b == N):
                ans += 1
print(ans)



### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-R*r)//G+1):
        if (N-R*r-G*g)%B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = sorted(LI())
F = sorted(LI(), reverse=True)


que = [(-A[i] * F[i], -F[i], A[i]) for i in range(n)]
heapify(que)
while k and que:
    x, f, a = heappop(que)
    if a:
        a -= 1
        x -= f
        heappush(que, (x, f, a))
        k -= 1




if que:
    print(-que[0][0])
else:
    print(0)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = sorted(LI())
F = sorted(LI(), reverse=True)
ok = A[-1] * F[0]
ng = -1
while ok > ng + 1:
    mid = (ok + ng) // 2
    ret = 0
    for i in range(n):
        if A[i] * F[i] > mid:
            ret += (A[i] * F[i] - mid) // F[i] + bool((A[i] * F[i] - mid) % F[i])
    if ret > k:
        ng = mid
    else:
        ok = mid


print(ok)
### BUGGY CODE ###

n = int(input())
a = sorted([int(input()) for _ in range(n)], reverse=True)
suma = sum(a)

mod = 998244353
memo = {}
def doit(index, s, c):
    if index >= len(a):
        if s * 2 < suma:
            return 0
        elif s * 2 == suma:
            return ((2 ** (len(a) - c) - 1) * 3) % mod
        else:
            return ((2 ** (len(a) - c)) * 3) % mod
    key = (index, s, c)
    if key not in memo:
        memo[key] = (doit(index + 1, s + a[index], c + 1) + doit(index + 1, s, c)) % mod
    return memo[key]

print((3 ** len(a) - doit(0, 0, 0)) % mod)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
suma = sum(a)
suma2 = suma // 2
mod = 998244353

dp1 = [3] + [0] * suma2
dp2 = [3] + [0] * suma2
for ai in a:
    for j in range(suma2, ai - 1, -1):
        dp1[j] = (dp1[j] + dp1[j - ai] * 2) % mod
        dp2[j] = (dp2[j] + dp2[j - ai]    ) % mod
half = dp2[suma2] if suma % 2 == 0 else 0
print(((3 ** n) - sum(dp1) + half + mod) % mod)
### BUGGY CODE ###

A, B = map(int, input().split())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


a = make_divisors(A)
b = make_divisors(B)
L = []
for x in a:
    if x in b:
        L.append(x)
L.sort()
L = L[1:]#1を消す

ans = 1
for l in L:
    flag = False
    for i in range(2, l):
        if l % i == 0:
            flag = True
            break
    if flag:
        continue
    ans += 1

print(ans)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors


def is_prime(p):
    if p == 1:
        return False
    for i in range(2, int(p ** 0.5) + 1):
        if p % i == 0:
            return False
    return True


A, B = map(int, input().split())

g = gcd(A, B)
d = make_divisors(g)

ans = 1
for i in d:
    if is_prime(i):
        ans += 1

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

#!/usr/bin/env python3

S = input()
lis_2019 = [2019 * i for i in range(1, 99)]
cnt = 0
S_len = len(S)
cnt_1 = 0
S_lis = [S]

for i in range(4, S_len):
    while cnt_1 != S_len - i + 1:
        for j in lis_2019:
            if str(j) == str(S[cnt_1:cnt_1+i]):
                cnt += 1
        cnt_1 += 1
    cnt_1 = 0

print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3

S = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for i in S:
    num += int(i) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for i in counts:
    ans += i * (i - 1) // 2

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

def f(mtrx):
	maxSum = -10000000
	for colStart in range(n):
		partSum = [0]*n
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] += mtrx[row][colEnd]
			calcSum = maxPart(partSum)
			maxSum = max(calcSum, maxSum)
	return maxSum

def maxPart(mtrx):
	maxSum = -10000000
	for startP in range(n):
		for endP in range(startP,n):
			calcSum = sum(mtrx[startP:endP+1])
			maxSum = max(calcSum,maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

### FIXED CODE ###

def x(a):
	m=-10**9
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			for r in N:
				p[r]+=a[r][e]
			m=max(P(p),m)
	return m
def P(a):
	m,c=-10**5,0
	for i in N:
		c+=a[i]
		m=max(c,m)
		if c<0:c=0
	return m
n = input()
N = range(n)
print x([map(int, raw_input().split()) for i in N])
### BUGGY CODE ###

N = int(input())
points = list(map(int, input().split(' ')))
points.insert(0, 0)
points.insert(len(points), 0)

results = []
for i in range(1, len(points) - 1):
    sum, prev = 0, 0
    for point in range(1, len(points)):
        if point == i:
            continue
        sum += abs(prev - points[point])
        prev = points[point]

    print(sum)


### FIXED CODE ###

N = int(input())
points = list(map(int, input().split(' ')))
points.insert(0, 0)
points.insert(len(points), 0)

sum = 0
for i in range(1, len(points)):
    sum += abs(points[i - 1] - points[i])


for i in range(1, len(points) - 1):
    tmp_sum = 0
    if points[i - 1] <= points[i] <= points[i + 1]:
        print(sum)
        continue

    if points[i - 1] <= points[i + 1] <= points[i]:
        print(sum - 2 * abs(points[i] - points[i + 1]))
        continue

    if points[i] <= points[i - 1] <= points[i + 1]:
        print(sum - 2 * abs(points[i] - points[i - 1]))
        continue

    if points[i] <= points[i + 1] <= points[i - 1]:
        print(sum - 2 * abs(points[i] - points[i + 1]))

        continue
    if points[i + 1] <= points[i - 1] <= points[i]:
        print(sum - 2 * abs(points[i] - points[i - 1]))

        continue
    if points[i + 1] <= points[i] <= points[i - 1]:
        print(sum)

        continue
### BUGGY CODE ###

#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            else:
                row[j] = max(prerow[j],row[j-1])
    print(array[na][nb])



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

s = input()
c = int(input())

quary = [list(map(str, input().split())) for i in range(c)]

for q in quary:
    if q[0] == '1':
        s = s[::-1]
    
    else:
        if q[1] == '1':
            s = q[2] + s
        
        else:
            s = s + q[2]

print(s)

### FIXED CODE ###

from collections import deque

s = input()
c = int(input())

que = deque(s)

flipped = False
for i in range(c):
    query = input()
    
    if query[0] == '1':
        flipped = not flipped
    
    else:
        t, f, c = query.split()
        if (f == '1') ^ flipped:
            que.appendleft(c)
        
        else:
            que.append(c)



ans = ''.join(que)

if flipped:
    ans = ans[::-1]

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

X=int(input())

for i in range(int(pow(X,0.5)+1),0,-1):
  if X%i==0:
    s=int(pow(X/i/4,1/4))
    l,u=s-X//i,s+X//i+1
    for j in range(l,u):
      if X==(j+i)**5-j**5:
        print(j+i,j)
        exit()


### FIXED CODE ###

X=int(input())

for a in range(-118,120):
  for b in range(-119,119):
    if X==a**5-b**5:
      print(a,b)
      exit()
### BUGGY CODE ###

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    minmaxs = (sorted((zs[j+k], z - zs[j+k])) for k in (-1, 0, 1) if 0 <= j+k <= i)
    _, max1, min1 = min((x-n, x, n) for n, x in minmaxs)

    j = bisect_left(zs, (total - z)/2 + z)
    minmaxs = (sorted((zs[j+k] - z, total - zs[j+k])) for k in (-1, 0, 1) if i <= j+k <= n-2)
    _, max2, min2 = min((x-n, x, n) for n, x in minmaxs)

    minn, _, _, maxx = sorted([max1, min1, max2, min2])
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

### FIXED CODE ###

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))
### BUGGY CODE ###

n,s=open(0)
n=int(n)
a=0
for i in range(n):
  t=0
  for v,w in zip(s,s[i:n]):
    t=-~t*(v==w)
    a=max(a,min(t,i))
print(a)

### FIXED CODE ###

from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include<iostream>
using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')
### BUGGY CODE ###

S = input()
ans = ""
for s in range(len(S)):
  if S[s] == "?":
    ans += "D"
  else:
    ans += S[s]
print(ans)


### FIXED CODE ###

S = input()
ans = ""
for s in range(len(S)):
  if S[s] == "?":
    print("D", end="")
  else:
    print(S[s], end="")
print("")
### BUGGY CODE ###

N = int(input())
A = input().split()
result = 1
line = pow(10,18)

for i in range(N):
  result *= int(A[i])
if result > line:
  result = -1

print(result)


### FIXED CODE ###

N = int(input())
A = input().split()
result = 1
line = pow(10,18)

if "0" in A:
  result = 0
else:
  for i in range(N):
    result *= int(A[i])
    if result > line:
      result = -1
      break

print(result)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
b = ["" for i in range(N)]

def int_to_2(X):
    r = ""
    while X>0:
        r = r + str(X%2)
        X = int((X- X%2)/2)
    return(r)
    
def xor(a,b):
    rr = ""
    r = 0
    aa = int_to_2(a)
    bb = int_to_2(b)
    if len(bb) > len(aa):
        cc = bb
        bb = aa
        aa = cc
    for i in range(len(aa)-len(bb)):
        bb = bb + "0"
    for i in range(len(aa)):
        if aa[i]!=bb[i]:
            rr = rr + "1"
        else:
            rr = rr + "0"
    for i in range(len(aa)):
        r = r + (2**i)*int(rr[i])
    return(r)

ans = [0 for i in range(N)]

for i in range(N-1):
    ans[0] = xor(ans[0],a[i+1])

for i in range(N-1):
    ans[i+1] = xor(ans[i],xor(a[i],a[i+1]))

writeout = ""

for i in range(N):
    writeout = writeout + str(ans[i]) + " "

print(writeout)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
S = 0
for i in range(N):
    S ^= a[i]

Ans = ""
for i in range(N):
    print(S^a[i])
### BUGGY CODE ###

N = int(input())
word = [input() for i in range(N)]
sorted_word = [tuple(sorted(list(word[i]))) for i in range(N)]
dict_word = {sorted_word[i]:0 for i in range(N)}
ans = 0



for i in range(N):
  if sorted_word[i] in sorted_word[i+1:]:
    dict_word[sorted_word[i]] += 1
    
for value in dict_word.values():
  ans += (1+value) * value / 2
  
print(int(ans))

### FIXED CODE ###

N = int(input())
ans = 0
dict_word = {}
for i in range(N):
  sorted_word = str(''.join(sorted(list(input()))))
  try:
    ans += dict_word[sorted_word]
    dict_word[sorted_word] += 1
  except:
    dict_word[sorted_word] = 1
print(ans)
### BUGGY CODE ###

s = input()
dp = [1]+[0]*12
M = 10**9+7
lens = len(s)
mods = [4,1,10,9,12,3]

for i in range(1,lens+1):
  if s[-i] == '?':
    m = mods[i%6]
    dp = [sum(dp[(j-(m*k))%13] for k in range(10))%M for j in range(13)]  
  else:
    m = mods[i%6]*int(s[-i])
    dp = [dp[(j-m)%13] for j in range(13)]
print(dp[5]%M)

### FIXED CODE ###

M=10**9+7
r=[[(j-k)*9%13for j in range(10)]for k in range(13)]
d=[1]+[0]*12
for c in input():
  d = [sum(d[j]for j in k)%M for k in r] if c>'9' else [d[(int(c)-k)*9%13]for k in range(13)]
print(d[5])
### BUGGY CODE ###

#from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)


S = sum(A)
divisors = []

for i in range(1, S):
    if S < i * i:
        break

    if S % i == 0:
        divisors.append(i)
        divisors.append(S // i)


def check(x):
    modX = A % x
    modX = np.sort(modX)
    modX = modX[modX > 0]

    L = len(modX)
    rtn = False

    for i in range(L):
        cnt = 0
        minus = modX[:i]
        plus = modX[i:]

        cnt_minus = sum(minus - 0)
        cnt_plus = sum(x - plus)

        if cnt_minus <= K and cnt_plus <= K:
            rest = abs(cnt_minus - cnt_plus)
            if rest % x == 0:
                rtn = True
                break

    return rtn


ans = 1
for x in divisors:
    if check(x):
        ans = max(x, ans)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
#A = np.array(input().split(), dtype=np.int64)
A = list(map(int, input().split()))


S = sum(A)
divisors = []

for i in range(1, S):
    if S < i * i:
        break

    if S % i == 0:
        divisors.append(i)
        divisors.append(S // i)


def check(x):
    modX = [a % x for a in A if a % x != 0]
    modX.sort()

    L = len(modX)
    rtn = False

    for i in range(L):
        cnt = 0
        minus = modX[:i]
        plus = modX[i:]

        cnt_minus = sum(minus)
        cnt_plus = x * (L - i) - sum(plus)

        if cnt_minus <= K and cnt_plus <= K:
            rest = abs(cnt_minus - cnt_plus)
            if rest % x == 0:
                rtn = True
                break

    return rtn


ans = 1
for x in divisors:
    if check(x):
        ans = max(x, ans)

print(ans)