Harryxun/stf_run huggingface dataset:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 18
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

### FIXED CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)
a,b,n=map(int(input().split()))
print(max(a-n,0),max(b-max(a-n,0),0))


### FIXED CODE ###

a,b,n=map(int,input().split())  
print(max(a-n,0),max(b-max(n-a,0),0))
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
#sys.stdin = open("input.txt", "r")
#sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)
is_prime=[1 for i in range(10**6+1)]
is_prime[0]=0
is_prime[1]=0
for i in range(2,10**6+1):
    if(is_prime[i]):
        for j in range(2*i,10**6+1,i):
            is_prime[j]=0
n=l()[0]
div=[]
if(n==1):
    print(0)
    exit()
for i  in range(2,int(n**0.5)+1):
    if(n%i==0 and is_prime[i]):
        div.append(i)
        if(is_prime[n//i] and n//i!=i):
            div.append(n//i)
ans=0
for p in range(1,n//div[0]):
    x=n
    for ele in div:
        if(n%(ele**p)==0):
            # print(n,ele**p)
            ans+=1
            n//=(ele**p)
        else:
            break
    if(x==n):
        break
# print(ans)
for i in range(ele**p,n+1):
    if(x%i==0):
        x//=i
        ans+=1
    if(x==1):
        break
print(ans)



### FIXED CODE ###

N = int(input())
 
ans = 0
f = 2
while True:
  if N%f==0:
    c = 0
    while N%f==0:
      N /= f
      c += 1
    n = 1
    while n*(n+1)//2<=c:
      n += 1
    ans += n-1
  if f*f>N:
    break
  f += 1
if N>1:
  ans += 1
print(ans)
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
print("YNeos"[sum([sum(a)/(4*m)<a[i] for i in range(m+1)])<m::2])

### FIXED CODE ###

n,m = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
for i in range(m):
    if a[i] < sum(a)/(4*m):
        print("No")
        exit()
print("Yes")
k,t=map(int,input().split())
l=list(map(int,input().split()))
if len(l)==n:
  print(n-1)
else:
  print(max(0,max(l)//2-n))

### FIXED CODE ###

k,t=map(int,input().split())
l=list(map(int,input().split()))
if len(l)==1:
  print(k-1)
else:
  if k%2==0:
    print(max(0,(max(l)-k//2)*2-1))
  else:
    print(max(0,(max(l)-k//2-1)*2))
k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in (1,n):
  b.append(a[i] - a[i-1])
b.append(k - a[n-1] + a[0])
b = sorted(b)

print(sum(b[:-1]))

### FIXED CODE ###

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

for i in range(1,n):
  b.append(a[i] - a[i - 1])
b.append(k - a[n-1] + a[0])

b = sorted(b)
print(sum(b[:n-1]))
import sys
f = sys.stdin


import string

OFFSET = ord('a')

def to_gamma(c):
    return ord(c) - OFFSET

def from_gamma(gamma, alpha, beta):
    return chr((alpha * gamma + beta) % 26 + OFFSET) 

def affine(c, alpha, beta):
    return from_gamma(to_gamma(c), alpha, beta)


# g[0]==g[3]である前提
def search_that(w):
    b = to_gamma(w[2])
    for a in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b):
            return a, b
    return -1, -1

def search_this(g):
    a = (to_gamma(w[0]) - to_gamma(w[3]) + 26) % 26
    for b in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b) and w[2] == affine('i',a,b) and w[3] == affine('s',a,b):
            return a, b
    return -1, -1

def search(w):
    if w[0] == w[3]:
        return search_that(w)
    else:
        return search_this(w)

n = int(f.readline())
for i in range(n):
    line = f.readline().strip()
    words = [word for word in line.split() if len(word) == 4]
    for word in words:
        a, b = search(word)
        if a != -1:
            print(line.translate(str.maketrans(''.join([affine(c, a, b) for c in string.ascii_lowercase]), string.ascii_lowercase)))
            break    
    

### FIXED CODE ###

import sys
f = sys.stdin

import string

OFFSET = ord('a')

def to_gamma(c):
    return ord(c) - OFFSET

def from_gamma(gamma, alpha, beta):
    return chr((alpha * gamma + beta) % 26 + OFFSET) 

def affine(c, alpha, beta):
    return from_gamma(to_gamma(c), alpha, beta)


# g[0]==g[3]である前提
def search_that(w):
    b = to_gamma(w[2])
    for a in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b):
            return a, b
    return -1, -1

def search_this(w):
    a = (to_gamma(w[0]) - to_gamma(w[3]) + 26) % 26
    for b in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b) and w[2] == affine('i',a,b) and w[3] == affine('s',a,b):
            return a, b
    return -1, -1

def search(w):
    if w[0] == w[3]:
        return search_that(w)
    else:
        return search_this(w)

n = int(f.readline())
for i in range(n):
    line = f.readline().strip()
    words = [word for word in line.split() if len(word) == 4]
    for word in words:
        a, b = search(word)
        if a != -1:
            print(line.translate(str.maketrans(''.join([affine(c, a, b) for c in string.ascii_lowercase]), string.ascii_lowercase)))
            break
N=list(int(input()))
N_=reversed(N)
if N==N_:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N=list(input())
N_=list(reversed(N))
if N==N_:
    print('Yes')
else:
    print('No')
a,b = map(int,input())
print('Even' if (a * b) % 2 == 1 else  'Odd')

### FIXED CODE ###

a,b = map(int,input().split())
print('Even' if (a * b) % 2 == 0 else  'Odd')
import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 15

count = 0
for x in range(k+1):
    if x = s:
        count = count + 1
        break
    for y in range(k+1):
        if s < x + y:
            break
        if x + y = s:
            count = count + 1
            break
        for z in range(k+1):
            if s - x - y < k:
                count = count + 1
                break
print(count)


### FIXED CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 14

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z <= k and 0 <= z:
            count += 1
print(count)
n,m=map(int,input().split())
print(n/(2n-4)+m/(2m-4))

### FIXED CODE ###

n,m=map(int,input().split())
print(((n*(n-1))+(m*(m-1)))//2)
import math
import functools

n = int(input())
v = list(map(int, input().split()))

if max(v) % 2 ==0:
	b = True
else:
	b = False
		
v.sort()

for index,_ in enumerate(v):
	if _  % 2 ==0:
		if not b:
			v[index] = v[-1]
			break
			
	else:
		if b:
			v[index] = v[-1]
			break
			
ans = functools.reduce(math.gcd,v)
print(ans)



### FIXED CODE ###

a,b,t = map(int, input().split())
c = 0
tt = 0

while t + 0.5 > tt + a:
	c+= b
	tt += a	

	
print(c)
N = int(input())
r = []
b = []
for i in range(N):
    r.append([int(i) for i in input().split()])

for i in range(N):
    b.append([int(i) for i in input().split()])

sorted_r = sorted(r, key=lambda r:r[0], reverse=True)
sorted_b = sorted(b)

ans = 0
for e1 in sorted_b:
    for e2 in sorted_r:
        if e2[0] < e1[0] and e2[1] < e1[1]:
            ans += 1
            sorted_r.remove(e2)
            break
print(ans)


### FIXED CODE ###

v =  [int(i) for i in input().split()]

if v[0] + v[1] >= v[2]:
    print("Yes")
else:
    print("No")
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
    exit()

A_abs = [abs(a) for a in A]
A_is_negative = [a < 0 for a in A]

# A_abs の大きい順にソート
A_abs, A_is_negative, A = zip(*sorted(zip(A_abs, A_is_negative, A), key=lambda x: x[0], reverse=True))

# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
if len(A_is_negative) == N and K%2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[-(i+1)]
        ans %= MOD
    print(ans)
    exit()

# case3. それ以外は、負の数は基本的に2つセットで選ばれることに注意
# まずは候補テーブルを作成
A_cost1 = []  # positive 要素
A_cost2 = []  # negative 要素を大きい順に 2 つセットにしたもの
tmp = 1
for a in A:
    if a >= 0:
        A_cost1.append(a)
    else:
        if tmp != 1:
            A_cost2.append(tmp*a)
            tmp = 1
        else:
            tmp *= a

cost = 0
ans = 1
while (cost < K):
    if K - cost >= 2:
        # まだ cost2 から入れる余地がある
        if A_cost2[0] >= A_cost1[0]:
            res = A_cost2.pop(0)
            ans *= res
            ans %= MOD
            cost += 2
        else:
            res = A_cost1.pop(0)
            ans *= res
            ans %= MOD
            cost += 1
    else:
        res = A_cost1.pop(0)
        ans *= res
        ans %= MOD
        cost += 1

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop


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

MOD = 10**9 + 7

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできる

    # K が奇数のとき、非負要素から1つ取って偶数の場合に帰着
    # K が偶数のとき、面倒なので 2 つセットで考えて K//2 個取る問題に帰着

    if K%2 == 1:
        ans = A.pop(0)  # あらかじめ最大値を確保
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

    # 絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    cand = []  # 非負要素、負要素をそれぞれ絶対値の大きい順に 2 つずつ掛けたもの

    BIGINT = 10**9 + 1  # tmp 用
    tmp1 = BIGINT
    tmp2 = BIGINT

    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = a
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    # あとは大きい方から n 個取る
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)
a = sorted(map(int,input().split(" ")),reverse=True)
for i in range(0,3):
	print(a[i])

### FIXED CODE ###

a = [int(input()) for i in range(0,10)]
a.sort(reverse=True)
for i in range(0,3):
	print(a[i])
N,C = map(int,input().split())
num = 100009
channel = [[0]*num for _ in range(C)]
time = [0]*num

max_num = 0
for i in range(N):
  s,t,c = map(int,input().split())
  s,t,c = 2*s-1,2*t,c-1
  if(channel[c-1][s-1] == 1): channel[c-1][s-1] = 0
  channel[c-1][s] = 1 
  channel[c-1][t] = 1
  max_num = max(max_num,t)

tmp = 0
for i in range(C):
 for j in range(max_num+9):
  if((tmp == 0)and(channel[i][j] == 1)):
    tmp = 1
    a = j
  elif((tmp == 1)and(channel[i][j] == 1)):
    tmp = 0
    b = j
    time[a] += 1
    time[b+1] -= 1

ans = 0    
for i in range(max_num+9):
  if(i != 0): time[i] += time[i-1]
  ans = max(ans,time[i])
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N,C = map(int,input().split())
time = [0]*(100009*2)
channel = [[0]*(100009*2) for _ in range(C)]
#(方針)チャンネル関係なしに
#同じチャンネルの連続だと録画開始時間に0.5秒のロスがない
# 同チャンネルで 1-7 7-8 → [0.5,8) → 録画機1つ(0.5~7.99) 
# 違うチャンネルで 1-7 7-8 → [0.5,7) 0.5~6.99 , [6.5,8) 6.5~7.99 → 録画機2つ

#前処理:　同チャンネル#0.5が扱いずらいので,sを2s-1,tを2tに対応させる
#ex: 1-3 → 0.5-3 → 1-6
#ex: 3-5 → 2.5-5 → 5-10
#ex: 1-3,3-5 → 1-6,5-10 → 2個必要の区間をつなげる(ex. 1-7 7-8 → 1-8）
max_num = 0
for i in range(N):
 s,t,c = map(int,input().split())
 s,t = 2*s-1,2*t 
 if(channel[c-1][s-1] == 1): channel[c-1][s-1] = 0
 else: channel[c-1][s] = 1
 channel[c-1][t] = 1
 max_num = max(max_num,t)

#imos法
#0.5が扱いずらいので,sを2s-1,tを2tに対応させる
#ex: 1-3 → 0.5-3 → 1-6
#ex: 3-5 → 2.5-5 → 5-10
#ex: 1-3,3-5 → 1-6,5-10 → 2個必要
#A = []
tmp = 0
for i in range(C):
 for j in range(max_num+10):
  if((tmp == 0)and(channel[i][j] == 1)):
    tmp = 1
    a = j
  elif((tmp == 1)and(channel[i][j] == 1)):
    tmp = 0
    b = j
    #A.append([a,b])
    time[a] += 1
    time[b+1] -= 1
#print(A)
    
ans = 0
for i in range(max_num+10):
  if(i != 0): time[i] += time[i-1]
  ans = max(ans,time[i])
print(ans)
#print(time)
A, B, C = map(int, input().split)

P = min(A+B+1, C)
print(P+B)

### FIXED CODE ###

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

P = min(A+B+1, C)
print(P+B)
if __name__ == "__main__":
    N = int(input())
    A = map(int, input().split())
    for i in A:
        if i % 2 == 0:
            if i % 3 == 0:
                ret = "APPROVED"
            elif i % 5 == 0:
                ret = "APPROVED"
            else:
                ret  = "DENIED"
                break
        else:
            continue
    print(ret)


### FIXED CODE ###



if __name__ == "__main__":
    N = int(input())
    A = map(int, input().split())
    for i in A:
        if i % 2 ==0:
            if i % 3 != 0 and i % 5 != 0:
                    print("DENIED")
                    exit(0)
            else:
                pass
        else:
            pass
    print("APPROVED")
N, K = input().split()
print(N - (K - 1))

### FIXED CODE ###

N, K = map(int, input().split())
print(N - (K - 1))
if __name__ == '__main__':
    a = int(input())
    ansdict= {}
    count = 100000
    mcount =100000 *-1

    for i in range(0,100000):
        c = i **5
        ansdict[i]=c
        ansdict[i*-1]=c*-1
    flag = 0

    for i in range(mcount,count):
        for j in range(mcount,count):
            ans = ansdict[j]-ansdict[i]
            if ans ==a:
                print(str(j) + " " +str(i))
                flag+=1
                break
        if flag == 1:
            break


### FIXED CODE ###

if __name__ == '__main__':
    a = int(input())
    ansdict= {}
    count = 1000
    mcount =1000 *(-1)

    for i in range(0,1000):
        c = i **5
        ansdict[i]=c
        ansdict[i*(-1)]=c*(-1)
    flag = 0

    for i in range(mcount+1,count):
        for j in range(mcount+1,count):
            ans = ansdict[j]-ansdict[i]
            if ans ==a:
                print(str(j) + " " +str(i))
                flag+=1
                break
        if flag == 1:
            break
N=int(input())
H=map(int, input().split())
for i in range(N-1):
    A=H[i+1]
    B=H[i]-1
    if A < B:
        print(No)
    else:
        print(Yes)

### FIXED CODE ###

N=int(input())
H=list(map(int, input().split()))
Z=0
count=0
for i in range(N-1):
    A=H[i+1]
    B=H[i]-1
    if A < B:
        print('No')
        Z=Z+1
        break
    if A == B:
        count=count+1
        if count >=2 and A < C:
            print('No')
            Z=Z+1
            break
        else:
            C=A
if Z == 0:
    print('Yes')
import math
chou = int(input())
tan = int(input())
ji = int(input())
hun = int(input())
ans = float(0)
kakudo = abs(((ji*30 + hun*.6) - (hun*6)))

if kakudo > 180:
    kakudo = kakudo-360
kakudo = abs(kakudo)

kakudo = math.cos(math.radians(kakudo))

ans =( chou**2 + tan**2 - 2*chou*tan*kakudo)
print((ans)**0.5)

### FIXED CODE ###

import math
chou, tan, ji, hun = map(int,input().split())

kakudo = abs(((ji*30 + hun*.5) - (hun*6)))

if kakudo > 180:
    kakudo = 360 - kakudo

kakudo = abs((math.radians(kakudo)))
ans =( chou**2 + tan**2 - 2*chou*tan*math.cos(kakudo))**.5
print(ans)
import numpy as np
H, W, M = map(int, input().split())
HW = []
A = np.zeros((H, W), dtype='int')

for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    HW.append((h, w))
    A[h, w] = 1

arr = A.sum(axis=0)
col_max = arr.max()
col_idx = np.where(arr == col_max)[0]

arr = A.sum(axis=1)
row_max = arr.max()
row_idx = np.where(arr == row_max)[0]

# print(A.sum(axis=0).argsort()[-1])

print(1)

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if A[r, c] == 0:
            print(ans)
            exit()
print(ans - 1)


### FIXED CODE ###

import numpy as np
H, W, M = map(int, input().split())

C = [0] * W
R = [0] * H
S = set()
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    C[w] += 1
    R[h] += 1
    S.add((h, w))

col_max = max(C)
col_idx = [i for i in range(W) if C[i] == col_max]
row_max = max(R)
row_idx = [i for i in range(H) if R[i] == row_max]

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if not (r, c) in S:
            print(ans)
            exit()
print(ans - 1)
a, b = map(int, input().split())
i = 0
count = 1
while true:
  if b <= count:
    break
  count = count + a - 1
  i += 1
print(i)


### FIXED CODE ###


a, b = map(int, input().split())
i = 0
count = 1
while True:
    if b <= count:
        break
    count = count + a - 1
    i += 1
print(i)
ind = 1
for i in a:
    if i == '0':
        print(ind)
        break
    ind += 1

### FIXED CODE ###

a = input().split()
ind = 1
for i in a:
    if i == '0':
        print(ind)
        break
    ind += 1
from bisect import bisect_left, bisect_right


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

nega = bisect_left(A, 0)
posi = N - bisect_right(A, 0)
zero = N - nega - posi

numNega = nega * posi
numZero = (nega + posi) * zero + zero * (zero - 1) // 2
numPosi = N * (N - 1) // 2 - numNega - numZero

Nega = A[:nega]
Posi = A[N - posi:]


def negaCnt(n):
    rst = 0
    for a in Nega:
        b = n // a
        idx = bisect_right(Posi, b)
        rst += posi - idx
    return rst


def posiCnt(n):
    rst = 0
    for i, a in enumerate(Posi):
        b = (n + a - 1) // a
        idx = bisect_left(Posi, b, i + 1)
        rst += idx - (i + 1)
    for i, a in enumerate(Nega):
        b = (n + a - 1) // a
        idx = bisect_left(Nega, b, i + 1)
        rst += idx - (i + 1)
    return rst


if K <= numNega:
    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = Nega[0] * Posi[0]
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if negaCnt(mid) < K:
            ok = mid
        else:
            ng = mid
    ans = ok
elif numNega < K <= numNega + numZero:
    ans = 0
else:
    K2 = K - numNega - numZero
    Nega = [-x for x in reversed(Nega)]
    ok = 0
    ng = max(Nega[-1] ** 2, Posi[-1] ** 2) if nega > 0 else Posi[-1] ** 2
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if posiCnt(mid) < K2:
            ok = mid
        else:
            ng = mid
    ans = ok

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for a in (plus, minus):
                l, r = 0, len(a) - 1
                while l < r:
                    while l < r and a[l] * a[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)

    if cnt < K:
        ok = mid
    else:
        ng = mid

print(ok)
import re
s = input()
k = int(input())

if s[0] != '1':
    print(s[0])
    exit()
else:
    pos = re.search(r'1+',s).end()
    if k < pos:
        print(1)
    else:
        print(s[pos])

### FIXED CODE ###

import re
s = input()
k = int(input())

if s[0] != '1':
    print(s[0])
    exit()
else:
    pos = re.search(r'1+',s).end()
    if k <= pos:
        print(1)
    else:
        print(s[pos])
import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

dp = [[0 for i in range(100005)] for j in range(13)]

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
    res = dp[n][5]
    
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

dp = [[0 for i in range(13)] for j in range(100005)]

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
        
    res = dp[n][5]
    
print(res)