Harryxun/stf_run huggingface dataset:
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [] # parent

def init():
    for i in range(N):
        par.append(i)

def root(x):
    if par[x] != x:
        par[x] = root(par[x])
    return par[x]

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

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[x] = y


init()

block_num = [0]*N
friend_num = [0]*N
cls_cnt = {} # cluster count

for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    unite(a,b)


for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    if same(a,b):
        friend_num[a] += 1
        friend_num[b] += 1


for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    if same(c,d):
        block_num[c] += 1
        block_num[d] += 1


cls_cnt = {} # cluster count
for i in range(N):
    r = root(i)
    if r in cls_cnt:
        cls_cnt[r] += 1
    else:
        cls_cnt[r] = 1


for i in range(N):
    r = root(i)
    ans = cls_cnt[r] - 1 - friend_num[i] - block_num[i]
    print(ans , end=' ')



### FIXED CODE ###

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

# -- Union Find
par = [i for i in range(N)]
rank = [0]*N

def root(x):
    if par[x] != x:
        par[x] = root(par[x])
    return par[x]

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

def unite(x, y):
    x, y = root(x), root(y)
    if x == y: return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

# -- Union Find


block_num = [0]*N
friend_num = [0]*N
cls_cnt = {} # cluster count

for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    unite(a,b)


for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    if same(a,b):
        friend_num[a] += 1
        friend_num[b] += 1


for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    if same(c,d):
        block_num[c] += 1
        block_num[d] += 1


cls_cnt = {} # cluster count
for i in range(N):
    r = root(i)
    if r in cls_cnt:
        cls_cnt[r] += 1
    else:
        cls_cnt[r] = 1


for i in range(N):
    r = root(i)
    ans = cls_cnt[r] - 1 - friend_num[i] - block_num[i]
    print(ans , end=' ')
import sys

print(int(sys.argv[1]) ** 3)

### FIXED CODE ###

print(int(input())**3)
N = int(input())
V_list = np.array(list(map(int, input().split())))
C_list = np.array(list(map(int, input().split())))

diff = V_list - C_list

print(diff[diff > 0].sum())

### FIXED CODE ###

import numpy as np
N = int(input())
V_list = np.array(list(map(int, input().split())))
C_list = np.array(list(map(int, input().split())))

diff = V_list - C_list

print(diff[diff > 0].sum())
N = int(input())
h = list(map(int,input().split()))

lmin = [] #極小値のリスト
lmax = [] #極大値のリスト

for i in range(1,N-1):
    if (h[i] >= h[i-1]) and (h[i] > h[i+1]):
        lmax.append(h[i])
    
for k in range(1,N-1):
    if (h[k] <= h[k-1]) and (h[k] < h[k+1]):
        lmin.append(h[k])

if h[0] > h[1]:
    lmax.append(h[0])
if h[N-1] > h[N-2]:
    lmax.append(h[N-1])

ans = sum(lmax) - sum(lmin)

print(ans)


### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
if max(h) == min(h):
    ans = h[0]

else:
    same = []
    for i in range(N-1):
        if h[i] == h[i+1]:
            same.append(i)
    
    if len(same) >= 1:
        for k in range (len(same))[::-1]:
            del h[same[k]]
    
    N = len(h)

    lmin = [] #極小値のリスト
    lmax = [] #極大値のリスト

    if N >=3:
        for i in range(1,N-1):
            if (h[i] > h[i-1]) and (h[i] > h[i+1]):
                lmax.append(h[i])
        
        for k in range(1,N-1):
            if (h[k] < h[k-1]) and (h[k] < h[k+1]):
                lmin.append(h[k])

        if h[0] > h[1]:
            lmax.append(h[0])
            
        if h[N-1] > h[N -2]:
            lmax.append(h[N-1])
                
        if (len(lmax) == 1) :
            ans = max(h)

        else:
            ans = sum(lmax) - sum(lmin)
    
    if N == 2:
        ans = max(h)

    if N == 1:
        ans = h[0]

#print(lmax)
#print(lmin)
print(ans)
abck = input().split(" ")
a = abck[0]
b = abck[1]
c = abck[2]
k = abck[3]

if k < a:
	print(a)
elif k < a + b:
	print(a)
else:
	print(a - (k - (a + b)))

 

### FIXED CODE ###

abck = input().split(" ")
a = int(abck[0])
b = int(abck[1])
k = int(abck[3])

if k < a:
	print(k)
elif k <= a + b:
	print(a)
else:
	c = k - (a + b)
	print(a - c)
length = raw_input()
count = length
answer = raw_input()


def compare(current, previous, i):
  if current[0] < previous[0]:
    answer = current
  elif current[0] == previous[0]:
    compare(current, previous, i+1)

while count > 0:
  if count == length:
    current_word = answer
  if count < length:
    previous_word = current_word
    current_word = raw_input()
    min_length = min([len(current_word), len(previous_word)])
    compare(current_word, previous_word, 0)
  count -= 1

print answer
  

### FIXED CODE ###

s = []
n = input()
 
for i in range(n):
    x = raw_input()
    s.append(x)
 
s.sort()
 
print s[0]
s = input()
 
count = 0
 
for i in s:
  if s[i] == '1':
    count++
  
print(count)

### FIXED CODE ###

s = input()
 
count = 0
 
for i in s:
  if i == '1':
    count = count + 1
  
print(count)
def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()
max_scores = [-10**12] * (N+10)
for init_i in range(1, N+1):
    i = init_i
    scores = [-10**9] * (K+10000)
    scores[0] = 0
    for l in range(1, K+1):
        i = P[i]
        scores[l] = scores[l-1] + C[i]
    scores[0] = -10**9
    max_scores[i] = max(scores)
print(max(max_scores))

### FIXED CODE ###

def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

def get_cycle_scores(cycle):
    score = 0
    scores = [score]
    for i in cycle:
        score += C[i]
        scores.append(score)
    return scores

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    scores = get_cycle_scores(cycle)
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    # 1cycle以下の場合は全て調べればよし
    if K <= len(cycle):
        max_score = max(scores[move] for move in range(1, K+1))
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがマイナスならサイクルを回らないのがハイスコア
    if score_per_cycle <= 0:
        max_score = max(scores[move] for move in range(1, cycle_len+1))
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがプラスなら限界までサイクルを回るのがハイスコア
    # ラスト1cycleのスコアを調べる
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        # 何周したか
        loop_cnt = move // cycle_len
        # あまり
        rest_move = move % cycle_len
        # スコア = 1周ごとのスコア * 何周したか + あまり
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))
N = int(input())
lower = []
upper = []
for i in range(N):
    a, b = map(int, input().split())
    lower.append(a)
    upper.append(b)
lower.sort()
upper.sort()
if N % 2 == 1:
    print(upper[(N+1)//2]-lower[(N+1)//2]+1)
else:
    print(upper[N//2 + 1]+upper[N//2]-lower[N//2 + 1]-lower[N//2]+1)

### FIXED CODE ###

N = int(input())
lower = []
upper = []
for i in range(N):
    a, b = map(int, input().split())
    lower.append(a)
    upper.append(b)
lower.sort()
upper.sort()
if N % 2 == 1:
    print(upper[(N-1)//2]-lower[(N-1)//2]+1)
else:
    print(upper[N//2]+upper[N//2 - 1]-lower[N//2]-lower[N//2 - 1]+1)
import numpy as np
MOD = 998244353
n, m = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in [0]*n])
#a[:, [0, 1]] = a[:, [1, 0]]
#print(a)
r = 0
for i in range(n):
	if a[i][i] != 1:
		for j in range(i+1, m):
			if a[i][j] == 1:
				a[:, [i, j]] = a[:, [j, i]]
				break
		else:
			for j in range(i+1, n):
				if a[j][i] == 1:
					a[[i, j]] = a[[j, i]]
				break
			else:
				break
	if a[i][i] == 0:
		continue

	r += 1
	for j in range(i+1, m):
		a[:, [j]] += a[i][j] * a[:, [i]]
		a[:, [j]] %= 2
	for j in range(i+1, n):
		a[[j]] += a[j][i] * a[[i]]
		a[[j]] %= 2
#print(r)
print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)

### FIXED CODE ###

import numpy as np
MOD = 998244353
n, m = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in [0]*n])
if n > m:
	a = a.T
	n, m = m, n
#a[:, [0, 1]] = a[:, [1, 0]]
#print(a)
r = 0
for i in range(n):
	if a[i][i] != 1:
		for j in range(i+1, m):
			if a[i][j] == 1:
				a[:, [i, j]] = a[:, [j, i]]
				break
		else:
			for j in range(i+1, n):
				if a[j][i] == 1:
					a[[i, j]] = a[[j, i]]
				break
			else:
				break
	if a[i][i] == 0:
		continue

	r += 1
	for j in range(i+1, m):
		a[:, j] += a[i][j] * a[:, i]
		a[:, j] %= 2
	for j in range(i+1, n):
		a[j] += a[j][i] * a[i]
		a[j] %= 2
#print(r)
print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)
def move(s, k):
    if len(s) == 1:
        return chr(97+(ord(s) + k - 97)%26)
    if s[0] == 'a' or 123-ord(s[0]) > k:
        return s[0] + move(s[1:], k)
    else:
        return 'a' + move(s[1:], k-(123-ord(s[0])))






s = input()
K = int(input())
print(move(s,K))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Sep 24 21:28:20 2016

@author: dotha
"""

#aまでいけそうなら動かす。駄目そうならその項は終わり

def move(s, k):
    if len(s) == 1:
        return chr(97+(ord(s) + k - 97)%26)
    if s[0] == 'a' or 123-ord(s[0]) > k:
        return s[0] + move(s[1:], k)
    else:
        return 'a' + move(s[1:], k-(123-ord(s[0])))

def move_(l,k):
    if l =='a' or 123-ord(l) > k:
        return (l,k)
    else:
        return ('a', k-(123-ord(l)))

s = input()
K = int(input())
answer=[]
#print(move(s,K))

for l in s:
    (x,K) = move_(l,K)
    answer.append(x)

answer[-1] = chr(97++(ord(answer[-1]) + K - 97)%26)
    
print(''.join(answer))
import math
a, b , n = map(int, input().split())

max = -1

if n < b:
    x = n
elif b < n:
    x = b-1

new = math.floor(a*x/b) - a * math.floor(x/b)

print(new)


### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = n

if b <= n:
    x = b-1

new = math.floor(a*x/b) - a * math.floor(x/b)
print(new)
#include <stdio.h>

int main() {
  int X;
  scanf("%d", &X);
  
  if (X == 3) {
    printf("YES");
  } else if (X == 5) {
    printf("YES");
  } else if (X == 7) {
    printf("YES");
  } else {
    printf("NO");
  }
  
  return 0;
  
}


### FIXED CODE ###

if int(input()) in [3, 5, 7]:
  print('YES')
else:
  print('NO')
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

from scipy import special

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

root = {1}
ans = K
while True:
    a = K - 2
    if 1 in root:
        a = K - 1
    children = set()
    for i in root:
        for j in d[i]:
            d[j].remove(i)
        b = len(d[i])
        if a < b:
            print(0)
            break
        ans *= special.perm(a, b, exact=True)
        children |= d[i]
    else:
        if len(children) == 0:
            print(ans % mod)
            break
        root = children
        continue
    break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
N = int(input())
X = input()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

a = X.count("1")
ap, am = a+1, a-1

Ap = []
Am = []
temp = 1

for i in range(N):
  if i == 0:
    Ap.append(temp%ap)
    Am.append(temp%am)
  else:
    temp *= 2
    Ap.append(temp%ap)
    Am.append(temp%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am

for i in range(N):
  cnt = 1
  if X[i] == "1":
    p = Ams - Am[-1-i]
    p %= am
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)

### FIXED CODE ###

N = int(input())
X = input()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)
a = int(input())
if (a >= 30):  
    print("Yes")
else
	print("No")

### FIXED CODE ###

a = int(input())
if a>=30:
    print("Yes")
else:
    print("No")
def cns(ls,m,sm):
    global n, s
    count = 0
    if m == n:
        if sm == s: return 1
        else      : return 0
    elif s-mx(n-m)-1 <= sm <= s:
        for i in range(9-m+1):
            rls = ls[:]
            k = rls.pop(i)
            count += cns(rls,m+1,sm+(m+1)*k)
        return count
    else: return 0

def mx(i):
    if i == 0: return 0
    else     : return (i+1)*i + mx(i-1)

ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    if s > mx(n): print 0
    else        : print cns(ls,0,0)

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
n,k = map(int, input().split())
s = str(input())
if s[k-1]=="A":
    s[k-1]="a"
elif s[k-1]=="B":
    s[k-1]="b"
else:
    s[k-1]="c"
print(s)

### FIXED CODE ###

n,k = map(int, input().split())
s = list(input())
if s[k-1]=="A":
    s[k-1]="a"
elif s[k-1]=="B":
    s[k-1]="b"
else:
    s[k-1]="c"
print("".join(s))
nums = [int(x) for x in input().split()]
N = nums[0]
K = nums[1]
arr = []
for i in range(N):
	nums = [int(x) for x in input().split()]
	arr.append(tuple(nums))

arr = sorted(arr, key=lambda x: x[0])

vol = 0
for i in range(len(arr)):
	vol = vol + arr[i][1]
	if vol >= K:
		print(arr[i][0])
		break


### FIXED CODE ###

nums = [int(x) for x in input().split()]

if nums[0] <= nums[2] <= nums[1]:
	print('Yes')
else:
	print('No')
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
def dfs(a, b, k):
	global ans

	if a == N and b ==M:
		return True

	if k <= 0:
		return False

	if a < N and k >= A[a] and dfs(a + 1, b, k - A[a]):
		ans += 1
		return True

	if b < M and k >= B[b] and dfs(a, b + 1, k - B[b]):
		ans += 1
		return True

	return True

dfs(0, 0, K)
print(ans)

### FIXED CODE ###

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

a = [0]
for i in range(N):
    a.append(a[i] +  A[i])
b = [0]
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
r = float_input()
  
l = 2*math.pi*r
s = r*r*math.pi
  
print "%.8f %.8f" %(s, l)

### FIXED CODE ###

import math
 
r = float(input())
    
l = 2*math.pi*r
s = r*r*math.pi
    
print "%.8f %.8f" %(s, l)
N=int(input())
S=[input() for i in range(N)]
print(len(set(S)))

### FIXED CODE ###

S,W=input().split()

if int(W)>=int(S):
    print("unsafe")
else:
    print("safe")
s = [input().split()]
print("Yes" if len(set(s)) == 2 else "No")

### FIXED CODE ###

s = list(input().split())
print("Yes" if len(set(s)) == 2 else "No")
S=input()
N=len(S)
X=(int(N)-1)/2
Y=(int(N)+3)/2
T=S(range(1,X))
U=S(range(Y,N))
if str(S)==str(S)[::-1] and str(T)==str(T)[::-1] and str(U)==str(U)[::-1]:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

S=str(input())
def f(x):
  return x==x[::-1]
N=len(S)
S1=S[:(N-1)//2]
S2=S[(N+1)//2:]
if f(S) and f(S1) and f(S2):
  print('Yes')
else:
  print('No')
import sys
#t=1

for i in range(len(s)):
	if p[0] == s[i]:
		for j in range(len(p)-1):
			if p[j+1] == s[(i+j+1)%len(s)]:
				t += 1
				#print(t,j,i+j)
			else:
				t = 0
			if t == len(p):
				#print('Yes')
				sys.exit()

if t < len(p):
	print('No')

### FIXED CODE ###

s = list(input())
p = list(input())
#print(len(p))
import sys

for i in range(len(s)):
	t=0
	for j in range(len(p)):
		if p[j] == s[(i+j)%len(s)]:
			t = t+1
			#print(p[j], s[(i+j)%len(s)])
		else:
			t = 0
		if t == len(p):
			print('Yes')
			sys.exit()

if t < len(p):
	print('No')
nk = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = [0] * (nk[0] + nk[1])
 
zeros = [0] * nk[1]
 
seq4search = zeros + p
 
for i in range(nk[1] + 1, nk[0] + nk[1]):
    seq4search[i] = (seq4search[i] + 1) / 2
    ans[i] = ans[i-1] + seq4search[i] - seq4search[i - k] 
 
print(max(ans))

### FIXED CODE ###

nk = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = [0] * (nk[0] + nk[1])
 
zeros = [0] * nk[1]
 
seq4search = zeros + p
 
for i in range(nk[1], nk[0] + nk[1]):
    seq4search[i] = (seq4search[i] + 1) / 2
    ans[i] = ans[i-1] + seq4search[i] - seq4search[i - nk[1]] 
 
print(max(ans))
if X>= 30:
    print('yes')
else:
    print('no')


### FIXED CODE ###

X = int(input())
if X>= 30:
    print('Yes')
else:
    print('No')
#import bisect
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
#A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                    cnt+=d
                    continue
                q,r=divmod(target,a)
                if a < 0:
                    #il = bisect.bisect_left(A,  q+(r>0))
                    #il = bisect.bisect_left(A,  target / a)
                    il = np.searchsorted(A,q+(r>0),side='left')
                    #ilからiまで、ただしilがiを超えたら0
                    d = max(i - il, 0)
                else:
                    #ir = bisect.bisect_right(A, q)
                    #ir = bisect.bisect_right(A, target / a)
                    ir = np.searchsorted(A,q,side='right')
                    #0からirまで、ただしirがiを超えたらi
                    d = min(ir, i)
                #print(target,a,d)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))


### FIXED CODE ###

import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))
n = int(input())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
sayTable.append(sayArray)

def count(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if say != 2:
			continue
		if say != honest[x]:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		if not checkHonest(sayTable[i]):
			return False
	return True









def search(sayTable, honest, i):
	if i >= n;
		if checkHonestAll(sayTable, honest):
return count(honest)
else:
	return 0

count = 0
h = honest[i]
if (h == 0 or h == 2) and checkHonest(sayTable, honest):
copyHonest = honest[:]
copyHonest[i] = 2
c = search(sayTable, copyHonest, i + 1)
if count < c:
	count = c

honest[i] = 1
c = search(sayTable, honest, i+1)
	if count < c:
		count = c
return count

print(search(sayTable, [0] * n, 0));



### FIXED CODE ###

n = int(input())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def countHonest(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if honest[x] == 0:
				continue
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		sayArray = sayTable[i]
		for x, y in sayArray:
			if y != honest[x]:
				return False
	return True

def setHonest(sayArray, honest):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n:
		if checkHonestAll(sayTable, honest):
			return countHonest(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	sayArray = sayTable[i]
	if (h == 0 or h == 2) and checkHonest(sayArray, honest):
		copyHonest = honest[:]
		setHonest(sayArray, copyHonest)
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i+1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
	if count < c:
		count = c
	return count

print(search(sayTable, [0] * n, 0))
N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)

ans = 0

for i in range(n-2):
  j = i + 1
  k = n - 1
  if l[i] < l[j] + l[k]:
    ans += k - j
    j += 1
  else:
    k -= 1
print(ans)

### FIXED CODE ###

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
 
ans = 0
 
for i in range(N-2):
  j = i + 1
  k = N - 1
  while j < k:
    if l[i] < l[j] + l[k]:
      ans += k - j
      j += 1
    else:
      k -= 1
print(ans)