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

class Node:
  def __init__(self):
    self.counter = 0
    self.childs = []
    self.parents = set()
  def add_child(self, node):
    self.childs.append(node)
  def add_parents(self, node):
    self.parents.add(node)

N, Q = [int(i) for i in input().split()]
ndic = {}
for i in range(1, N+1):
  ndic[i] = Node()
  ndic[i].add_child(ndic[i])
for i in range(N-1):
  a, b = [int(i) for i in input().split()]
  ndic[a].add_child(ndic[b])
  ndic[b].add_parents(ndic[a])
  for n in ndic[a].parents:
    n.add_child(ndic[b])  
    ndic[b].add_parents(n)

for i in range(Q):
  p, x = [int(i) for i in input().split()]
  for j in ndic[p].childs:
    j.counter += x
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

### FIXED CODE ###

n, q = map(int, input().split())
 
tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
cnt = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
 
check = [0]*n
 
tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)
 
 
print(" ".join(map(str, cnt)))
### BUGGY CODE ###

n = int(input())

m = 10 ** 9 + 7
ans = 1
for i in range(n):
    ans *= i + 1
print(ans % m)


### FIXED CODE ###

import math
n = int(input())

m = 10 ** 9 + 7

print(math.factorial(n) % m)
### BUGGY CODE ###

slist = list(str(input()))
L = len(slist)
count = 0
fcount = 0
i = 0
while i < 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
        fcount+=1
        i+=1
    elif i == L-1:
        if fcount == 0:
            break
        else:
            i = 0
            fcount = 0
    else:
        i+=1
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 ###

import sys
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.per = list(range(n))
        self.point = n*(n-1) // 2
        self.counts = [1]*n

    def root(self, x):
        while self.per[x] != x:
            x = self.per[x]
        return x
        # if self.per[x] == x:
        #     return x
        # return self.root(self.per[x])

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        self.per[rx] = ry
        self.point -= self.counts[ry] * self.counts[rx]
        self.counts[ry] += self.counts[rx]
        self.counts[rx] = 0

    def is_same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


u = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(u.point)
    x, y = a-1, b-1
    u.union(x, y)

# print(*results[::-1])
for r in results[::-1]:
    print(r)


### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        self.par[ry] = rx
        return True

    def is_same(self, x, y):
        rx, ry = self.root(x), self.root(y)
        return rx == ry

    def get_size(self, x):
        return self.size[self.root(x)]


uf = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(uf.point)
    x, y = a-1, b-1
    uf.unite(x, y)

print(*results[::-1], sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
  tmp = 0
  for j in a:
    tmp += (j>>i)&1
  ans += tmp*(n-tmp)*(2**i)
  ans %= 10**9+7
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
  tmp = sum([1 for j in a if (j>>i)&1])
  ans += tmp*(n-tmp)*(2**i)
  ans %= 10**9+7
print(ans)
### BUGGY CODE ###

def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(x*0.5+1),2):
            if x % j == 0: return False
        else: return True

n = input()
count = 0
for i in range(n):
    if prime(input()): count += 1
print count

### FIXED CODE ###

import math
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            return True 
n = input()
count = 0
for i in xrange(n):
    if prime(input()): count += 1
print count
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

D = []
for i in range(X):
    for j in range(Y):
        D.append(A[i] + B[j])

D.sort(reverse=True)
E = []
for i in range(min(K, len(D))):
    for j in range(Z):
        E.append(D[i] + C[j])

E.sort(reverse=True)
for i in range(K):
    print(E[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

D = []
for i in range(X):
    for j in range(Y):
        D.append(A[i] + B[j])

D.sort(reverse=True)
E = []
for i in range(min(K, len(D))):
    for j in range(Z):
        E.append(D[i] + C[j])

E.sort(reverse=True)
for i in range(K):
    print(E[i])
### BUGGY CODE ###

k, s = map(int, input().split())

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import math
from functools import reduce

def calc(a, b, c):
    return reduce(math.gcd, set([a, b, c]))

def solve(k):
    import itertools
    pattern = itertools.product(range(1, k+1), repeat=3)

    count = 0
    for x in pattern:
        gcd = calc(x[0], x[1], x[2])
        count += gcd

    return count


k = int(input())

print(solve(k))


### FIXED CODE ###

from math import gcd

k = int(input())

ir = range(1, k+1)
jr = range(1, k+1)
lr = range(1, k+1)

count = 0
for i in ir:
  for j in jr:
    for l in lr:
      count += gcd(i, gcd(j, l))

print(count)
### BUGGY CODE ###

from math import factorial as fac
from collections import defaultdict as ddict
n,m = map(int,input().split())
d = ddict(int)
ans = 1
mod = 10**9+7
def cc(n,r):
  return fac(n)//fac(r)//fac(n-r)
for i in range(2,int(m**.5)+1):
  while m % i == 0:
    d[i] += 1
    m //= i
if m > 1:
  d[m] += 1
for x in d:
  ans = ans * cc(d[x]+n-1,d[x])%mod
print(ans)

### FIXED CODE ###

from math import factorial as fac
from collections import defaultdict as ddict
n,m = map(int,input().split())
d = ddict(int)
ans = 1
mod = 10**9+7
def f2(n,r):
  ret = 1
  for i in range(n,n-r,-1):
    ret *= i
  return ret
def cc(n,r):
  t = min(r,n-r)
  return f2(n,t)//fac(t)
for i in range(2,int(m**.5)+1):
  while m % i == 0:
    d[i] += 1
    m //= i
if m > 1:
  d[m] += 1
for x in d:
  ans = ans * cc(d[x]+n-1,d[x])%mod
print(ans)
### BUGGY CODE ###

N,M,Q=map(int,input().split())
N=550
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)

### FIXED CODE ###

N,M,Q=map(int,input().split())
N=550
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)
### BUGGY CODE ###

N, K = map(int, input().split())
n1 = N-K
mod = 10**9+7
def comb(n, k):
    ans = 1
    for i in range(1, k+1):
        ans = ans*(n+1-i)//i
    return ans

for i in range(1, K+1):
    ans = comb(n1+1, i)
    ans %= mod
    ans *= comb(K-1, i-1)
    ans %= mod
    print(ans)
    

### FIXED CODE ###

N, K = map(int, input().split())
n1 = N-K
mod = 10**9+7
def comb(n, k):
    ans = 1
    for i in range(1, k+1):
        ans = ans*(n+1-i)//i
    return ans

for i in range(1, K+1):
    ans = comb(n1+1, i)
    ans %= mod
    ans *= comb(K-1, i-1)
    ans %= mod
    print(ans)
### BUGGY CODE ###

n=int(input())
now=0
for i in range(1,n+1):
    now+=sum([j for j in range(1,n+1) if j%i==0])
print(now)

### FIXED CODE ###

n=int(input())
now=0
for i in range(1,n+1):
    now+=(i+(i*(n//i)))*(n//i)//2
print(now)
### BUGGY CODE ###

import numpy as np
from numba import njit


@njit("i2(i2, i2, i2[:,:])")
def solve(H, W, field):
    u = field.copy()
    d = field.copy()
    l = field.copy()
    r = field.copy()

    for i in range(1, H):
        u[i] = (u[i - 1] + 1) * u[i]
        d[-i - 1] = (d[-i] + 1) * d[-i - 1]

    for j in range(1, W):
        l[:, j] = (l[:, j - 1] + 1) * l[:, j]
        r[:, -j - 1] = (r[:, -j] + 1) * r[:, -j - 1]

    return (u + d + l + r - 3).max()


H, W = map(int, input().split())
field = [[c == "." for c in input()] for _ in range(H)]
field = np.array(field, dtype=np.int16)

print(solve(H, W, field))


### FIXED CODE ###

import numpy as np


H, W = map(int, input().split())
field = [[c == "." for c in input()] for _ in range(H)]
field = np.array(field, dtype=np.int16)

u = field.copy()
d = field.copy()
l = field.copy()
r = field.copy()

for i in range(1, H):
    u[i] = (u[i - 1] + 1) * u[i]
    d[-i - 1] = (d[-i] + 1) * d[-i - 1]

for j in range(1, W):
    l[:, j] = (l[:, j - 1] + 1) * l[:, j]
    r[:, -j - 1] = (r[:, -j] + 1) * r[:, -j - 1]

print((u + d + l + r - 3).max())
### BUGGY CODE ###

N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range(int(pow(P,1/N))+1,0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(i,n+1,i):
        ans += j
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    x = n//i
    ans += i*(x*(x+1)//2)
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

# nCr -- START --
def nCr(n,r):
  if n<r:
    return 0
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
# nCr --- END ---

def main():
  n=I()
  l=LI()
  mp=[0]*(n+1)

  sl=summarize_list(l)
  # print(sl)

  ans=0
  for x,c in sl:
    mp[x]=c
    ans+=nCr(c,2)

  # print(mp)
  # print(ans)

  for x in l:
    print(ans-nCr(mp[x],2)+nCr(mp[x]-1,2))

main()
# print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

# nCr -- START --
def nCr(n):
  return (n*(n-1))//2
# nCr --- END ---

def main():
  n=I()
  l=LI()
  mp=[0]*(n+1)

  sl=summarize_list(l)
  # print(sl)

  ans=0
  for x,c in sl:
    mp[x]=c
    ans+=nCr(c)

  # print(mp)
  # print(ans)

  for x in l:
    print(ans-nCr(mp[x])+nCr(mp[x]-1))

main()
# print(main())
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    i = 3
    while i < n:
        if n%2 == 0 or n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))



### FIXED CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    if n % 2 == 0:
        return 0
    i = 3
    while i <= n/i:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))
### BUGGY CODE ###

n,m=map(int,input().split())
a1=[]
an=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.append(bi)
    elif bi==n:
        an.append(ai)

a1.sort()
an.sort()

flag = False

for i in range(len(a1)):
    if a1[i] in an:
        flag = True
        break
  
if flag==True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###


n,m=map(int,input().split())
a1=set()
an=set()
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.add(bi)
    elif bi==n:
        an.add(ai)

if len(a1&an)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7
def main():
	MAXN = 1000001
	spf = [0 for i in range(MAXN)] 
	sett = set()
	def sieve(): 
		spf[1] = 1
		for i in range(2, MAXN):  
			spf[i] = i 

		for i in range(4, MAXN, 2): 
			spf[i] = 2

		for i in range(3, ceil(sqrt(MAXN))): 
			
			if (spf[i] == i): 
				
				for j in range(i * i, MAXN, i): 
					
					if (spf[j] == j): 
						spf[j] = i
	sieve()
	
	# def getFactorization(x): 
	# 	ret = set() 
	# 	# print("This is for ",x)
	# 	flag = 1
	# 	while (x != 1):
	# 		# print("\t", x, spf[x], sett)
	# 		if spf[x] in sett:
	# 			flag = 0
	# 		ret.add(spf[x]) 
	# 		x = x // spf[x]
	# 	sett = sett.union(ret)
	# 	return flag


	n = int(input()); arr = read()
	gcd_ = arr[0]
	f1 = 0; f2 = 1
	for i in arr:
		gcd_ = gcd(gcd_, i)
		# res = getFactorization(i)
		x = i
		ret = set() 
		# print("This is for ",x)
		flag = 1
		while (i != 1):
			# print("\t", i, spf[x], sett)
			if spf[i] in sett:
				flag = 0
			ret.add(spf[i]) 
			i = i // spf[i]
		sett = sett.union(ret)
		# print(x, flag)
		f1 += flag; f2 &= flag

	# print(sett)

	if f2:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")



	



if __name__ == "__main__":
	main()

# import math as mt 




# # def getFactorization(x): 
# # 	ret = list() 
# # 	while (x != 1): 
# # 		ret.append(spf[x]) 
# # 		x = x // spf[x] 

# # 	return ret 
# sieve()
# # print(spf[:100])


### FIXED CODE ###

import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7
def main():
	MAXN = 1000001
	spf = [0 for i in range(MAXN)] 
	# sett = set()
	def sieve(): 
		spf[1] = 1
		for i in range(2, MAXN):  
			spf[i] = i 

		for i in range(4, MAXN, 2): 
			spf[i] = 2

		for i in range(3, ceil(sqrt(MAXN))): 
			
			if (spf[i] == i): 
				
				for j in range(i * i, MAXN, i): 
					
					if (spf[j] == j): 
						spf[j] = i
	sieve()
	n = int(input()); arr = read()
	gcd_ = arr[0]
	check = [0]*(10**6 +1)
	f1 = 0; f2 = 1
	for i in arr:
		gcd_ = gcd(gcd_, i)
		# x = i
		ret = []
		flag = 1
		while (i != 1):
			if check[spf[i]]:# in sett:
				flag = 0
			ret.append(spf[i]) 
			i = i // spf[i]
		for j in ret:check[j] = 1
		# sett = sett.union(ret)
		# print(x, flag)
		f1 += flag; f2 &= flag

	# print(sett)

	if f2:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")



	



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

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(n):
  dp_temp = 0
  for j in range(1, k+1):
    if i-j > -1:
      temp = dp[i-j] + abs(h[i]-h[i-j])
      if dp_temp == 0:
        dp_temp = temp
      else:
        if dp_temp > temp:
          dp_temp = temp
  dp[i] = dp_temp
print(dp[n-1])
  

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(n):
  dp_temp = 0
  flag = 0
  for j in range(1, k+1):
    if i-j >= 0:
      temp = dp[i-j] + abs(h[i]-h[i-j])
      if flag == 0:
        dp_temp = temp
        flag = 1
      else:
        if dp_temp >= temp:
          dp_temp = temp
    else:
      break
  dp[i] = dp_temp
print(dp[n-1])
### BUGGY CODE ###

import itertools

N=int(input())
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0
for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(counter)
        counter=1
if counter!=0:
            counts.append(counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer+=sum(kumiawase)
print(answer%(7+10**9))

### FIXED CODE ###

N=list(range(int(input())))
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0

for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(1+counter)
        counter=1
if counter!=0:
    counts.append(1+counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

answer=soujou(counts)-1
print(answer%(7+10**9))
### BUGGY CODE ###

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

# input
N = int(input())
X = list(map(int, input().split()))

# solve
X_sorted = sorted(X)
for i in range(len(X)):
    Y = list(X_sorted)
    Y.remove(X[i])
    print(Y[int((len(Y)+1)/2-1)])


### FIXED CODE ###

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

# input
N = int(input())
X = list(map(int, input().split()))

# solve
X_sorted = sorted(X)
n0 = X_sorted[int(len(X_sorted)/2-1)]
n1 = X_sorted[int(len(X_sorted)/2)]
for i in range(len(X)):
    if (n1 > X[i]):
        print(n1)
    elif (n0 <= X[i]):
        print(n0)
### BUGGY CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB.append(row)
 
  dp = [[set([]) for j in range(w+1)] for i in range(h+1)]
  dp[0][0].add(AB[0][0])
  for i in range(h):
    for j in range(w):
      dif1 = 0
      dif2 = 0
      if j < w - 1:
        dif1 = AB[i][j+1]
      if i < h - 1:
        dif2 = AB[i+1][j]
      for item in dp[i][j]:
        if j < w - 1:
          dp[i][j+1].add(item+dif1)
          dp[i][j+1].add(abs(item-dif1))
        if i < h - 1:
          dp[i+1][j].add(item+dif2)
          dp[i+1][j].add(abs(item-dif2))
  print(min(dp[h-1][w-1]))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

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

A = sorted(A)
B = sorted(B)
C = sorted(C)
b_list = {}
for i in range(N):
    for j in range(N):
        if B[i] < C[j]:
            b_list[i] = N - j
            break
        b_list[i] = 0
m = 0

for i in range(N):
    for j in range(N):
        if B[j] > A[i]:
            m += sum(list(b_list.values())[j:])
            break

print(m)


### FIXED CODE ###

from bisect import bisect_right
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

B = sorted(B)
C = sorted(C)
b_list = {N:0}
for i in range(N-1,-1,-1):
    j = bisect_right(C,B[i])
    b_list[i] = N - j + b_list[i+1]
m = 0
for i in range(N):
    j = bisect_right(B,A[i])
    m += b_list[j]
print(m)
### BUGGY CODE ###

import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
for i in range(n-1):
    ans = (l[i])**2%m
    if ans in l:
        loop_start = int(np.where(l==ans)[0])
        loop_num, mod = divmod((n-loop_start),(i-loop_start+1))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
print(np.sum(l))

### FIXED CODE ###

import sys

n,x,m = (int(i) for i in input().split())
l = [x]
ans = x
memo_array = [-1]*(m+1)

for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(sum(l[:idx]) + sum(l[idx:])*(loop_num)+sum(l[idx:idx+mod]))
        sys.exit()
    l.append(ans)
    memo_array[ans]=i
print(sum(l))