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

import sys
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)


visited = [0]*n
ans = [0]*n

# DFS for tree
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        if visited[to]: continue

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')


### FIXED CODE ###

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

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

ans = [0]*n

# DFS for tree (再帰はpypyの方が遅かったりするので注意)
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')
### BUGGY CODE ###

n = int(input())
s = input()

ans = s.count('W')
ans = min(ans, s.count('E'))

for i in range(n):
    test = s[:i]
    test = s[i+1:]
    ans = min(ans, s[:i].count('W') + s[i+1:].count('E'))

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 3 * 10**7
w = [0]
e = [0]

for i, a in enumerate(s):
    if a == 'W':
        w.append(w[-1]+1)
    else:
        w.append(w[-1])

for i, a in enumerate(s[::-1]):
    if a == 'E':
        e.append(e[-1]+1)
    else:
        e.append(e[-1])

e.reverse()

for i in range(n):
    ans = min(ans, w[i]+e[i+1])

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

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

    cnt = 0

    for i in range(min(a),max(a)+1):
        cnt = max(cnt,a.count(i-1)+a.count(i)+a.count(i+1))
    
    print(cnt)

main()

### FIXED CODE ###

# 辞書を用意して最大値を取得する

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

cnt = {}

for i in a:
    for j in [-1,0,1]:
        cnt.setdefault(i+j, 0)
        cnt[i+j] += 1

print(max(cnt.values()))
### BUGGY CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
A += [i+K for i in A]
diff = [A[i+1] - A[i] for i in range(N*2-1)]

length = sum(A)

for i in range(len(diff) - N + 1):
    length = min(length, sum(diff[i:i+N-1]))
print(length)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
diff = [A[i+1] - A[i] for i in range(N-1)]
if 0 in A:
    diff.append(K- A[-1])
else:
    diff.append(A[0] + K - A[-1])


print(sum(diff) - max(diff))
### BUGGY CODE ###

s = input()

maxlen = 0
for i, char_1 in enumerate(s):
  for j, char_2 in enumerate(s):
    if char_1=='A' and char_2=='Z' and maxlen < j - i + 1:
      maxlen = j - i + 1
print(maxlen)

### FIXED CODE ###

s = input()
print(s.rfind('Z') - s.find('A') + 1)
### BUGGY CODE ###

n=int(input())
ls=[[int(s) for s in input().split()] for _ in range(n-1)]
ans=[-1]*(n+1)
ans[1]=0
position=1
e_num=n-1
pan=[0]
while e_num>0:
  for i in range(e_num):
    if ls[i][0]==position:
      next_pos=ls[i][1]
      d=ls[i][2]
      ls.pop(i)
      break
    elif ls[i][1]==position:
      next_pos=ls[i][0]
      d=ls[i][2]
      ls.pop(i)
      break
  if next_pos==0:
    position=pan[-1]
    pan.pop(-1)
  else:
    ans[next_pos]=(ans[position]+d)%2
    pan.append(position)
    position=next_pos
    next_pos=0
    e_num-=1
for i in range(1,n+1):
  print(ans[i])
  
  

### FIXED CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1): #辺の情報と距離を記録
  u, v, w = map(int, input().split())
  edge[u-1].add((v-1, w))
  edge[v-1].add((u-1, w))

#幅優先検索
dist = [0] * N #距離
stack = [0]
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to, w in edge[vrt].copy():
    stack.append(to)
    dist[to] = dist[vrt] + w
    edge[vrt].discard((to, w))
    edge[to].discard((vrt, w))
    
for i in range(N):
  print(dist[i]%2)
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    s = input()
    if not s in l:
        l.append(s)
print(len(l))

### FIXED CODE ###

n = int(input())
l = [input() for i in range(n)]
l =  list(set(l))
print(len(l))
### BUGGY CODE ###

X, Y = map(int, input().split())

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (2*Y - X) < 0:
    print(0)
elif (2*X - Y) < 0:
    print(0)
else:
    if (X - 2*Y) % 3 != 0 or (2*X - Y) % 3 != 0:
        print(0)
    else:
        a = (2 * Y - X) // 3
        b = (2 * X - Y) // 3
        m = 10**9+7
        res = 1
        for i in range(1,a+b+1):
            res = res*i%m
        for i in range(1,a+1):
            res = res*mod_inv(i,m)%m
        for i in range(1,b+1):
            res = res*mod_inv(i,m)%m
        print(res)

### FIXED CODE ###

X, Y = map(int, input().split())
M = 1000000007

def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result


if (2*Y - X) < 0:
    print(0)
elif (2*X - Y) < 0:
    print(0)
else:
    if (X - 2*Y) % 3 != 0 or (2*X - Y) % 3 != 0:
        print(0)
    else:
        a = (2 * Y - X) // 3
        b = (2 * X - Y) // 3
        ans = cmb(a+b, a)
        ans = ans % M
        print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]==a[j]:
      b.append(a[i])
      a[j]=0
      break
if len(b)<=1:
  print(0)
else:
  b.sort()
  b.reverse()
  print(b[0]*b[1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
max1=0;max2=0
count=0
for i in range(n-3):
  if a[i]==a[i+1]:
    max1=a[i]
    a[i+1]=0
    count=i+1
    break
if count==0:
  print(0)
  exit()
for j in range(count,n-1):
  if a[j]==a[j+1]:
    max2=a[j]
    break
print(max1*max2)
### BUGGY CODE ###

n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 1:
    return a
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  rs = 1
  for i in range(s):
    rs = rs*(n-i)%mod
  rl = rs
  for i in range(s,l):
    rl = rl*(n-i)%mod
  L = 1
  for i in range(1,s+1):
    L = L*mpow(i,mod-2)%mod
  rs = rs*L%mod
  rl = rl*L%mod
  for i in range(s+1,l+1):
    rl = rl*mpow(i,mod-2)%mod
  if a < b:
    nCa, nCb = rs, rl
  else:
    nCa, nCb = rl, rs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa,nCb)

### FIXED CODE ###

import math
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*pow(i,mod-2,mod)%mod
  return ans

print((pow(2,n,mod)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(n,a))
### BUGGY CODE ###

S = list(input())
S.reverse()
def check(s):
    if s[:5] == list("maerd"):
        del s[:5]
        return True
    elif s[:7] == list("remaerd"):
        del s[:7]
        return True
    elif s[:5] == list("esare"):
        del s[:5]
        return True
    elif s[:6] == list("resare"):
        del s[:6]
        return True
    else:
        return False

while check(S):
    c = 0

if S == []:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = list(input())
 
while len(a) >= 5:
    if a[-5:] == list('dream'):
        del a[-5:]
        continue
    if a[-7:] == list('dreamer'):
        del a[-7:]
        continue
    if a[-5:] == list('erase'):
        del a[-5:]
        continue
    if a[-6:] == list('eraser'):
        del a[-6:]
        continue
    break
 
if a == []:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
x=[0]*(10**3+1)
y=[]
for i in range(n):
    x[l[i]]+=1
for i in range(10**3+1):
    if i==0:
        y.append(0)
    else:
        y.append(y[i-1]+x[i])
y.append(y[len(y)-1])
ans=0
for i in range(n):
    for j in range(n):
        if i!=j:
            a=min(l[i],l[j])
            b=max(l[i],l[j])
            m=b-a
            M=min(a+b,10**3+1)
            g=y[M-1]-y[m]
            ans+=g
            if m<a<M:
                ans-=1
            if m<b<M:
                ans-=1
print(ans//6)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
x=[0]*(10**3+1)
y=[]
for i in range(n):
    x[l[i]]+=1
for i in range(10**3+1):
    if i==0:
        y.append(0)
    else:
        y.append(y[i-1]+x[i])
y.append(y[len(y)-1])
ans=0
for i in range(n):
    for j in range(n):
        if i!=j:
            a=min(l[i],l[j])
            b=max(l[i],l[j])
            m=b-a
            M=min(a+b,10**3+1)
            g=y[M-1]-y[m]
            ans+=g
            if m<a<M:
                ans-=1
            if m<b<M:
                ans-=1
print(ans//6)
### BUGGY CODE ###

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

count = 1
for i in range(1, (m//n)+1):
    temp = m - (i*n)
    if temp % i == 0:
        count = i
        
print(count)


### FIXED CODE ###

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

count = 1
for i in range((m//n), 0, -1):
    if m % i == 0:
        count = i
        break

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

from operator import itemgetter
import numpy as np


def f(idx):
    ret = np.zeros((1 << n, n), np.int64)

    for i in range(1 << n):
        lines = [0]
        now = i
        for j in range(n):
            if now & 1:
                lines.append(xyp[j][idx])
            now >>= 1

        for j, (e, p) in enumerate(map(itemgetter(idx, 2), xyp)):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))

            ret[i, j] = dist * p

    return ret


def pow3topow2(pow3):
    v = 0
    h = 0
    cnt = 0
    pow2 = 1
    while pow3:
        pow3, r = divmod(pow3, 3)
        if r == 1:
            v += pow2
            cnt += 1
        elif r == 2:
            h += pow2
            cnt += 1

        pow2 *= 2

    return v, h, cnt


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
powers = [pow3topow2(i) for i in range(3 ** n)]
for i in range(3 ** n):
    vi, hi, cnt = powers[i]
    score = np.minimum(ver[vi], hor[hi]).sum()
    ans[cnt] = min(ans[cnt], score)

print(*ans, sep="\n")


### FIXED CODE ###

import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")
### BUGGY CODE ###

#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

# main
n = int(readline())
xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
# [..., (x_i, y_i, i), ...]
# sort by x
xy.sort()

root = int(math.sqrt(len(xy)))

low = [x for x, y, i in xy[::root]]
high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = xy[i]
        for i in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[i][0] <=tx:
                ret.append(v[i][2])
    if ret:
        ret.sort()
        print('\n'.join(map(str,ret)))
    print()

### FIXED CODE ###

#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()
### BUGGY CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a

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

inf = float('inf')
dp = [inf] * N

dp[0] = 0
dp[1] = abs(H[1] - H[0])

for i in range(2,N):
    for j in range(1,K+1):
        if i - j < 0:
            continue
        dp[i] = chmin(dp[i], dp[i-j] + abs(H[i] - H[i-j]))
        

print(dp[N-1])

### FIXED CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a

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

inf = float('inf')
dp = [inf] * N

dp[0] = 0
dp[1] = abs(H[1] - H[0])

for i in range(2,N):
    for j in range(1,K+1):
        if i - j < 0:
            continue
        dp[i] = chmin(dp[i], dp[i-j] + abs(H[i] - H[i-j]))
        

print(dp[N-1])
### BUGGY CODE ###

from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()



### FIXED CODE ###

from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        q = collections.deque(map(int, input().split()))
        Q.append(q)
    
    L = [N-1 for _ in range(N)]
    games = N*(N-1)//2
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if L[i] == 0 or gamed[i] != 0:
                continue
            j = Q[i][0] - 1
            if L[j] > 0 and gamed[j] == 0:
                if Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    L[i] -= 1
                    L[j] -= 1
                    gamed[i] = 1
                    gamed[j] = 1
                    games -= 1
                    continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = [[0,0,0,0] for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        for j in range(4):
            dp[i+1][j] = t * dp[i][j]
        if (s[i] == "A") or (s[i] == "?"):
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
        if (s[i] == "B") or (s[i] == "?"):
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
        if (s[i] == "C") or (s[i] == "?"):
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD
    return dp[n][3] % MOD

s = input()
print(solve(s))

### FIXED CODE ###

import numpy as np
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = np.zeros((n+1, 4), dtype=int)
    dp[0,0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        dp[i+1] = t * dp[i] % MOD
        if s[i] == "A":
            dp[i+1,1] += dp[i,0]
        elif s[i] == "B":
            dp[i+1,2] += dp[i,1]
        elif s[i] == "C":
            dp[i+1,3] += dp[i,2]
        else:
            dp[i+1,1:] += dp[i,:-1]
    return dp[n][3] % MOD

s = input()
print(solve(s))
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N, K = map(int, f_i.readline().split())
    
    import numpy as np
    A = np.array(f_i.readline().split(), dtype=int)
    A.sort()
    
    INF = 10 ** 18 + 1
    l = -INF
    r = INF
    
    zero_num = len(A[A==0])
    tot_init = zero_num * (N - 1)
    
    mA = A[A<0]
    pA = A[A>0]
    
    while l + 1 < r:
        x = (l + r) // 2
        if x > 0:
            tot = tot_init
        else:
            tot = 0
        
        for a in mA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    right = mid
                else:
                    left = mid
            tot += (N - right)
            if a ** 2 < x:
                tot -= 1
        
        for a in pA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    left = mid
                else:
                    right = mid
            tot += right
            if a ** 2 < x:
                tot -= 1
        
        tot //= 2
        if tot < K:
            l = x
        else:
            r = x
    
    print(l)

solve()

### FIXED CODE ###

from sys import stdin
f_i = stdin

import numpy as np

N, K = map(int, f_i.readline().split())
A = np.array(f_i.read().split(), dtype=int)

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * N
    
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    
    cnt -= np.count_nonzero(A ** 2 <= x)
    return cnt // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)
### BUGGY CODE ###

N = int(input())
tmp = []
for _ in range(N):
    tmp.append(input())
tmp.sort()

w = []
c = []

# print(tmp)
m = 0
for i in tmp:
    if i not in w:
        w.append(i)
        c.append(tmp.count(i))
        if m < tmp.count(i):
            m = tmp.count(i)

# print(w)
# print(c)

for i in c:
    if m == i:
        print(w[c.index(i)])
        c[c.index(i)] = -1

### FIXED CODE ###

N = int(input())

ans = {}
m = 1
for _ in range(N):
    w = input()
    c = ans.get(w)
    # print(c)
    # print(type(c))
    if c == None:
        ans[w] = 1
    else:
        ans[w] = c + 1
        if c + 1 > m:
            m = c + 1
# print(ans)

tmp = []
for a in ans:
    if ans[a] == m:
        tmp.append(a)

tmp.sort()
for t in tmp:
    print(t)
### BUGGY CODE ###

# 79
# ABC106 D


def solve():
    N, M, Q = map(int, input().split())
    LR_L = tuple([int(x) for x in input().split()] for y in range(M))
    Q_L = tuple([int(x) for x in input().split()] for y in range(Q))

    imos_l = [[0] * (N+2) for _ in range(N+1)]

    for l, r in LR_L:
        imos_l[l][l] += 1
        imos_l[l][r+1] -= 1
    for i in range(1, N+1):
        for j in range(1, N+2):
            imos_l[i][j] += imos_l[i][j-1]

    for p, q in Q_L:
        ans = 0
        for i in range(p, q+1):
            ans += imos_l[i][i] - imos_l[i][q+1]
        print(ans)


solve()


### FIXED CODE ###

# 79
# ABC106 D


def solve():
    N, M, Q = map(int, input().split())
    LR_L = tuple([int(x) for x in input().split()] for y in range(M))
    Q_L = tuple([int(x) for x in input().split()] for y in range(Q))

    imos_l = [[0] * (N+2) for _ in range(N+1)]

    for l, r in LR_L:
        imos_l[l][l] += 1
        imos_l[l][r+1] -= 1
    for i in range(1, N+1):
        for j in range(1, N+2):
            imos_l[i][j] += imos_l[i][j-1]

    for p, q in Q_L:
        ans = 0
        for i in range(p, q+1):
            ans += imos_l[i][i] - imos_l[i][q+1]
        print(ans)


solve()