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

def solve():
    BASE = 10**9 + 7
    MOD = 2**61 - 1  # メルセンヌ素数
    ordA = ord('a')

    N = int(input())
    Ss = input().rstrip()

    As = [ord(S)-ordA for S in Ss]

    def genRollingHash_AllRight(As, lenInit, BASE, MOD):
        hashA = 0
        for A in As[:lenInit]:
            hashA = (hashA*BASE + A) % MOD
        yield hashA

        powB_L = pow(BASE, lenInit, MOD)
        for Aadd, Asub in zip(As[lenInit:], As[:len(As)-lenInit]):
            hashA = (hashA*BASE + Aadd - Asub*powB_L) % MOD
            yield hashA

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i, RH in enumerate(genRollingHash_AllRight(As, L, BASE, MOD)):
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                print(L)
                break
        else:
            continue
        break
    else:
        print(0)


solve()


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import math

K = int(input())

sum = 0
cache = {}
for a in range(1, K+1) :
    for b in range(1 , K+1) :
        for c in range(1 , K+1) :
            bc = str(b) + "-" + str(c)
            if bc in cache :
                sum = sum + math.gcd(a, cache[bc])
            else :
                cache[bc] = math.gcd(b, c)
                sum = sum + math.gcd(a, cache[bc])

print(sum)


### FIXED CODE ###

import math

K = int(input())

sum = 0
for a in range(1, K+1) :
    for b in range(1 , K+1) :
        tmp = math.gcd(a, b)
        for c in range(1 , K+1) :
            sum = sum + math.gcd(tmp, c)

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

class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300001,[0]*300001)
ans = 1
for i in range(N):
  A = int(input())
  l,r = max(0,A-K),min(A+K,300000)
  v = ST.prod(l,r+1)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

### FIXED CODE ###

class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300001,[0]*300001)
ans = 1
for i in range(N):
  A = int(input())
  l,r = max(0,A-K),min(A+K,300000)
  v = ST.prod(l,r+1)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)
### BUGGY CODE ###

import numpy as np
N,M=input().split(" ")
N=int(N)
M=int(M)
Alist=input().split(" ")
Alist = [float(A) for A in Alist]


for m in range(M):
    i=Alist.index(max(Alist))
    Alist[i]=Alist[i]/2
    if Alist[i]==0:
        break
    # print(Alist)


Alist_i = [int(A) for A in Alist]

print(sum(Alist_i))

### FIXED CODE ###

from heapq import heappush,heappop
N,M=input().split(" ")
N=int(N)
M=int(M)
Alist=input().split(" ")
# Alist = [-float(A) for A in Alist]
hAqueue=[]
for A in Alist:
    heappush(hAqueue,-float(A))

for m in range(M):
    tmp=heappop(hAqueue)
    heappush(hAqueue,tmp/2)
Alist = [-int(A) for A in hAqueue]
print(sum(Alist))
### BUGGY CODE ###

import heapq

n,m  = map(int,input().split())
a = list(map(int, input().split()))
bcs = []
for _ in range(m):
    bcs.append(list(map(int, input().split())))

heapq.heapify(a)
bcs.sort(key=lambda x: x[1])

for bc in bcs:
    b = bc[0]
    c = bc[1]
    while b > 0:
        ta = heapq.heappop(a)
        if ta < c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,ta)
            break
        b -= 1

print(sum(a))

### FIXED CODE ###

import heapq

n,m  = map(int,input().split())
a = list(map(int, input().split()))
bcs = []
for _ in range(m):
    bcs.append(list(map(int, input().split())))

heapq.heapify(a)
bcs.sort(key=lambda x: x[1],reverse=True)

for bc in bcs:
    b = bc[0]
    c = bc[1]
    while b > 0:
        ta = heapq.heappop(a)
        if ta < c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,ta)
            break
        b -= 1

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

K=int(input())

if K%2==0:
    print(-1)
    exit()

loop=10**6

for i in range(1, loop):
    a_n=(10**i -1)//9
    a_n*=7

    if a_n%K==0:
        print(i)
        exit()

### FIXED CODE ###

k=int(input())
cnt=1
mod=7

for i in range(k):
    if mod%k==0:
        break
    
    cnt+=1
    mod=(mod*10 + 7)%k

if mod%k==0:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

from collections import defaultdict
S = [int(x) for x in input()]
N = len(S)
l = 1
ans = 0
dic = defaultdict(int)
dic[0] = 1
m = 0
for x in S[::-1]:
    m = (x * l + m) % 2019
    ans += dic[m]
    l *= 10
    dic[m] += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
S = [int(x) for x in input()]
N = len(S)
l = 1
ans = 0
dic = defaultdict(int)
dic[0] = 1
m = 0
for x in S[::-1]:
    m = (x * l + m) % 2019
    ans += dic[m]
    l = l * 10 % 2019
    dic[m] += 1
print(ans)
### BUGGY CODE ###

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

result=1

if 0 in A:
    result=0
else:
    for i in A:
        result = result*i
if result > 10**18:
    result=-1
print(result)


### FIXED CODE ###

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

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

    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(i == j):
                continue
            if(P[i] == max(P)):
                flag = False
                break
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

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

    #result = list()

    minimum = P[0]
    count = 1
    for i in range(N):
        if(minimum > P[i]):
            minimum = P[i]
            count += 1
    print(count)
#        Pj = list(P[j] for j in range(i+1))
        #print(Pj)
        #Pj = P[0:i+1]
#        min_P = min(Pj)
#        result.append(min_P)
#        print(min_P)
#        if(P[i] == min_P):
#            count += 1

    '''
    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)
    '''

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

import numpy as np
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h = np.array(sorted(h))
diff = np.diff(h)
low_score = np.inf
for i in range(n - k + 1):
    mask = np.arange(i, i + k - 1)
    cost = diff[mask].sum()
    low_score = min(low_score, cost)
print(low_score)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(sorted([int(input()) for _ in range(n)]))
h_roll = np.roll(h, -k + 1)
x = h_roll - h
print(int(x[:-k + 1].min()))
### BUGGY CODE ###

import sys

while 1:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    sums = []

    for i in range(len(a)+1):
        for j in range(i, len(a)+1):
            sums.append(sum(a[i:j]))

    print(max(sums))

### FIXED CODE ###

while 1:
    n = int(input())
    if n == 0:
        break
    a = []
    for _ in range(n):
        a.append(int(input()))

    dp = []
    dp.append(a[0])
    for i in range(1,len(a)):
        dp.append(max(dp[i-1] + a[i], a[i]))

    print(max(dp))
### BUGGY CODE ###

import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    b = set(A)
    def find(x):
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    return 0
            else:
                if j in b:
                    return 0
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())


### FIXED CODE ###

#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(A)
    a = Counter(A)
    l = [0] * (10**6+1)
    v = [0] * (10**6+1)
    for i in B:
        if v[i] == 1 or l[i] == 1:
            continue
        else:
            v[i] = 1
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
dic={}
for i in range(n):
    tmp=input()
    if tmp not in dic.keys():
        dic[tmp]=1
print(len(dic))
### BUGGY CODE ###

a1 = int(input())
b2 = input().split(" ")

def check(a , b):
  score = 1
  now = 10 ** 18
  if '0' in b:
    return print(0)
  else:
    for i in range(a):
      score *= int(b[i])
    if score > 10 ** 18:
      return print(-1)
    else:
      return print(score)

check(a1 , b2)

### FIXED CODE ###

a1 = int(input())
b2 = input().split(" ")

def check(a , b):
  score = 1
  if '0' in b:
    return 0
  else:
    for i in range(a):
      score *= int(b[i])
      if score > 10 ** 18:
        return -1
    
    return score

print(check(a1 , b2))
### BUGGY CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    tmp = list(input())
    tmp.sort()
    tmp = "".join(tmp)
    S.append(tmp)
L = set(S)
L = list(L)
L_cnt = [0 for i in range(len(L))]
for i in S:
    L_cnt[L.index(i)]+=1
for i in range(len(L)):
    ans+=((L_cnt[i])*(L_cnt[i]-1))//2
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    tmp = list(input())
    tmp.sort()
    tmp = "".join(tmp)
    S.append(tmp)

S.sort()

cnt = 0
ans = 0

for i in range(N):
    if i == 0 or S[i] == S[i-1]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
ans += cnt*(cnt-1)//2
    
print(ans)
### BUGGY CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = 0
for s in lis:
    flag = 0
    for i in range(N-2):
        if flag:break
        if S[i] == s[0]:
            if s[1] in set(S[i+1:]):
                a = S[i+1:].index(s[1])
                if s[2] in set(S[i+a+2:]):
                    ans += 1
                    flag = 1
                    break
print(ans)

### FIXED CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = 0
from collections import defaultdict
d = defaultdict(list)
for i,s in enumerate(S):
    d[s].append(i)

for s in lis:
    if d[s[0]]:
        i = min(d[s[0]])
        if d[s[1]]:
            for j in d[s[1]]:
                if j > i:
                    if d[s[2]]:
                        if max(d[s[2]]) > j:
                            ans += 1
                            break
                    break
        else:continue
    else:continue
                            
print(ans)
### BUGGY CODE ###

from collections import deque
N,X,Y = map(int,input().split())
G = [[] for i in range(N+1)] 
for i in range(1,N+1):
  if i-1 >= 1:
    G[i].append(i-1)
  if i+1 <= N:
    G[i].append(i+1)

G[X].append(Y)
G[Y].append(X)

dl = [0]*(N+1)
def bfs(p):
  seen = [False]*(N+1)
  seen[p] = True
  dist = [0]*(N+1)
  d = deque([p])
  while len(d) > 0:
    v = d.popleft()
    for i in G[v]:
      if seen[i] == False:
        seen[i] = True
        dist[i] = dist[v]+1
        dl[dist[i]] += 1
        d.append(i)      


for i in range(1,N+1):
  bfs(i)

for i in range(1,N):
  print(dl[i]//2)

### FIXED CODE ###

import collections
from collections import deque

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

#辺のリスト
n = N
l_hen = [[i,i+1] for i in range(1,n)]+[[X,Y]]

#頂点のラベルリスト
l_chouten =list( set(sum(l_hen, [])) )

#G={頂点:[頂点に繋がっている点たち],... } を取得する
G = dict( [ (key,[]) for key in l_chouten]  )
for i in range(n):
   G[l_hen[i][0]].append(l_hen[i][1])

#無効グラフの場合両方から見ているので以下のコードも実行する
for i in range(n):
   G[l_hen[i][1]].append(l_hen[i][0])

'''
以上グラフの準備
'''
#seenとtodoの初期設定
l_seen = {i:False for i in l_chouten}
l_todo = []
dist = {i:-1 for i in l_chouten}
#距離の羅列用  
l_d =deque([])  

for point in range(1,N+1):
  #seenとtodoの初期設定
  for key in l_seen:
    l_seen[key] = 0
  l_todo = []  
  for key in dist:
    dist[key] = 0

  #seenに出発地点pを決めてやる、出発点の隣接リストもtodoに入れる
  p = point
  l_seen[p] = True #pはチェック済み
  for i in G[p]:
    l_seen[i] = True #pに隣接する頂点もチェック済み
  l_todo = l_todo + G[p] #pに隣接する頂点をtodoリストに追加
  l_todo = deque(l_todo)
  dist[p] = 0
  for i in G[p]:
    dist[i] = 1 #pに隣接する頂点とpとの距離を1とする
    l_d.append(dist[i])
  

  #探索
  while len(l_todo) != 0:
    #幅優先探索
    v = l_todo.popleft() #todoの左端つまりindex0から処理しているので
    for i in G[v]:
      #回り込まれて先越された時
      if l_seen[i] == True:
        continue
      else:
        l_seen[i] = True
        l_todo.append(i)
        dist[i]=dist[v]+1
        l_d.append(dist[i])
###
c = collections.Counter(l_d)
for i in range(1,N):
  print(c[i]//2)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((ny,nx))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((ny,nx))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())
### BUGGY CODE ###

h, w, n = map(int, input().split())

ans = [0]*10

a = []

if n != 0:
    for i in range(n):
        s = input()
        a.append(s)


for i in range(1,h-1):
    for j in range(1,w-1):
        s = 0
        for p in range(3):
            for q in range(3):
                st = str(i+p) + " " + str(j+q)
                if st in a:
                    s += 1
        if s == 0:
            ans[0] += 1
        else:
            ans[s] += 1

for i in range(10):
    print(ans[i])

### FIXED CODE ###

f=lambda:map(int,input().split())
h,w,n = f()

d={}
while n:
 n-=1
 x,y=f()
 for i in range(9):
     a=(x+i%3,y+i//3)
     d[a]=d.get(a,0)+(h>=a[0]>2<a[1]<=w)

c=[list(d.values()).count(i+1)for i in range(9)]

print((h-2)*(w-2)-sum(c))
for i in range(9):
    print(c[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for i, a in enumerate(A):
    ans += l // a
print(ans%MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for i, a in enumerate(A):
    ans += l // a
print(ans%MOD)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
accepted = np.array([0] * N, dtype=np.int32)
penalties = np.array([0] * N, dtype=np.int32)
for _ in range(M):
    p, ac = [func(c) for func, c in zip([lambda n: int(n) - 1, lambda s: s == "AC"], input().split())]
    accepted[p] |= ac
    penalties[p] += not accepted[p]
print(sum(accepted), accepted.dot(penalties))


### FIXED CODE ###

N, M = map(int, input().split())
accepted = [0] * N
penalties = [0] * N
for _ in range(M):
    p, ac = input().split()
    p, ac = int(p) - 1, ac == "AC"
    accepted[p] |= ac
    penalties[p] += not accepted[p]
print(sum(accepted), sum(p for ac, p in zip(accepted, penalties) if ac))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=set(A)
ans=0
for i in B:
  counts=A.count(i)
  ans+=(counts)*(counts-1)/2
for k in A:
  counts2=A.count(k)
  print(int(ans-counts2+1))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in A:
  if i not in dic.keys():
    dic.update({i:1})
  else:
    dic[i]+=1
ans=sum([int(j*(j-1)/2) for j in dic.values()])
for k in A:
  num=dic[k]
  if num>=1:
    print(int(ans-num+1))
  else:
    print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
from collections import Counter
n,m = map(int,input().split())

l = np.array([[0]*n for _ in range(n)])

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

x,labels= connected_components(l)
c = Counter(list(labels))
print(c.most_common()[0][1])

### FIXED CODE ###

from collections import defaultdict,deque
n,m = map(int,input().split())

d = defaultdict(list)

if m==0:
    print(1)
    exit()

visited = [-1] + [False]*n
for i in range(m):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
maxi = 1
for i in range(1,n+1):
    if visited[i]:
        continue
    cnt = 0
    que = deque([i])
    while que:
        v = que.pop()
        if not visited[v]:
            visited[v] = True
            cnt += 1
        for j in d[v]:
            if not visited[j]:
                que.append(j)
    maxi = max(maxi,cnt)
print(maxi)
### BUGGY CODE ###

I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(int,input().split()))
for i in range(M):
    num = A.index(max(A))
    A[num] = A[num] / 2
ans = 0
A = list(map(int,A))
ans = sum(A)
print(ans)

### FIXED CODE ###

import heapq
import math
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(lambda x:-x,map(int,input().split())))
heapq.heapify(A)
for i in range(M):
    num = heapq.heappop(A)
    num = math.ceil(num / 2)
    heapq.heappush(A,num)

print(-sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


class Node:
    def __init__(self, index):
        self.index = index
        self.leaf = {}
        self.score = 0

    def set_parent(self, parent):
        self.leaf.pop(parent)
        for l in self.leaf.values():
            l.set_parent(self.index)

    def add_score(self, score):
        self.score += score
        for l in self.leaf.values():
            l.add_score(score)


N, Q = map(int, input().split())
tree = {i: Node(i) for i in range(1, N + 1)}
tree[1].leaf[1] = tree[1]

for i in range(N-1):
    n1, n2 = map(int, input().split())
    tree[n1].leaf[n2] = tree[n2]
    tree[n2].leaf[n1] = tree[n1]

tree[1].set_parent(1)
for _ in range(Q):
    p, x = map(int, input().split())
    tree[p].add_score(x)
# [tree[p].add_score(x) for p, x in map(int, input().split())]

print(' '.join([str(t.score) for t in tree.values()]))


### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = [0 for i in range(N)]
que = [(1, 0, -1)]
while len(que) > 0:
    tmp = []
    for v, x, par in que:
        x += c[v]
        ans[v - 1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w, x, v))
    que = tmp

print(*ans)