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

N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()


### FIXED CODE ###

N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()
### BUGGY CODE ###

from collections import deque

X = int(input())

q = deque()
q.append((0, 1))

while len(q) > 0:
    pos = q.popleft()
    if pos[0] + pos[1] == X or pos[0] - pos[1] == X:
        print(pos[1])
        break
    q.append((pos[0] + pos[1], pos[1] + 1))
    q.append((pos[0] - pos[1], pos[1] + 1))
    q.append((pos[0]         , pos[1] + 1))


### FIXED CODE ###

X = int(input())
t = 1

while True:
    if t * (t + 1) / 2 >= X:
        print(t)
        break
    t += 1
### BUGGY CODE ###

import itertools
N = int(input())
S = input()
S = list(S)
L = set()
for i, j, k in itertools.combinations(S,3):
  L.add(i + j + k)
#print(L)
print(len(L))

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

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

a.sort()

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
  

sMAX = 1
memo=[a[1],a[0]]
memo2=[a[1],a[0]]
for i in range(n):
  MAX = 1
  for j in range(0, i):
    temp = cmb(a[i], a[j])
            
    if MAX <= temp:
      MAX = temp
      memo = [a[i], a[j]]
    else:
      break
      
  if sMAX < MAX:
    sMAX = MAX
    memo2 = memo
    
for i in range(2):
  print(memo2[i], end=" ")

### FIXED CODE ###

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

left = a[-1]
sa = 199999999999999999999999999
for i in range(n):
  if sa > abs((left/2) -a[i]):
    right = a[i]
    sa = abs((left/2) - a[i])
    
print(left, right)
### BUGGY CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
ans = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)

### FIXED CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
t = a = 1
for i in range(N):
    n = max(-(-t//T[i]), -(-a//A[i]))
    t = n*T[i]
    a = n*A[i]
print(t+a)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def use_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    divisors.append(n//i)
    divisors.sort()
    return divisors

N = I()
X = str(input())

ans = 0
divisors = use_divisors(2*N)

C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

ans = 0
divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

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

n=int(input())
s_list=[]

for i in range(n):
  s_elem=''.join(sorted(list(input())))
  s_list.append(s_elem)

unq_list=list(set(s_list))
count=0

for j in range(len(unq_list)):
  match_n=s_list.count(unq_list[j])
  count+=sum(range(1, match_n))

print(count)

### FIXED CODE ###

n=int(input())
dic={}

count=0
for i in range(n):
  s_elem=''.join(sorted(list(input())))
  if s_elem in dic:
    count+=dic[s_elem]
    dic[s_elem]+=1
  else:
    dic[s_elem]=1

print(count)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
C = sorted([r, g, b], reverse=True)
r, g, b = C[0], C[1], C[2]

for i in range(n//r+2):
    for j in range((n-r*i)//g+2):
        if n - r*i - g*j >= 0 and (n - r*i - g*j) % b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
C = sorted([r, g, b], reverse=True)
r, g, b = C[0], C[1], C[2]

for i in range(n//r+2):
    for j in range((n-r*i)//g+2):
        if n - r*i - g*j >= 0 and (n - r*i - g*j) % b == 0:
            ans += 1

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

from collections import Counter
import math
def comb(n, r):
    # print(n, r)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

# comb = Combination(n-1)
c = Counter(a)

for i in range(n):
    num = a[i]
    # c[num] - 1
    temp = 0
    for (key, val) in c.items():
        # print('\n', key, val)
        if val < 2:
            continue
        if key == num:
            if val > 2:
                temp += comb(val - 1, 2)
        else:
            temp += comb(val, 2)
    print(temp)

'''
5
1 1 2 1 2
'''

### FIXED CODE ###

from collections import Counter
import math
def comb(n, r):
    # print(n, r)
    return (n * (n-1))//2
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

# All combination
total = 0
for (key, val) in c.items():
    # print('\n', key, val)
    if val > 1:
        total += comb(val, 2)

# print('all:', total)

for i in range(n):
    num = a[i]
    org = c[num]
    # print(org)
    # total - orgC2 + (org-1)C2
    if org > 2:
        ans = total - comb(org, 2) + comb(org-1, 2)
    elif org == 1 or org == 0:
        ans = total
    else:
        ans = total - comb(org, 2)
    print(ans)
### BUGGY CODE ###

a = list(map(int,input().split()))
p = list(map(int,input().split()))
n = a[0]
k = a[1]

sum_k = 0
max_i = 0
max_sum = 0
for i in range(n-k+1):
  sum_k = 0
  for j in range(i,i+k):
    sum_k += p[j]
  if max_sum < sum_k:
    max_sum = sum_k
    max_i = i

c = [0]*k
for i in range(k):
  c[i] = p[max_i+i]
    
#print(c)
ans = 0
for i in range(len(c)):
  n = c[i]+1
  for j in range(1,n):
    ans += j*(1/(n-1))

print(ans)

### FIXED CODE ###

a = list(map(int,input().split()))
p = list(map(int,input().split()))
n = a[0]
k = a[1]

E = [0]*(n+1)

sum_E = 0
max_E = 0

for i in range(1,n+1):
  sum_E += (p[i-1]+1)/2
  E[i] = sum_E

for i in range(n-k+1):
  #print(E[i+k] - E[i])
  if max_E < E[i+k] - E[i]:
    max_E = E[i+k] - E[i]
#print(E)
print(max_E)
### BUGGY CODE ###

i=j=c=x=int(input())
while i**5-j**5-x:i=c%128;j=c>>7;c-=1
print(i,j)

### FIXED CODE ###

x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]
### BUGGY CODE ###

n = int(input())
c = list(input())
ans = 0

for i in range(n-1):
    if c[i] == "W":
        for j in range(n-i-1):
            if c[n-1-j]=="R":
                c[i]="R"
                c[n-1-j]="W"
                ans+=1
                break

print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())

ans = 0

r = c.count("R")
for i in range(r):
    if c[i] == "W":
        ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
addarr = [i+1+A[i] for i in range(N)]
difarr = [i+1-A[i] for i in range(N)]
ans = 0
for i in range(1,N):
    tmp = difarr[i]
    ans += addarr[:i].count(tmp)
    
print(ans)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
addarr = [i+1+arr[i] for i in range(n)]
diffarr = [i+1-arr[i] for i in range(n)]

from collections import Counter
cnt = Counter([addarr[0]])
ans = 0

for i in range(1,n):
    tmp = diffarr[i]
    ans += cnt[tmp]
    cnt.update([addarr[i]])

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

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


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

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
for k in range(N):
    C = A[k:]+A[:k]
    if B == C:
        ans.append((k,a[k]^b[0]))
for x in ans:
    print(*x)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)
### BUGGY CODE ###

a, b, k = map(int, input().split())
result_list = [i for i in range(a, b+1) if (i < a+k) or (i > b-k)]

for res in result_list:
  print(res)

### FIXED CODE ###

a, b, k = map(int, input().split())
list_1 = [i for i in range(a, a+k) if i<=b]
list_2 = [i for i in range(b-k+1, b+1) if a<=i]
list_1.extend(list_2)
print(*sorted(set(list_1)), sep = '\n')
### BUGGY CODE ###

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

ans = []
for i in range(1, n+1):
  ans.append(l.index(i)+1)

a = ""
for idx in range(n-1):
  a += str(ans[idx])
  a += " "

a += str(ans[n-1])
print(a)

### FIXED CODE ###

import numpy as np

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

k = np.argsort(l)

for i in range(n):
  k[i]+=1

print(' '.join(map(str, k)))
### BUGGY CODE ###

import sys
n =int(input())
a =list(map(int ,input().split()))
for i in range(n):
    for j in range(n):
        if  i !=j:
            if a[i] ==a[j]:
                print("NO")
                sys.exit()
else:
    print("YES")

### FIXED CODE ###

n =int(input())
a =list(map(int ,input().split()))
s =set(a)
if len(a) >len(s):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

from collections import deque
import numpy as np

global d
global temp

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if temp[ny][nx] < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = temp[ny][nx]
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]

maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i, j))

for i in slist:
    #s = bfs(i[0], i[1])
    #if s>max:
       # max = s
    s = bfs(i[0], i[1])

print(s)


### FIXED CODE ###

from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

h, w, m = map(int, input().split())
lsh = [0] * h
lsw = [0] * w

bom = []
for _ in range(m):
    m1, m2 = map(int, input().split())
    lsh[m1 - 1] += 1
    lsw[m2 - 1] += 1
    bom.append((m1-1, m2-1))

lshmax = max(lsh)
lswmax = max(lsw)

hin = [i for i in range(h) if lsh[i] == lshmax]
win = [i for i in range(w) if lsw[i] == lswmax]

jd = False

for i in hin:
    for j in win:
        if (i, j) not in bom:
            jd = True

if jd:
    print(lshmax + lswmax)
else:
    print(lshmax + lswmax -1)

### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    lsh = [0] * h
    lsw = [0] * w

    bom = set()
    for _ in range(m):
        m1, m2 = map(int, input().split())
        lsh[m1 - 1] += 1
        lsw[m2 - 1] += 1
        bom.add((m1-1, m2-1))

    lshmax = max(lsh)
    lswmax = max(lsw)

    hin = [i for i in range(h) if lsh[i] == lshmax]
    win = [i for i in range(w) if lsw[i] == lswmax]

    for i in hin:
        for j in win:
            if (i, j) not in bom:
                print(lshmax + lswmax)
                exit(0)
    else:
        print(lshmax + lswmax -1)


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

S = list(input())
count = 0
while True:
    if '1' not in S or '0' not in S:
        break
    L = len(S)
    for i in range(L):
        if i < L-1 and (S[i] == '0' and S[i+1] == '1' or S[i] == '1' and S[i+1] == '0'):
            count += 2
            S = S[:i] + S[i+2:]
            break
print(count)

### FIXED CODE ###

S = input()
print(min(2*S.count('0'),2*S.count('1')))
### BUGGY CODE ###

n = int(input())
As = list(map(int, input().split()))
ans = [0] * n
for a in As:
  ans[a - 1] = As.index(a) + 1
print(*ans)

### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
ans = [0] * n
for a, i in zip(As, range(1, n+1)):
  ans[a - 1] = i
print(*ans)
### BUGGY CODE ###

# coding: utf-8
N, M = [int(x) for x in input().split(" ")]
As = [int(x) for x in input().split(" ")]
As.sort()
for i in range(M):
    As[-1] //= 2
    As.sort()
sum = 0
for num in As:
    sum += num
print(sum)

### FIXED CODE ###

# coding: utf-8
import heapq

N, M = [int(x) for x in input().split(" ")]

prices = [-int(x) for x in input().split(" ")]

heapq.heapify(prices)

for i in range(M):
    maxp = heapq.heappop(prices)
    heapq.heappush(prices, -((-maxp) // 2))

total = 0
for x in prices:
    total += -x

print(total)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)



### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")
### BUGGY CODE ###

def bound2(a,y,x):
  ok=-1
  ng=len(a)
  while ng-ok>1:
    mid=(ok+ng)//2
    if a[mid]*y<=x:ok=mid
    else:ng=mid
  return ok
def bound1(x):
  s=t=0
  for y in a:
    s+=bound2(b,y,x)+1
    t+=bound2(a,y,x)
    if y*y>x:t+=1
  s+=t//2
  t=0
  for y in c:
    t+=bound2(c,y,x)
    if y*y>x:t+=1
  return s+t//2
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bound2(t,1,0)+1
a,b,c=t[i:],t[:i],t[i-1::-1]
ok=10**19
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if bound1(mid)>=k:ok=mid
  else:ng=mid
print(ok)

### FIXED CODE ###

from bisect import*
def solve(x):
  s=t=0
  i=n
  j=-1
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)