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

N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)
import math

c=0
while B:
    x,h=heappop(B)
    sup=x+2*D
    bomb=math.ceil(h/A)
    temp=[]
    c+=bomb
    while B:
        X,H=heappop(B)
        if X<=sup:
            H=max(0,H-A*bomb)
            if H>0:
                temp.append((X,H))
        else:
            temp.append((X,H))
            break
    for t in temp:
        heappush(B,t)
print(c)


### FIXED CODE ###

N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

dic={}

ans=0
atk_cnt=0
while B:
    x,h=heappop(B)
    if h==-1:
        atk_cnt-=dic[x-1]
        continue
    if h<=A*atk_cnt:
        continue
    h-=A*atk_cnt
    sup=x+2*D
    bomb=(h-1)//A+1
    ans+=bomb
    dic[sup]=bomb
    atk_cnt+=bomb
    heappush(B,(sup+1,-1))
    
    
print(ans)
### BUGGY CODE ###

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

memo = {1: 1, 0: 0}
def dfs(n):
    if n in memo:
        return memo[n]

    y = 1
    res = n
    while y*y <= n:
        y += 1
        if y + A > n:
            break
        res = min(res, y + A + dfs((n + y - 1) // y))
    memo[n] = res
    return res
print(dfs(N))

### FIXED CODE ###

# seishin.py
N, A = map(int, input().split())

ans = N
if N > 1:
    for k in range(1, 41):
        left = 0; right = N+1
        while left+1 < right:
            mid = (left + right) // 2
            if mid**(k+1) < N:
                left = mid
            else:
                right = mid
        m = right
        v = (m-1)**(k+1)
        for i in range(k+1):
            v //= m-1
            v *= m
            if N <= v:
                ans = min(ans, A*k + (m-1)*(k+1) + (i+1))
                break
print(ans)
### BUGGY CODE ###

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

for i in range(n-k+1):
    xtmp = x[i:i+k]
    if i==0:
        MIN = abs(xtmp[0]-xtmp[-1]) + abs(xtmp[0])

    MIN = min(MIN, abs(xtmp[0]-xtmp[-1]) + abs(xtmp[0]))
    MIN = min(MIN, abs(xtmp[0]-xtmp[-1]) + abs(xtmp[-1]))

print(MIN)

### FIXED CODE ###

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

n, k = map(int, input().split())
X = list(map(int, input().split()))
ans = 10**10
for i in range(n-k+1):
    left = X[i]
    right = X[i+k-1]
    ans = min(ans, abs(left)+abs(left-right), abs(right)+abs(right-left))
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())

j_cnt = 0
i_cnt = 0
i = L
j = L+1
min_num = 2020
while i <= R:
    j = i+1
    while j <= R:
        min_num = min(min_num,((i%2019)*j)%2019)
        if not min_num:
            break
        j += 1
    i += 1
print(min_num)

### FIXED CODE ###

L,R = map(int,input().split())
 
cnt = 0
i = L
j = L+1
min_num = 2020
while i <= R and cnt <= 2019:
    j = i+1
    while j <= R:
        min_num = min(min_num,(i*j)%2019)
        if not min_num:
            break
        j += 1
    i += 1
    cnt += 1
print(min_num)
### BUGGY CODE ###

x = input()
n = int(input())

for i in range(n):
    a = input()
    if a[0] == "2":
      a, b, c = a.split()
      a = int(a)
      b = int(b)

      if b == 1:
          x = x[::-1] + c
          x = x[::-1]
      elif b == 2:
          x = x + c
    else:
        x = x[::-1]

print(x)

### FIXED CODE ###

import collections

x = collections.deque(input())
n = int(input())
rev = False

for i in range(n):
    y = input().split()
    if len(y) == 1:
      rev = not rev
    elif rev:
      if int(y[1]) == 2:
          x.appendleft(y[2])
      else:
          x.append(y[2])
    else:
      if int(y[1]) == 2:
          x.append(y[2])
      else:
          x.appendleft(y[2])

if rev:
  x.reverse()

print("".join(x))
### BUGGY CODE ###

S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len)]

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * num) % 13] = (DP[i][(j + int(S[i]) * num) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * num) % 13] = (DP[i][
                                                         (j + k * num) % 13] +
                                                     DP[i + 1][j]) % 1000000007

print(DP[0][5])



### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


b_searched = set()
b_unsearched = []


b_searched.add(tuple(b))
delit = delitable(b)

if delit == []:
    print("-1")
for delit_num in delit:
    b_unsearched.append([[v for i, v in enumerate(b) if delit_num != i + 1], [delit_num]])

b_unsearched.reverse()

while b_unsearched:
    b, log = b_unsearched.pop()

    b_tuple = tuple(b)
    b_searched.add(b_tuple)
    delit = delitable(b)
    if not delit:
        if not b:
            log.reverse()
            print("\n".join(map(str, log)))
            break
        else:
            continue
    for delit_num in delit:
        b_temp = [v for i, v in enumerate(b) if delit_num != i + 1]
        if not tuple(b_temp) in b_searched:
            b_unsearched.append([b_temp, log + [delit_num]])
else:
    print("-1")

### FIXED CODE ###

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


log = []
while b:
    delit = delitable(b)
    if not delit:
        print(-1)
        break
    del b[delit[-1] - 1]
    log.append(delit[-1])
else:
    log.reverse()
    print("\n".join(map(str, log)))
### BUGGY CODE ###

def counter(flag,st):
  count = 0
  if st == '':
    return count
  for i in range(len(st)):
    if not st[i] in flag:
      flag+=st[i]
      count += 1
      if count > 10**9:
        count%=10**9+7
      if i < len(st)-1:
        count += counter(flag,st[i+1:])
      flag.pop(-1)
  return count

N = int(input())
S = input()

cnt = counter([],S)
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
charCnt = []
flag = {}
for c in S:
  if not c in flag:
    flag[c] = 1
    charCnt.append([c,1])
  else :
    flag[c] += 1
    for i in range(len(charCnt)):
      if charCnt[i][0] == c:
        charCnt[i][1] += 1
        break

cnt = 1
for i in range(len(charCnt)):
  cnt *= (charCnt[i][1]+1)
cnt -= 1
cnt %= 10**9+7
print(cnt)
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
count=0
flag=True
for i in range(N):
    for k in range(i):
        l=min(P[:i])
        if P[i]>l:
            flag=False
    if flag:
        count+=1
    else:
        flag=True
print(count)


### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
count=1
min=P[0]
for i in range(1,N):
    if min>P[i]:
      count+=1
      min=P[i]
print(count)
### BUGGY CODE ###

from fractions import gcd

n, m = map(int, input().split())
s = input()
t = input()

s_num = [0] * n
t_num = [0] * m
s_num[0], t_num[0] = 1, 1
l = n * m / gcd(n, m)

for i in range(1, n):
    s_num[i] = i * l / n + 1

for i in range(1, m):
    t_num[i] = i * l / m + 1

match_num = list(set(s_num) & set(t_num))
ans = l

for i in range(len(match_num)):
    s_str = s[s_num.index(match_num[i])]
    t_str = t[t_num.index(match_num[i])]

    if s_str != t_str:
        print('-1')
        exit()

print(int(ans))


### FIXED CODE ###

import fractions


def binary_search(list, number, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid][0]
        if guess == number:
            if list[mid][1] == item:
                return False
            else:
                return True
        if guess > number:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return False


n, m = map(int, input().split())
s = input()
t = input()
check = []
l = n * m // fractions.gcd(n, m)
for i in range(n):
    check.append([i * l // n, s[i]])
for i in range(m):
    if binary_search(check, i * l // m, t[i]):
        print(-1)
        exit()
print(l)
### BUGGY CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

ld=cf(a,b)
ld.append(1)

#ld2 = divisor(gcd(a,b))
cnt=0
#print(ld)
ansl=[]
for i in ld:
    flg=0
    for j in ansl:
        #if i==j or i==1:
        #    break
        if gcd(i,j) !=1:
            flg = 1
            #print('flg',i,j)
            #if j in ld:
            #    print('in',i,j,gcd(i,j))
            #    ld.remove(j)
            break
        #print(i,j,gcd(i,j))
    if flg == 0:
        ansl.append(i)


print(len(ansl))

#print(ld)

### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

ld=divisor(gcd(a,b))
ld.sort()
#ld.append(1)

#ld2 = divisor(gcd(a,b))
cnt=0
#print(ld)
ansl=[]
for i in ld:
    flg=0
    for j in ansl:
        #if i==j or i==1:
        #    break
        if gcd(i,j) !=1:
            flg = 1
            #print('flg',i,j)
            #if j in ld:
            #    print('in',i,j,gcd(i,j))
            #    ld.remove(j)
            break
        #print(i,j,gcd(i,j))
    if flg == 0:
        ansl.append(i)
    #print(ansl)


print(len(ansl))

#print(ld)
### BUGGY CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def dfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        dfs(check)
print(cnt)


### FIXED CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)
### BUGGY CODE ###

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

counter = 0

for num_1, i in enumerate(L):
  for num_2, j in enumerate(L):
    if num_1 <= num_2:
      continue
    else:
      for num_3, k in enumerate(L):
        if num_2 <= num_3:
          continue
        else:
          if i+j >k and j+k>i and k+i>j:
            counter += 1
print(counter)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() #小さい順
counter = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    index = bisect.bisect_left(L, L[i]+L[j], 0, N)
    counter = counter + index - j - 1
       
print(counter)
### BUGGY CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
tmp=sorted(p)
P=tmp[::-1]
tmp=sorted(q)
Q=tmp[::-1]
tmp=sorted(r)
R=tmp[::-1]
ans=0
while(1):
	if X==0 and Y==0:
		print(ans)
		break
	elif X>0 and Y>0:
		tmp=max(P[0],Q[0],R[0])
		ans+=tmp
		if tmp==P[0]:
			P=P[1:]
			X-=1
		elif tmp==Q[0]:
			Q=Q[1:]
			Y-=1
		elif tmp==R[0]:
			if P[0]>=Q[0]:
				R=R[1:]
				Y-=1
			else:
				R=R[1:]
				X-=1
	elif X==0:
		tmp=max(Q[0],R[0])
		ans+=tmp
		if tmp==Q[0]:
			Q=Q[1:]
			Y-=1
		elif tmp==R[0]:
			R=R[1:]
			Y-=1
	elif Y==0:
		tmp=max(P[0],R[0])
		ans+=tmp
		if tmp==P[0]:
			P=P[1:]
			X-=1
		elif tmp==R[0]:
			R=R[1:]
			X-=1

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
tmp=sorted(p)
P=tmp[::-1]
tmp=sorted(q)
Q=tmp[::-1]
tmp=sorted(r)
R=tmp[::-1]
tmp=P[:X]+Q[:Y]+R
tmp=sorted(tmp)
tmp=tmp[::-1]
ans=sum(tmp[:X+Y])
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
INF = float('inf')
N,M = map(int,input().split())

d_from = defaultdict(lambda:[])
d_to = defaultdict(lambda:[])

for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    d_from[x].append(y)
    d_to[y].append(x)

dp = [-INF]*N
for i in range(N):
    if d_from[i] == []:
        dp[i] = 0
        que = deque([])
        for j in d_to[i]:
            dp[j] = max(dp[i]+1,dp[j])
            que.append(j)
        while que:
            j = que.pop()
            for k in d_to[j]:
                dp[k] = max(dp[j]+1,dp[k])
                que.append(k)
print(max(dp))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())

d = defaultdict(lambda:[])

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

dp = [-1]*N

def dist(s):
    if dp[s] >= 0:
        return dp[s]
    if d[s] == []:
        dp[s] = 0
        return 0
    res = 0
    for t in d[s]:
        res = max(res,1+dist(t))
    dp[s] = res
    return res

ans = 0
for i in range(N):
    ans = max(ans,dist(i))

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

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    edges = [set() for i in range(N+1)]
    score = [0] * (N+1)

    for i in range(N-1):
        edges[a[i]].add(b[i])
        edges[b[i]].add(a[i])

    for i in range(Q):
        # print(p[i], [z for z in edges[p[i]] if z > p[i]], x[i])
        # すべての以下のものに配布されるようにする
        tl = [p[i]]
        al = set()
        al.add(p[i])
        while(len(tl) != 0):
            t = tl.pop(0)
            tl += [s for s in edges[t] if s > t]
            # print("tl", tl, set(tl))
            al = al | set(tl)
            # print("al", al)
        # print(p[i], al, x[i])
        for y in al:
            score[y] += x[i]

    print(' '.join(map(str,score[1:])))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    dedges = [set() for i in range(N+1)]
    uedges = [set() for i in range(N+1)]
    score = [0] * (N+1)

    for i in range(N-1):
        dedges[a[i]].add(b[i])
        # uedges[b[i]].add(a[i])

    # 自分以下のすべての子ノードを記録するようにする
    for i in range(Q):
        score[p[i]] += x[i]

    for i in range(1, N+1):
        for j in dedges[i]:
            score[j] += score[i]

    print(' '.join(map(str, score[1:])))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

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

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N=ri()
X=rl()
Xs = sorted(X)
Xsl = Xs[:N//2]
Xsr = Xs[N//2:]

for x in X:
    if x in Xsl:
            print(Xsr[0])
    else:
            print(Xsl[-1])



### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
import numpy as np
import copy
md = np.median(x)
x_c = copy.copy(x)
x_c.sort()
a = x_c[int(n/2 - 1)]
b = x_c[int(n/2)]
for i in range(n):
    if x[i] < md:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
tpmem = [-1]*(n+1)
tpmem[1] = tpoint[1]
for i in range(1, n+1):
    pi = 0
    j = i
    prej = j
    while True:
        if tpmem[j] != -1:
            pi += tpmem[j]
            tpmem[prej]=tpmem[j]
            break
        pi += tpoint[j]
        if parray[j] == -1:
            break
        prej = j
        j = parray[j]
    print(pi)
    tpmem[i] = pi
    

### FIXED CODE ###

n, q = list(map(int, input().split()))
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    nodes[ai-1].append(bi-1)
    nodes[bi-1].append(ai-1)
    
cnts = [0]*n
for _ in range(q):
    pi, xi = list(map(int, input().split()))
    cnts[pi-1] += xi
    
stack = []
visited = set()
stack.append(0)
while stack:
    current = stack.pop(-1)
    visited.add(current)
    for j in nodes[current]:
        if j in visited:
            continue
        cnts[j] += cnts[current]
        stack.append(j)
        
print(*cnts)
### BUGGY CODE ###

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

### FIXED CODE ###

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())