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

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)
i = 0
'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_list[i] = 1

for _ in range(q):
    lr = tuple(map(int, input().split()))
    print(sum(ac_list[lr[0]-1:lr[1]-1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)

'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1] = ac_list[i] + 1
    else:
        ac_list[i+1] = ac_list[i]
# print(ac_list)
for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])
### BUGGY CODE ###

from collections import deque
H,W,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1
Pond = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)
#print(Pond)
Q = deque([])
Q.append((sx,sy))
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  step = K
  for i in range(4):
    for fac in range(1,K+1):
      tx = nx + fac*dxdy[i][0]
      ty = ny + fac*dxdy[i][1]
      #print(i,tx,ty)
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": #or reach[tx][ty] != INF:
        #print(i,tx,ty,reach[2][0])
        break #範囲外やハスがあった、到達済みの場合には終了
      #print(i,tx,ty)
      if reach[nx][ny] + 1 > reach[tx][ty]: #もし現時点よりもステップが大きい場合はだめ。
        #同じ場合は向き的に得している場合もあるので残す。
        break
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append((tx,ty))
    if tx == gx and ty == gy:
      print(reach[gx][gy])
      exit()
#print(reach)
ans = reach[gx][gy]
if ans == INF:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
        res %= 1000000007
    return res


print(find(1, K, False))



### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
        res %= 1000000007
    return res


print(find(1, K, False))
### BUGGY CODE ###

import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

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

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        dp = [x % mod for x in accum(dp, lambda x, y: (x + y) % mod)]
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))


### FIXED CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))
### BUGGY CODE ###

from collections import deque

N, K= map(int, input().split())
A = { n+1:int(i) for n,i in enumerate(input().split())} 

x = deque([1])
point = 1
while True:
  next_point = A[point]
  if next_point in x :
    x.append(next_point)
    break
  x.append(next_point)
  point = next_point
f = x.index(x[-1])
if K <=f:
    print(x[K])
else :
    num = len(x) - f -1
    x = list(x)
    dic = {(n+1+f) %(num): i for n, i in enumerate(x[ f+1:])}
    print(dic[K%num])


### FIXED CODE ###

N, K= map(int, input().split())
A = list(map(int, input().split()))
x = {1:0}
point = 1
count = 0
while True:
  next_point = A[point-1]
  count +=1
  if next_point in x :
    flag=next_point
    break
  x[next_point] =count
  point = next_point
  
#print(count, x[flag])
c = count - x[flag]
f = x[flag]
#print(c)
if K <f:
    print([i for i in x if x[i] == K ][0])
else :
    dic = {j-f: i for i,j in x.items()}
    print(dic[(K-f) % c])
### BUGGY CODE ###

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

n, t = map(int, input().split())
shops = []
shopsA0 = [0]

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b + 1)
    else:
        shops.append([a / (b + 1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t + 10] * 30, dtype=np.int64)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
residual_time = t - DP
ans = [0]
count_A0 = len(cumA0) - 1
for count, residue in enumerate(residual_time):
    while count_A0 > 0 and cumA0[count_A0] > residue:
        count_A0 -= 1
    ans.append(count_A0+count)
print(max(ans))


### FIXED CODE ###

def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = [0]

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b + 1)
        else:
            shops.append([a / (b + 1), a, b])

    shopsA0.sort()
    shops.sort(reverse=True)


    DP = [t+10] * 30
    DP[0] = 0

    for _, a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


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

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]

def calc(x):
    res = 0
    last = 0
    for day,i in enumerate(range(D),1):
        if t[i] == x:
            last = day
            res += s[i][x]
        res -= c[x]*(day-last)
    return res

score = [0]*26
for i in range(26): score[i] = calc(i)
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    old = t[d]
    t[d] = q
    score[old] = calc(old)
    score[q] = calc(q)
    ans[i] = sum(score)
for i in range(M): print(ans[i])

### FIXED CODE ###

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]

def scoreing(x):
    res = 0
    last = 0
    for day,i in enumerate(range(D),1):
        if t[i] == x:
            last = day
            res += s[i][x]
        res -= c[x]*(day-last)
    return res

score = [0]*26
for i in range(26): score[i] = scoreing(i)
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    old = t[d]
    t[d] = q
    score[old] = scoreing(old)
    score[q] = scoreing(q)
    ans[i] = sum(score)
for i in range(M): print(ans[i])
### BUGGY CODE ###


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

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"

while endnum < N:

    while True:

        if end[endp] == 0:
            Q.append(endp)
            break

        endp += 1

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"

        endnum += 1
        end[q] = 1

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

import bisect, sys
n = sys.stdin.readline()
cnt = 0
a = []
for ai in map(int, sys.stdin.readline().split()):
    pos = bisect.bisect_left(a, ai)
    cnt += len(a) - pos
    a.insert(pos, ai)
 
print(cnt)

### FIXED CODE ###

SENTINEL = 10 ** 9 +1
cnt = 0
def merge(A, left, mid, right):
    global cnt

    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += mid - left - i  # ☆

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

n = input()
A = list(map(int, input().split()))
merge_sort(A,0,len(A))
print(cnt)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N ** 0.999 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

for i in range(N):
  print(A.index(i+1)+1,end=' ')

### FIXED CODE ###

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

d={}
for i in range(N):
  d[i]=A[i]
  
#print(A)  
#print(d)
#print(sorted(d.items(), key=lambda x:x[0]))
#print(sorted(d.items(), key=lambda x:x[1]))
ans=sorted(d.items(), key=lambda x:x[1])
for i in range(N):
  print(ans[i][0]+1,end=' ')
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
if len(a) == 1:
    ans = a[0] * (0.5) ** m
    print(int(ans))
    exit()
while m > 0:
    a.sort(reverse=True)
    #print(m)
    plus = a[0] - a[0]//2
    ngtv = a[1] - a[1]//2
    if plus > ngtv:
        m -= 1
        a[0] = a[0]//2
    else:
        m -= 1
        a[1] = a[1]//2
    #print(a)
print(sum(a))


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [ -i for i in a ]
heapq.heapify(a)

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
ss = s
t = []
for i in range(s.count("AC")):
  t.append(ss.index("AC")+1)
  u = ss.index("AC")+2
  ss = 'Q'*u+ss[u:]
for i in range(q):
  l,r = map(int, input().split())
  print(len(["" for i in t if l <= i and i+1 <= r]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
a.sort()
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=0
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = 0
    else:
        i+=1

for i in u:
    print(i)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(i) - 1 for i in input().split()]
    c += 1
    e[a].append([b, c])
    e[b].append([a, c])

c = [0] * n


def dfs(i=0, r=-1, co=0):
    c[i] = co
    for j, k in e[i]:
        if j != r:
            dfs(j, i, (co+k) % 2)


dfs()
print("\n".join(map(str, c)))
### BUGGY CODE ###

a=[];n,k=map(int,input().split())
for _ in[0]*n:
    b,c=map(int,input().split())
    a+=[b]*c
print(sorted(a)[~-k])

### FIXED CODE ###

a=[];n,k=map(int,input().split())
for _ in[0]*n:a+=[list(map(int,input().split()))]
a.sort();i=0
while k>0:k-=a[i][1];i+=1
print(a[~-i][0])
### BUGGY CODE ###

N = int(input())
AS = [int(x) for x in input().split()]

ok = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if AS[i] % AS[j] == 0:
            break
    else:
        ok.append(i)

print(len(ok))


### FIXED CODE ###

N = int(input())
AS = [int(x) for x in input().split()]

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  # 1..max(AS)

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b=-b
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-A[ind])//d
  if dd==0:
    if b!=A[ind]:
      ans=-1
      break
  else:
    ans+=dd
    b-=d*dd
    B[ind]=b
    push(b,ind)
  
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

# D TLE
import itertools
import bisect

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

L.sort()
value = 0

for i, j in itertools.combinations(range(len(L)-1), 2):
    Z = L[j+1:]
    
    index = bisect.bisect_left(Z, L[i]+L[j])
    value+=index
    

print(value)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)
### BUGGY CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
ope=[]
for i in range(Q):
  ope.append(list(map(int,input().split())))
ope=np.array(ope)
A=np.array(A)

for b,c in ope:
  A[A==b]=c
  print(np.sum(A))


### FIXED CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Adic={}
for i in A:
  if Adic.get(i)==None:
    Adic[i]=1
  else:
    Adic[i]+=1
Q=int(input())
ope=[]

for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)

sum=0
for key,value in Adic.items():
  sum+=key*value
for b,c in ope:
  if Adic.get(b)!=None:
    if Adic.get(c)==None:Adic[c]=0
    sum=sum-b*Adic[b]+c*Adic[b]
    Adic[c]+=Adic.pop(b)
    print(sum)
  else:
    print(sum)