Harryxun/sft_time huggingface dataset:
### 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()))
L = []
for a in A:
  for b in B:
    L.append(a + b)
L.sort(reverse = True)
ans = []
for i, l in enumerate(L):
  if i == K:
    break
  else:
    for c in C:
      ans.append(l + c)
ans.sort(reverse = True)
for i, a in enumerate(ans):
  if i == K:
    break
  else:
    print(a)


### 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.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

L = []
for i, a in enumerate(A):
  for j, b in enumerate(B):
    if i * j > K:
      continue
    else:
      L.append(a + b)

L.sort(reverse = True)
ans = []
for i, l in enumerate(L):
  if i == K:
    break
  else:
    for c in C:
      ans.append(l + c)
ans.sort(reverse = True)
for i, a in enumerate(ans):
  if i == K:
    break
  else:
    print(a)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[]
q=0
for i in range(n):
    p=[int(j) for j in input().split()]
    q=max(q,p[0])
    ab.append(p)
from operator import itemgetter
 
ab.sort(key=itemgetter(1))
ab.reverse()
ab.sort(key=itemgetter(0))
l=[]
import bisect
ans=0
for i in range(1,m+1):
    while True:
        if ab==[]:
            break
        if ab[0][0]<=i:
            insert_index = bisect.bisect_left(l,ab[0][1])  #2
            l.insert(insert_index,ab[0][1])
            del ab[0]
        else:
            break
    if l!=[]:
        ans+=l[-1]
        del l[-1]
        

print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
ab=[]
l=[[] for i in range(m+1)]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    ab.append(tmp)
    a,b=tmp
    if a<=m:
        l[a].append(b)
import heapq
q=[]
ans=0
for i in range(1,1+m):
    for j in l[i]:
        heapq.heappush(q,-j)
    if q:
        ans-=heapq.heappop(q)
print(ans)
### BUGGY CODE ###

S = input()

S_mod = [0] * (len(S)+1)

mod_count = [0] * 2019

for i in range(len(S)):
    S_mod[i] = int(S[i:len(S)])%2019
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))



### FIXED CODE ###

S = input()[::-1]

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

mod_count = [0] * 2019

d = 10

#for i in range(len(S)):
#    S_mod[i] = int(S[i:len(S)])%2019

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))
### BUGGY CODE ###

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

cards = []
for _ in range(a):
    cards.append(1)
for _ in range(b):
    cards.append(0)
for _ in range(c):
    cards.append(-1)

ans = 0
for i in range(k):
    ans += cards[i]

print(ans)


### FIXED CODE ###

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

import sys

ans = 0
if a != 0 and a >= k:
    # a = 1
    print(k)
    sys.exit()
elif a != 0:
    ans += a
    k -= a

if b != 0 and b >= k:
    print(ans)
    sys.exit()
elif b != 0:
    k -= b

ans += k * -1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    inlis = tuple(map(int, input().split()))
    ans = 1
    for i in inlis:
        ans *= i
    if ans > 10 ** 18:
        ans = -1
    print(ans)
    



if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    inlis = list(map(int, input().split()))
    if 0 in inlis:
        ans = 0
    else:
        ans = 1
        for i in inlis:
            ans *= i
            #print(ans)
            if ans > 10 ** 18:
                ans = -1
                break
    print(ans)
    
 
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from operator import mul
from functools import reduce
import bisect
n = int(input())
A = sorted(list(map(int, input().split())))

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

cand = 0
for i in range(n):
    big_num = A[-1 - i]
    th_max = combinations_count(big_num, big_num // 2)
    if cand >= th_max:
        break
    else:
        near_mid_pointer = bisect.bisect_left(A, big_num / 2)
        dif1 = 10**9 + 1
        if near_mid_pointer != 0:
            dif1 = big_num / 2 - A[near_mid_pointer - 1]
        dif2 = A[near_mid_pointer] - big_num / 2
        if dif1 <= dif2:
            if cand < combinations_count(big_num, A[near_mid_pointer - 1]):
                num1 = big_num
                num2 = A[near_mid_pointer - 1]
                cand = combinations_count(big_num, A[near_mid_pointer - 1])

        else:
            if cand < combinations_count(big_num, A[near_mid_pointer]):
                num1 = big_num
                num2 = A[near_mid_pointer]
                cand = combinations_count(big_num, A[near_mid_pointer])

print(num1, num2)

### FIXED CODE ###

from operator import mul
from functools import reduce
import bisect
n = int(input())
A = sorted(list(map(int, input().split())))

big_num = A[-1]
near_mid_pointer = bisect.bisect_left(A, big_num / 2)
dif1 = 10**9 + 1
if near_mid_pointer != 0:
        dif1 = big_num / 2 - A[near_mid_pointer - 1]
dif2 = A[near_mid_pointer] - big_num / 2
if dif1 <= dif2:
    num1 = big_num
    num2 = A[near_mid_pointer - 1]

else:
    num1 = big_num
    num2 = A[near_mid_pointer]

print(num1, num2)
### BUGGY CODE ###


def make_mat(grid):
    H = len(grid)
    W = len(grid[0])
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if grid[h][w] == "#":
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if grid[h][w] == ".":
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append(list(input().rstrip()))

A = make_mat(grid)
grid_t = list(zip(*grid))
B = list(zip(*make_mat(grid_t)))
res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[h][w], res)

print(res-1)

### FIXED CODE ###

def make_mat(grid, H, W):
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if (grid[h]>>w)&1 == 1:
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if (grid[h]>>w)&1 == 0:
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())


grid = []
grid_t = [0]*W
for h in range(H):
    temp = 0
    for w, s in enumerate(input().rstrip()):
        if s=="#":
            temp += 1<<w
            grid_t[w] += 1<<h
    grid.append(temp)

A = make_mat(grid, H, W)
B = make_mat(grid_t, W, H)

res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[w][h], res)

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

a, b, x = [int(i) for i in input().split()]
c = 0
d = 0
while c <= b:
    if a <= c:
        d += 1
    c += x
print(d)

### FIXED CODE ###

a, b, x = map(int, input().split())
if a%x == 0:
    print((b//x+1) - (a//x))
else:
    print((b//x+1) - (a//x+1))
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
graph=[[float('inf')]*w for _ in range(h)]
queue=deque()
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            queue.append([i,j])
            graph[i][j]=0

def bfs():
    while queue:
        x,y=queue.popleft()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=x+dx<h and 0<=y+dy<w:
                if graph[x+dx][y+dy]==float('inf'):
                    graph[x+dx][y+dy]=graph[x][y]+1
                    queue.append([x+dx,y+dy])
bfs()
print(max(max(graph[s]) for s in range(h)))

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='#' else float('inf') for i in list(input())] for _ in range(h)]
graph=np.array(graph)
for x in range(w-1):
    graph[:,x+1]=np.minimum(graph[:,x]+1,graph[:,x+1])
for x in range(w-1,0,-1):
    graph[:,x-1]=np.minimum(graph[:,x]+1,graph[:,x-1])
for y in range(h-1):
    graph[y+1,:]=np.minimum(graph[y,:]+1,graph[y+1,:])
for y in range(h-1,0,-1):
    graph[y-1,:]=np.minimum(graph[y,:]+1,graph[y-1,:])

print(int(np.max(graph)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions

N = int(input().rstrip())
As = list(map(int, input().rstrip().split()))


def gcd_list(cur_gcd, numbers):
    res = cur_gcd
    for num in numbers:
        res = fractions.gcd(res, num)
    return res


max_gcd = max(As)
if N > 2:
    # i == 0
    # others = As[1:]
    max_gcd = gcd_list(max_gcd, As[1:])
    tmp_gcd = As[0]

    # i >= 1
    for i in range(1, N):
        # others = As[i + 1:]
        max_gcd = max(gcd_list(tmp_gcd, As[i + 1:]), max_gcd)
        tmp_gcd = fractions.gcd(tmp_gcd, As[i])

print(max_gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions

N = int(input().rstrip())
A = [0] + list(map(int, input().rstrip().split())) + [0]

L = [0] * (N + 2)
R = [0] * (N + 2)

for i in range(0, N):
    L[i + 1] = fractions.gcd(L[i], A[i + 1])

for i in range(N, 0, -1):
    R[i] = fractions.gcd(R[i + 1], A[i])

print(max(fractions.gcd(L[i], R[i + 2]) for i in range(0, N)))
### BUGGY CODE ###

import numpy as np

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


checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1


dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp += np.array(mae_zero)

print(dp[N] % 998244353)

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

# multiple
line = input()
ln = []
combi = 0
for i in range(len(line)):
    n = int(line[i:])% 2019 
    combi += ln.count(n)
    ln.append(n)
    #print( str(i) +',' +str(combi)+','+ str(n), ln)
n = 0
combi += ln.count(n)
ln.append(n)
#print( str(i) +',' +str(combi)+','+ str(n), ln)
print(combi)

### FIXED CODE ###

# multiple
line = input()
ln = 0
d = 1
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*d))%2019
    counts[ti1] += 1
    ln = ti1
    d *= 10
    d %= 2019
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))
### BUGGY CODE ###

import math
K = int(input())
gcd: int = 0
a: int = 0
b: int = 0
c: int = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in (range(1, K+1)):
            tmp = math.gcd(a, b)
            gcd += math.gcd(tmp, c)
    
print(gcd)


### FIXED CODE ###

import math
K = int(input())
gcd: int = 0
a: int = 0
b: int = 0
c: int = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in (range(1, K+1)):
            tmp = math.gcd(a, b)
            gcd += math.gcd(tmp, c)
    
print(gcd)
### BUGGY CODE ###

from queue import Queue
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[0]*N for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1][graf2-1] = 1
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = Queue(3*N+1)
q.put((S, 0))
while not q.empty():
    v, l = q.get()
    for i in range(N):
        if vector[v][i] != 1:
            continue
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.put((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = deque()
q.append((S, 0))
while q:
    v, l = q.popleft()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.append((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))
### BUGGY CODE ###

#ないよりも10倍以上早くなる
import sys
input = sys.stdin.readline

K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    count=0
    Ks=[]
    wa=[]
    for i in range(K+1):
        Ks.append(i)
    X,Y,Z =Ks,Ks,Ks
    for x in X:
        if x<=S:
            X_=[]
            X_.append(x)
            for y in Y:
                if y<=S:
                    X_Y_=[]
                    X_Y_=list(X_)
                    X_Y_.append(y)
                    for z in Z:
                        if z<=S:
                            X_Y_Z_=list(X_Y_)
                            X_Y_Z_.append(z) 
                            wa_=sum(X_Y_Z_)
                            wa.append(wa_)
    for j in wa:
        if j==S:
            count+=1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

from collections import Counter
N = int(input())
s = [input() for i in range(N)]

c = []
ans = 0
for i in range(N):
    c.append(Counter(s[i]))

for i in range(N):
    for j in range(i+1, N):
        if c[i] == c[j]:
            ans += 1

print(ans)

### FIXED CODE ###

#from collections import defaultdict
N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

#print(s)
#d = defaultdict(int)
d = dict()

ans = 0
for key in s:
    if key not in d:
        d[key] = 0
    else:
        ans += d[key]    
    d[key] += 1

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

def solve(N, A):
    ret = 1
    upper = 10**18
    for a in A:
        ret *= a
    return ret if ret <= upper else -1

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))

### FIXED CODE ###

def solve(N, A):
    ret = 1
    upper = 10**18
    if 0 in A:
      return 0
    for a in A:
        ret *= a
        if upper < ret:
          return -1
    return ret
 
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))
### BUGGY CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


def main():
    [N, M, X] = list(map(int, input().split()))

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)


    cost = 0
    status = [0]*M
    minValues = [sys.maxsize]*M
    for n in range(N):
        cost += l[n][0]
        for m in range(M):
            if l[n][m + 1] < minValues[m]:
                minValues[m] = l[n][m + 1]
            status[m] += l[n][m + 1]
    
    for i in range(len(status)):
        if status[i] < X:
            print(-1)
            return
        if status[i] - minValues[i] < X:
            print(cost)
            return 

    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            if min_cost < cost:
                break
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations):
    price = 0
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  # couldn't understand
            return -1
    return price


def main():
    global N, M, X, BOOKS
    N, M, X = list(map(int, input().split()))
    BOOKS = [list(map(int, input().split())) for i in range(N)]

    ans = float('inf')
    for i in range(1, 2 ** N):  # => 1: at least one book should be buy
        price = calc_price([(i >> j) & 1 for j in range(N)])
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


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

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = [0] * (K+1)
    dp[0] = 1
    nonzeros = [1]
    for a in As:
        ndp = []
        nonzero = 0
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t == 0:
                ndp.append(0)
            else:
                nonzero |= 1 << i
                ndp.append(1)
        nonzeros.append(nonzero)
        dp = ndp
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()


### FIXED CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = [[0]*t for _ in range(n+1)]
for i, a in enumerate(A[:-1]):
  for j in range(t):
    if j < a:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-a]+B[i], dp[i][j])
ans = 0
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
for i in range(n-1):
  ans = max(ans, dp[i+1][-1] + maxB[i+1])
print(ans)

### FIXED CODE ###

n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)
### BUGGY CODE ###

n = int(input())
x = input().split(" ")
b_x = [i for i in range(n)]
c = list(zip(map(int, x), b_x))
c.sort()
x, b_x = zip(*c)
for i in range(n):
    if b_x.index(i) < n//2:
            print(x[n//2])
    else:
            print(x[n//2-1])

### FIXED CODE ###

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

#A
def A():
    n = I()
    print(n*800-200*(n//15))

#B
def B():
    k = I()
    ans = 0
    for i in range(1,k):
        for j in range(i+1,k+1):
            if (i%2)^(j%2):
                ans += 1
    print(ans)

#C
def C():
    x,t = LI()
    print(max(0,x-t))

#D
def D():
    n = I()
    ans = 1
    for i in range(1,n+1):
        ans *= i
        ans %= mod
    print(ans)

#E
def E():
    x,y,s,t = LI()
    return

#F
def F():
    n = I()
    x = LI()
    a = sorted(x)
    for i in range(n):
        j = bisect.bisect_left(a,x[i])
        if j >= n//2:
            print(a[n//2-1])
        else:
            print(a[n//2])

#G
def G():
    return

#H
def H():
    return

def J():
    return

def K():
    return

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

n = int(input())
ans = 0

l = []

for _ in range(n):
    s = sorted(input())
    for le in l:
        if le == s:
            ans += 1

    l.append(s)

print(ans)

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()