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

N, Q= map(int, input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)] 

T = "AC"

for val in range(len(lr)):
	counter = 0
	lr_part = S[lr[val][0]-1:lr[val][1]]
	counter = lr_part.count(T)
	print(counter)

### FIXED CODE ###

N, Q= map(int, input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)] 

T = "AC"
t = [0] * (N+1)

for val in range(N):
	if S[val:val+2] == "AC":
		t[val + 1] = t[val] + 1
	else:
		t[val + 1] = t[val]

for val in range(Q):

	print(t[lr[val][1]-1] - t[lr[val][0]-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def check(a,b,n):
  l=n.bit_length()
  for i in range(l):
    if n&(1<<i):
      a=dbl[i][a]
  return a>=b

n=int(input())
arr=list(map(int,input().split()))
l=int(input())
dbl=[[0]*(n+1)]
pos=0
for i in range(n):
  for j in range(pos,n):
    if arr[j]-arr[i]>l:
      dbl[0][i+1]=j
      pos=j
      break
  else:
    dbl[0][i+1]=n
for _ in range(n.bit_length()-1):
  tmp=[0]*(n+1)
  for i in range(n+1):
    tmp[i]=dbl[-1][dbl[-1][i]]
  dbl.append(tmp)
q=int(input())
for _ in range(q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  l=0
  r=b-a+1
  while r-l!=1:
    mid=(l+r)//2
    if check(a,b,mid):
      r=mid
    else:
      l=mid
  print(r)

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
      dbl[0][i+1]=bisect.bisect_right(arr,arr[i]+l)
  for _ in range(n.bit_length()-1):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(mid.bit_length()):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()
### BUGGY CODE ###

import numpy as np
N, K=map(int,input().split(' '))
H=list(map(int,input().split(' ')))
dp=[]

for i in range(N):
	if i==0:
		dp.append(0)
	elif i==1:
		dp.append(abs(H[1]-H[0]))
	else:
		d = np.min(np.array([ dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,K+1) if i-j>=0]))
		dp.append(d)
		
print(dp[N-1])

### FIXED CODE ###

N, K=map(int,input().split(' '))
H=list(map(int,input().split(' ')))
dp=[]

for i in range(N):
	if i==0:
		dp.append(0)
	elif i==1:
		dp.append(abs(H[1]-H[0]))
	else:
		d = min([ dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,K+1) if i-j>=0])
		dp.append(d)
		
print(dp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math

N,M = map(int,input().split())
S = input()
if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    N, K = NMI()
    A = list(sorted([NLI() for _ in range(K)]))
    
    ls = [0 for _ in range(N+A[-1][1]+10)]
    ls[0] = 1
 
    for n in range(N):
        for k in range(K):
            for x in range(A[k][0],A[k][1]+1):
                ls[n+x] += ls[n]%MOD2
    print(ls[N-1]%MOD2)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    LR = list(sorted([NLI() for _ in range(K)]))
    
    dp = [0 for _ in range(N)]
    dp[0] = 1
    
    cumsum = [0 for _ in range(N+1)]
    cumsum[0] = 0
    cumsum[1] = 1
    
    for n in range(1,N):
        for k in range(K):
            r = n-LR[k][0]
            l = n-LR[k][1]
            if r < 0:
                continue
            else:
                l = max(0,l)
            dp[n] += cumsum[r+1]-cumsum[l]
        dp[n] = dp[n]%MOD2
        cumsum[n+1] = (dp[n] + cumsum[n])%MOD2
    print(dp[-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

l = int(input())

lst = list(str(l))
lin = list(map(int,lst[:]))

#print(l)
#print(lst)
#print(lin)

le = len(lin)

dp1 = [0] * le#A+BがL以下だとわかっている
dp2 = [0] * le#A+BがL以下だとわかっていない

dp1[0] = 1
dp2[0] = 2

for i in range(1,le):
    if lin[i] == 0:
        dp1[i] = (dp1[i-1] * 3)%(10**9+7)
        dp2[i] = dp2[i-1]
    else:
        dp1[i] = (dp1[i-1] * 3 + dp2[i-1])%(10**9+7)
        dp2[i] = dp2[i-1] * 2

print((dp1[-1]+dp2[-1])%(10**9+7))



### FIXED CODE ###

L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点で
#既にA+BがL以下であることが分かっているような値組(A, B)の個数
dp2 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点では
#まだA+BがL以下になるかどうか分かっていないような値組 (A, B) の個数

dp1[0] = 1 #(A,B)=(0,0)
dp2[0] = 2 #(A,B)=(1,0),(0,1)

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)
### BUGGY CODE ###

S=input()
ans=0
N=len(S)
for i in range(N-2):
  s=S[i:i+3]
  for j in range(i+3,N):
    s+=S[j]
    if int(s)%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
### BUGGY CODE ###

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

def keisan(h,w):
    k = 0
    while h-k>=0:
        if G[h-k][w] == ".":
            k += 1
        else:
            break
    l = 0
    while h+l<H:
        if G[h+l][w] == ".":
            l += 1
        else:
            break
    m = 0
    while w-m>=0:
        if G[h][w-m] == ".":
            m += 1
        else:
            break
    n = 0
    while w+n < W:
        if G[h][w+n] == ".":
            n += 1
        else:
            break
    return k+l+m+n-3

ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
                ans = max(ans,keisan(h,w))
                if ans == H+W-1:
                    print(ans)
                    exit(0)
print(ans)


### FIXED CODE ###

H, W = map(int,input().split())
G = [input() for k in range(H)]
yoko = [[0 for k in range(W)] for k in range(H)]
tate = [[0 for k in range(W)] for k in range(H)]


for h in range(H):
    t = 0
    s = 0
    for w in range(W):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,w):
                    yoko[h][k] = t
            s = w+1
            t = 0
    if t > 0:
        for k in range(s,W):
            yoko[h][k] = t


for w in range(W):
    t = 0
    s = 0
    for h in range(H):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,h):
                    tate[k][w] = t
            s = h+1
            t = 0
    if t > 0:
        for k in range(s,H):
            tate[k][w] = t

ans = 0
for w in range(W):
    for h in range(H):
        ans = max(ans,tate[h][w]+yoko[h][w]-1)
print(ans)
### BUGGY CODE ###

import heapq
H,W,K = map(int,input().split())
s1,e1,s2,e2 = map(int,input().split())
s1-=1
e1-=1
s2-=1
e2-=1
L = []
board = []
for _ in range(H):
    a = input()
    L.append(a)
for i in range(H):
    l = L[i]
    tmp = []
    for j in range(len(l)):
        tmp.append(l[j])
    board.append(tmp)

hq = []
heapq.heappush(hq,[0,s1,e1])
seen = [[False]*(W) for _ in range(H)]
destination = [(1,0),(-1,0),(0,1),(0,-1)]
while hq:
    cost,x,y = heapq.heappop(hq)
    seen[x][y] = True
    if x==s2 and y ==e2:
        print(cost);exit()
        break
    for dx,dy in destination:
        X,Y = x,y
        for i in range(K):
            X +=dx
            Y += dy
            if 0>X or X>=H or 0>Y or Y>=W: break
            else:
                if board[X][Y]=='@':
                    break
                elif not seen[X][Y]:
                    heapq.heappush(hq,[cost+1,X,Y])
                    seen[X][Y] = True

print(-1)

### FIXED CODE ###

import collections
H,W,K = map(int,input().split())
s1,e1,s2,e2 = map(int,input().split())
s1-=1
e1-=1
s2-=1
e2-=1
L = []
board = []
for _ in range(H):
    a = input()
    L.append(a)
for i in range(H):
    l = L[i]
    tmp = []
    for j in range(len(l)):
        tmp.append(l[j])
    board.append(tmp)

queue = collections.deque()
queue.append([0,s1,e1])
seen = [[float('inf')]*(W) for _ in range(H)]
destination = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
    cost,x,y = queue.popleft()
    seen[x][y] = cost
    if x==s2 and y ==e2:
        print(cost);exit()
        break
    for dx,dy in destination:
        X,Y = x,y
        for i in range(1,K+1):
            NX = X +i*dx
            NY = Y + i*dy
            if 0>NX or NX>=H or 0>NY or NY>=W or seen[NX][NY] < seen[X][Y]+1: break
            else:
                if board[NX][NY]=='@':
                    break
                elif seen[NX][NY] ==float('inf'):
                    queue.append([cost+1,NX,NY])
                    seen[NX][NY] = cost+1

print(-1)
### BUGGY CODE ###

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

sum_a = [sum(a[0:i]) for i in range(1, N)]
a.reverse()
sum_b = [sum(a[0:i]) for i in range(1, N)]

res = abs(sum_a[0] - sum_b[N-2])
for i in range(N-1):
  res = min(res, abs(sum_a[i] - sum_b[N-2-i]))
  
print(res)

### FIXED CODE ###

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

for i in range(1, N):
  a[i] += a[i-1]

res = abs(a[0] - (a[-1]-a[0]))
for i in range(N-1):
  res = min(res, abs(a[i] - (a[-1] - a[i])))

print(res)
### BUGGY CODE ###

from collections import deque
import numpy as np
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
k = np.array(L)
count = 0
for i in range(N-2):
    l = k[i]
    for j in range(1,N-i-1):
        m = k[i+j]
        n = np.count_nonzero(k[i+j+1:] > (l-m))
        if n == 0:
            break
        else:
            count += n
print(count)

### FIXED CODE ###

from copy import copy
from collections import deque
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
first = deque(L)
count = 0
for i in range(N-2):
    l = first.pop()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.pop()
        n = len(second) - bisect.bisect_right(second,l-m)
        if n > 0:
            count += n
        else:
            break
print(count)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations
N= int(input())
s = [''.join(sorted(list(input()))) for i in range(N)]
tmp = list(combinations(s,2))
result = [i for i in tmp if i[0] == i[1]]
print(len(result))

### FIXED CODE ###

def nCr(n, r):
    r = min(r, n-r)
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i
    return numerator // denominator

N= int(input())
s = [''.join(sorted(list(input()))) for i in range(N)]

dic={}
for i in s:
	if i in dic:
		dic[i] +=1
	else:
		dic[i] = 1

result = 0
for j in dic.values():
	if j > 1:
		result += nCr(j,2)

print(result)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
S = [sorted(input()) for i in range(N)]
S = ["".join(S[i]) for i in range(N)]

S_ = S[:]
S_ = set(S_)

c = 0

for i in S_:
    a = S.count(i)
    if a == 1 :
        continue
    ans = combinations_count(a, 2)
    c += int(ans)

print(c)


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
existed = {}
c = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))

  if sorted_s in existed:
    c += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(c)
### BUGGY CODE ###

import numpy as np

def solve(S, i, Ns):
    #print("i:{}".format(i))
    #print("Ns:{}".format(Ns)) 
    if len(S) <= i:
        return 0 # Ns[i] でインデックスの外
    if Ns[i] != -1:
        return Ns[i]
    N = 0
    for j in range(i+4, len(S)+1):
        s = int(S[i:j])
        #print(s)
        if s % 2019 == 0:
            N = 1+solve(S,i+j, Ns)
            break
    Ns[i] = N
    return N


if __name__ == "__main__":
    # 2019 = 3 * 673
    S = str(input())
    n = len(S)
    Ns = [-1 for i in range(n)]

    # ans = 0
    # # for i in range(2019):
    # #     for j in range(1, 10):
    # #         if (i*10+j) % 2019 == 0:
    # #             print(i,j)
    # # for i in range(0, n):
    # #     for j in range(i+1, n+1):
    # #         s = int(S[i:j])
    # #         #print(s)
    # #         if s % 2019 == 0:
    # #             #print("i,j : {}, {}".format(i, j))
    # #             ans += 1
    # print(ans)

    for i in range(len(S)):
        solve(S, i, Ns)
    #print(Ns)
    print(sum(Ns))




### FIXED CODE ###

import numpy as np
import collections

def main():
    S = str(input())
    n = len(S)

    T = [-1 for i in range(n+1)]
    T[-1] = 0
    # for i in range(n):
    #     #print(S[i:])
    #     T[i] = int(S[i:]) % 2019
    # print(T)
    b = [1 for i in range(n)]
    for i in reversed(range(n-1)):
        b[i] = b[i+1]*10 % 2019
    #print(b)

    # for i in reversed(range(n)):
    #     T[i] = (int(S[i])*10**(n-1 -i) + T[i+1]) % 2019
    # print(T)

    for i in reversed(range(n)):
        T[i] = (b[i]*int(S[i]) + T[i+1]) % 2019
    #print(T)


    C = collections.Counter(T)
    #print(C) # dict 型のサブクラス，Counter
    ans = 0
    for value, count in C.items():
        ans += int(count*(count-1)/2)
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

a,b,k = map(int,input().split())
num = [i for i in range(a,b+1)]
for i in range(min(k,len(num))):
    print(num[i])
if k<=len(num)-k:
    for i in range(len(num)-k,len(num)):
        print(num[i])
else:
    for i in range(k,len(num)):
        print(num[i])

### FIXED CODE ###

a,b,k = map(int,input().split())
if k<=(b-a)-k:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)
### BUGGY CODE ###

n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
b = []
for k in range(n):
    if k == 0:
        b = a[:]
    else:
        for i in range(n):
            b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print ans

### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))
### BUGGY CODE ###

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

for _ in range(m):
    b, c = map(int, input().split())
    a += [c]*b
a.sort()

print(sum(a[-n:]))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(x)) for x in input().split()]

for _ in range(m):
    b, c = map(int, input().split())
    a += [(b, c)]

from operator import itemgetter
a = sorted(a, key=itemgetter(1))

ans = 0
t = 0
while n-t > 0:
    (k, x) = a.pop()
    ans += x * min(k, n-t)
    t += k

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

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            if j < n - 1:
                j += 1
                count += n - j 
            else:
                count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid
    #print(l, r)

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)



    


### FIXED CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)
### BUGGY CODE ###

from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<nn and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)
### BUGGY CODE ###

k = int(input())
i = 7

if k%2 ==0:
    print('-1')
else:
    while True:
        if i % k == 0:
            print(len(str(i)))
            break
        else:
            i = int(str(i)+'7')



### FIXED CODE ###

k = int(input())
x = 7%k
cnt = 0

if k%2 ==0:
    print('-1')
else:
    while True:
        cnt += 1
        if x == 0:
            print(cnt)
            break
        elif cnt == k:
            print('-1')
            break
        else:
            x = (x*10+7)%k
### BUGGY CODE ###

def solve(n, tbl):
    for k, tbl_k in enumerate(tbl):
        for i, tbl_i in enumerate(tbl):
            ik = tbl_i[k]
            if ik == 0:
                continue
            for j in range(i + 1, n):
                ij, kj = tbl_i[j], tbl_k[j]
                if ij == 0 or kj == 0:
                    continue
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    tbl_i[j] = 0
    return sum(sum(row[i + 1:]) for i, row in enumerate(tbl))


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))


### FIXED CODE ###

def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min((ik + kj for ik, kj in zip(row_i, row_j) if ik and kj), default=float('inf'))
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [int(i) for i in input().rstrip().split()]
A = np.array(A)
sum = 0

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


ans = sum % (10**9+7)
print(ans) 

### FIXED CODE ###

from itertools import accumulate
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
Ac = list(accumulate(A))

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