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

n = int(input())
s = input()

ok = list()
ans = 0

for i in range(n):
    if len(ok) == 10:
        break
    same = 0
    for j in range(len(ok)):
        if ok[j] == s[i]:
            same = 1
    if same == 1:
        continue
    ok.append(s[i])
    nd = list()
    for j in range(i+1,n):
        same = 0
        if len(nd) == 10:
            break
        for k in range(len(nd)):
            if nd[k] == s[j]:
                same = 1
        if same == 1:
            continue
        nd.append(s[j])
        rd = list()
        for k in range(j+1, n):
            if len(rd) == 10:
                break
            same = 0
            for l in range(len(rd)):
                if rd[l] == s[k]:
                    same = 1
            if same == 1:
                continue
            rd.append(s[k])
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ok = [0,0,0,0,0,0,0,0,0,0]
ans = 0

for i in range(n):
    if sum(ok) == 10:
        break
    if ok[int(s[i])] == 1:
        continue
    ok[int(s[i])] = 1
    nd = [0,0,0,0,0,0,0,0,0,0]
    for j in range(i+1,n):
        if sum(nd) == 10:
            break
        if nd[int(s[j])] == 1:
            continue
        nd[int(s[j])] = 1
        rd = [0,0,0,0,0,0,0,0,0,0]
        for k in range(j+1, n):
            if sum(rd) == 10:
                break
            if rd[int(s[k])] == 1:
                continue
            rd[int(s[k])] = 1
            ans += 1

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

S = input()

a=0
ab=0
ans=0
q=0
m=10**9+7
for s in S:
    if s=='A':
        a+=3**q
    elif s=='B':
        ab+=a
    elif s=='C':
        ans+=ab
    else:
        ans+=2*ans+ab
        ab+=2*ab+a
        a+=2*a+3**q
        q+=1
    ans%=m
    ab%=m
    a%=m
print(ans)



### FIXED CODE ###

S = input()

a=0
ab=0
ans=0
n=1
m=10**9+7
for s in S:
    if s=='A':
        a+=n
    elif s=='B':
        ab+=a
    elif s=='C':
        ans+=ab
    else:
        ans+=2*ans+ab
        ab+=2*ab+a
        a+=2*a+n
        n*=3
        n%=m
    ans%=m
    ab%=m
    a%=m
print(ans)
### BUGGY CODE ###

x, y= map(int, input().split())
mod=10**9+7
import math
a=(2*y-x)//3
b=(2*x-y)//3

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	ab=L[a]*L[b]
	ab=ab%mod
	for j in range(1, mod):
		abj=(ab*j)%mod
		if abj==L[a+b]:
			print(j)
			break


### FIXED CODE ###

x, y= map(int, input().split())
mod=10**9+7
import math
a=(2*y-x)//3
b=(2*x-y)//3

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	p=pow(L[a], mod-2, mod)
	q=pow(L[b], mod-2, mod)
	ans=(L[a+b]*p*q)%mod
	print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

if sum(A) < K:
    K = sum(A)

A.sort()
F.sort()
F = F[::-1]

left = 0
right = 10 ** 12
while left < right:
    mid = (left + right) // 2
    sum = 0
    G = A - (mid // F)
    for i in range(N):
        sum += max(0, G[i])
    if sum <= K:
        right = mid
    else:
        left = mid + 1

print(right)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

if sum(A) < K:
    K = sum(A)

A.sort()
F.sort()
F = F[::-1]

left = 0
right = 10 ** 12
while left < right:
    mid = (left + right) // 2
    sum = 0
    G = A - (mid // F)
#    for i in range(N):
#        sum += max(0, G[i])
    if G[G>0].sum() <= K:
        right = mid
    else:
        left = mid + 1

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

import math
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    acopy = a.copy()
    del acopy[i]
    l = len(acopy)
    acopy.sort()
    cnt = 1
    ans = 0
    for j in range(l-1):
        if acopy[j] == acopy[j+1]:
            cnt += 1
            continue
        else:
            if cnt != 1:
                if cnt == 2:
                    ans += 1
                    cnt = 1
                    continue
                else:
                    ans += math.factorial(cnt)//(math.factorial(cnt-2)*math.factorial(2))
                    cnt = 1
                    continue
    if cnt != 1:
        ans += math.factorial(cnt)//(math.factorial(cnt-2)*math.factorial(2))
    print(ans)

### FIXED CODE ###

import math
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
m = len(set(a))
nans = 0
tbl = list(Counter(a).values())
tbl2 = Counter(a)
for i in range(m):
    if tbl[i] >= 2:
        nans += math.factorial(tbl[i])//(math.factorial(tbl[i]-2)*math.factorial(2))
for i in range(n):
    num = a[i]
    numcnt = tbl2[num]
    print(nans-(numcnt-1))
### BUGGY CODE ###

n, = map(int, input().strip().split())

# a5 - b5 = (a-b)(a4 + a3b + a2b2 + ab3 + b4)

def check(x):
  u = n//x+1
  for a in range(u+1):
    b = a - x
    if abs(b) > u:
      continue
    c = a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
    d = x * c
    if d == n:
      return [a, b]

    a += 1
  return None

for i in range(1, n+1):
  res = check(i)
  if res:
    break

r1, r2 = res
print(r1, r2)
    

### FIXED CODE ###

n, = map(int, input().strip().split())

# a5 - b5 = (a-b)(a4 + a3b + a2b2 + ab3 + b4)

def check(x):
  for a in range(200):
    b = a - x
    c = a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
    d = x * c
    if d == n:
      return [a, b]
  return None

for i in range(1, n+1):
  res = check(i)
  if res:
    break

r1, r2 = res
print(r1, r2)
### BUGGY CODE ###

def training(N) :
  power = 1
  for i in range(1, N + 1) : 
    power *= i
    
  return power % (10 ** 9 + 7)

N = int(input())

print(training(N))

### FIXED CODE ###

def training(N) :
  power = 1
  for i in range(1, N + 1) : 
    power = (power * i) % (10 ** 9 + 7)
    
  return power

N = int(input())

print(training(N))
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

    A = [tuple(map(int, input().split())) for _ in range(N)]

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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

#a = [746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#a = [7,6,8]
#n = len(a)
max_value = 0
for i in range(n):
    b = a.copy()
    b.pop(i)
    x = reduce(gcd, b)
    if x > max_value:
        max_value = x
        max_pos = i
print(max_value)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
ans = 0
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
for i in range(n-1):
    r.append(gcd(r[i],a[n-1-i]))
for i in range(n):
    ans = max(ans,gcd(l[i],r[-i-1]))
print(ans)
### BUGGY CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*10**(i-1))%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

def anagram(s):
    count = 0
    for i in range(n):
        for j in range(i+1,n):
            if s[i] == s[j]:
                count += 1
    return count
  
n = int(input())
s = []
for i in range(n):
    li = sorted(input())
    s.append(li)
print(anagram(s))

### FIXED CODE ###

def anagram(n,s):
    count = 0
    dic = {}
    for s in S:
        if s in dic:
            count += dic[s]
            dic[s] += 1
        else:
            dic[s] = 1
    return count

N = int(input())
S = []
for i in range(N):
    li = sorted(input())
    li = ''.join(li)
    S.append(li)
print(anagram(N,S))
### BUGGY CODE ###

def main():
	N, M = map(int, input().split())
	A = list(map(int, input().split()))
	sums = [0]*(N+1)
	for i in range(N+1):
		sums[i] = sums[i-1] + A[i-1]

	ans = 0
	for i in range(N+1):
		for j in range(i+1, N+1):
			if (sums[j] - sums[i]) % M == 0:
				ans += 1
	print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
	N, M = map(int, input().split())
	A = list(map(int, input().split()))
	sums = [0]*(N+1)
	ans = 0
	mod = defaultdict(int)
	mod[0] = 1
	for i in range(1, N+1):
		sums[i] = (sums[i-1] + A[i-1]) % M
		ans += mod[sums[i]]
		mod[sums[i]] += 1

	print(ans)

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

from collections import deque
import sys
input=sys.stdin.readline


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]] :
            if not D[h+p][w+q] :
                pos.append([h+p,w+q,depth+1])
                D[h+p][w+q]=True

    return depth            

print(search())

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

for i in range(q):
    l,r = map(int, input().split())
    ss = s[l-1:r]
    k = 0
    for j in range(len(ss)-1):
        if ss[j] == "A" and ss[j+1] == "C":
            k += 1
    print(k)


### FIXED CODE ###

import sys
input=sys.stdin.readline

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

t = [0]*(n)
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(q):
    l,r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n = int(input())
s = str(input())

lst = ['0','']
for idx in range(n-1):
	org = lst
	tmp = []
	for org_i in org:
		tmp.append(org_i+str(idx+1))
	lst.extend(tmp)
lst.remove('')

cnt = 0
for lst_i in lst:
	tmp = []
	for str_i in lst_i:
		tmp.append(s[int(str_i)])
	if len(tmp) == len(list(set(tmp))):
		cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

dic = {}
for s_i in set(s):
	dic[s_i] = s.count(s_i)+1

p = 10**9+7
res = 1
for v in dic.values():
	res = (res*v)%p

print(res-1)
### BUGGY CODE ###

from collections import Counter
import copy

def count(dic, key):
    ans = 0
    for i in key:
        d = dic[i]
        ans += d * (d - 1) // 2
    return(ans)

N = int(input())
A = list(map(int, input().split()))
a = dict(Counter(A))
k = list(a.keys())
for i in range(N):
    a2 = copy.copy(a)
    a2[A[i]] -= 1
    print(count(a2, k))


### FIXED CODE ###

from collections import Counter
import copy

def count(dic, key):
    ans = 0
    for i in key:
        d = dic[i]
        ans += d * (d - 1) // 2
    return(ans)

N = int(input())
A = list(map(int, input().split()))
a = dict(Counter(A))
k = list(a.keys())
m = count(a, k)
dic = {}
for i in k:
    dic[i] = m - a[i] + 1
for i in range(N):
    print(dic[A[i]])
### BUGGY CODE ###

N = int(input())
L = sorted(list(map(int,input().split())))
table = [[0 for _ in range(N)] for _ in range(N)]
ans = 0
for i in range(1,N-1):
  for j in range(i):
    for k in range(i+1,N):
      if L[i]+L[j]<=L[k]:break 
      elif L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
        ans += 1
print(ans)

### FIXED CODE ###

import bisect 
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    idx = bisect.bisect(L,L[i]+L[j]-1)
    ans += idx-j-1
print(ans)
### BUGGY CODE ###

h,w = map(int, input().split())
a = ["#"+input()+"#" for _ in range(h)]
s = "#"*(w+2)
a = [s] + a + [s]


ds = [[0] + [-1]*w + [0] for _ in range(h)]
ds = [[0]*(w+2)] + ds + [[0]*(w+2)]

vectors = set([(-1,0),(1,0),(0,-1),(0,1)])

stack = []

ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j] == "#":
            stack.append((i,j))
            ds[i][j] = 0

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if ds[nh+vh][nw+vw] == -1:
            stack.append((nh+vh,nw+vw))
            ds[nh+vh][nw+vw] = ds[nh][nw] + 1
            ans = ds[nh][nw] + 1

print(ans)


### FIXED CODE ###

import numpy as np
import copy

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

a = np.array([[0 if (ai[j] == "#") else np.inf for j in range(w)] for ai in a])

for i in range(1, h):
    a[i] = np.minimum(a[i], a[i - 1] + 1)
for i in range(h - 2, -1, -1):
    a[i] = np.minimum(a[i], a[i + 1] + 1)
for i in range(1, w):
    a[:, i] = np.minimum(a[:, i], a[:, i - 1] + 1)
for i in range(w - 2, -1, -1):
    a[:, i] = np.minimum(a[:, i], a[:, i + 1] + 1)

print(int(a.max()))
### BUGGY CODE ###

n = int(input())
p = [0] + list(map(float, input().split()))
q = [1 - p[i] for i in range(n + 1)]
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] * q[i]
        if not j == 0:
            dp[i][j] += dp[i - 1][j - 1] * p[i]
ans = 0
for i in range((n + 1) // 2):
    ans += dp[n][n - i]
print(ans)

### FIXED CODE ###

n = int(input())
p = [0] + list(map(float, input().split()))
q = [1 - p[i] for i in range(n + 1)]
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] * q[i]
        if not j == 0:
            dp[i][j] += dp[i - 1][j - 1] * p[i]
ans = 0
for i in range((n + 1) // 2):
    ans += dp[n][n - i]
print(ans)
### BUGGY CODE ###

import sys
x=50000
sys.setrecursionlimit(x)

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

### FIXED CODE ###


n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(n+1) for i in range(n+1)]
def func(n,x):
    for i in range(0,n+1):
        for j in range(0,n+1):
            if j==0:
                dp[i][j] = 1
            elif i==0:
                dp[i][j]=0
            else:
                p=(arr[i-1])*dp[i-1][j-1]
                q=(1-arr[i-1])*dp[i-1][j]
                dp[i][j] = p+q 
    
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))
### BUGGY CODE ###

from collections import deque
n=int(input())
d=[-1]*n
l=deque([])
for i in range(n-1):
    u,v,w=map(int,input().split())
    u,v=min(u,v),max(u,v)
    l.append((u-1,v-1,w))
f=0
while len(l):
    x=l.popleft()
    if f:
        if x[2]%2 and d[x[0]]==0:
            d[x[1]]=1
        elif x[2]%2 and d[x[0]]==1:
            d[x[1]]=0
        elif x[2]%2==0 and d[x[0]]==1:
            d[x[1]]=1
        elif x[2]%2==0 and d[x[0]]==0:
            d[x[1]]=0
        elif x[2]%2 and d[x[1]]==0:
            d[x[0]]=1
        elif x[2]%2 and d[x[1]]==1:
            d[x[0]]=0
        elif x[2]%2==0 and d[x[1]]==1:
            d[x[0]]=1
        elif x[2]%2==0 and d[x[1]]==0:
            d[x[0]]=0
        else:
            l.append(x)
    else:
        f=1
        if x[2]%2:
            d[x[0]]=0
            d[x[1]]=1
        else:
            d[x[0]]=0
            d[x[1]]=0
for i in d:
    print(i)

### FIXED CODE ###

from collections import deque
def sol():
    n=int(input())
    d=[-1]*n
    l=deque([])
    for i in range(n-1):
        u,v,w=map(int,input().split())
        u,v=min(u,v),max(u,v)
        l.append((u-1,v-1,w))
    f=0
    while len(l):
        x=l.popleft()
        if f:
            if x[2]%2 and d[x[0]]==0:
                d[x[1]]=1
            elif x[2]%2 and d[x[0]]==1:
                d[x[1]]=0
            elif x[2]%2==0 and d[x[0]]==1:
                d[x[1]]=1
            elif x[2]%2==0 and d[x[0]]==0:
                d[x[1]]=0
            elif x[2]%2 and d[x[1]]==0:
                d[x[0]]=1
            elif x[2]%2 and d[x[1]]==1:
                d[x[0]]=0
            elif x[2]%2==0 and d[x[1]]==1:
                d[x[0]]=1
            elif x[2]%2==0 and d[x[1]]==0:
                d[x[0]]=0
            else:
                l.append(x)
        else:
            f=1
            if x[2]%2:
                d[x[0]]=0
                d[x[1]]=1
            else:
                d[x[0]]=0
                d[x[1]]=0
    for i in d:
        print(i)

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

from collections import Counter
n=int(input())
l=[]
count=0
for i in range(n):
  b=list(input())
  b.sort()
  l.append(b)
for i in range(n):
  for j in range(i+1,n):
    if l[i]==l[j]:
      count+=1
print(count)

### FIXED CODE ###

n=int(input())
count=0
d={}
for i in range(n):
  b=list(input())
  b.sort()
  c=str(b)
  if c in d.keys():
    d[c]+=1
  else:
    d[c]=1
for i in d.values():
  count+=i*(i-1)/2
print(int(count))
### BUGGY CODE ###

import sys
from functools import lru_cache
from collections import OrderedDict

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


class Graph():
    def __init__(self):
        self.adjacency_dict = {}
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def add_count(self, v, count):
        self.counter_dict[v] += count

    @lru_cache(maxsize=None)
    def dfs(self, v, pv):
        for nv in self.adjacency_dict[v]:
            if nv != pv:
                self.counter_dict[nv] += self.counter_dict[v]
                self.dfs(nv, v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_count(p, x)
    tree.dfs(1, 0)
    tree.print_counters()


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import OrderedDict

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


class Graph():
    def __init__(self):
        self.adjacency_dict = {}
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = set()
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].add(v2)
        self.adjacency_dict[v2].add(v1)

    def add_count(self, v, count):
        self.counter_dict[v] += count

    def dfs_stack(self, start):
        stack = [start]
        visited = set()

        parent_vertex = 0
        while stack:
            current_vertex = stack.pop()
            visited.add(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v != parent_vertex:
                    self.counter_dict[v] += self.counter_dict[current_vertex]
                    stack.append(v)
            parent_vertex = current_vertex

    def dfs_rec(self, v, pv):
        for nv in self.adjacency_dict[v]:
            if nv != pv:
                self.counter_dict[nv] += self.counter_dict[v]
                self.dfs_rec(nv, v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_count(p, x)
    tree.dfs_stack(1)
    # tree.dfs_rec(1, 0)
    tree.print_counters()


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

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

for i in range(M):
    A.sort()
    A[N-1] = int(A[N-1] / 2)

print(sum(A))


### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

for i in range(M):
    _ = -heapq.heappop(A)
    _ = int(_ / 2)
    heapq.heappush(A, -_)

print(-sum(A))