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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N,M,K = map(int,input().split())

mod = 10 ** 9 + 7
ans= 0
NCK = cmb(N*M-2,K-2) % mod

for i in range(N-1):
    for j in range(i,N):
        ans += M**2 * NCK * (j-i) 
        ans %= mod
        
for i in range(M-1):
    for j in range(i,M):
        ans += N**2 * NCK * (j-i) 
        ans %= mod
        
print(ans)

### FIXED CODE ###

  
    
N,M,K = map(int,input().split())


mod = 10 ** 9 + 7
MAX = N*M
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()
ans= 0
NCK = cmb(N*M-2,K-2) 
M2 = M**2 * NCK
N2 = N**2 * NCK
for i in range(1,N):
    ans += M2 * i * (N-i)
    ans %= mod
    
for i in range(1,M):
    ans += N2 * i * (M-i)
    ans %= mod
        
print(ans)
### BUGGY CODE ###

import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

MOD = 10 ** 9 + 7

N = I()
A = LI()
ans = 0

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

### FIXED CODE ###

import math
import sys
import os
from operator import mul
import numpy as np

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

MOD = 10 ** 9 + 7

N = I()
A = LI()
ans = 0

# A = np.array(A)
sum = [0]*(N+1)
for i in range(N):
        sum[i+1] = sum[i]+A[i]

for i in range(N-1):
    ans += A[i] * (sum[N] - sum[i+1]) % MOD

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

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

for i in range(N) :
  print(A.index(i+1)+1, end="")
  if (i+1) != N :
    print(" ", end="")


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = [0 for i in range(N)]
  
for i in range(N) :
  result[A[i]-1] = i+1

for i in range(N) :
  print(result[i], end="")
  print(" ", end="")
### BUGGY CODE ###

import bisect
import math
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    # print(a)
    # print(math.floor(a[-1] / 2))
    b = bisect.bisect_left(a, math.floor(a[-1] / 2))
    a.insert(b, math.floor(a[-1] / 2))
    a.pop(-1)

    if len(a) == 1:
        print(math.floor(a[0] / 2**(m - i - 1)))
        exit()
print(sum(a))


### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x * (-1), a))

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

c = list(map(lambda x: x * (-1), b))

print(sum(c))
### BUGGY CODE ###

# D - Dice in Line

n,k=map(int, input().split())
p=list(map(int, input().split()))
q=[0]*n

for i in range(n):
    q[i]=(p[i]+1)/2

max=0
for i in range(n-k+1):
    sum=0
    for j in range(i, i+k):
        sum+=q[j]
    if sum > max:
        max=sum
print(max)


### FIXED CODE ###

# D - Dice in Line

n,k=map(int, input().split())
p=list(map(int, input().split()))
q=[0]*n

for i in range(n):
    q[i]=(p[i]+1)/2

max=0
for i in range(k):
    max+=q[i]

sum=max
for i in range(1, n-k+1):
    sum=sum-q[i-1]+q[i+k-1]
    if sum > max:
        max=sum
print(max)
### BUGGY CODE ###

n,m,q=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    S[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n):
        S[i][j+1]+=S[i][j]

for i in range(q):
    a,b=map(int,input().split())
    ans=0
    for y in range(a,b+1):
        ans+=S[y][b]-S[y][a-1]
    print(ans)


### FIXED CODE ###

n,m,q=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    S[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n):
        S[i][j+1]+=S[i][j]

for i in range(q):
    a,b=map(int,input().split())
    ans=0
    for y in range(a,b+1):
        ans+=S[y][b]-S[y][a-1]
    print(ans)
### BUGGY CODE ###

from collections import deque
 
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
# BFSでは、同じステップ数のノードを先に全探索するので、訪問済みフラグはグローバル共有しても大丈夫
 
max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            if step > largest_step:
                largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                    continue
                if maze[next_y][next_x] == "#":
                    continue
                # 訪問済みでないかチェック
                if visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        if largest_step > max_step:
            max_step = largest_step
 
print(max_step)

### FIXED CODE ###

import sys
import numpy as np
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)
### BUGGY CODE ###

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

cards = []
for i in range(M):
    Li, Ri = s_input()
    L.append(Li)
    R.append(Ri)
    cards.append(list(range(Li, Ri+1)))

cards = set(sum(cards, []))

ng_cards = set()
for card in cards:
    for i in range(M):
        if card < L[i] or card > R[i]:
            ng_cards.add(card)
            break

print(len(list(cards - ng_cards)))




### FIXED CODE ###

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])

L_max = max(L)
R_min = min(R)

num = R_min - L_max

if num >= 0:
    print(num + 1)
else:
    print(0)
### BUGGY CODE ###


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

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"

while endnum < N:

    while True:

        if end[endp] == 0:
            Q.append(endp)
            break

        endp += 1

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break
        endnum += 1
        end[q] = 1

    if ans == "No":
        break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for j in range(n):
        if i - a[j] >= 0 and dp[i-a[j]] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")

### FIXED CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))
	print(len(l), len([x for x in l if x % 2 == 0]), len([x for x in l if x % 2 == 1]))
	if max(l) >= 30001:
		print("max >= 30001")
		return False

	if len(set(l)) != len(l):
		print("not unique")
		return False

	tmp = l[0]


	for i in range(len(l) - 1):
		tmp = fractions.gcd(tmp, l[i+1])
	if tmp != 1:
		print("gcd is 1")
		return False 

	for i in range(len(l)):
		if fractions.gcd(l[i], sum(l) - l[i]) == 1:
			print("not special")
			return False

	return True


def main(n):
	if n == 3:
		return "2 5 63"

	sub1 = [str(i * 3) for i in range(1, 10001) if i % 2 == 1]
	sub2 = [str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0]
	sub3 = [str(i) for i in range(1, 30001) if i % 6 == 0]
	if n <= 5003:
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub[0:(n-3)]])
			return(s)
	elif n <= 15000:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = " ".join(sub2[0:(n-5000)]) + " " +  " ".join(sub1)
			return(s)
		else:
			s = " ".join(sub2[0:(n-5001)]) + " 6 " +  " ".join(sub1)
			return(s)
	else:
		s = " ".join(sub2) + " " +  " ".join(sub1) + " " + " ".join(sub3[0:(n-15000)]) 
		return(s)

if __name__ == '__main__':
	n = int(input())
	#print(check(main(n)))
	#print(main(20000))
	print(check(main(20000)))
	#print(check("2 4 3 20001"))
	#for i in range(5001, 5006):
	#	ans = main(i)
	#	print(i, check(ans))
	

### FIXED CODE ###

# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))
	print(len(l), len([x for x in l if x % 2 == 0]), len([x for x in l if x % 2 == 1]))
	if max(l) >= 30001:
		print("max >= 30001")
		return False

	if len(set(l)) != len(l):
		print("not unique")
		return False

	tmp = l[0]


	for i in range(len(l) - 1):
		tmp = fractions.gcd(tmp, l[i+1])
	if tmp != 1:
		print("gcd is 1")
		return False 

	for i in range(len(l)):
		if fractions.gcd(l[i], sum(l) - l[i]) == 1:
			print("not special")
			return False

	return True


def main(n):
	if n == 3:
		return "2 5 63"

	sub1 = [str(i * 3) for i in range(1, 10001) if i % 2 == 1]
	sub2 = [str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0]
	sub3 = [str(i) for i in range(1, 30001) if i % 6 == 0]
	if n <= 5003:
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub1[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub1[0:(n-3)]])
			return(s)
	elif n <= 15000:
		if n % 2 == 0:
			s = " ".join(sub2[0:(n-5000)]) + " " +  " ".join(sub1)
			return(s)
		else:
			s = " ".join(sub2[0:(n-5001)]) + " 6 " +  " ".join(sub1)
			return(s)
	else:
		s = " ".join(sub2) + " " +  " ".join(sub1) + " " + " ".join(sub3[0:(n-15000)]) 
		return(s)

if __name__ == '__main__':
	n = int(input())
	#print(check(main(n)))
	#print(check(main(15)))
	#print(check(main(17)))
	#print(check(main(5002)))
	#print(check(main(5003)))
	#print(check(main(15002)))
	#print(check(main(15003)))
	print(main(n))
	#print(check("2 4 3 20001"))
	#for i in range(5001, 5006):
	#	ans = main(i)
	#	print(i, check(ans))
### BUGGY CODE ###

import sys

s=[]
ans=[]
 
def dfs(a,b,c,i,root):
    if i==n:
        global ans
        ans=root.copy()
        return True
    l=False
    r=False
    if s[i]=='AB':
        if a>0:
            root.append('B')
            l=dfs(a-1,b+1,c,i+1,root)
            root.pop()
        if b>0:
            root.append('A')
            r=dfs(a+1,b-1,c,i+1,root)
            root.pop()
    elif s[i]=='AC':
        if a>0:
            root.append('C')
            l=dfs(a-1,b,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('A')
            r=dfs(a+1,b,c-1,i+1,root)
            root.pop()
    else:
        if b>0:
            root.append('C')
            l=dfs(a,b-1,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('B')
            r=dfs(a,b+1,c-1,i+1,root)
            root.pop()
    return l or r
 
sys.setrecursionlimit(10**6)
n,a,b,c=map(int,input().split())
s=['']*n
for i in range(n):
    s[i]=input()
flag=dfs(a,b,c,0,[])
 
if flag:
    print("Yes")
    for t in ans:
        print(t)
else:
    print("No")

### FIXED CODE ###

n,a,b,c=map(int,input().split())
s=[]
for i in range(n):
    s.append(input())
s.append('EOF')

ans=[]
 
flag=True
 
for i in range(n):
    if s[i]=='AB':
        if a==0 and b==0:
            flag=False
            break
        if a==0 or (b!=0 and a==1 and s[i+1]=='AC'):
            ans.append('A')
            a+=1
            b-=1
        else:
            ans.append('B')
            a-=1
            b+=1
    elif s[i]=='AC':
        if a==0 and c==0:
            flag=False
            break
        if a==0 or (c!=0 and a==1 and s[i+1]=='AB'):
            ans.append('A')
            a+=1
            c-=1
        else:
            ans.append('C')
            a-=1
            c+=1
    else:
        if c==0 and b==0:
            flag=False
            break
        if c==0 or (b!=0 and c==1 and s[i+1]=='AC'):
            ans.append('C')
            c+=1
            b-=1
        else:
            ans.append('B')
            c-=1
            b+=1

if flag:
    print("Yes")
    for i in ans:
        print(i)
else:
    print("No")
### BUGGY CODE ###

# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0

for i in range(1,max(p)+1):
	arc=[z for z in p if z>=i]
	abc=[z for z in p if z<i]
	if len(arc)==len(abc):cnt+=1
	if len(arc)<len(abc):break

print (cnt)



### FIXED CODE ###

# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0

p=sorted(p)

if p[n//2]!=p[(n//2)-1]:
	cnt=p[n//2]-p[(n//2)-1]



print (cnt)
### BUGGY CODE ###

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


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0
for i in range(N):
    for j in range(i+1,N):
        a = L[i]
        b = L[j]
        ans += bisect_left(L[j+1:], a+b)
print(ans)
### BUGGY CODE ###

s = input()[::-1] # 右からn桁の数についてループを回していきたいので、文字列を反転させる

sum_of_digits = 0 # 余りの値
cnts = [0] * 2019 # 余りの値ごとに余りが同じ値の数を格納する変数。2019で割る場合、余りは0~2018までの2019通りあるので、リストの長さは2019
cnts[0] = 1 # for文はn回しか回らないが、余りを計算したい桁数は0~n桁のn+1個ある。そこで0桁の余はfor文の前に計算しておく。0桁の値を2019で割った余りは0なので、cnts[0]に1を代入しておく
d = 1 # sum_of_digitsの計算に使う10の累乗値

# まず余りの値ごとに余りが同じ値の数を数える
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
#    d %= 2019 # オーバーフローを避けるために2019の剰余を取る。後述
    cnts[sum_of_digits] += 1

# 次に余りの値ごとにその組み合わせを計算し、足し合わせる
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

print(ans)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

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

answer_list = []

for i in range(N):
    answer = 0
    for j in range(N):
        # print(i, j, i-1-j, A[i-1-j])
        if j % 2 == 0:
            answer += A[i-1-j]
        else:
            answer -= A[i-1-j]

    answer_list.append(answer)
print(" ".join(map(str, answer_list)))

### FIXED CODE ###

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

answer_list = []

for i in range(N):
    answer = 0
    if i == 0:
        for j in range(N):
            # print(i, j, i-1-j, A[i-1-j])
            if j % 2 == 0:
                answer += A[i-1-j]
            else:
                answer -= A[i-1-j]
    else:
        answer = 2*A[i-1] - answer_list[i-1]

    answer_list.append(answer)
print(" ".join(map(str, answer_list)))
### BUGGY CODE ###

from collections import deque

h, w = list(map(int, raw_input().split()))
grid = [raw_input() for _ in range(h)]

ans = 0

for startx in range(w):
    for starty in range(h):
        for endx in range(w):
            for endy in range(h):
                if grid[starty][startx] == "#" or grid[endy][endx] == "#":
                    continue

                dist = [[10000]*w for _ in range(h)]
                dist[starty][startx] = 0

                q = deque([(startx, starty)])

                while q:
                    curx, cury = q.popleft()
                    if (curx, cury) == (endx, endy):
                        break

                    adj = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                    for xo, yo in adj:
                        x, y = curx + xo, cury + yo

                        if x < 0 or x >= w or y < 0 or y >= h:
                            continue
                        if grid[y][x] == "#":
                            continue

                        newDist = dist[cury][curx] + 1
                        if newDist < dist[y][x]:
                            dist[y][x] = newDist
                            q.append((x, y))

                ans = max(ans, dist[endy][endx])

print(ans)

### FIXED CODE ###

from collections import deque

h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]

ans = 0

for startx in range(w):
    for starty in range(h):
        if grid[starty][startx] == "#":
            continue

        dist = [[10000]*w for _ in range(h)]
        dist[starty][startx] = 0
        maxDist = 0

        q = deque([(startx, starty)])

        while q:
            curx, cury = q.popleft()

            adj = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for xo, yo in adj:
                x, y = curx + xo, cury + yo

                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if grid[y][x] == "#":
                    continue

                newDist = dist[cury][curx] + 1
                if newDist < dist[y][x]:
                    dist[y][x] = newDist
                    q.append((x, y))

                    maxDist = max(maxDist, newDist)

        ans = max(ans, maxDist)

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

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos,Zero,Neg=[],[],[]

for i in L:
    if i>0:
        Pos.append(i)
    elif i==0:
        Zero.append(i)
    else:
        Neg.append(i)

P=int(len(Pos)*(len(Pos)-1)/2+len(Neg)*(len(Neg)-1)/2)
Z=int(len(Zero)*(len(Zero)-1)/2+len(Zero)*(len(Pos)+len(Neg)))
Ne=int(len(Pos)*len(Neg))
A=int(N*(N-1)/2)

if K<=Ne:
    NeL=[Pos[i]*Neg[j] for i in range(len(Pos)) for j in range (len(Neg))]
    print(sorted(NeL)[K-1])

elif Ne<K<=Ne+Z:
    print(0)

else:
    if len(Pos)==1:
        PoL = [Neg[i] * Neg[i + j] for i in range(0, len(Neg) - 1) for j in range(1, len(Neg)-i)]
    elif len(Neg)==1:
        PoL = [Pos[i] * Pos[i + j] for i in range(0, len(Pos) - 1) for j in range(1, len(Pos)-i)]
    else:
        PoL=[Pos[i]*Pos[i+j] for i in range(0,len(Pos)-1) for j in range(1,len(Pos)-i)]
        PoL+=[Neg[i]*Neg[i+j] for i in range(0,len(Neg)-1) for j in range(1,len(Neg)-i)]
    print(sorted(PoL,reverse=True)[A-K])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)