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

S = str(input())
slist = list(S)
L = len(slist)
count = 0
for i in range(L):
  if i < L-1 and slist[i] == "B" and slist[i+1] == "W":
    slist[i],slist[i+1] = slist[i+1],slist[i]
    count+=1
  else:
    fcount = 0
    for j in range(L-1):
        if j < L-1 and slist[j] == "B" and slist[j+1] == "W":
          slist[j],slist[j+1] = slist[j+1],slist[j]
          fcount+=1
    if fcount != 0:
      count+=fcount
      i = 0
print(count)

### FIXED CODE ###

S = str(input())
slist = list(S)
L = len(slist)
count = 0
fcount = 0
for i in range(L):
  if slist[i] == "W":
    count+=(i-fcount)
    fcount+=1
print(count)
### BUGGY CODE ###

N = int(input())

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

c = 0
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i-j) == A[i] + A[j]:
            c += 1
            
print(c)

### FIXED CODE ###

import collections
N = int(input())

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

plus = [0] * (N-1)
for i in range(N-1):
  plus[i] = i + A[i]

minus = [0] * (N-1)
for j in range(1, N):
  minus[j-1] = j - A[j]

sum = 0
c = dict(collections.Counter(minus))
for i in range(N-1):
  sum += c.get(plus[i], 0)
  c[minus[i]] -= 1

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

n = input().split()
N = int(n[0])
K = int(n[1])

lista = []
listb = [1]
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if C not in listb:
        listb.append(C)
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[D+M])

### FIXED CODE ###

n = input().split()
N = int(n[0])
K = int(n[1])

listb = [1]
listc = [0]*N
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if listc[C-1] == 0:
        listb.append(C)
        listc[C-1] = 1
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[(D+M)%L])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
a = list(range(1,N+1))
bbef = -N//2
baft = (-N//2)+1
elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
sumbef = sum(elementbef)
elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
sumaft = sum(elementaft)
while(sumaft-sumbef < 0):
    bbef = bbef+1
    baft = baft+1
    elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
    sumbef = sum(elementbef)
    elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
    sumaft = sum(elementaft)
print(sumbef)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
a = list(range(1,N+1))
elements = sorted([i-j for (i,j) in zip(A,a)])
if(N%2 == 1):
    b = elements[N//2]
else:
    b = elements[(N//2)-1]
answer = sum([abs(i-j-b) for (i,j) in zip(A,a)])
print(answer)
### BUGGY CODE ###

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

import functools
import operator


result = functools.reduce(operator.mul, a)

if result>10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

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

x=a[0]

if 0 not in a:
    for i in range (1,n):
        x=x*a[i]
        if x > pow(10,18):
            print(-1)
            exit()           
    print(x)         
else:
    print(0)
### BUGGY CODE ###

A,B = map(int,input().split())
import fractions
gcd = fractions.gcd(A,B)
import math
n = math.floor(gcd)
a = [i for i in range(2,n+1)]
soinsu = [1]
while len(a) > 0:
    x = a.pop(0)
    if gcd % x == 0:
        soinsu.append(x)
    y = n//x
    for j in range(1,y+1):
        z = j*x
        if z in a:
            a.remove(z)
ans = len(soinsu)
print(ans)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

A,B = map(int,input().split())
import fractions
gcd = fractions.gcd(A,B)
ans = 1 + len(factorization(gcd))
if factorization(gcd)[0][0] == 1:
    ans -= 1
print(ans)
### BUGGY CODE ###

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

for n in range(1, 999):
    for x in range(1, 499500):
        if a == (1/2)*n*(n+1)-x and b == (1/2)*(n+1)*(n+2)-x:
            print(x)
            break

### FIXED CODE ###

a, b = map(int, input().split())
print(int((0.5)*(b-a)*(b-a+1)-b))
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()
ans = 0

if p == 2:
  for i in range(n):
    if s[i] == '0' or s[i] == '2' or s[i] == '4' or s[i] == '6' or s[i] == '8' :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] == '0' or s[i] == '5':
      ans += i + 1
else:
  sp = [0]*n
  for i in range(n):
    sp[i] = int(s[i:n])%p
  cj = sp.count(0)
  ans += int(cj*(cj+1)/2)
  for j in range(1,p):
      cj = sp.count(j)
      ans += int(cj * (cj-1)/2)
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)
### BUGGY CODE ###

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

S = input()
items = []
for i in range(Q):
    items.append(input().split())

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

print(ans)


### FIXED CODE ###

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

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

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

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

ans = 1
for ll in l:
  ans = ans*ll
  
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
l = sorted(list(map(int, input().split())))

ans = 1
for ll in l:
  ans *= ll
  if ans > 10**18 or ans==0:
    break
  
if ans > 10**18:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

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

A.sort(reverse=True)

happiness = A.pop(0)
tree = []
tree.append(A.pop(0))

index = 0
while(len(A)>0):
  happiness += tree[index]
  tree.append(A.pop(0))
  if(len(A)==0):
    break
  happiness += tree[index]
  tree.append(A.pop(0))
  index += 1

print(happiness)




### FIXED CODE ###

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

A.sort(reverse=True)

happiness = A.pop(0)
tree = [0] * N
tree[0] = A[0]

index = 0
appendIndex = 1
while(len(A)>appendIndex):
  happiness += tree[index]
  tree[appendIndex] = A[appendIndex]
  appendIndex += 1
  if(len(A)==appendIndex):
    break
  happiness += tree[index]
  tree[appendIndex] = A[appendIndex]
  appendIndex += 1
  index += 1

print(happiness)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    a = [(i/2 + 0.5) for i in A]
    ans = 0
    for i in range(N-M+1):
        ans = max(ans, sum(a[i:M+i]))

    return ans

print(solve())


### FIXED CODE ###

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # スコアの累積和
    l = list(itertools.accumulate(A))

    score = sum(A[:M])
    for i in range(1, N-M):
        score = max(score, l[i+M] - l[i])
        
    ans = (M + score) / 2

    return ans

print(solve())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 04:56:52 2020

@author: Kanaru Sato
"""

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

Max = -100000
for i in range(n-k+1):
    sum = 0
    for j in range(k):
        sum += p[i+j]
    if Max <= sum:
        Max = sum

print((Max+k)/2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 04:56:52 2020

@author: Kanaru Sato
"""

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

sum = 0
sumlist = [0]
for i in range(n):
    sum += p[i]
    sumlist.append(sum)


Max = -100000
for i in range(n-k+1):
    e = sumlist[i+k]-sumlist[i]
    if Max < e:
        Max = e

print((Max+k)/2)
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
diffs = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
max_diff = 0
for diff in diffs:
    max_diff = max(max_diff, max(diff))
r_k = max_diff*(H+W)+1
dp = [[[False] * r_k for _ in range(W)] for _ in range(H)]
dp[0][0][0] = True
for i in range(H):
    for j in range(W):
        diff = diffs[i][j]
        dp_ = dp[i][j]
        if j < W-1:
            dpj = dp[i][j + 1]
            for k in range(r_k):
                if dp_[k] == True:
                    dpj[k + diff] = True
                    dpj[abs(k-diff)] = True
        if i < H - 1:
            dpi = dp[i + 1][j]
            for k in range(r_k):
                if dp_[k] == True:
                    dpi[k + diff] = True
                    dpi[abs(k-diff)] = True

ans = pow(80, 3)
diff = diffs[H-1][W-1]
for k, flg in enumerate(dp[H - 1][W - 1]):
    if flg:
        ans = min(ans, abs(k-diff), k+diff)
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
diffs = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
max_diff = 0
for diff in diffs:
    max_diff = max(max_diff, max(diff))
r_k = max_diff*(H+W)//2+1
dp = [[[False] * r_k for _ in range(W)] for _ in range(H)]
dp[0][0][0] = True
for i in range(H):
    for j in range(W):
        diff = diffs[i][j]
        dp_ = dp[i][j]
        if j < W-1:
            dpj = dp[i][j + 1]
            for k in range(r_k):
                if dp_[k] == True:
                    dpj[abs(k - diff)] = True
                    if k+diff<r_k:
                        dpj[k + diff] = True
        if i < H - 1:
            dpi = dp[i + 1][j]
            for k in range(r_k):
                if dp_[k] == True:
                    dpi[abs(k-diff)] = True
                    if k+diff < r_k:
                        dpi[k + diff] = True

ans = pow(80, 3)
diff = diffs[H-1][W-1]
for k, flg in enumerate(dp[H - 1][W - 1]):
    if flg:
        ans = min(ans, abs(k-diff), k+diff)
print(ans)
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
ans = 0
a = [True] * len(array)
for i in range(N):
    for j in range(N):
        if a[i] == False:
            break
        if i != j and (array[i] % array[j] == 0 or array[i] == array[j]) :
            break
        if i != j and (array[j] % array[i] == 0):
            a[j] == False
        if j == N-1:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = 0
a = [True] * (10**6 + 1)
i = 0
before = 0
for i in array:
    if a[i] == True:
        j = 2*i
        if i == before:
            a[i] = False
        while j <= array[N-1]:
            a[j] = False
            j += i
        before = i
for i in array:
    if a[i] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = [1] * (m + 1)
primes[0], primes[1] = 0, 0
if m > 1: primes[2] = 2
else: primes[1] = 0

for i in range(2, int(m ** 0.5)+1):
    if primes[i] == 0: continue
    for j in range(i, m+1, i):
        if primes[j] == 1:
            primes[j] = i

for i in range(m+1):
    if primes[i] == 1: primes[i] = i

b = [0] * (m + 1)
def factorization(n):
    aset = set()
    temp = n
    while temp != 1:
        aset.add(primes[temp])
        temp = temp // primes[temp]
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
maxb = max(b)
if maxb <= 1: print('pairwise coprime')
elif maxb < n: print('setwise coprime')
else: print('not coprime')

### FIXED CODE ###

import sys, math
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
jdg_p = True
for aa in a:
    aset = set()
    while aa != 1:
        aset.add(primes[aa])
        aa //= primes[aa]
    for aaset in aset:
        b[aaset] += 1
        if b[aaset] >= 2:
            jdg_p = False
            break
        else:
            b[aaset] += 1
    if not jdg_p: break

x = a[0]
jdg_s = True
for aa in a[1:]:
    x = math.gcd(x, aa)
if x != 1: 
    jdg_s = False

if jdg_p: print('pairwise coprime')
elif jdg_s: print('setwise coprime')
else: print('not coprime')
### BUGGY CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0 for _ in range(N)]
    for s in range(N):
        dist = [-1 for _ in range(N)]
        dist[s] = 0

        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if dist[Y] == -1:
                    d.append(Y)
                    dist[Y] = dist[v] + 1
            if v == Y:
                if dist[X] == -1:
                    d.append(X)
                    dist[X] = dist[v] + 1
            if v + 1 < N:
                if dist[v+1] == -1:
                    d.append(v+1)
                    dist[v+1] = dist[v] + 1
            if v - 1 >= 0:
                if dist[v-1] == -1:
                    d.append(v-1)
                    dist[v-1] = dist[v] + 1

        for i in range(N):
            ans[dist[i]] += 1
  
    for k in range(1, N):
        print(ans[k] // 2)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0 for _ in range(N)]
    for s in range(N):
        dist = [-1 for _ in range(N)]
        dist[s] = 0

        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if dist[Y] == -1:
                    d.append(Y)
                    dist[Y] = dist[v] + 1
            if v == Y:
                if dist[X] == -1:
                    d.append(X)
                    dist[X] = dist[v] + 1
            if v + 1 < N:
                if dist[v+1] == -1:
                    d.append(v+1)
                    dist[v+1] = dist[v] + 1
            if v - 1 >= 0:
                if dist[v-1] == -1:
                    d.append(v-1)
                    dist[v-1] = dist[v] + 1

        for i in range(N):
            ans[dist[i]] += 1
  
    for k in range(1, N):
        print(ans[k] // 2)


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

H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b =map(int,input().split())
    A.append(a)
    B.append(b)

G = [0]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if i == 1:
            if j-A[i-1]<0:
                G[j] = B[i-1]
            else:
                G[j] = G[j-A[i-1]]+B[i-1]
        elif j-A[i-1]<0:
            G[j] = min(G[j], B[i-1])
        else:
            G[j] = min(G[j], G[j-A[i-1]]+B[i-1])
        
print(G[H])

### FIXED CODE ###

H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b =map(int,input().split())
    A.append(a)
    B.append(b)

G = [0]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if i == 1:
            if j-A[i-1]<0:
                G[j] = B[i-1]
            else:
                G[j] = G[j-A[i-1]]+B[i-1]
        elif j-A[i-1]<0:
            G[j] = min(G[j], B[i-1])
        else:
            G[j] = min(G[j], G[j-A[i-1]]+B[i-1])
        
print(G[H])
### BUGGY CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l_new = sorted(l)
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l_new[i+1::],l_new[i]+l_new[j])
        count += k
print(count)
        


### FIXED CODE ###

import bisect
n = int(input())
l = sorted(([int(x) for x in input().split()]))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l,l[i]+l[j])
        count += k-(i+1)
print(count)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
for i, b in enumerate(B):
    q.append([-b, i])
heapq.heapify(q)
ans = 0
while len(q)>0:
    b, idx = heapq.heappop(q)
    b = -b
    if b==A[idx]:
        continue
    nb = max(B[(idx+1)%N], B[idx-1], B[idx])
    d = B[(idx+1)%N] + B[idx-1]
    p = (b - nb) // d + 1
    b -= p * d
    B[idx] = b
    heapq.heappush(q, [-b, idx])
    ans += p
    if b < A[idx]:
        print(-1)
        exit()
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
q = [(-b, i) for i, b in enumerate(B)]
heapq.heapify(q)
ans = 0
N_m1 = N-1
while len(q)>0:
    b, idx = q[0]
    b = -b
    b_p1, b_m1 = B[idx+1 if idx<N_m1 else 0], B[idx-1]
    d = b_p1 + b_m1

    a = A[idx]
    p = min((b-a)//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    if b > a:
        heapq.heapreplace(q, (-b, idx))
        if q[0][1] == idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)
### BUGGY CODE ###

from collections import deque

# BFSで通す
N, Q = map(int, input().split())  # N頂点, Q個の命令

G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):  # 辺はN-1本
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    count[p-1] += x

q = deque([0])  # 頂点のノードを入れる
flag = [False]*N

while len(q):
    v = q.pop()
    flag[v] = True  # 部分木の親を到達済みにする

    for e in G[v]:  # vを親にもつノードについてループを回す
        # if flag[e]:  # 頂点eに到達済みであれば
        #     continue
        count[e] += count[v]  # それぞれの子たちに親の値を伝播させる
        q.append(e)

print(*count)


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if n < 3:
    print(max(x))
    exit()
x.sort(reverse=True)
k = n - 2
ans = x[0]
x.pop(0)
while k:
    t = x.pop(0)
    ans += t
    k -= 1
    if k == 0:
        break
    ans += t
    k -= 1
print(ans)

    


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if n < 3:
    print(max(x))
    exit()
x.sort(reverse=True)
k = n - 2
ans = x[0]
x.pop(0)
ans += 2*sum(x[:k//2])
if k%2:
    ans += x[k//2]
print(ans)