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

n = int(input())
strlist = []
for i in range(n):
    strlist.append(sorted(list((str(input())))))
    
count = 0
for i in range(n):
    for j in range(i+1, n):
        if(strlist[i] == strlist[j]):
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
strdict = {}
count = 0
for i in range(n):
    sortedstr = "".join(sorted(str(input())))
    strdict.setdefault(sortedstr, 0)
    count += strdict[sortedstr]
    strdict[sortedstr] += 1
print(count)
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline
s = [int(x) if x!="?" else -1 for x in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*n
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i,j):
	if j-a*data[i]%A>=0:
		re = j-a*data[i]%A
	else:
		re = j-a*data[i]%A+13
	return re

for i in range(n):
	for j in range(A+1):
		if s[i]!=-1:
			dp[i+1][j]=dp[i][benri(s[i],i,j)]

		else:
			for c in range(10):
				dp[i+1][j]+=dp[i][benri(c,i,j)]

			
			
# print(dp)
print(dp[n][5]%(10**9+7))
				


### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])
### BUGGY CODE ###

import math
K=int(input())
sum_gcd=0
for a in range(1,K+1):
    for b in  range(1,K+1):
        for c in  range(1,K+1):
            sum_gcd+=math.gcd(c,math.gcd(a,b))
print(sum_gcd)

### FIXED CODE ###

import math
K=int(input())
dp=[[0][0]]*K
sum_gcd=0
c=1
for a in range(1,K+1):
    for b in  range(1,K+1):
            for c in  range(1,K+1):
                sum_gcd+=math.gcd(c,math.gcd(a,b))
print(sum_gcd)
### BUGGY CODE ###

import itertools

N = int(input())
L = list(map(int, input().split()))
L.sort()

comb = itertools.combinations([i for i in range(N)], 2)
cnt = 0

for cmb in comb:
    a = L[cmb[0]]
    b = L[cmb[1]]
    for i in range(cmb[1]+1, N):
        if L[i] < a+b:
            cnt += 1
    

print(cnt)

### FIXED CODE ###

import math
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        cnt += bisect.bisect_left(L[j+1:N], L[i]+L[j])
        
print(cnt)
### BUGGY CODE ###

from itertools import product
from math import gcd

k = int(input())

result = 0
for a, b, c in product(range(1, k+1), repeat=3):
    result += gcd(a, gcd(b, c))

print(result)


### FIXED CODE ###

from itertools import product
from math import gcd

k = int(input())

result = 0
for a, b, c in product(range(1, k+1), repeat=3):
    result += gcd(a, gcd(b, c))

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

# key not available ""
n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[0 for i in range(w+1)] for j in range(n)]
def go(i,w):
    if w <= 0 or i < 0:
        return 0
    if dp[i][w] >0:
        return dp[i][w]
    if weights[i] <= w:
        dp[i][w] = max(go(i-1, w), go(i-1, w-weights[i])+value[i])
    else:
        dp[i][w] = go(i-1,w)
    return dp[i][w]
print(go(n-1,w))
## 0 1 2 3  4  5  6  7  8
#  0 0 0 30 30 30 30 30 30
#  0 0 0 30 50 50 50 80 80
#  0 0 0 30 50 60 60 80 90

### FIXED CODE ###

# key not available ""
n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[0 for i in range(w+1)] for j in range(n)]
for i in range(n):
    for j in range(1, w+1):
        if weights[i] <= j:
            dp[i][j] = max(value[i] + dp[i-1][j-weights[i]],dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

## 0 1 2 3  4  5  6  7  8
#  0 0 0 30 30 30 30 30 30
#  0 0 0 30 50 50 50 80 80
#  0 0 0 30 50 60 60 80 90
### BUGGY CODE ###

import collections
s = collections.deque(input())
q = int(input())

for i in range(q):
    t = tuple(input().split())
    if t[0] == "1":
        s.reverse()
    elif t[1] == "1":
        s.appendleft(t[2])
    else:
        s.append(t[2])

ans = ""

for i in range(len(s)):
    ans += s.popleft()

print(ans)

### FIXED CODE ###

s = input()
q = int(input())

rev = 0
head = []
tail = []

for i in range(q):
    t = input().split()
    if t[0] == "1":
        rev ^= 1
    else:
        if (int(t[1])-1)^rev == 0:
            head.append(t[2])
        else:
            tail.append(t[2])

h = "".join(head)
t = "".join(tail)

if rev == 0:
    print(h[::-1] + s + t)
else:
    s = s[::-1]
    print(t[::-1] + s + h)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
import fractions



def main():
    N = int(input())
    A = tuple([int(x) for x in input().split()])
    MOD = 10 ** 9 + 7

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

    ans = 0
    for a in A:
        ans += x // a
        ans %= MOD

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

input = sys.stdin.readline
import fractions



def main():
    N = int(input())
    A = tuple([int(x) for x in input().split()])
    MOD = 10 ** 9 + 7

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

    ans = 0
    for a in A:
        ans += x // a

    print(ans % MOD)



    
    

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

import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = [None for i in range(n - 1)]
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[edge.index((min(num, prev), max(num, prev)))]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        temp = edge.index((a, b))
        if color[temp] != None:
            continue
        else:
            if count == col:
                color[temp] = count + 1
                count += 2
            else:
                color[temp] = count
                count += 1
            queue.append((i, num))
print(max(color))
for i in range(n - 1):
    print(color[i])

### FIXED CODE ###

import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = {}
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[(prev, num)]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        if (a, b) in color.keys():
            continue
        else:
            if count == col:
                color[(a, b)] = count + 1
                count += 2
            else:
                color[(a, b)] = count
                count += 1
            queue.append((i, num))
print(max([len(graph[i]) for i in range(n + 1)]))
for i, j in edge:
    print(color[(i, j)])
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
now=[[0,0] for i in range(n)]
day=0

while 1:
    day+=1
    siaisuu=0
    for i in range(n):
        if now[i][0]==n-1:
            continue
        # print(i)
        nex=a[i][now[i][0]]
        # print(day)
        # print(now)
        # print(nex)
        # print(a[nex-1][now[nex-1]])
        if i+1==a[nex-1][now[nex-1][0]] and now[i][1] != day and now[nex-1][1] != day:
            siaisuu+=1
            now[i][0]+=1
            now[i][1],now[nex-1][1]=day,day
            now[nex-1][0]+=1
    if siaisuu==0:
        break

for i in range(n):
    if now[i][0]!=n-1:
        print(-1)
        quit()

print(day-1)

### FIXED CODE ###

from collections import deque

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

for i in range(n):
    for j in range(n-1):
        a[i][j]-=1
    a[i].reverse()
# print(a)
day=[0]*n
pair=[-1]*n

q=deque(range(n))

while q:
    me=q.popleft()
    if not a[me]:
        continue
    oppo=a[me].pop()
    if pair[oppo]==me:
        now=max(day[me],day[oppo])+1
        day[me]=now
        day[oppo]=now
        q.append(me)
        q.append(oppo)
    else:
        pair[me]=oppo


for i in range(n):
    if a[i]:
        print(-1)
        break
else:
    print(max(day))
### BUGGY CODE ###

import numpy

tmp=input()
list=input().split(" ")
array=numpy.zeros(len(list),dtype=">i4")
for i in range(len(list)):
  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  if int(b[0]) in array:
    pos=numpy.where(array==int(b[0]))[0]
    for j in pos:
      array[j]=int(b[1])
    sum=numpy.sum(array)
    print(sum)
  else:
    sum=numpy.sum(array)
    print(sum)

### FIXED CODE ###

import numpy

tmp=input()
list=input().split(" ")
list=[int(x) for x in list]
array=numpy.array(list,dtype=">i4")
sum=numpy.sum(array)
all=numpy.zeros(100001,dtype=">i4")
for i in array:
  all[i]+=1
#for i in range(len(list)):
#  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  b0=int(b[0])
  b1=int(b[1])
  diff=all[b0]*(b1-b0)
  sum+=diff
  all[b1]+=all[b0]
  all[b0]=0
  print(sum)
### BUGGY CODE ###

N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = 10 ** 8 * K
for i in range(N-K+1):
  for j in range(i+(K-1), N):
    a = min(abs(x[i]), abs(x[j])) + abs(x[i] - x[j])
    if ans > a:ans = a
print(ans)

### FIXED CODE ###

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

ans = float('inf')
for i in range(n-k+1):
    l, r = X[i], X[i+k-1]
    if r <= 0:
        ans = min(abs(l), ans)
    elif 0 <= l:
        ans = min(abs(r), ans)
    else:
        dist = min(abs(l), abs(r))*2+max(abs(l), abs(r))
        ans = min(dist, ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    r_append = wv.append
    for _ in range(N):
        r_append(list(map(int,input().split())))
    dp = [[0]*(W+1) for i in range(N+1)]

    #print(wv)
    #print(dp)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

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

N = int(input())
S = input()
ans = 0
for n in range(N):
    X = S[:n]
    Y = S[n:]
    dp = [[0 for i in range(len(X)+1)] for j in range(len(Y)+1)] #0で初期化

    for i in range(len(Y)):
        for j in range(len(X)):
            if X[j] == Y[i]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    ans = max(ans, dp[-1][-1])
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N):
    k = ans + 1
    for j in range(k, N-i):
        if S[i:i+j] in S[i+j:]:
            ans = max(ans, j)
        else:
            break
print(ans)
### BUGGY CODE ###

import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
A = sorted(list(map(int, inputs[1].split())))
MOD = 10 ** 9 + 7

ans = 0
for i in range(n-1):
    for j in range(i, n):
        ans += A[i] ^ A[j]
        ans %= MOD
print(ans)

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))
MOD = 10 ** 9 + 7

bit = len(format(max(A), 'b'))
ans = 0
for i in range(bit):
    nb_1 = sum(((a >> i) & 1 for a in A))
    ans += (nb_1 * (n - nb_1)) << i
    ans %= MOD
    
print(ans)
### BUGGY CODE ###

N, M, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]
B = [int(x) for x in input().split(' ')]

# N, M, K = [int(x) for x in [2e3, 2e3, 1e9]]
# A = [int(x) for x in range(N)]
# B = [int(x) for x in range(M)]

stack = [[0, 0, 0, 0]]
ans = 0
while len(stack):
  s = stack[-1]
  stack.pop()

  count = s[3]
  a = count 
  b = count
  i = s[0]
  j = s[1]
  time = s[2]

  if i > N - 1 and j > M - 1:
    ans = max(ans, count)
    continue
  if time > K:
    ans = max(ans, count - 1)
    continue

  if i < N:
    stack.append([i + 1, j, time + A[i], count + 1])
  if j < M:
    stack.append([i, j + 1, time + B[j], count + 1])

print(ans)

### FIXED CODE ###

N, M, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]
B = [int(x) for x in input().split(' ')]

# N, M, K = [int(x) for x in [2e3, 2e3, 1e9]]
# A = [int(x) for x in range(N)]
# B = [int(x) for x in range(M)]

A_deep = 0
B_deep = 0
time = 0
while A_deep < N:
  if K >= time + A[A_deep]:
    time += A[A_deep]
    A_deep += 1
  else:
    break 
while B_deep < M:
  if K >= time + B[B_deep]:
    time += B[B_deep]
    B_deep += 1
  else:
    break 

i = A_deep - 1
j = B_deep
ans = i + j + 1
while i >= 0 and j < M:
  while i >= 0:
    time -= A[i]
    i -= 1
    if K - time >= B[j]:
      break 
  while j < M:
    if K >= time + B[j]:
      time += B[j]
      j += 1
      ans = max(ans, i + j + 1)
    else: 
      break 


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

n, w = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= t[i][0]:
            dp[i+1][j] = max(dp[i][j-t[i][0]] + t[i][1], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

n, w = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= t[i][0]:
            dp[i+1][j] = max(dp[i][j-t[i][0]] + t[i][1], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])
### BUGGY CODE ###

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

for i, a in enumerate(A):
    if i == 0:
        bits = [[0] * 60]
    else:
        bits.append(bits[i - 1].copy())

    cnt = 0
    while a != 0:
        if a & 1:
            bits[i][cnt] += 1

        cnt += 1
        a >>= 1


all_sum = 0
two_exp = [pow(2, i, MOD) for i in range(60)]

for i, a in enumerate(A):
    temp_sum = 0
    cnt = 0
    while cnt < 60:
        ones = bits[-1][cnt] - bits[i][cnt]
        zeros = N - (i + 1) - ones

        if a & 1:
            temp_sum += (two_exp[cnt] * zeros) % MOD
        else:
            temp_sum += (two_exp[cnt] * ones) % MOD

        temp_sum %= MOD

        a >>= 1
        cnt += 1

    all_sum += temp_sum
    all_sum %= MOD


print(all_sum)



### FIXED CODE ###

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

sum_all = 0
p = 1
for i in range(60):
    ones = 0
    zeros = 0

    x = 1 << i
    for a in A:
        if a & x:
            ones += 1
        else:
            zeros += 1

    sum_all += p * ones * zeros % MOD
    p *= 2 % MOD


print(sum_all % MOD)
### BUGGY CODE ###

import math
k= int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)


### FIXED CODE ###

import math
k= int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        x = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(x,c)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a_sort = sorted(a)
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang, pos):
    lb_rang = 0
    ub_rang = len(rang) - 1
    lb_pos = 0
    ub_pos = len(pos) - 1
    ret= 0 
    while lb_rang <= ub_rang:
        if abs(rang[lb_rang]-pos[ub_pos]) < abs(rang[ub_rang]-pos[lb_pos]):
            ret += abs(rang[ub_rang]-pos[lb_pos])
            ub_rang -= 1
            lb_pos += 1
        else:
            ret += abs(rang[lb_rang]-pos[ub_pos]) 
            lb_rang += 1
            ub_pos -= 1
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang, pos):
    lb_rang = 0
    ub_rang = len(rang) - 1
    lb_pos = 0
    ub_pos = len(pos) - 1
    ret= 0 
    while lb_rang <= ub_rang:
        if abs(rang[lb_rang]-pos[ub_pos]) < abs(rang[ub_rang]-pos[lb_pos]):
            ret += abs(rang[ub_rang]-pos[lb_pos])
            ub_rang -= 1
            lb_pos += 1
        else:
            ret += abs(rang[lb_rang]-pos[ub_pos]) 
            lb_rang += 1
            ub_pos -= 1
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))
### BUGGY CODE ###

S=list(input())
T=list(input())
N=len(S)

i=-1
for t in T:
  if t in set(S[(i+1)%N:]):
    i+=S[(i+1)%N:].index(t)+1
  elif t in set(S[:(i+1)%N]):
    i+=N-1-i%N+S.index(t)+1
  else:
    print(-1)
    exit()

print(i+1)

### FIXED CODE ###

import bisect
S=list(input())
T=list(input())
sT=set(T)
N=len(S)
TI={}
for i in range(N):
  s=S[i]
  if s in sT:
    if s in TI:
      TI[s].append(i)
    else:
      TI[s]=[i]

i=-1
for t in T:
  if t not in TI:
    print(-1)
    exit()
  else:
    ni=TI[t][(bisect.bisect_right(TI[t],i%N))%len(TI[t])]
    if ni>i%N:
      i+=ni-i%N
    else:
      i+=N-i%N+ni
print(i+1)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
cost = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
    cost[a].append(b)
    cost[a].sort()

#print(cost)
for i,j in ab:
    ID = cost[i].index(j)+1
    i = str(i)
    i = (6-len(i))*'0'+i
    ID = str(ID)
    ID = (6-len(ID))*'0'+ID
    print(i+ID)

### FIXED CODE ###

n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):
 
        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)
 
 
for i, tmp in enumerate(py):
    print(ans[tmp])
### BUGGY CODE ###

from functools import reduce
import fractions
import copy


def gcd(L):
    return reduce(fractions.gcd, L)

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

    ans = 0
    for a in A:
        B = copy.deepcopy(A)
        B.remove(a)
        ans = max(ans,gcd(B))

    print(ans)






main()

### FIXED CODE ###

import fractions


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

    gcd_ans = []
 
    l = [0] * N
    r =[0] * N
    for i in range(N-1):
        l[i+1] = fractions.gcd(l[i],A[i])
        r[i+1] = fractions.gcd(r[i],A[N-1-i])
    r.reverse()
 
    for i in range(N):
        gcd_ans.append(fractions.gcd(l[i],r[i]))
 
    print(max(gcd_ans))


main()
### BUGGY CODE ###

import bisect
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
ok = -10**20  # There are <= K pairs <= ok
ng = 10**20   
# x, count

while ok + 1 < ng:
  x = (ok + ng) //2
  count = 0
  for i, a in enumerate(A):
    if a > 0:
      j = bisect.bisect_right(A, x // a)
      if i < j:
        count += j - 1
      else:
        count += j
    elif a < 0:
      j = bisect.bisect_left(A, - (-x // a))
      #print(x, a, -(-x//a), j)
      if i >= j:
        count += N - j - 1
      else:
        count += N - j
    else: # a == 0
      if x >= 0:
        count += N-1
    #print(x, a, count)
  count //= 2
  #print(x, count)
  if count < K:
    ok = x
  else:
    ng = x
  
  
print(ng)

### FIXED CODE ###

def main(N, K, A):
  cp = 0
  cn = 0
  cz = 0
  An = []
  Anp = []
  Ap = []
  for a in A:
    cp += a > 0
    cn += a < 0
    cz += a == 0
    if a > 0:
      Ap.append(a)
    if a < 0:
      An.append(a)
      Anp.append(-a)
  Anp = sorted(Anp)
	
  if K <= cn * cp:
    # negative 
    #print(K)
    
    ok = -10**20  # There are <= K pairs <= ok
    ng = 0
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      i_an = -1
      for i, a in enumerate(Ap): # a: increasing -> x // a increasing
        while i_an + 1 < len(An) and An[i_an + 1]* a <= x:
          i_an += 1

        count += i_an + 1
        #print(x, a, count)
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng
  elif K <= cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2:
    
    return 0
  else:
    # positive
    #print(K)
    K -=  cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2
    #print(K)
    ok = 0
    ng = 10**20  # There are <= K pairs <= ok
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      for Aa in [Ap, Anp]:
        i_ap = -1
        for i, a in zip(range(len(Aa)-1, -1, -1), Aa[::-1]):
          # a: decreasing -> x // a increasing
          while i_ap+1 < len(Aa) and Aa[i_ap+1] * a <= x:
            i_ap += 1
          count += i_ap + 1
          count -= i <= i_ap
          #print(x, a, count, i, i_ap, Aa)
      count //= 2
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
print(main(N,K,A))
#pairs = []
#for i in range(len(A)):
#  for j in range(i + 1, len(A)):
#    pairs.append(A[i]*A[j])
#pairs.sort()
#for K, p in zip(range(1, N*(N+1)//2+1), pairs):
#  
#  result = main(N, K, A)
#  if result != p:
#    print(K, p, result)
#print('done')