Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

s=deque(list(input()))
for i in range(int(input())):
  dir=input().split()
  if int(dir[0])==1:s.reverse()
  else:
    if int(dir[1])==1:s.appendleft(dir[2])
    else:s.append(dir[2])
s=list(s)
print(*s,sep='')

Fixed submission:
from collections import deque

s=deque(list(input()))
flag=0
for i in range(int(input())):
  dir=input().split()
  if int(dir[0])==1:flag+=1
  else:
    if int(dir[1])==1:
      if flag%2==0:s.appendleft(dir[2])
      else:s.append(dir[2])
    else:
      if flag%2==0:s.append(dir[2])
      else:s.appendleft(dir[2])
s=list(s)
if flag%2==1:s.reverse()
print(*s,sep='')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
k=list(input())

kk=0
for i in range(1000):
  if i<10:
    p=['0','0',str(i)]
  elif i<100:
    p=['0',str(i)[0],str(i)[1]]
  else:
    p=list(str(i))
    
    
  flag=False
  for x in range(n-2):
    if flag==True:break
    if k[x]!=p[0]:continue
    else:
      for y in range(x+1,n-1):
        if flag==True:break
        if k[y]!=p[1]:continue
        else:
          for z in range(y+1,n):
            if k[z]!=p[2]:continue
            else:
              flag=True
              break
  
  if flag==True:
    #print(i)
    kk+=1
  else:pass
print(kk)

Fixed submission:
n=int(input())
k=list(input())

kk=0
for i in range(1000):
  if i<10:
    p=['0','0',str(i)]
  elif i<100:
    p=['0',str(i)[0],str(i)[1]]
  else:
    p=list(str(i))
    
  flag=0
  for w in k:
    if w==p[flag]:
      flag+=1
    if flag==3:
      break
  
  if flag==3:
    #print(i)
    kk+=1
  else:pass

print(kk)
Buggy python submission (verdict: Runtime Error):
s=list(input())
n=len(s)
ans=[]
for i in range(n-1):
  for j in range(i+1,n+1):
    part=set(s[i:j])
    flag=True
    for p in part:
      if p not in list('ATGC'):
        flag=False
        break
    if flag==True:
      ans.append(len(part))
print(max(ans))

Fixed submission:
s=list(input())
n=len(s)
ans=[]
if n==1:
  if s.pop() in list('ATCG'):
    print(1)
    exit()

for i in range(n-1):
  for j in range(i+1,n+1):
    part=set(s[i:j])
    flag=True
    for p in part:
      if p not in list('ATGC'):
        flag=False
        break
    if flag==True:
      ans.append(len(s[i:j]))
#print(ans)
if ans:
  print(max(ans))
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
st=input()
ssum=[0,0]
for i in range(1,n):
    if st[i-1]=="A" and st[i]=='C':
        ssum.append(ssum[-1]+1)
    else:
        ssum.append(ssum[-1])

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

Fixed submission:
n,q=map(int,input().split())
st=input()
ssum=[0,0]
for i in range(1,n):
    if st[i-1]=="A" and st[i]=='C':
        ssum.append(ssum[-1]+1)
    else:
        ssum.append(ssum[-1])
#print(len(ssum))
for i in range(q):
    a,b=map(int,input().split())
    print(ssum[b]-ssum[a])
Buggy python submission (verdict: Runtime Error):
n=int(input())
if n<105:
  print(0)
else:
  c=0
  for i in range(105,n+1,2):
    p=0
    for j in range(1,i//2+1,2):
      if i%j==0:
        p+=1
    if p==7:
      c+=1
print(c)
    

Fixed submission:
n=int(input())
if n<105:
  print(0)
  exit()
else:
  c=0
  for i in range(105,n+1,2):
    p=0
    for j in range(1,i//2+1,2):
      if i%j==0:
        p+=1
    if p==7:
      c+=1
print(c)
Buggy python submission (verdict: Runtime Error):
n=int(input())
alis=list(map(int,input().split()))
xlis=set()
for i in alis:
    xlis.add(i-1)
    xlis.add(i+1)
    xlis.add(i)
#print(xlis)
counter=[0 for _ in range(len(xlis))]
t=-1
for x in xlis:
    t+=1
    for i in range(n):
        if x-1<=alis[i] and alis[i]<=x+1:
            counter[t]+=1
print(max(counter))

Fixed submission:
x,t=map(int,input().split())
print(max(0,x-t))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
alis=list(map(int,input().split()))
xlis=set()
for i in alis:
    xlis.add(i-1)
    xlis.add(i+1)
    xlis.add(i)
#print(xlis)
counter=[0 for _ in range(len(xlis))]
t=-1
for x in xlis:
    t+=1
    for i in range(n):
        if x-1<=alis[i] and alis[i]<=x+1:
            counter[t]+=1
print(max(counter))

Fixed submission:
n=int(input())
alis=list(map(int,input().split()))
xlis=dict()
for i in set(alis):
    xlis[i-1]=0
    xlis[i+1]=0
    xlis[i]=0
for i in alis:
    xlis[i-1]+=1
    xlis[i+1]+=1
    xlis[i]+=1
print(max(xlis.values()))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
alis=list(map(int,input().split()))
xlis=set()
for i in alis:
    xlis.add(i-1)
    xlis.add(i+1)
    xlis.add(i)
#print(xlis)
counter=[0 for _ in range(len(xlis))]
t=-1
for x in xlis:
    t+=1
    for i in range(n):
        if x-1<=alis[i] and alis[i]<=x+1:
            counter[t]+=1
print(max(counter))

Fixed submission:
n=int(input())
alis=list(map(int,input().split()))
xlis=dict()
for i in set(alis):
    xlis[i-1]=0
    xlis[i+1]=0
    xlis[i]=0
for i in alis:
    xlis[i-1]+=1
    xlis[i+1]+=1
    xlis[i]+=1
print(max(xlis.values()))

Buggy python submission (verdict: Runtime Error):
n=int(input())
alis=list(map(int,input().split()))
xlis=set(alis)
for al in alis:
    alis.add(al-1)
    alis.add(al+1)
counter=[0 for _ in range(n)]
for x in xlis:
    for i in range(n):
        if x-1<=alis[i]<=x+1:
            counter[i]+=1
print(max(counter))

Fixed submission:
n=int(input())
alis=list(map(int,input().split()))
xlis=dict()
for i in set(alis):
    xlis[i-1]=0
    xlis[i+1]=0
    xlis[i]=0
for i in alis:
    xlis[i-1]+=1
    xlis[i+1]+=1
    xlis[i]+=1
print(max(xlis.values()))
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 7)

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

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

CNT = [0] * (10 ** 6)

ans = 0
for i in range(N):
    a = A[i]
    p = i - a

    if p > 0:
        ans += CNT[p]

    CNT[i + a] += 1

print(ans)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

CNT = [0] * (10 ** 7)

ans = 0
for i in range(N):
    a = A[i]
    p = i - a

    if 0 <= p <= (10 ** 7):
        ans += CNT[p]

    if 0 <= i + a <= (10 ** 7):
        CNT[i + a] += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    while c <= N:
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B

print(ans)


Fixed submission:
import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    cnt = 1
    while c <= N:
        cnt += 1
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B
        if B < cnt:
            break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    while c <= N:
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B

print(ans)


Fixed submission:
import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    cnt = 1
    while c <= N:
        cnt += 1
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B
        if B < cnt:
            break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

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

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c, 2019)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

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

A_and_i = [[a, i] for i, a in enumerate(A)]
A_and_i.sort(reverse=True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        # 右に持っていく
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

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

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

A_and_i = [[a, i] for i, a in enumerate(A)]
A_and_i.sort(reverse=True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        # 右に持っていく
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)
Buggy python submission (verdict: Runtime Error):
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())


# nの約数列挙
def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i**2 == n:
                continue
            ans.append(n // i)
    return ans  # sortされていない


MOD = 10 ** 9 + 7

ans = 0
num = 0
CNT = [0] * (K+1)
for i in range(K, 1, -1):
    n = K // i
    c = pow(n, N, MOD)

    c -= CNT[i]

    num += c

    f = divisor(i)
    for n in f:
        CNT[n] += c

    ans += c * i
    ans %= MOD


al = pow(K, N, MOD)
ans += al - num
ans %= MOD

print(ans)


Fixed submission:
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())


# nの約数列挙
def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i**2 == n:
                continue
            ans.append(n // i)
    return ans  # sortされていない


MOD = 10 ** 9 + 7

ans = 0
num = 0
CNT = [0] * (K+1)
for i in range(K, 1, -1):
    n = K // i
    c = pow(n, N, MOD)

    c -= CNT[i]

    num += c

    f = divisor(i)
    for n in f:
        CNT[n] += c

    ans += c * i
    ans %= MOD


al = pow(K, N, MOD)
ans += al - num
ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

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


# 解説見た

H, W, K = map(int, input().split())
MEIJI = []
for _ in range(H):
    MEIJI.append(list(map(int, list(input()))))

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):
    # 分割できるか
    ok = False

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    if ok:
        ans = min(num_cut, ans)

print(ans)


Fixed submission:
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

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


# 解説見た

H, W, K = map(int, input().split())
MEIJI = []
for _ in range(H):
    MEIJI.append(list(map(int, list(input()))))

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):
    # 分割できるか
    ok = False

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    if ok:
        ans = min(num_cut, ans)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

H, W = map(int, input().split())
MEIJI = [input() for _ in range(H)]


def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)


Fixed submission:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

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

H, W = map(int, input().split())
MEIJI = [input() for _ in range(H)]


@lru_cache(maxsize=None)
def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

H, W = map(int, input().split())
MEIJI = [input() for _ in range(H)]


def dfs(r, c, cnt, iswhite=True):
    #if r == H - 1 and c == W - 1:
        #return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)
        
    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)


Fixed submission:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

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

H, W = map(int, input().split())
MEIJI = [input() for _ in range(H)]


@lru_cache(maxsize=None)
def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7


ans = 2 ** N - 1
ans %= MOD


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


fact, fact_inv = make_fact(B + 10, MOD)

arr = cumprod(list(range(N, N-B, -1)), MOD)

a = arr[A - 1] * fact_inv[A]
a %= MOD
b = arr[B-1] * fact_inv[B]
b %= MOD

# print(mb)
# print(fact_inv)

'''
a = ma * fact_inv[A]
a %= MOD

b = mb * fact_inv[B]
b %= MOD
'''

ans -= (a + b)
ans %= MOD

print(ans)


Fixed submission:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7


def myPow(x, n, MOD):
    if n == 0:
        return 1

    res = 1
    while(n > 0):
        if n & 1 == 1:
            res = res * x % MOD

        x = x * x % MOD
        n = n >> 1

    return res


ans = myPow(2, N, MOD)
ans -= 1

# print("hoge")


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


fact, fact_inv = make_fact(B + 10, MOD)

arr = cumprod(list(range(N, N-B, -1)), MOD)

a = arr[A - 1] * fact_inv[A]
a %= MOD
b = arr[B-1] * fact_inv[B]
b %= MOD

# print(mb)
# print(fact_inv)

'''
a = ma * fact_inv[A]
a %= MOD

b = mb * fact_inv[B]
b %= MOD
'''

ans -= (a + b)
ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
import bisect
sys.setrecursionlimit(10 ** 7)

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

A.sort()
minus = bisect.bisect_left(A, 0)
plus = bisect.bisect_right(A, 0)
zero = plus - minus

negative = minus * plus
positive = (plus * (plus - 1) // 2) + (minus * (minus - 1) // 2)
zeros = (N * N - 1) // 2 - (positive + negative)

if K <= negative:
    A0 = A[:minus]
    A1 = A[plus:]
    A1.sort()

    left = -(10 ** 18)
    right = 0

    print(A0)
    print(A1)

    def test(val):
        cnt = 0
        lg = len(A0)
        for a0 in A0:
            p = val // a0
            cnt += lg - bisect.bisect_left(A1, p)
        return cnt

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        print("mid,cnt", mid, res)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()


elif negative < K and K <= (negative + zeros):
    print(0)
    exit()
else:
    A0 = A[:minus]
    A1 = A[plus:]

    A0.sort(reverse=True)

    K -= zeros + negative

    def test(val):
        cnt = 0
        lg = len(A0)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l

        lg = len(A1)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l
        return cnt

    left = 0
    right = 10 ** 18

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()


Fixed submission:
import sys
import numpy as np
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(), np.int64)

A = np.sort(A)
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]


def test(x):
    cnt = 0

    if x >= 0:
        cnt += len(zero) * N

    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // -neg, side='right')).sum()
    cnt -= np.count_nonzero(A * A <= x)

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  # NG
r = 10 ** 19  # OK

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)