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

import copy

N = int(input())

A = [int(input()) for _ in range(N)]

B = copy.copy(A)

for i in range(len(A)):
    A[i] = 0
    print(max(A))
    A[i] = B[i]


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    max1st = max(A)
    max1stIndex = A.index(max1st)

    for i in range(len(A)):
        if i == max1stIndex:
            tmp = A[i]
            A[i] = 0
            print(max(A))
            continue

        print(max1st)




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

N = int(input())
ls = list(map(int, input().split()))
m = 1000000007
ans = 0
for i in range(0, N):
    for j in range(i+1, N):
        ans += (ls[i]*ls[j])
print(ans%m)

### FIXED CODE ###

N = int(input())
ls = list(map(int, input().split()))
m = 1000000007
sumNum = sum(ls)
currentSum, lastAns = 0, 0
for i in range(N -1):
    currentSum += ls[i]
    lastAns = (lastAns + (ls[i] * (sumNum - currentSum))) % m
print(lastAns)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
A = []
for i in range(N):
    j = Y.index(X[i])
    A.append((Y[:j] + Y[j+1:])[(N-1)//2])
print('\n'.join(map(str, A)))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
l, r = Y[N//2-1], Y[N//2]
A = []
for i in range(N):
    if X[i] <= l:
        A.append(r)
    else:
        A.append(l)
print('\n'.join(map(str, A)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#S = list(input())
	#L,R = map(int, input().split(" "))
	#L = list(map(int, input().split(" ")))

	A = input().split()
	A = [int(s) for s in A]

	ans = [0 for _ in range(N)]
	
	ed = min(A[0]*2, A[-1]*2)
	s = 0
	if ed > 1000000 * 2:
		s = 100000
	for i in range(s, ed+1, 2):
		fin = True
		for j in range(N):
			if j == 0:
				ans[j] = i
				continue
			tmp = (A[j-1] - (ans[j-1] / 2))*2

			if tmp < 0 or tmp % 2 == 1:
				fin = False
				break
			else :
				ans[j] = int(tmp)
		
		if fin == False:
			pass
		else:
			if (ans[-1] / 2) + (ans[0] / 2) == A[-1]:
				#print("sss")
				break

	ans = [str(a) for a in ans]
	print(' '.join(ans))


if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	A = input().split(" ")
	A = [int(s) for s in A]
	
	tmp = 0
	for i, val in enumerate(A):
		if i == 0:
			tmp += 2*val
			continue
		if i % 2 == 1:
			tmp -= 2*val
		else:
			tmp += 2*val
	
	x = tmp / 2
	
	ans = []
	ans.append(int(x))
	for i, val in enumerate(A):
		tmp = (val - (ans[i]/2)) * 2
		ans.append(int(tmp))
	
	ans = ans[:-1]
	ans = [str(s) for s in ans]
	print(" ".join(ans))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

N=int(input())
l=list()
for n in range(N):
  A=int(input())
  l.append(A)
  ll=sorted(l,reverse=True)
  
for n in range(N):
  if l[n]==max(l):
    print(ll[1])
  else:
    print(max(l))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A)
a=max(A)
b=ll[-2]
  
for n in A:
  if n==a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
depth = [[1]]
i = 0
co = 1
se = set(depth[0])
while co < n:
    te = [k for j in depth[i] for k in c[j]]
    te = set(te) - se
    if len(te) == 0:
        break
    co += len(te)
    se = te | se
    depth.append(list(te))
    i += 1

    
if co != n:
    print("No")
else:
    print("Yes")
    for i in range(1, len(depth)):
        te = depth[i-1]
        for j in depth[i]:
            t = c[j]
            for k in te:
                if k in t:
                    lis[j] = k
                    break
    print("\n".join(map(str, lis[2:])))

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    for i in lis[2:]:
        print(i)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
from copy import deepcopy
def main():
    n, *a = map(int, read().split())
    if n == 1:
        print(1)
        sys.exit()
    if n == 2:
        if a[0] == a[1]:
            print(0)
            sys.exit()
        elif max(a) % min(a) == 0:
            print(0)
            sys.exit()
        else:
            print(2)
            sys.exit()
    a.sort()
    notdiv = [True] * n
    for i1, ae in enumerate(a):
        if notdiv[i1]:
            for i2 in range(i1+1, n):
                notdiv[i2] = notdiv[i2] and a[i2] % ae != 0
    if a[0] == a[1]:
        notdiv[0] = False
    if a[-1] == a[-2]:
        notdiv[-1] = False
    for j1 in range(1, n - 1):
        if a[j1-1] == a[j1] or a[j1] == a[j1+1]:
            notdiv[j1] = False
    r = sum(notdiv)
    print(r)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    a.sort()
    tf = [0] * (a[-1] + 1)
    for ea in a:
        tf[ea] = 1
    for i1 in range(n - 1):
        if a[i1] == a[i1 + 1]:
            tf[a[i1]] = 0

        for i2 in range(2, a[-1]//a[i1] + 1):
            tf[a[i1] * i2] = 0
    r = sum(tf)
    print(r)


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

import numpy as np
from scipy.signal import convolve

n, k = map(int, input().split())
P = np.array(input().split(), dtype=int)
template = np.ones(k)

a = convolve(P, template, mode="valid")

print((max(a) + k) / 2)

### FIXED CODE ###

import numpy as np
from scipy.signal import fftconvolve

n, k = map(int, input().split())
P = np.array(input().split(), dtype=int)
template = np.ones(k)

a = fftconvolve(P, template, mode="valid")

print((max(a) + k) / 2)
### BUGGY CODE ###

n,m = map(int, input().split())
p = [0] * m
s = [0] * m
for i in range(m):
    p[i], s[i] = input().split()
for i in range(m):
    p[i]=int(p[i])
AC=[]
AC1=[]
WA=0
for i in range(m):
    if s[i]=="AC" and p[i] not in AC:
        AC.append(p[i])
        AC1.append(i)
for i in range(m):
    if s[i]=="WA" and p[i] in AC:
        if AC1[AC.index(p[i])]>i:
            WA=WA+1
print(len(AC),WA)


### FIXED CODE ###

n,m = map(int, input().split())
p = [0]*m 

for i in range(m):
    p[i] = input().split()
AC=[[0,-1] for j in range(n)]
k=0
WA=0
for i in range(m):
    if p[i][1]=="AC" and AC[int(p[i][0])-1][0]==0 :
        AC[int(p[i][0])-1][0]=1
        AC[int(p[i][0])-1][1]=i
        k=k+1
for i in range(m):
    if p[i][1]=="WA" and AC[int(p[i][0])-1][0]==1 and AC[int(p[i][0])-1][1]>i:
        WA=WA+1

print(k,WA)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
flag=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if flag[n1][n2][n3]:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0
    flag[n1][n2][n3]=1
    ret=1/(1-(n-n1-n2-n3)/n)
    if n1>0:
        ret+=f(n1-1,n2,n3)*(n1/n)/(1-(n-n1-n2-n3)/n)
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*(n2/n)/(1-(n-n1-n2-n3)/n)
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*(n3/n)/(1-(n-n1-n2-n3)/n)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

import math
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N = I()

ans = 1
for i in range(N):
    ans *= (i+1)

ans %= MOD
print(ans)

### FIXED CODE ###

import math
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N = I()

ans = 1
for i in range(N):
    ans *= (i+1)
    ans %= MOD

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

n, k = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int ,input().split())

#愚直な実装だけどいけるかなって感じ
lis = []

for i in range(n):
    for j in range(b[i]):
        lis.append(a[i])

lis.sort()
print(lis[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int ,input().split())


judge = 0
dic = {}


for i in range(n):
    if a[i] in dic:
        dic[a[i]] += b[i]
    else:
        dic[a[i]] = b[i]
#print(dic)
dic = list(dic.items())
dic.sort()
#print(dic)


for i in range(10**9):
    if judge >= k:
        print(dic[i-1][0])
        break
    else:
        judge += int(dic[i][1])
    #print(judge)
### BUGGY CODE ###

import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    x,y = IL()
    bit = 2**x
    for i in range(bit):
        tmp = 0
        for j in range(x):
            if (i>>j)&1:
                tmp += 2
            else:
                tmp += 4
            if y<tmp:
                continue
        if tmp == y:
            print('Yes')
            exit()
    print('No')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    x,y = IL()
    if 4*x<y or y%2!=0:
        print('No')
        exit()
    for i in range(x+1):
        if 4*i+2*(x-i)==y:
            print('Yes')
            exit()
    print('No')
    return

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

s = list(input())
n = len(s)
a_count = 0
ans = 0
i = 0
while i < n-2:
    if s[i:i+3] == ['A','B','C']:
        ans +=  1
        s[i:i+3] = ['B','C','A']
        i -= 2
    i += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s = list(s.replace('BC','D'))
a_count = 0
ans = 0
i = 0
while i < len(s) - 1 :
    if s[i:i+2] == ['A','D']:
        ans += a_count + 1
        s[i+1] = 'A'
        s[i] = 'D'
    else:
        if s[i] == 'A':
            a_count += 1
        else:
            a_count = 0
    i += 1
print(ans)
### BUGGY CODE ###

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

cnt = [x * 0.5 + 0.5 for x in p]
ans = [sum(cnt[x:y]) for x, y in zip(range(0, N-K+1), range(K, N+1))]

print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

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

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
for h,n in itertools.product(range(1,3501),range(1,3501)):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""

### FIXED CODE ###

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
if(N>2000):st=-1
else:st=1
for h,n in itertools.product(range(1,3501)[::st],range(1,3501)[::st]):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""
### BUGGY CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


A = np.array(A)
pos = np.arange(N + 1)
pos[0] = -1
pos[A] = np.arange(N + 1)

ans = 0
lefts = np.arange(N)
rights = np.arange(N)
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        # 右とつながった
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        # 左とつながった
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (abs(left - p) + 1) * (abs(right - p) + 1) * i
print(ans)


### FIXED CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


pos = list(range(N + 1))
pos[0] = -1
for i, a in enumerate(A):
    pos[a] = i

ans = 0
lefts = list(range(N + 1))
rights = list(range(N + 1))
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        # 右とつながった
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        # 左とつながった
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (abs(left - p) + 1) * (abs(right - p) + 1) * i
print(ans)
### BUGGY CODE ###

N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
        else:
            ans=0
        if l-1>=nextK:
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        return ans
ans=solve(N,K)
print(ans)

### FIXED CODE ###

N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        else:
            return 0
ans=solve(N,K)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(k):
    c = [0]*n
    for i,j in enumerate(A):
        for k in range(i-j,i+j+1):
            if 0 <= k <= n-1:
                c[k] += 1
    if A == c:
        break
    A = c
print(" ".join(map(str,A)))

### FIXED CODE ###

from itertools import accumulate
n,k = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(min(k,50)):
    c = [0]*n
    for i,j in enumerate(A):
        l = max(0,i-j)
        r = min(n-1,i+j)
        c[l] += 1
        if r+1 < n:
            c[r+1] -= 1
    A = list(accumulate(c))
print(" ".join(map(str,A)))
### BUGGY CODE ###

N = int(input())

N_list = [i+1 for i in range(N)]


sum = 0

for i in range(0, len(N_list), 1):
    sum = sum + i

print(sum)

### FIXED CODE ###

N = int(input())

print((N*(N-1))//2)
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)


def ok(x):
    need = 0
    for i in range(N):
        need += max(0, A[i] - x // F[i])
    if need <= K:
        return True
    return False


left = -1
right = 10 ** 12 + 1

while right - left > 1:
    mid = (right + left) // 2
    if ok(mid):
        right = mid
    else:
        left = mid

print(right)

### FIXED CODE ###

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)


def ok(x):
    need = 0
    for i in range(N):
        need += max(0, A[i] - x // F[i])
    if need <= K:
        return True
    return False


left = -1
right = 10 ** 12 + 1

while right - left > 1:
    mid = (right + left) // 2
    if ok(mid):
        right = mid
    else:
        left = mid

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

#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

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


color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n

color_max = 1

d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))

    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])
    # print("clr:", color_list_rest)

    for i in index_list:
        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num

    for i in index_list:
        if check_list[i] == 0:
            check_list[i] = 1
            d.append(i)

print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])


### FIXED CODE ###

#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

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


color_list = {}
check_list = [0]*n

color_max = max(map(len, connect_list))

vertex = [0 for i in range(n)]
d = deque([0])

while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]

    for i in index_list:
        if check_list[i] == 1:
            continue

        check_list[i] = 1
        d.append(i)
        num = vertex[index] % color_max+1
        color_list[(min(index, i), max(index, i))] = num
        vertex[index], vertex[i] = num, num


print(color_max)
for a, b in ab:
    print(color_list[(a-1, b-1)])