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

class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time typ position')

    GO = 0
    STOP = 1

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

    works = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        e1 = Event(time=s - x, typ=STOP, position=x)
        e2 = Event(time=t - x, typ=GO, position=x)
        works.append(e1)
        works.append(e2)
        xs.add(x)

    xs = sorted(xs)

    works.sort(key=attrgetter('time', 'typ'))
    works = deque(works)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while works and works[0].time <= d:
            e = works.popleft()
            p = compress[e.position]
            if e.typ == GO:
                b.add(p, -1)
            else:
                # STOP
                b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
ans = deque(s)
for _ in range(q):
    inp = readline().rstrip()
    if inp[0] == "2":
        if inp[2] == "1":
            ans.appendleft(inp[4])
        else:
            ans.append(inp[4])
    else:
        ans = deque(list(ans)[::-1])

print("".join(ans))


### FIXED CODE ###

import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
ans = deque(s)
cnt = 0
for _ in range(q):
    inp = readline().rstrip()
    if inp[0] == "2":
        if inp[2] == "1":
            if cnt % 2 == 0:
                ans.appendleft(inp[4])
            else:
                ans.append(inp[4])
        else:
            if cnt % 2 == 1:
                ans.appendleft(inp[4])
            else:
                ans.append(inp[4])
    else:
        cnt += 1

if cnt % 2 == 1:
    ans = list(ans)[::-1]
    
print("".join(ans))
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    P.insert(0, 0)
    Dis = [[abs(P[i]-P[(i+j+1)%(N+1)]) for i in range(N+1)] for j in range(2)]
    
    for i in range(N): print(sum(Dis[0])-sum(Dis[0][i:i+2])+Dis[1][i])

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    P.insert(0, 0)
    Dis = [[abs(P[i]-P[(i+j+1)%(N+1)]) for i in range(N+1)] for j in range(2)]
    temp = sum(Dis[0])
    temp2 = [sum(Dis[0][i:i+2]) for i in range(N)]
    for i in range(N): print(temp-temp2[i]+Dis[1][i])
### BUGGY CODE ###

#! /usr/bin/env python3
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())

ans = 1
for a in A:
    ans *= a

print(ans) if ans <= pow(10, 18) else print(-1)


### FIXED CODE ###

#! /usr/bin/env python3
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

limit = pow(10, 18)
N, *A = map(int, read().split())
A = sorted(A)

ans = 1
for a in A:
    ans *= a
    if ans > limit:
        print(-1)
        sys.exit()

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
judge = 1
for i in A[:K]:
  judge *= i
for i in range(N-K):
  judge2 = judge / A[i] * A[K+i]
  if judge2 > judge:
    print('Yes')
  else:
    print('No')
  judge = judge2

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
judge = 1
for i in range(N-K):
  if A[K+i] > A[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans *= i
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in a:
    ans *= i
    if ans > 10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
P = LIST()

flag = [N+1]*N
sortP = sorted(P)
total = 0

for i in range(1, N+1):
	num = P.index(i)
	if min(flag[0:num+1]) > P[num]:
		total += 1
	flag[num] = P[num]

print(total)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
P = LIST()

total = 0
com = N + 1
for i in range(N):
	com = min(com, P[i])
	if P[i] == com:
		total += 1
print(total)
### BUGGY CODE ###

import bisect

A,B,Q = map(int,(input().split()))
s = [[0]*3 for _ in range(A)]
t = [[0]*3 for _ in range(B)]
x = [[0]*3 for _ in range(Q)]
slen = []
tlen = []
road = []
for i in range(A):
    s[i][0] = int(input())
    slen.append(s[i][0])
    s[i][1] = "s"
    road.append(s[i])
for i in range(B):
    t[i][0] = int(input())
    tlen.append(t[i][0])
    t[i][1] = "t"
    road.append(t[i])
for i in range(Q):
    x[i][0] = int(input())
road.sort()

for i in range(len(s)):
    index = bisect.bisect_left(tlen,s[i][0])
    if index < B:
        s[i][2] = min(abs(s[i][0]-tlen[index-1]),abs(tlen[index]-s[i][0]))
    else:
        s[i][2] = abs(s[i][0]-tlen[index-1])
for i in range(len(t)):
    index = bisect.bisect_left(slen,t[i][0])
    if index < A:
        t[i][2] = min(abs(t[i][0]-slen[index-1]),abs(slen[index]-t[i][0]))
    else:
        t[i][2] = abs(t[i][0]-slen[index-1])

for i in range(Q):
    index = bisect.bisect_left(road,x[i])
    if index < A+B:
        print(min(abs(x[i][0]-road[index-1][0])+road[index-1][2],abs(x[i][0]-road[index][0])+road[index][2]))
    else:
        print(abs(x[i][0]-road[index-1][0])+road[index-1][2])

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

A,B,Q = map(int,(input().split()))
s = [[0]*3 for _ in range(A)]
t = [[0]*3 for _ in range(B)]
x = [[0]*3 for _ in range(Q)]
slen = []
tlen = []
road = []
for i in range(A):
    s[i][0] = int(input())
    slen.append(s[i][0])
    s[i][1] = "s"
    road.append(s[i])
for i in range(B):
    t[i][0] = int(input())
    tlen.append(t[i][0])
    t[i][1] = "t"
    road.append(t[i])
for i in range(Q):
    x[i][0] = int(input())
road.sort()

for i in range(len(s)):
    index = bisect.bisect_left(tlen,s[i][0])
    if index < B:
        s[i][2] = min(abs(s[i][0]-tlen[index-1]),abs(tlen[index]-s[i][0]))
    else:
        s[i][2] = abs(s[i][0]-tlen[index-1])
for i in range(len(t)):
    index = bisect.bisect_left(slen,t[i][0])
    if index < A:
        t[i][2] = min(abs(t[i][0]-slen[index-1]),abs(slen[index]-t[i][0]))
    else:
        t[i][2] = abs(t[i][0]-slen[index-1])

for i in range(Q):
    index = bisect.bisect_left(road,x[i])
    if index < A+B:
        print(min(abs(x[i][0]-road[index-1][0])+road[index-1][2],abs(x[i][0]-road[index][0])+road[index][2]))
    else:
        print(abs(x[i][0]-road[index-1][0])+road[index-1][2])
### BUGGY CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
s = input()
n = int(input())
for i in range(n):
    a = input().split()
    # print(a)
    if len(a) == 1:
        s = s[::-1]
    elif a[1] == "1":
        s = a[2] + s
        # print(a[2])
    else:
        s = s + a[2]
    # print(s)
print(s)


### FIXED CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60

# ここから書き始める
s = input()
q = int(input())
cnt = 0
left = []
right = []
for i in range(q):
    query = input().split()
    if len(query) == 1:
        cnt += 1
    else:
        f = query[1]
        c = query[2]
        if cnt % 2 == 0:
            if f == "1":
                # s = c + s
                left.append(c)
            else:
                # s += c
                right.append(c)
        else:
            if f == "1":
                # s += c
                right.append(c)
            else:
                # s = query[2] + s
                left.append(c)

left = left[::-1]
right = "".join(right)
left = "".join(left)
ans = "".join([left, s, right])
# print(right, s, left)
if cnt % 2 != 0:
    ans = ans[::-1]

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

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)


k = int(input())
sum = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            sum += gcd(gcd(i, j), l)

print(sum)

### FIXED CODE ###

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)


k = int(input())

sum = 0

# gcd(a,a,a)
sum += int((1+k)*k/2)

# gcd(a,b,b)
if k >= 2:
    for i in range(1, k):
        for j in range(i+1, k+1):
            sum += gcd(i, j)*6

# gcd(a,b,c)
if k >= 3:
    for i in range(1, k-1):
        for j in range(i+1, k):
            for l in range(j+1, k+1):
                sum += gcd(gcd(i, j), l)*6

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

from itertools import accumulate
from bisect import bisect_left

N = int(input())
l = [int(x) for x in range(1,N+1)]

al = list(accumulate(l))
b = bisect_left(al,N)

if al[b] == N:
  for i in range(b+1):
    print(i+1)
else:
  ng = al[b] - N
  for j in range(1,b+2):
    if j != ng:
      print(j)

### FIXED CODE ###

N = int(input())
l = [int(x) for x in range(1,N+1)]

total_num,max_num = 0,0

if N <= 2:
  print(N)
  exit()

for i in range(1,N):
  total_num += i
  if total_num >= N:
    max_num = i
    break

if total_num == N:
  for i in range(max_num):
    print(i+1)
else:
  ng_num = total_num - N
  for j in range(max_num):
    if j+1 != ng_num:
      print(j+1)
### BUGGY CODE ###

import itertools


max_num = 3000
num_list = [i for i in range(-max_num,  max_num+1)]
num_list_5 = [i ** 5 for i in num_list]
num_comb = list(itertools.combinations(num_list, 2))

x = int(input().strip())
for comb in num_comb:
    a = comb[0]
    b = comb[1]
    a5 = num_list_5[a]
    b5 = num_list_5[b]
    if a5 - b5 == x:
        print(num_list[a], num_list[b])
        break

### FIXED CODE ###

import itertools


max_num = 200
num_list = [i for i in range(-max_num,  max_num+1)]
num_comb = list(itertools.permutations(num_list, 2))

x = int(input().strip())
for comb in num_comb:
    a = comb[0]
    b = comb[1]
    # print(a, b)
    a5 = a ** 5
    b5 = b ** 5
    if a5 - b5 == x:
        print(a, b)
        break
### BUGGY CODE ###

N,M,Q = [ int(it) for it in input().split()]

grid = [ [0]*N for i in range(N) ]
gridsml = [ [0]*N for i in range(N) ]

for i in range(M):
  s,g = [ int(it)-1 for it in input().split()]
  grid[s][g]+=1

for i in range(N):
  gridsml[i][0]=grid[i][0]
  for j in range(1,N):
    gridsml[i][j]+=gridsml[i][j-1]+grid[i][j]


for i in range(Q):
  s,g = [ int(it)-1 for it in input().split()]
  m = 0
  for i in range(s,N):
    m += gridsml[i][g]
  print (m)

### FIXED CODE ###

N,M,Q = [ int(it) for it in input().split()]

grid = [ [0]*N for i in range(N) ]
gridsml = [ [0]*N for i in range(N) ]

for i in range(M):
  s,g = [ int(it)-1 for it in input().split()]
  grid[s][g]+=1

for i in range(N):
  gridsml[i][0]=grid[i][0]
  for j in range(1,N):
    gridsml[i][j]+=gridsml[i][j-1]+grid[i][j]


for i in range(Q):
  s,g = [ int(it)-1 for it in input().split()]
  m = 0
  for i in range(s,N):
    m += gridsml[i][g]
  print (m)
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0
start = 1
x = K - 1
for i in range(N - K + 1):
  if i > 0:
    start = start * (K - 1 + i) // i
  ans += (A[- N + K + i - 1] - A[N - K - i]) * start
  ans = ans % MOD
    
print(ans % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N2 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

#print(cmb(n, r, p))
for i in range(len(A)):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * cmb(N - 1 - i, K - 1, MOD)
    ans = ans % MOD
    
    
print(ans % MOD)
### BUGGY CODE ###

import fractions

a, b = map(int, input().split())
l = []
x = fractions.gcd(a, b)
i = 1
while i * i <= x:
    if x % i == 0:
        l.append(i)
        l.append(x//i)
    i += 1
table = list(set(l))
ans = []
for i in range(len(table)):
    check = True
    for j in range(2, int(table[i]**0.5)+1):
        if table[i] % j == 0:
            check = False
    if check:
        ans.append(table[i])
print(len(ans))

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
n = fractions.gcd(a, b)
i = 1
ass = [1]
for i in range(2, int(n**0.5)+1):
    while n % i == 0:
        ass.append(i)
        n = n//i
if n != 1:
    ass.append(n)
print(len(set(ass)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
H = list(map(int,input().split()))
L = [list(map(int,input().split())) for _ in range(M)]
ans = 0
for i in range(N):
    try:
        ls = set([j[0]-1 for j in L if i+1 in j] + [j[1]-1 for j in L if i+1 in j])
        h = [H[k] for k in ls]
        if max(h) == H[i] and h.count(max(h))==1:
            ans += 1
    except:
        ans += 1
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
L = [0] * N
for _ in range(M):
    a,b = map(int,input().split())
    if H[a-1] > H[b-1]:
        L[b-1] += 1
    elif H[a-1] < H[b-1]:
        L[a-1] += 1
    else:
        L[a-1] += 1
        L[b-1] += 1
ans = L.count(0)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, K = readi(2)
    h = readi(N)
    h.extend([0] * K)
    dp = arr(N + K, fill_value=INF)
    dp[0] = 0
    for i in range(N):
        for j in range(K):
            dp[i + j + 1] = min(dp[i + j + 1], dp[i] + abs(h[i + j + 1] - h[i]))
    print(dp[N - 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

n, k = map(int, input().split())
hs = list(map(int, input().split()))

inf = 10**20
dp = [inf] * n
dp[0] = 0

for i in range(1, n):
    for j in range(i - 1, max(0, i - k) - 1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])

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

#!/usr/bin/env python3
import fractions

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b % mod

ans = t % mod
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import fractions

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b

ans = t % mod
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(set(A))
C = []
for b in B:
    C.append(A.count(b))
C = list(reversed(sorted(C)))
print(sum(C[K:len(C)]))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = {i:0 for i in set(A)}
for a in A:
    B[a] += 1
print(sum(sorted(B.values())[:-K]))
### BUGGY CODE ###

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

for _ in range(N+M-1):
    A, B = map(int, input().split())
    d[A].append(B)
    e[B].append(A)

root = [k for k,v in e.items() if not v][0]
dist = [0] * (N+1)

q = [(root, 0, 0)]
parents = [0] * (N+1)

while q:
    s, r, x = q.pop()
    if x>dist[s]:
        dist[s] = x
        parents[s] = r
    for t in d[s]:
        q.append((t, s, x+1))

for i in range(1, N+1):
    print(parents[i])


### FIXED CODE ###

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

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

l = []
h = [0] * (N+1)

for _ in range(N+M-1):
    A, B = map(int, input().split())
    d[A].append(B)
    e[B].append(A)
    h[B] += 1

st = set()
for i in range(1, N+1):
    if h[i]==0:
        st.add(i)

l = []
while st:
    i = st.pop()
    l.append(i)
    for j in d[i]:
        h[j] -= 1
        if h[j] == 0:
            st.add(j)

tp = {j:i for i,j in enumerate(l, start=1)}
ans = [0] * (N+1)
for i in range(1, N+1):
    s, t = 0, 0
    for j in e[i]:
        if s < tp[j]:
            s = tp[j]
            t = j
    print(t)
### BUGGY CODE ###

N,K=input().split()
N,K=[int(N),int(K)]
A=list(map(int,input().split()))
F=list(map(int,input().split()))

A=sorted(A)
F=sorted(F,reverse=True)

goal_max=10**12+1
goal_min=0-1

while(goal_max-goal_min!=1):
   goal=(goal_max+goal_min)//2
   counter=0

   for i in range(N):
      counter+=max(0,A[i]-goal//F[i])

   if(counter<=K):
      goal_max=goal

   else:
      goal_min=goal
      
print(goal_max)

### FIXED CODE ###

N,K=input().split()
N,K=[int(N),int(K)]
A=list(map(int,input().split()))
F=list(map(int,input().split()))

A=sorted(A)
F=sorted(F,reverse=True)

goal_max=10**12+1
goal_min=0-1

while(goal_max-goal_min!=1):
   goal=(goal_max+goal_min)//2
   counter=0

   for i in range(N):
      counter+=max(0,A[i]-goal//F[i])

   if(counter<=K):
      goal_max=goal

   else:
      goal_min=goal
      
print(goal_max)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
from bisect import bisect, bisect_left


class Node:
    def __init__(self, idx):
        self.idx = idx
        self.v = 0
        self.parent = None
        self.children = []

    def add(self, x):
        self.v += x
        for c in self.children:
            c.add(x)

    def make_tree(self):
        keyidx = bisect_left(brs_keys, self.idx)
        while keyidx < len(brs_keys) and brs_keys[keyidx] == self.idx:
            ni = brs[keyidx][1]
            node = nodes[ni]
            if not node.children:
                self.children.append(node)
            keyidx += 1
        for c in self.children:
            c.make_tree()

    def __str__(self):
        return str(self.idx)


N, Q = [int(_) for _ in input().split()]
nodes = [Node(i) for i in range(0, N)]

brs = []
for i in range(N - 1):
    a, b = [int(_) - 1 for _ in input().split()]
    brs.append((a, b))
    brs.append((b, a))

brs.sort()
brs_keys = [b[0] for b in brs]
nodes[0].make_tree()

# for n in nodes:
#     print(n.idx, [str(c) for c in n.children])

for i in range(Q):
    p, x = [int(_) for _ in input().split()]
    nodes[p - 1].add(x)

print(*[n.v for n in nodes])

### FIXED CODE ###

import sys
from collections import deque

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

N, Q = [int(_) for _ in input().split()]

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

P = [0] * (N + 1)

for q in range(Q):
    p, x = [int(_) for _ in input().split()]
    P[p] += x

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

while que:
    v, parent = que.popleft()
    P[v] += P[parent]
    for next_v in edges[v]:
        if next_v == parent: continue
        que.append((next_v, v))

# def f(v, parent=0):
#     P[v] += P[parent]
#
#     for next_v in edges[v]:
#         if next_v == parent: continue
#         f(next_v, v)
#
#
# f(1)
print(*[P[i] for i in range(1, N + 1)])