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

def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))


### FIXED CODE ###


def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()
for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0
dist = [[1,0], [0,1], [-1,0], [0,-1]]
ans = 0
while len(to_search) > 0:
    nowi, nowj , nowd = to_search.pop()
    for di, dj in dist:
        nexti = nowi+di
        nextj = nowj+dj
        if 0<= nexti< H and 0<= nextj< W:
            if distance[nexti][nextj] > nowd+1:
                to_search.appendleft((nexti, nextj, nowd+1))
                distance[nexti][nextj] = nowd+1
                ans = max(ans, nowd+1)
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()
for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0
dist = [[1,0], [0,1], [-1,0], [0,-1]]
ans = 0
while len(to_search) > 0:
    nowi, nowj , nowd = to_search.pop()
    for di, dj in dist:
        nexti = nowi+di
        nextj = nowj+dj
        if 0<= nexti< H and 0<= nextj< W:
            if distance[nexti][nextj] > nowd+1:
                to_search.appendleft((nexti, nextj, nowd+1))
                distance[nexti][nextj] = nowd+1
                ans = max(ans, nowd+1)
print(ans)
### BUGGY CODE ###

s = input()
s_list = list(s)
s_len = len(s)
count = 0
while(1):
  ind = s.find('BW')
  if ind == -1:
    break
  s_list[ind] = 'W'
  s_list[ind+1] = 'B'
  s = ''.join(s_list)
  count += 1
print(count)



### FIXED CODE ###

S = list(input())
W_i = [i for i,j in enumerate(S) if j == 'W']
W_n = S.count('W')
cur = 0
ans = 0
for i in W_i:
  ans += i-cur
  cur += 1
print(ans)
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        if ball >0:ball,man[a%n] =ball-1, man[a%n]+1
        elif ball == 0:ball,man[a%n] = man[a%n],ball
        a+=1
        if p in man:break
    print(man.index(max(man)))                 

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

prime = [True]*(10**5+1)
prime[0] = False
prime[1] = False

for a in range(2,318): # >>> gmpy2.isqrt(10**5+1) -> mpz(316)
  if prime[a] == False:
    continue
  else:
    for b in range(a*2,10**5+1,a): 
      prime[b] = False
"""
print prime
import gmpy2

for a in range(0,10**5+1):
  if prime[a] != gmpy2.is_prime(a):
    print "NO"
    print a
"""
ans = [False]*(10**5+1)
for a in range(3,10**5+1,2):
  if prime[a] == True and prime[(a+1)/2] == True:
    ans[a] = True

q = int(raw_input())
for a in range(q):
  l,r = map(int,raw_input().split(" "))
  print ans[l:r+1].count(True)


### FIXED CODE ###

prime = [True]*(10**5+1)
prime[0] = False
prime[1] = False

for a in range(2,318): # >>> gmpy2.isqrt(10**5+1) -> mpz(316)
  if prime[a] == False:
    continue
  else:
    for b in range(a*2,10**5+1,a): 
      prime[b] = False
"""
print prime
import gmpy2

for a in range(0,10**5+1):
  if prime[a] != gmpy2.is_prime(a):
    print "NO"
    print a
"""
ans = [0]*(10**5+1)
now = 0
for a in range(3,10**5+1,2):
  if prime[a] == True and prime[(a+1)/2] == True:
    now = now + 1
  ans[a] = now

q = int(raw_input())
for a in range(q):
  l,r = map(int,raw_input().split(" "))
  x = ans[r] - ans[l]
  if prime[l] == True and prime[(l+1)/2] == True:
    x = x + 1
  print x
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(1,N+1):
    ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(1,N+1):
    ans = (ans * i)%(10**9+7)
print(ans)
### BUGGY CODE ###

import bisect

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

alist = list(map(int, input().split()))

for _ in range(m):
  b, c = map(int, input().split())
  alist.extend([c for _ in range(b)])

print(sum(sorted(alist, reverse=True)[:n]))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

n = int(input())
as_ = list(map(int, input().split()))
bs_ = list(map(int, input().split()))
cs_ = list(map(int, input().split()))

ans = 0
for a in as_:
  for b in bs_:
    if b > a:
      ans += len([c for c in cs_ if c >b])
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
as_ = list(map(int, input().split()))
bs_ = list(map(int, input().split()))
cs_ = list(map(int, input().split()))

as_.sort()
bs_.sort()
cs_.sort()

ans = 0
for b in bs_:
  ans += bisect.bisect_left(as_, b) * (n-bisect.bisect_right(cs_, b))
print(ans)
### BUGGY CODE ###

import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]

for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N][math.ceil(N/2):]))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))
### BUGGY CODE ###

l, r = map(int, input().split())

ans = 2020

for i in range(l, r):
    for j in range(i + 1, r + 1):
        tmp = i * j % 2019
        if ans > tmp:
            ans = tmp
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())

ans = 2020
if r - l >= 2019:
    r = l + 2018
for i in range(l, r):
    for j in range(i + 1, r + 1):
        tmp = i * j % 2019
        if ans > tmp:
            ans = tmp
    
print(ans)
### BUGGY CODE ###

from sys import exit
import copy
#import numpy as np
#from collections import deque


d, = map(int, input().split())
c= list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
#  t=[int(input()) for _ in range(d)]

sche=[0 for _ in range(d)]
s_tmp=float("inf")*(-1)
for off in range(0,13):
    last=[0 for _ in range(26)]
    sche=[0 for _ in range(d)]
    for day in range(1,d+1):
        idx=day-1
        d_tmp=float("inf")*(-1)
        i_tmp=0
        for t in range(26):    
            delta=0
            l_tmp=copy.copy(last)
            delta+=s[idx][t]
            l_tmp[t]=day
            for k in range(off+1):
                for l in range(26):
                    delta-=c[l]*(day+k-l_tmp[l])
            if delta>=d_tmp:
                d_tmp=delta
                i_tmp=t
        
        sche[idx]=i_tmp+1
        # score+=d_tmp
        last[i_tmp]=day
        # print(score)
        # print(i_tmp+1)

    score=0
    last=[0 for _ in range(26)]
    for i in range(1,d+1):
        idx=i-1
        score+=s[idx][sche[idx]-1]
        for l in range(26):
            score-=c[l]*(i-last[l])
        last[sche[idx]-1]=i
    
    # print(score)
    if score>=s_tmp:
        s_tmp=score
        sche_tmp=copy.copy(sche)


for i in sche_tmp:
    print(i)
# print(s_tmp)






### FIXED CODE ###

from sys import exit
import copy
#import numpy as np
#from collections import deque


d, = map(int, input().split())
c= list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
#  t=[int(input()) for _ in range(d)]

sche=[0 for _ in range(d)]
last=[0 for _ in range(26)]

score=0
for day in range(1,d+1):
    idx=day-1
    d_tmp=0
    i_tmp=0
    for t in range(26):    
        delta=0
        l_tmp=copy.copy(last)
        delta+=s[idx][t]
        l_tmp[t]=day
        for l in range(26):
            delta-=c[l]*(day-l_tmp[l])
        if delta>=d_tmp:
            d_tmp=delta
            i_tmp=t
    sche[idx]=i_tmp
    score+=d_tmp
    last[i_tmp]=day
    # print(score)
    print(i_tmp+1)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-w, -1, -1):
            if dp[j] >= 0 and j+w <= W and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter,deque

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque([key for key, val in count.items() if val == 0])
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
            count[cur_match] = -1
        que.extend(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_id(x, y):
        return min(x, y) * 10007 + max(x, y)

    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        count[calc_id(x, a[0])] += 0
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            u_id = calc_id(x, y)
            v_id = calc_id(x, z)
            edge[u_id].append(v_id)
            count[v_id] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


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

from sys import stdin
mod = 10**9+7
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

maxn = 2*10**6

fac  = [0 for _ in range(maxn)]
finv = [0 for _ in range(maxn)]
inv  = [0 for _ in range(maxn)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,maxn):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod%i] * (mod // i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
A.sort()
for ind,a in enumerate(A):
    ans -= a*combinations(N-ind-1,K-1) % mod
    ans %= mod
    
A.reverse()
for ind,a in enumerate(A):
    ans += a*combinations(N-ind-1,K-1) % mod
    ans %= mod
    
print(ans%mod)

### FIXED CODE ###

from sys import stdin
mod = 10**9+7
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

maxn = 2*10**6

fac  = [0 for _ in range(maxn)]
finv = [0 for _ in range(maxn)]
inv  = [0 for _ in range(maxn)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,maxn):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod%i] * (mod // i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
A.sort()
for ind,a in enumerate(A):
    ans -= a*combinations(N-ind-1,K-1) % mod
    ans %= mod
    
A.reverse()
for ind,a in enumerate(A):
    ans += a*combinations(N-ind-1,K-1) % mod
    ans %= mod
    
print(ans%mod)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(N)]
for i in range(N):
    for j in range(i,N-1):
        if A[j]>=A[j+1]:
            B[i]+=1
        else:
            break
print(max(B))

### FIXED CODE ###

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

import sys
input = sys.stdin.readline

# 自分の解答
def myAnswer(N:int,dic:dict) -> int: # pythonはlist操作が重いので辞書で処理する
   ans = 0
   for a in dic.values():
      if(a % 2 == 1):
         ans += 1
   return ans
def modelAnswer(N:int,A:list) -> int:
   ans = []
   A.sort()
   for a in A:
      if(a in ans):
         ans.remove(a)
      else:
         ans.append(a)
   return len(ans)

def main():
   N = int(input())
   dic = {}
   A =[]
   for _ in range(N):
      a = int(input())
      A.append(a)
      if(a in dic.keys()):
         dic[a]+=1
      else:
         dic[a]=1
   print(modelAnswer(N,A))
if __name__ == '__main__':
   main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
ans=dict()
cnt=0

for _ in range(N):
    A=int(input())
    if((A in ans)==False):
        ans[A]=1
    else:
        ans[A]+=1

for value in ans.values():
    if(value%2==1):
        cnt+=1

print(cnt)
### BUGGY CODE ###

m,n=map(int,input().split())
print(m**n%(1000000007))


### FIXED CODE ###

x = 1000000007
m,n=map(int,input().split())
print(pow(m,n,x))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
M = []
q = []
for i in range(h):
    line = input().strip()
    M.append(list(line))
    for j in range(w):
        if line[j] == "#":
            M[i][j] = 0
            q.append((j, i))

dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while q:
    next_q = []
    cnt += 1
    for x, y in q:
        for dx,dy in dir:
            next_x, next_y = x + dx, y + dy
            if 0 <= next_y <= h - 1 and 0 <= next_x <= w - 1:
                if M[next_y][next_x] == ".":
                    M[next_y][next_x] = M[y][x] + 1
                    q.append((next_x, next_y))
    q = next_q

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, M[i][j])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
M = []
q = []
for i in range(h):
    line = input().strip()
    M.append(list(line))
    for j in range(w):
        if line[j] == "#":
            M[i][j] = 0
            q.append((j, i))

dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while q:
    next_q = []
    cnt += 1
    for x, y in q:
        for dx,dy in dir:
            next_x, next_y = x + dx, y + dy
            if 0 <= next_y <= h - 1 and 0 <= next_x <= w - 1:
                if M[next_y][next_x] == ".":
                    M[next_y][next_x] = M[y][x] + 1
                    q.append((next_x, next_y))
    q = next_q

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, M[i][j])
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
Qr = [list(input().split()) for i in range(Q)]
isForward = True
for i in range(Q):
    if Qr[i][0] == "1":
        isForward = not(isForward)
    elif (isForward and  Qr[i][1] == "1") or (not(isForward) and Qr[i][1] == "2"):
        S = Qr[i][2] + S
    else:
        S = S + Qr[i][2]
if not(isForward):
    S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
Qr = [list(input().split()) for i in range(Q)]
isForward = True
for i in range(Q):
    if Qr[i][0] == "1":
        isForward = not(isForward)
    elif (isForward and  Qr[i][1] == "1") or (not(isForward) and Qr[i][1] == "2"):
        S.appendleft(Qr[i][2])
    else:
        S.append(Qr[i][2])
S = list(S)
if not(isForward):
    S.reverse()
print("".join(S))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
u = [0 for i in range(len(a))]

def binarySearch(alist, item,exhi):
    first = 0
    last = len(alist)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item and u[midpoint] <= 0 and midpoint != exhi:
            found = True
            u[midpoint] += 1
        else:
            if item > alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1

    return found


b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

sum = 0
i = 0

#print(a)
while True:

    if u[i] > 0:
        i = i + 1
        if i >= len(a)-1:
            break        
        continue

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    if t > a[i]:
        i = i + 1
        if i >= len(a)-1:
            break
        continue

    if t in a :
        idx = 0
        while True:
            try:
                idx = a.index(t,idx)
                if u[idx] == 0 and idx != i:
                    u[idx] += 1
                    sum += 1
                    break
                elif idx == i:
                    break
            except:
                break
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

### FIXED CODE ###

from bisect  import bisect_left

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

sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    #print("2^",t)

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)
### BUGGY CODE ###

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

for i in X:
  t = x.index(i)
  if t < n//2:
    print(x[n//2])
  else:
    print(x[n//2 -1])

### FIXED CODE ###

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

res1 = x[n//2]
res2 = x[n//2 -1]

for i in range(n):
  if X[i] >= res1:
    print(res2)
  elif X[i] <= res2:
    print(res1)