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

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

N, Q = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append(B)
    adjL[B].append(A)

anss = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p = p-1
    anss[p] += x

useds = [False] * N
def dfs(vNow, x):
    useds[vNow] = True
    anss[vNow] += x
    for v2 in adjL[vNow]:
        if not useds[v2]:
            dfs(v2, anss[vNow])

dfs(0, 0)

print(' '.join(map(str, anss)))


### FIXED CODE ###

def solve():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

    anss = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p = p-1
        anss[p] += x

    useds = [False] * N
    def dfs(vNow, x):
        useds[vNow] = True
        anss[vNow] += x
        ans = anss[vNow]
        for v2 in adjL[vNow]:
            if not useds[v2]:
                dfs(v2, ans)

    dfs(0, 0)

    print(' '.join(map(str, anss)))

solve()
### BUGGY CODE ###

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

Q = int(input())
for i in range(Q):
    l = input().split()
    if l[0] == "1":
        S = S[::-1]
    else:
        if l[1] == "1":
            S = l[2] + S
        else:
            S += l[2]
print(S)

### FIXED CODE ###

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

Q = int(input())
query = [list(input().split()) for _ in range(Q)]
direction = 1
S_front = ""
S_back = ""
for l in query:
    if l[0] == "1":
        direction *= -1
    else:
        if (l[1] == "1" and direction == 1) or (l[1] == "2" and direction == -1):
            S_front += l[2]
        else:
            S_back += l[2]

if direction == 1:
    print(S_front[::-1] + S + S_back)
else:
    print(S_back[::-1] + S[::-1] + S_front)
### BUGGY CODE ###

N=int(input())
hlist=list(map(int,input().split()))
hantei="Yes"
for i in range(1,N):
  if hantei=="No":
    break
  for j in range(i):
    if hlist[j]>=hlist[i]+2:
      hantei="No"
      break
      
print(hantei)

### FIXED CODE ###

N=int(input())
hlist=list(map(int,input().split()))
hantei="Yes"
kabe=0
for i in range(1,N):
  if hantei=="No":
    break
  kabe=max(kabe,hlist[i])
  if kabe>=hlist[i]+2:
    hantei="No"
print(hantei)
### BUGGY CODE ###

s = str(input())
q = int(input())
query = [0 for _ in range(q)]
w = True
for i in range(q):
    query[i] = list(map(str,input().split()))
for i in range(q):
    if(query[i][0] == "1"):
        w = not(w)
    else:
        mem = query[i][2]
        if(query[i][1] == "1"):
            if(w):
                s = mem + s
            else:
                s = s + mem
        else:
            if(w):
                s = s + mem
            else:
                s = mem + s
if(w):
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = str(input())
q = int(input())
s = deque(s)
query = []
w = True
for i in range(q):
    query = list(map(str,input().split()))
    if(query[0] == "1"):
        w = not(w)
    else:
        mem = query[2]
        if(query[1] == "1"):
            if(w):
                s.appendleft(mem)
            else:
                s.append(mem)
        else:
            if(w):
                s.append(mem)
            else:
                s.appendleft(mem)
if(w):
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A = {i: int(height) for i, height in enumerate(input().split(), 1)}

res = 0
for a1_id, a2_id in combinations(A.keys(), 2):
    a1_h = A[a1_id]
    a2_h = A[a2_id]
    if abs(a1_id - a2_id) == (a1_h + a2_h):
        res += 1

print(res)


### FIXED CODE ###

from collections import Counter

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

m = Counter(i - elem for i, elem in enumerate(A))
res = 0
for i, elem in enumerate(A):
    res += m[i + elem]

print(res)
### BUGGY CODE ###

a = int(input())
ar = []
for i in range(a):
    l = list(map(int,input().split(" ")))
    ar.insert(0,l)
count = 0
for r in ar:
    x = r[0] + count
    y = r[1]
    while True:
        if x % y == 0:
            break
        x += 1
        count += 1
print(count)# 

### FIXED CODE ###

a = int(input())
ar = []
for i in range(a):
    l = list(map(int,input().split(" ")))
    ar.append(l)
ar.reverse()
count = 0
for r in ar:
    x = r[0] + count
    y = r[1]
    m = x % y
    if m != 0:
        count += y - m
print(count)
### BUGGY CODE ###

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

for i in range(n-1):
  if a[n-1-i]%2 == 1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

n,m=map(int,input().split())
e=[]
for i in range(m):
    e.append(list(map(int,input().split())))
ans=0
for i in range(m):
    nall=[]
    for j in range(m):
        if i==j:
            continue
        nall.append(e[j])
    visited=[0]*n
    visited[0]=1
    t=[1]
    while len(t)>0:
        tmp=[]
        ntmp=[]
        for p in t:
            visited[p-1]=1
            for q in nall:
                if q[0]==p:
                    if visited[q[1]-1]==0:
                        tmp.append(q[1])
                        visited[q[1]-1]=1
                elif q[1]==p:
                    if visited[q[0]-1]==0:
                        tmp.append(q[0])
                        visited[q[0]-1]=1
                else:
                    if visited[q[0]-1]==0 or visited[q[1]-1]==0:
                        ntmp.append(q)
        t=tmp
        nall=ntmp
    if sum(visited)!=n:
        ans+=1
print(ans)
                    


### FIXED CODE ###

n,m=map(int,input().split())
e=[]
for i in range(m):
    e.append(list(map(int,input().split())))
ans=0
for i in range(m):
    g=[[] for _ in range(n)]
    for j in range(m):
        if i==j:
            continue
        g[e[j][0]-1].append(e[j][1])
        g[e[j][1]-1].append(e[j][0])
    visited=[0]*n
    visited[0]=1
    q=[1]
    while len(q)>0:
        a=q.pop(0)
        visited[a-1]=1
        for k in g[a-1]:
            if visited[k-1]==0:
                q+=[k]
    if sum(visited)!=n:
        ans+=1
print(ans)
### BUGGY CODE ###

# D
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)
    
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][W])

### FIXED CODE ###

# D
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)
    
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][W])
### BUGGY CODE ###

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

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
# from collections import deque
import queue


stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# H, W = map(int, input().split())
data = [ns() for _ in range(H)]

# data = [None] * H
# for i in range(H):
#     data[i] = input()


def judge(h, w, dist):
    if (h < 0) or (h >= H) or (w < 0) or (w >= W):
        return False
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if judge(h_new, w_new, dist):
                q.put((h_new, w_new, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)


### FIXED CODE ###

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

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def bfs(h, w):
    dist = [[-1] * (W+2) for _ in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    # while len(q) > 0:
    while len(q) > 0:
        h, w, val = q.popleft()

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))
                dist[h_new][w_new] = val + 1
                max_dist = max(max_dist, val + 1)

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

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

N, M = map(int, input().split())
A = list(map(float, input().split()))
for i in range(M):
    A = sorted(A)
    A[-1] /= 2
yen = 0
for i in range(N):
    yen += int(A[i])

print(yen)

### FIXED CODE ###

import sys
import math
from collections import deque
import heapq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M = NMI()
    A = NLI()
    A = [-a for a in A]
    heapq.heapify(A)
    for i in range(M):
        a_max = -heapq.heappop(A)
        a_max = a_max // 2
        heapq.heappush(A, -a_max)
    print(-sum(A))



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

d={"o":1,"x":-1}
N=int(raw_input())
s=raw_input()
s+=s[0]
def ans(a):
    for i in range(1,N+1):
        a=a+[a[i]*a[i-1]*d[s[i]]]
    if a[:2]==a[-2:]:
        return a[:-2]
    else:
        return []
for ini in [[1,1],[1,-1],[-1,1],[-1,-1]]:
    a=ans(ini)
    if a:
        print "".join(['S' if x>0 else 'W' for x in a])
        break
else:
    print "-1"

### FIXED CODE ###

d={"o":1,"x":-1}
w={"S":1,"W":-1}
n={1:"S",-1:"W"}
N=int(raw_input())
s=raw_input()
s+=s[0]
def ans(a):
    for i in range(1,N+1):
        a+=n[w[a[i]]*w[a[i-1]]*d[s[i]]]
    if a[:2]==a[-2:]:
        return a[:-2]
    else:
        return []
for ini in ["SS","SW","WS","WW"]:
    a=ans(ini)
    if a:
        print a
        break
else:
    print "-1"
### BUGGY CODE ###

n, *aa = map(int, open(0).read().split())

for i in range(1, n+1):
    have = aa.count(i)    
    print(have)


### FIXED CODE ###

n, *aa = map(int, open(0).read().split())

from collections import Counter
ca = Counter(aa)

for i in range(1, n+1):
    have = ca[i]
    print(have)
### BUGGY CODE ###

def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    i = 1
    while i < len(A) - 1:
        if A[i+1][1]-A[i-1][1] < L :
            if A[i+1][0]==A[i-1][0] :
                del A[i]
                continue
        i += 1
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
# 深さ優先探索で各直線を考える


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        # 累積和の計算
        ans[u] += ans[v]
        dfs(u, v)


n, q = map(int, input().split())
# tree[i]: 頂点i+1の子どもたち
tree = [[] for i in range(n)]
ans = [0] * n

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

for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x

# 根ノードの頂点 1 から開始
dfs(0, -1)

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
# 深さ優先探索で各直線を考える


def main():
    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            # 累積和の計算
            ans[u] += ans[v]
            dfs(u, v)

    n, q = map(int, input().split())
    # tree[i]: 頂点i+1の子どもたち
    tree = [[] for i in range(n)]
    ans = [0] * n

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

    for _ in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x

    # 根ノードの頂点 1 から開始
    dfs(0, -1)

    print(*ans)


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

N,Q=map(int,input().split())
S=input()
for i in range(Q):
  l,r=map(int,input().split())
  AC=S[l-1:r]
  print(AC.count("AC") )

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
li=[0]*N
t=0
for i in range(N-1):
  if S[i:i+2]=="AC":
      t+=1
  li[i+1]=t
for _ in range(Q):
  l,r=map(int,input().split())
  print(li[r-1]-li[l-1])
### BUGGY CODE ###

x = int(input())

a = int(x**(1/5))
b = -150

flag = 0
if flag == 0:
    for i in range(a,a+3000):
        for j in range(b,b+3000):
            if i**5 - j**5 == x:
                print(i,j)
                flag = 1
                break

if flag == 0:
    b = 0
    for i in range(a,a-3000):
        for j in range(b,b-3000):
            if i**5 - j**5 == x:
                print(i,j)
                break

### FIXED CODE ###

x = int(input())

for a in range(-200,200):
    for b in range(-200,200):
        if a**5 - b**5 == x:
            print(a,b)
            break
    else:
        continue
    break
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    num_a = 0
    while num_a <= n:
        # Aの上からi冊の和
        s = sum(a[:num_a])
        if s > k:
            break
        # Bから読める本の数
        for j in range(len(b)):
            if s + b[j] <= k:
                s += b[j]
            else:
                num_b = j
                break
        else:
            num_b = len(b)
        if num_a + num_b > ans:
            ans = num_a + num_b
        num_a += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate


def main():
    input = sys.stdin.buffer.readline
    n, m, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    b = [0] + list(map(int, input().split()))
    a = list(accumulate(a))
    b = list(accumulate(b))
    ans = 0
    num_b = m
    for num_a in range(n + 1):
        sum_a = a[num_a]
        if sum_a > k:
            break
        while sum_a + b[num_b] > k:
            num_b -= 1
        ans = max(num_a + num_b, ans)
    print(ans)


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

def dijkstra(s: int, n: int, w: int, cost: list) -> list:
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i

        if v == -1:
            break

        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v]+cost[v][j])

    return d

n = int(input())
t = [[float("inf")]*(n) for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c

q, k = map(int, input().split())
k -= 1
d = dijkstra(k, n, n-1, t)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(v: int, p: int = -1, s: int = 0):
    dist[v] = s
    for i, j in t[v]:
        if i == p:
            continue
        dfs(i, v, s + j)

n = int(input())
t = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1;
    t[a].append((b, c))
    t[b].append((a, c))

q, k = map(int, input().split())
k -= 1

dist = [0]*n

dfs(k)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])
### BUGGY CODE ###


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

MOD = 10**9+7

from collections import Counter

def prime(n):
    p = Counter()

    while not n % 2:
        p[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            p[i] += 1
            n //= i
        i += 2
        
    if n > 1: p[n] += 1
    
    return p

c = Counter()
for a in A:
    p = prime(a)

    for key, value in p.items():
        c[key] = max(c[key], value)

n = 1
for key, value in c.items():
    n *= key**value

ans = 0
for a in A:
    ans += n * pow(a, MOD-2, MOD) 
    ans %= MOD

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set(A)
    
    m = max(B)+1    
    prime = {i:i for i in range(m)}
    is_prime = [False] * m
    
    for i in range(2, int(m**0.5)+1):
        if is_prime[i]: continue
        is_prime[i] = True
        
        for j in range(2*i, m, i):
            if not is_prime[j]: prime[j] = i
            is_prime[j] = True
            
    from collections import Counter
    
    count = Counter()
            
    for a in A:
        c = Counter()
        while a > 1:
            n = prime[a]
            c[n] += 1
            a //= n
        for k, v in c.items(): count[k] = max(count[k], v)
            
    x = 1
    for k, v in count.items(): x = x * k**v % MOD
    
    ans = 0
    for a in A: ans += x * pow(a, MOD-2) % MOD
    
    print(ans%MOD)

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

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
XY = len(AB)
ABC = [AB[xy] + C[z] for xy in range(XY) for z in range(Z)]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])
### BUGGY CODE ###

k=int(input())

queue=[1,2,3,4,5,6,7,8,9]

for i in range(k):
    x=queue.pop(0)
    if (x%10!=0):
        queue.append(10*x+(x%10)-1)
    queue.append(10*x+(x%10))
    if (x%10!=9):
        queue.append(10*x+(x%10)+1)
        
print(x)

### FIXED CODE ###

from queue import deque

k=int(input())
q=deque()
for i in range(1,10):
    q.append(i)

for i in range(k):
    x=q.popleft()
    if (x%10!=0):
        q.append(10*x+(x%10)-1)
    q.append(10*x+(x%10))
    if (x%10!=9):
        q.append(10*x+(x%10)+1)
        
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S=list(input().strip())

flag=True
cnt=0
i=0
f=[]
if len(S) != 1:
    while flag:
        if S[i] != S[i+1]:
            f.append(i)
            f.append(i+1)
            i+=2
        else:
            i+=1
        if i>=len(S)-1:
            cnt+=len(f)
            f.reverse()
            for k in f:
                S.pop(k)
            f=[]
            if '1' not in S or '0' not in S:
                break
            i=0
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
S=list(input().strip())
zero=S.count('0')
one=S.count('1')
print(min(zero,one)*2)