Harryxun/stf_run huggingface dataset:
import numpy as np

n,m = [int(i) for i in input().split()]
a = np.array([0]*m)
b = np.array([0]*m)
ans = np.array([0]*m)
ans[m - 1] = n * (n - 1) / 2

for i in range(m):
	a[i],b[i] = [int(i) for i in input().split()]

class UnionFind:
    def __init__(self, n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはself.parの値をすべて-1にする
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def size(self, x):
        return -self.par[self.find(x)]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.size(x) < self.size(y):
            x , y = y , x
        self.par[x] += self.par[y]
        self.par[y] = x

uni = UnionFind(n)

for i in range(m-1,0,-1):
    ans[i-1] = ans[i]
    if uni.find(a[i]-1) != uni.find(b[i]-1):
        ans[i-1] -= uni.size(a[i]-1)*uni.size(b[i]-1)
    
        uni.union(a[i]-1,b[i]-1)

for i in ans:
    print(i)
    



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    
def main():
    N, M = [int(_) for _ in input().split()]
    bridge = [tuple(map(int, input().split())) for _ in range(M)]

    last = []
    last.append(int(N * (N-1) * 0.5))

    ins = UnionFind(N)
    last_temp = 0

    for i in range(M-1):
        #print(ins.par)
        if ins.same_check(bridge[M-1-i][0],bridge[M-1-i][1]):
            last.append(last[-1])
            #ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
        else:
            last_temp = last[-1] - (ins.size[ins.find(bridge[M-1-i][0])]) * (ins.size[ins.find(bridge[M-1-i][1])])
            #print(ins.size,i)
            last.append(last_temp)
            ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
    
    [print(last[M-i-1]) for i in range(M)]
    exit()
    
main()
import math
import scipy.special

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

def factorize(M):
    P = []
    F = []
    for m in range(2, int(math.sqrt(M))+1):
        n = 0
        while M % m == 0:
            M/= m
            n +=1
        if n != 0:
            P.append(m)
            F.append(n)
    if M != 1:
        P.append(M)
        F.append(1)
    return P,F

P, F = factorize(M)

X = 1
for f in F:
    X *= int(scipy.special.comb(N+f-1, f, exact=True))
    X %= int(pow(10,9)+7)

print(X)
    
     


### FIXED CODE ###

import math
from scipy.misc import comb

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

def factorize(M):
    P = []
    F = []
    for m in range(2, int(math.sqrt(M))+1):
        n = 0
        while M % m == 0:
            M/= m
            n +=1
        if n != 0:
            P.append(m)
            F.append(n)
    if M != 1:
        P.append(M)
        F.append(1)
    return P,F

P, F = factorize(M)

X = 1
for f in F:
    X *= int(comb(N+f-1, f, exact=True))
    X %= int(pow(10,9)+7)

print(X)
s=list(input())
s[3]=8
S="".join(s)
print(S)


### FIXED CODE ###

s=list(input())
s[3]="8"
S="".join(s)
print(S)
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,K = LI()
A = LI()
B = LI()
accumulate_A = list(itertools.accumulate(A))
accumulate_B = list(itertools.accumulate(B))
ans,j = 0,M-1
for i in range(N):
    if accumulate_A[i]>K:
        break
    while accumulate_A[i]+accumulate_B[j]>K:
        j -= 1
    ans = max(ans,i+j+2)
print(ans)


### FIXED CODE ###

import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,K = LI()
A = LI()
B = LI()
accumulate_A = [0]+list(itertools.accumulate(A))
accumulate_B = [0]+list(itertools.accumulate(B))
ans,j = 0,M
for i in range(N+1):
    if accumulate_A[i]>K:
        break
    while accumulate_A[i]+accumulate_B[j]>K:
        j -= 1
    ans = max(ans,i+j)
print(ans)
N=int(input())

for N in 10000:
  if 1000 % N == 0：
  print(0)
else:
  sen = 1000/N:
  atai = N-sen
  print(sen + atai )

### FIXED CODE ###

#! /usr/bin/python3

N = int(input())
1 <= N <= 10000

if N % 1000 == 0:
 print(0)
else:
  sen = N//1000
  sen2 = sen*1000
  atai = N-sen2
  atai2 = 1000-atai
  print(atai2)
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m, k = ns()
    a = na()
    b = na()

    a_idx = 0
    b_idx = 0
    ans = 0
    cnt = 0
    while True:
        if a_idx == n and b_idx == m:
            break

        if a_idx != n:
            if a[a_idx] < b[b_idx]:
                if ans + a[a_idx] > k:
                    break
                else:
                    ans += a[a_idx]
                    a_idx += 1
                    cnt += 1
            else:
                if ans + b[b_idx] > k:
                    break
                else:
                    ans += b[b_idx]
                    b_idx += 1
                    cnt += 1
        else:
            if ans + b[b_idx] > k:
                break
            else:
                ans += b[b_idx]
                b_idx += 1
                cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m, k = ns()
    a = na()
    b = na()

    perm_a = [0 for _ in range(n + 1)]
    perm_b = [0 for _ in range(m + 1)]

    for i, ai in enumerate(a):
        perm_a[i + 1] = perm_a[i] + ai

    for i, bi in enumerate(b):
        perm_b[i + 1] = perm_b[i] + bi

    perm_a.append(INF)
    perm_b.append(INF)

    ans = 0
    for i, pa in enumerate(perm_a):
        bserch = k - pa
        if bserch < 0:
            continue
        if bserch == 0:
            ans = max(ans, i)
            continue

        idx = bisect.bisect_left(perm_b, bserch)
        tmp_ans = i + idx - 1
        if perm_b[idx] == bserch:
            tmp_ans += 1
        ans = max(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()
a,b=map(int,input().split())
for i in range(1,a):
  if a<=(b*2+1)*i :
    break
print(i)
    

### FIXED CODE ###

a,b=map(int,input().split())

print((a-1) // (2*b+1)+1)
N, M = map(int, input().split())
parent = [-1] * N


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

for _ in range(M):
    a, b = map(int, input().split())
    union(a - 1, b - 1)


count = [0] * N
for i in range(N):
    count[find(i)] += 1
# res = 0
# for value in count.values():
#     res = max(res, value)
print(max(count))


### FIXED CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)


N, M = map(int, input().split())
parent = [-1] * N


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

for _ in range(M):
    a, b = map(int, input().split())
    union(a - 1, b - 1)


count = Counter(find(i) for i in range(N))
print(count.most_common(1)[0][1])
li = list(map(str, input()))
for i in len(li):
  if(not i == 0 and li[i] == "B"): 
    li[i-1] = ""
    li[i] = ""
print("".join(li))

### FIXED CODE ###

li = list(input())
ans = ""
for i in li:
  if i == "0":
    ans = ans + "0"
  elif i == "1":
    ans = ans + "1"
  elif i == "B":
    ans = ans[:len(ans)-1]
print(ans)
import math


"""再帰的な解(メモ化つき)"""
N = int(input())
h = list(map(int, input().split()))

dp = list([math.inf for i in range(N)])  # dpテーブル


def recursive(i):
    if dp[i] < math.inf:
        return dp[i]
    if i == 0:
        return 0

    if i > 0:
        res = math.inf
        res = min(res, recursive(i - 1) + abs(h[i] - h[i - 1]))
    if i > 1:
        res = min(res, recursive(i - 2) + abs(h[i] - h[i - 2]))
    dp[i] = res
    return res


print(recursive(N - 1))


### FIXED CODE ###

import math

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

dp = list([math.inf for i in range(N)])  # dpテーブル
dp[0] = 0
for i in range(N):
    a = dp[i]
    b = dp[i - 1] + abs(h[i] - h[i - 1])
    if a > b:
        dp[i] = b
    else:
        dp[i] = a
    a = dp[i]
    if i > 1:
        b2 = dp[i - 2] + abs(h[i] - h[i - 2])
        if a > b2:
            dp[i] = b2
        else:
            dp[i] = a

print(dp[N - 1])
ts = input()
h = ts/3600
ts-= h*3600
m = ts/60
ts -= m*60
text = str(h)+":"+str(m)+":"+str(ts)
print(text)


### FIXED CODE ###

ts = input()
ts = int(ts)
h = int(ts/3600)
ts-= h*3600
m = int(ts/60)
ts -= m*60
text = str(h)+":"+str(m)+":"+str(ts)
print(text)
s=input()
t=input()
ans=""
k=0
l=0
for i in range(len(s)):
    x=i+k
    y=0
    if x>=len(s):
        break
    if s[i+k]==t[0]:
        for j in range(len(t)):
            if (s[x+j]==t[j] or s[x+j]=="?")and x+j<len(s):
                y+=1
            else:
                break
        if y==len(t):
            ans+=t
            k+=len(t)-1
            l=1
        
    else:
        ans+=s[i+k]

ans=ans.replace("?","a")  
if l==1:
    print(ans)    
else:
    print("UNRESTORABLE")

### FIXED CODE ###

s=input()
t=input()

ls=len(s)
lt=len(t)

def f(a,b):
    r=""
    for i in range(lt):
        if a[i]==b[i] or a[i]=="?":
            r+=b[i]
        else:
            return False
    return True
        
ans=[]

for i in range(ls-lt+1):
    c=""
    if f(s[i:i+lt],t):
        c+=s[0:i]
        c+=t
        c+=s[i+lt:ls]
        c=c.replace("?","a")
        ans.append(c)

if ans==[]:
    print("UNRESTORABLE")
else:
    print(min(ans))
n,k = map(int,input().split())
s = input()
zero,one = [],[]
cnt = 0
if s[0] == "0":
    flag = True
else:
    flag = False
for i in range(n-1):
    if s[i] == "0" and flag == True:
        cnt +=1
        if s[i] == "0" and s[i+1] =="1":
            zero.append(cnt)
            flag = False
            cnt = 0
    elif s[i] == "1" and flag == False:
        cnt +=1
        if s[i+1] =="0":
            one.append(cnt)
            flag = True
            cnt = 0
    else:
        cnt +=1
        
    if i == n-2:
        if s[i+1] == "0":
            cnt +=1
            zero.append(cnt)
        elif s[i+1] == "1":
            cnt +=1
            one.append(cnt)
            
sum1 = sum(zero[:k]) + sum(one[:k+1])
ans = sum1
#print(sum1,ans,len(zero),zero,one)
if k >= len(zero):
    print(n)
    exit()
else:
    if s[0] == "1":
        for i in range(1,len(zero)-k):
            #print(sum1)
            sum1 -=(zero[i] + one[i])
            sum1 +=(zero[i+k] + one[i+k+1])
            ans = max(ans,sum1)
            #print(sum1,ans)
    elif s[0] =="0":
        print(sum1,ans)
        for i in range(1,len(zero)-k):
            sum1 -=(zero[i] + one[i])
            
            sum1 +=(zero[i+k] + one[i+k])
            ans = max(ans,sum1)
            
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
s = input()

L = []
from itertools import groupby
for key ,value in groupby(s):
    L.append((key,len(list(value))))
#print(L)
c = []
for i in range(len(L)):
    c.append(L[i][1])
c = [0] + c

for i in range(1,len(c)):
    c[i] +=c[i-1]
#print(c)
l = 0 
r = 2*k

ans = 0
while True:
    if L[l][0] == "1":
        if l + r +1 < len(L):
            ans = max(ans,c[l+r+1] - c[l])#add 5
        else:
            ans = max(ans,c[len(L)] - c[l])
    elif L[l][0] == "0":
        if l + r < len(L):
            ans = max(ans,c[l+r] - c[l])#add 4
        else:
            ans = max(ans,c[len(L)] - c[l])
    if l == len(L)-1:
        break
    l +=1
print(ans)
A, B = map(int, input().split())

print(max([A+B, A-B, A*B])

### FIXED CODE ###

A, B = map(int, input().split())

print(max([A+B, A-B, A*B]))
import sys
import math

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

cur = a[0]
for x in a[1:]:
    g = math.gcd(cur, x)
    if (cur // 2) % g != (x // 2) % g:
        print(0)
        sys.exit(0)
    else:
        cur = cur // g * x
    if cur > m * 2:
        print(0)
        sys.exit(0)

print((m + cur // 2) // cur)


### FIXED CODE ###

import sys

def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

cur = a[0]
for x in a[1:]:
    g = gcd(cur, x)
    if (cur // 2) % g != (x // 2) % g:
        print(0)
        sys.exit(0)
    else:
        cur = cur // g * x
    if cur > m * 2:
        print(0)
        sys.exit(0)

print((m + cur // 2) // cur)
from collections import deque

def bfs():
    global ans
    que = deque([])
    black = 0
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append((i, j))
               d[i][j] = 0
               black += 1
    if black == h*w:
        print(0)
        exit()
            
    white = True
    while white == True:
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for k in range(len(que)):
            i = 0
            while i < 4: 
                nx = que[k][0] + dx[i]
                ny = que[k][1] + dy[i]
                if 0 <= nx < w and 0 <= ny < h and A[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    d[nx][ny] = d[que[k][0]][que[k][1]] + 1
                    A[nx][ny] = "#"
                i += 1
        que = deque([])
        black = 0
        for i in range(h):
            for j in range(w):
              if A[i][j] == "#":
                  que.append((i, j))
                  black += 1
                  ans = max(ans, d[i][j])
        if black == h * w:
            white = False
      
        


h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
d = [[float("inf")] * w for _ in range(h)]
ans = 0
bfs()

print(ans)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

"""))
def main():

	a,b = map(int,input().split())

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

	if b == 0 or b == 1:
		print(combinations_count(a,2))
	else:
		print(combinations_count(a,2) + combinations_count(b,2))


if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	# s = int(input())
	# s = str(input())
	a,b = map(int,input().split())
	#1行R列
	# a = list(map(int,input().split()))
	#R行1列
	# l = [str(input()) for i in range(n)]
	#R行C列
	# qu = [list(map(str,input().split())) for x in range(q)]
	# print(' '.join(map(str,)))
	import math
	def combinations_count(n, r):
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

	if a <= 1 and b > 1:
		print(combinations_count(b,2))
	elif a <= 1 and b <= 1:
		print(0)
	elif a > 1 and b <= 1:
		print(combinations_count(a,2))
	else:
		print(combinations_count(a,2) + combinations_count(b,2))


if __name__ == '__main__':
	main()
import numpy as np
a,b=input().split()
c=a+b
d=np.sqrt(c)
if isinstance(d,int):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b=input().split()
c=int(a+b)
d=c**0.5
if float.is_integer(d):
  print('Yes')
else:
  print('No')
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return (ans/2)%(10**9+7)

### FIXED CODE ###

n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))
a,b,x = map(int,input().split())
h = x/(a*a)

import math

def f1(d,H,h):
    if h > H/2:
        return math.degrees(math.atan(d/(2*(H-h))))
    else:
        return math.degrees(math.atan((2*d*h)/(H*H)))

print(str.format('{0:.10f}', 90 - f1(a,b,h)))


### FIXED CODE ###

a,b,x = map(int,input().split())
h = x/(a*a)

import math

def f1(d,H,h):
    if h == H:
        return 90
    if h > H/2:
        return math.degrees(math.atan(d/(2*(H-h))))
    else:
        return math.degrees(math.atan((2*d*h)/(H*H)))

print(str.format('{0:.10f}', 90 - f1(a,b,h)))
x = int(input())
for i in range(1,10):
  for  j in range(1,10):
    f = 0
    if(i*j==x):
      	f = 1
      	print("Yes")
      	break
  if(f==1):
 	break
 

 if(f==0):
  print("No")

### FIXED CODE ###

x = int(input())
for i in range(1,10):
  for  j in range(1,10):
    f = 0
    if(i*j==x):
      	f = 1
      	print("Yes")
      	break
  if(f==1):
    break
  
if(f==0):
  print("No")
print(len(a=set(input()))-1)

### FIXED CODE ###

a = set(input().split())
print(len(a))
while True:
    n, x = map(int, raw_input().split())
    if n == 0 and x == 0:
        break

    a = 0
    for i in range(1, n):
        for j in range(i + 1, n):
            b = x - (i + j)
            if b > j and b <= n:
                a += 1
        print(a)

### FIXED CODE ###

while True:
	n, x = map(int, input().split())
	if n == 0 and x == 0:
		break

	ans = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			a = x - (i + j)
			if j < a <= n:
				ans += 1
	print(ans)
h,w,k=map(int,input().split())
G=[["."]*w for i in range(h)]
for i in range(h):
  G[i]=list(input())
ans=[[0]*w for i in range(h)]
GG=[[0] for i in range(h)]
for i in range(h):
  for j in range(w):
    if G[i][j]=="#":
      GG[i].append(j)
  GG[i].append(w)
B=[0]
a=1
for i in range(h):
  if len(GG[i])==2:
    continue
  B.append(i)
  ans[i][GG[i][0]:GG[i][2]]=[a]*(GG[i][2]-GG[i][0])
  a=a+1
  for j in range(len(GG[i])-3):
    ans[i][GG[i][j+2]:GG[i][j+3]]=[a]*(GG[i][j+3]-GG[i][j+2])
    a=a+1
B.append(h)
for i in range(B[2]-B[0]):
  ans[i]=ans[B[1]]
for i in range(B[2],h):
  if B[i]==0:
    ans[i]=ans[i-1]
for i in range(h):
  for j in range(w):
    print(ans[i][j],end=" ")
  print()

### FIXED CODE ###

h,w,k=map(int,input().split())
G=[["."]*w for i in range(h)]
for i in range(h):
  G[i]=list(input())
ans=[[0]*w for i in range(h)]
GG=[[0] for i in range(h)]
for i in range(h):
  for j in range(w):
    if G[i][j]=="#":
      GG[i].append(j)
  GG[i].append(w)
B=[0]
a=1
for i in range(h):
  if len(GG[i])==2:
    continue
  B.append(i)
  ans[i][GG[i][0]:GG[i][2]]=[a]*(GG[i][2]-GG[i][0])
  a=a+1
  for j in range(len(GG[i])-3):
    ans[i][GG[i][j+2]:GG[i][j+3]]=[a]*(GG[i][j+3]-GG[i][j+2])
    a=a+1
B.append(h)
for i in range(B[2]-B[0]):
  ans[i]=ans[B[1]]
for i in range(B[2],h):
  if i not in B:
    ans[i]=ans[i-1]
for i in range(h):
  for j in range(w):
    print(ans[i][j],end=" ")
  print()
#リストAの丸太を全てx以下にK回以内の切る回数で揃えることができるかを判断する関数。
def can_or_cannot(A,K,x):
    kaisuu_sum = 0
    for i in range(len(A)):
        if A[i]%x == 0:
            temp = (A[i]//x) - 1
            kaisuu_sum += temp
        else:
            temp = A[i]//x
            kaisuu_sum += temp

        if kaisuu_sum > K:
            return 'No'

    return 'Yes'

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    #二分探索するよ
    left = 0
    right = A[N-1]
    mid = 0
    while True:
        mid = (left + right)//2 
        #print(left,mid,right)
        judge = can_or_cannot(A,K,mid)
        #print(left,mid,right,judge)
        if judge == 'No':
            left = mid+1
        elif judge == 'Yes':
            right = mid

        if left == right:
            #print(left,mid,right)
            return right

print(main())


### FIXED CODE ###

#リストAの丸太を全てx以下にK回以内の切る回数で揃えることができるかを判断する関数。
def can_or_cannot(A,K,x):
    kaisuu_sum = 0
    for i in range(len(A)):
        if A[i]%x == 0:
            temp = (A[i]//x) - 1
            kaisuu_sum += temp
        else:
            temp = A[i]//x
            kaisuu_sum += temp

        if kaisuu_sum > K:
            return 'No'

    return 'Yes'

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    #二分探索するよ
    left = 0
    right = A[N-1]

    if right == 1:
        return 1

    mid = 0
    while True:
        if right == 1:
            return 1
            
        mid = int( (left + right)/2 )
        #print(left,mid,right)
        judge = can_or_cannot(A,K,mid)
        #print(left,mid,right,judge)
        if judge == 'No':
            left = mid+1
        elif judge == 'Yes':
            right = mid

        if left == right:
            #print(left,mid,right)
            return right

print(main())
s = int(input())
w = int(input())

if w >= s:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

s, w = map(int, input().split())

if w >= s:
    print('unsafe')
else:
    print('safe')
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val


def dfs(node_index, pairent_index):
    for child in linked_node_list[node_index]:
        
        if child != pairent_index:
            val_list[child] += val_list[node_index]
            dfs(child, node_index)

    return val_list


res = dfs(0, -1)

print(*res)

### FIXED CODE ###

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

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)