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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M,L = inpl()
cost = [[INF]*N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    cost[a][b] = c
    cost[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])

# print(cost)

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            cost[i][j] = 0
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF


for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])


Q = inp()
ans = []
for _ in range(Q):
    s,t = inpl()
    tmp = cost[s-1][t-1]
    if tmp == INF:
        print(-1)
    else:
        print(tmp-1)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M,L = inpl()
cost = [[INF]*N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    cost[a][b] = c
    cost[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])

# print(cost)

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            cost[i][j] = 0
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF

# print(cost)

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])


Q = inp()
ans = []
for _ in range(Q):
    s,t = inpl()
    tmp = cost[s-1][t-1]
    if tmp == INF:
        ans.append(-1)
    else:
        ans.append(tmp-1)

print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
A = sorted([int(x) for x in input().split()])

while M > 0:
    a = A.pop()
    bisect.insort(A, a//2)
    M -= 1

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmin = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmin//2))

print(-sum(A))
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10 ** 6)

p=[100,101,102,103,104,105]
x=int(input())

def dfs(sum):
    ans=False
    if sum>=x:
        return sum==x
    for i in p:
        ans|=dfs(sum+i)
    return ans 

if dfs(0):
    print(1)
else:
    print(0)
    

### FIXED CODE ###

x=int(input())
p=[100,101,102,103,104,105]
ans=[False]*2001
ans[0]=True
for i in range(2000):
    if ans[i]:
        for j in p:
            if i+j>2000:
                continue
            else:
                ans[i+j]=True
if x>2000:
    print(1)
elif ans[x]:
    print(1)
else:
    print(0)
### BUGGY CODE ###

import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        elif i - bisect.bisect_right(l,(l[j]-l[i])) > 0:
            ans += i - bisect.bisect_right(l,(l[j]-l[i]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
for _ in range(K):
  if A == B == C:
    break
  A, B, C = B + C, A + C, A + B
if A - B > 10 ** 18:
  print('Unfair')
else:
  print(A-B)

### FIXED CODE ###

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

o = B - A
e = A - B
if K % 2 == 0:
  r = e
else:
  r = o 
print(r)
### BUGGY CODE ###

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    P_part = P[:tar] + P[tar+1:]
    C_part = C[:tar] + C[tar+1:]

    cnt_part = [0 for _ in range(D-1)]
    point_part = [0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar
        if cnt_tar == P[tar]:
            point_base += C[tar]

        if True:
#            print('point_base = ',point_base,)
            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]

                for j in range(D-1):
                    bit = int(s_bit[j:j+1])
                    cnt_part[j]   = (P_part[j])*bit
                    point_part[j] = (P_part[j]*(P.index(P_part[j])+1)*100 + C_part[j])*bit

                num = num_base + sum(cnt_part)
                point = point_base + sum(point_part)
#                print(cnt_tar,cnt_part,point)
                if point >= G:
                    # print('point = ',point,'/',G)
                    # print(num)
                    ans = min(ans,num)
        if point_base >= G:
            break

print(ans)


### FIXED CODE ###

import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100*tar_min

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

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

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10 ** 20
dp = [[INF]*(H+10**4) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    a, b = next(AB)
    for j in range(H+10**4):
        dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b if j-a >= 0 else INF)
print(min(dp[-1][H:]))


### FIXED CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


mod = 10 ** 9 + 7

l = 1
for i in A:
    l = (l * i) // gcd(l,i)
    
ans = 0
for i in range(N):
    ans += (l // A[i]) % mod
    ans %= mod
    
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


mod = 10 ** 9 + 7

l = 1
ans = 0
for i in A:
    l = (l * i) // gcd(l,i)
    ans += pow(i, mod-2, mod)
    ans %= mod
l %= mod
ans = (l * ans) % mod

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

n = int(input())
s = input()
r,g,b =0,0,0
for i in range(len(s)):
    if s[i]=='R':
        r+=1
    elif s[i]=='G':
        g+=1
    elif s[i]=='B':
        b+=1
cnt =0
for j in range(1,len(s)-1):
    for i in range(j):
        k = 2*j-i
        if k<len(s):
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                cnt+=1
print(r*g*b-cnt)


### FIXED CODE ###

n = int(input())
s = input()
r,g,b =0,0,0
ls = len(s)
for i in range(ls):
    if s[i]=='R':
        r+=1
    elif s[i]=='G':
        g+=1
    elif s[i]=='B':
        b+=1
cnt =0
for j in range(1,ls-1):
    for i in range(j):
        k = 2*j-i
        if k<ls:
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                cnt+=1
print(r*g*b-cnt)
### BUGGY CODE ###

from math import ceil
from decimal import Decimal

N, K = map(int, input().split())
A = list(map(int, input().split()))
# N, K = 2*10**5, 1
# A = [10**9]*N

def solve(x):
    m = 0
    for a in A:
        m += a//x - (a%x == 0)
    # print(x, m)
    return m <= K

ok, ng = Decimal(max(A)), Decimal(0)
while abs(ok-ng > Decimal(0.1**6)):
    mid = (ok+ng)/Decimal(2)
    # print(mid)
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ceil(mid))

### FIXED CODE ###

BIG = 10**10

N, K = map(int, input().split())
A = list(map(int, input().split()))
# N, K = 2*10**5, 2*10**5
# A = [10**9]*N

def solve(x):
    m = 0
    for a in A:
        m += -(-(a//x))
    # print(x, m)
    return m > K

A = [a*BIG for a in A]

# c = 0
ok, ng = 0, max(A)
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid)
    if solve(mid):
        ok = mid
    else:
        ng = mid
    # c += 1

# print(c)

print(-(-ok//BIG))
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

H, W  = map(int, input().split())

A = [[0]*(W+1)]
for i in range(H):
    A.append([0] + list(map(int, input().split())))

B = [[0]*(W+1)]
for i in range(H):
    B.append([0] + list(map(int, input().split())))

C = [[0 for j in range(W+1)] for i in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j] = A[i][j] - B[i][j]

dp = [[set() for j in range(W+1)] for i in range(H+1)]
dp[0][1] = set([0])
dp[1][0] = set([0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in list(dp[i-1][j]):
            if k + C[i][j] <= 6400 and k + C[i][j] >= -6400:
                dp[i][j].add(k + C[i][j])
            if k - C[i][j] <= 6400 and k - C[i][j] >= -6400:
                dp[i][j].add(k - C[i][j])
        for k in list(dp[i][j-1]):
            if k + C[i][j] <= 6400 and k + C[i][j] >= -6400:
                dp[i][j].add(k + C[i][j])
            if k - C[i][j] <= 6400 and k - C[i][j] >= -6400:
                dp[i][j].add(k - C[i][j])

ans = list(dp[H][W])
ans = [abs(i) for i in ans]
print(sorted(ans)[0])

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

H, W  = map(int, input().split())

A = [[0]*(W+1)]
for i in range(H):
    A.append([0] + list(map(int, input().split())))

B = [[0]*(W+1)]
for i in range(H):
    B.append([0] + list(map(int, input().split())))

C = [[0 for j in range(W+1)] for i in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1<<6400
dp[1][0] = 1<<6400
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] = dp[i-1][j]<<C[i][j] | dp[i-1][j]>>C[i][j] | dp[i][j-1]<<C[i][j] | dp[i][j-1]>>C[i][j]

for i in range(6400,INF):
    if dp[H][W]>>i & 1:
        print(i-6400)
        sys.exit()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

query = [list(input().split()) for _ in range(q)]

if n == 1:
    for w, dir in query:
        if w == s:
            print(0)
            exit()
    print(1)
    exit()
# 左に落ちる (1から, leftで判断(leftは落ちる個数))
left = 0
right = n
while right - left > 1:
    mid = (left + right) // 2
    index = mid - 1
    for w, dir in query:
        if s[index] != w:
            continue
        if dir == 'R':
            index += 1
        elif dir == 'L':
            index -= 1

        if index == n:
            right = mid
            break
        elif index == -1:
            left = mid
            break
    if index != -1:
        right = mid
c1 = left

# 右 (leftで判断(leftが落ちないギリギリ。最大はn-1, 最小は-1))
left = -1
right = n
while right - left > 1:
    mid = (left + right) // 2
    index = mid
    for w, dir in query:
        if s[index] != w:
            continue
        if dir == 'R':
            index += 1
        elif dir == 'L':
            index -= 1

        if index == n:
            right = mid
            break
        elif index == -1:
            left = mid
            break
    if index != n:
        left = mid

c2 = n - 1 - left

print(n - c1 - c2)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

query = [list(input().split()) for _ in range(q)]

# 左に落ちる。leftから左(leftを含む)は左に落ちて、rightから右は左に落ちない。
left = -1
right = n
while right - left > 1:
    mid = (left + right) // 2
    index = mid
    for w, dir in query:
        if s[index] != w:
            continue
        if dir == 'R':
            index += 1
        elif dir == 'L':
            index -= 1

        if index == n:
            right = mid
            break
        elif index == -1:
            left = mid
            break
    if index != -1:
        right = mid
c1 = left + 1

# 右に落ちる。leftから左(leftを含む)は右に落ちず、rightから右は右に落ちる。
left = -1
right = n
while right - left > 1:
    mid = (left + right) // 2
    index = mid
    for w, dir in query:
        if s[index] != w:
            continue
        if dir == 'R':
            index += 1
        elif dir == 'L':
            index -= 1

        if index == n:
            right = mid
            break
        elif index == -1:
            left = mid
            break
    if index != n:
        left = mid

c2 = n - 1 - left

print(n - c1 - c2)
### BUGGY CODE ###

a, b=map(int, input().split())
k=min(a, b)
l=max(a, b)
for i in range(k, l+1):
    if abs(a-i)==abs(b-i):
        print(i)
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

a, b=map(int, input().split())
k=max(a, b)
l=min(a, b)
if (k+l)%2==0:
    print((k+l)//2)
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N,M = map(int,input().split())
Bridge = [[int(x)-1 for x in input().split()] for _ in range(M)] 

Igr = [{i} for i in range(N)]
Inconv = [N*(N-1)//2] * (M+1)

for i in range(M):  
    A = Bridge[M-1-i][0] 
    B = Bridge[M-1-i][1]
    if B in Igr[A]:     
        Inconv[M-1-i] = Inconv[M-i]  
    else:
        Inconv[M-1-i] = Inconv[M-i]-(len(Igr[A])*len(Igr[B]))
        Ngr = Igr[A] | Igr[B]   
        for x in list(Ngr):   
            Igr[x] = Ngr
        
for i in range(1,M+1):
    print(Inconv[i])


### FIXED CODE ###

N,M = map(int,input().split())
Bridge = [[int(x)-1 for x in input().split()] for _ in range(M)]

Parent = [-1] * N
Size = [1] * N

def Pr(x):
    if Parent[x] == -1:
        return x
    else:
        return Pr(Parent[x])

Igr = [{i} for i in range(N)]
Inconv = [N*(N-1)//2] * (M+1)

for i in range(M):
    A = Bridge[M-1-i][0]
    B = Bridge[M-1-i][1]
    if Pr(A) == Pr(B):
        Inconv[M-1-i] = Inconv[M-i]
    else:
        Inconv[M-1-i] = Inconv[M-i]-(Size[Pr(A)]*Size[Pr(B)])
        if Size[Pr(A)]<Size[Pr(B)]:
            P = B
            C = A
        else:
            P = A
            C = B
        Size[Pr(P)] = Size[Pr(P)] + Size[Pr(C)]
        Parent[Pr(C)] = Pr(P)

for i in range(1,M+1):
    print(Inconv[i])
### BUGGY CODE ###

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

def CalExVal(x):
    return (1/2*(x+1))
Ex = list(map(CalExVal, A))
temp = len(A)-K + 1
#adjlist = [0]*(temp)
adjlist = [sum(Ex[i:(K+i)]) for i in range(temp)]
#for i in range(temp):
#    adjlist[i] = sum(Ex[i:(K+i)])

print(max(adjlist))


### FIXED CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  #temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  tem = sum(Ex[:K])
  res = tem
  for i in range(0,N-K):
      tem = tem - Ex[i] + Ex[i+K]
      if res < tem:
      	res = tem
  print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])


### FIXED CODE ###

from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=visited[n]+t
for z in keika:
    print(visited[z[0]]+visited[z[1]])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
ln = max(max(a), max(b)) + 1
for i in range(ln):
  y = (1 << (i + 1))
  u = [x % y for x in a]
  v = [x % y for x in b]
  y >>= 1
  u.sort(reverse = True)
  v.sort()
  t = 0
  k = 0
  kk = 0
  s = 0
  ss = 0
  for x in u:
    while k < N and x + v[k] < y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 2: kk += 1
    t -= N - kk
    while s < N and x + v[s] < y * 2 + y: s += 1
    t += N - s
    while ss < N and x + v[ss] < y * 4: ss += 1
    t -= N - ss
    #print(t)
  #print(u, v, t)
  res ^= t % 2 * y
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
ln = max(max(a), max(b)).bit_length() + 1
for i in range(ln):
  y = (1 << (i + 1))
  u = [x % y for x in a]
  v = [x % y for x in b]
  y >>= 1
  u.sort(reverse = True)
  v.sort()
  t = 0
  k = 0
  kk = 0
  for x in u:
    while k < N and x + v[k] < y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 2: kk += 1
    t -= N - kk
  k = 0
  kk = 0
  #print(t)
  for x in u:
    while k < N and x + v[k] < y * 2 + y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 4: kk += 1
    t -= N - kk
    #print(t)
  #print(u, v, t)
  res ^= t % 2 * y
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
set_a=list(set(a))
set_a.sort()
count=0
for i in set_a:
    if i<a.count(i):
        count+=a.count(i)-i
    elif a.count(i)<i:
        count+=a.count(i)
print(count)

        


### FIXED CODE ###

from collections import Counter
n=int(input())
counter=Counter(map(int,input().split()))
sum=0
for a,cnt in counter.items():
    if cnt<a:
        sum+=cnt
    else:
        sum+=cnt-a
print(sum)
### BUGGY CODE ###

import bisect

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

A.sort()

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if b*(n-a)-(b-a)-(b-a)*(b-a-1)//2>=k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for a in A:
        if a==0:
            if pos>=0:
                count+=n-1
        elif a<0:
            i=bisect.bisect_right(A,(-1-pos)//(-a))
            count+=n-i + (-1 if a*a<=pos else 0)
        else:
            i=bisect.bisect_right(A,pos//a)
            count+=i + (-1 if a*a<=pos else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)


### FIXED CODE ###

import numpy as np

n,k=map(int,input().split())
A=np.array(input().split(),np.int64)
A.sort()

zero=A[A==0]
neg=A[A<0]
pos=A[A>0]

def f(x): # count pairs x or less
    cnt=0
    #zero
    if x>=0:
        cnt += len(zero)*n
    #pos
    cnt += A.searchsorted(x//pos,side="right").sum()
    #neg
    cnt += (n-A.searchsorted(-(-x//neg),side="left")).sum()
    #except a*a
    cnt-=np.count_nonzero(A*A<=x)
    return cnt//2

l=-10**18
r=10**18

while l<r:
    pov=(l+r)//2
    if f(pov)>=k:
        r=pov
    else:
        l=pov+1
print(l)
### BUGGY CODE ###

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

for i in range(q):
    prototype = input()
    if prototype == '1':
        s_copy = ""
        for j in range(len(s)):
            s_copy = s_copy + s[(len(s) - 1) - j]
        
        s = s_copy
    else:
        num, f_num, c = prototype.split()
        
        if(f_num == '1'):
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

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

cnt = 0
left = ''
right = ''
for i in range(q):
    q_very = input()

    #print(q_very)
    if q_very[0] == '1':
        #print('t is 1')
        cnt += 1
    else:
        instruction = q_very.split()
        # 反転していない
        if cnt % 2 == 0:
            if instruction[1] == '1':
                left = instruction[2] + left
            else:
                right = right + instruction[2]
        else: # 反転している
            if instruction[1] == '1':
                right = right + instruction[2]
            else:
                left = instruction[2] + left

s = left + s + right

if cnt % 2 != 0:
    s = s[::-1]
print(s)