A group of $n$ friends living in an $m$-dimensional hyperspace want to meet up at some central location. The hyperspace is in the form of an $m$-dimensional grid, and each person can only move along grid lines. For example, to go from $(0,0)\rightarrow(1,1)$ in a $2$-dimensional space, one possible route is $(0,0)\to(0,1)\to(1,1)$ for a total distance traveled of $2$ units.

Given the coordinates, $(X[0,1,\ldots,m-1])$, for $n$ friends, find a point at which all $n$ friends can meet such that the total sum of the distances traveled by all $n$ friends is minimal. If there are multiple such points, choose the lexicographically smallest one. The point $P_1[0,1,\ldots,m-1]$ is lexicographically smaller than $P_2[0,1,\ldots,m-1]$ if there exists such $j\lt m$ that $\forall i<j P_1[i]=P_2[i]$ and $P_1[j]<P_2[j]$.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $m$. 

Each line ${i}$ of the $n$ subsequent lines contains $m$ space-separated integers describing the respective coordinates (i.e., $x_0,x_1,\ldots,x_{m-1}$) for friend ${i}$.

Constraints

$1\leq n\leq10^4$  
$1\leq m\leq10^2$  
$-10^9\leq x_i\leq10^9$  

Output Format

Print $m$ space-separated integers describing the coordinates of the meeting point.

Sample Input
3 2
1 1
2 2
3 3

Sample Output
2 2

Explanation

There are $n=3$ friends (we'll call them ${a}$, ${b}$, and ${c}$) located at points $a=(1,1)$, $b=(2,2)$, and $c=(3,3)$. The minimal solution is for friends ${a}$ and ${c}$ to meet at friend ${b}$'s current location; this means ${a}$ travels $2$ units from $(1,1)$ to $(2,2)$, ${c}$ travels $2$ units from $(3,3)$ to $(2,2)$, and ${b}$ stays put at $(2,2)$. The total distance traveled by all friends is $2+0+2=4$, which is minimal. Thus, we print $m=2$ space-separated integers describing the coordinate where the $n=3$ friends meet: 2 2.

Difficulty: MEDIUM
Tags: Geometry

Starter code:

Solutions:
import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()


from statistics import median
(n, m) = map(int, input().split())
points = []
for _ in range(n):
	points.append(list(map(int, input().split())))
for i in range(m):
	vals = sorted((point[i] for point in points))
	if len(vals) % 2 == 0:
		vals.pop(len(vals) - 1)
	print(median(vals), end=' ')


import math
(n, m) = [int(tmp) for tmp in input().split()]
a = [[0] * n for _ in range(m)]
for i in range(n):
	j = 0
	for tmp in input().split():
		a[j][i] = int(tmp)
		j += 1
for j in range(m):
	b = [0] * n
	for i in range(n):
		b[i] = a[j][i]
	b = sorted(b)
	print(b[math.floor((n - 1) / 2)], end=' ')


import sys
(m, n) = map(int, sys.stdin.readline().split(' '))
x = [[] for i in range(0, n)]
for _ in range(0, m):
	for (i, c) in enumerate(sys.stdin.readline().split(' ')):
		x[i].append(int(c))
for i in range(0, n):
	x[i] = sorted(x[i])
	print(x[i][(m - 1) // 2], end=' ')


(n, m) = [int(x) for x in input().strip().split()]
result = [[] for _ in range(m)]
for _ in range(n):
	for (id, value) in enumerate(input().strip().split()):
		result[id].append(int(value))
result = [str(sorted(x)[(n - 1) // 2]) for x in result]
print(' '.join(result))


(n, m) = map(int, input().split())
coords = [[] for i in range(m)]
for i in range(n):
	a = map(int, input().split())
	for (idx, x) in enumerate(a):
		coords[idx].append(x)
result = []
for i in range(m):
	coords[i].sort()
	result.append(str(coords[i][(n - 1) // 2]))
print(' '.join(result))


def readintline():
	return map(int, input().split())
(n, m) = readintline()
c = []
for i in range(m):
	c.append([])
for i in range(n):
	l = list(readintline())
	for j in range(m):
		c[j].append(l[j])
a = []
for i in range(m):
	a.append(sorted(c[i])[(n - 1) // 2])
print(' '.join(map(str, a)))


from statistics import median_low
(n, m) = map(int, input().split())
data = []
for _ in range(n):
	cur_data = list(map(int, input().split()))
	data.append(cur_data)
data = zip(*data)
result = []
for x in data:
	result.append(str(median_low(x)))
print(' '.join(result))


(n, m) = map(int, input().split())
pos = [[0 for i in range(n)] for j in range(m)]
for i in range(n):
	for (j, p) in enumerate(map(int, input().split())):
		pos[j][i] = p
for j in range(m):
	pos[j].sort()
print(*(pos[j][(n - 1) // 2] for j in range(m)))


(n, m) = map(int, input().split())
values = [[] for _ in range(m)]
for _ in range(n):
	for (x, vs) in zip(map(int, input().split()), values):
		vs.append(x)
print(' '.join((str(sorted(vs)[(n - 1) // 2]) for vs in values)))


(N, M) = [int(X) for X in input().split(' ')]
pos = [[] for _ in range(M)]
sums = [0] * M
for _ in range(N):
	newp = [int(X) for X in input().split(' ')]
	for (I, X) in enumerate(newp):
		pos[I].append(X)
for I in range(M):
	v = list(sorted(pos[I]))
	if N % 2:
		sums[I] = v[N // 2]
	else:
		sums[I] = v[(N - 1) // 2]
print(' '.join([str(X) for X in sums]))


import itertools

def solve(n, m, L):
	mins = []
	maxs = []
	medianIndex = (n - 1) // 2
	answer = []
	for i in range(m):
		iths = sorted((x[i] for x in L))
		answer.append(iths[medianIndex])
	return answer
(n, m) = [int(x) for x in input().split()]
L = [tuple((int(x) for x in input().split())) for i in range(n)]
p = solve(n, m, L)
print(*p)


(n, m) = map(int, input().split())
points = [[] for i in range(m)]
meeting_point = []
for i in range(n):
	point = list(map(int, input().split()))
	for j in range(m):
		points[j].append(point[j])
for j in range(m):
	points[j].sort()
	if n % 2 == 0:
		med = points[j][n // 2 - 1]
	else:
		med = points[j][n // 2]
	meeting_point.append(med)
print(' '.join(map(str, meeting_point)))


import statistics
(n, m) = map(int, input().split())
f = []
for i in range(n):
	f.append(list(map(int, input().split())))
p = []
for i in range(m):
	p.append(statistics.median_low([f[c][i] for c in range(n)]))
print(*p)


(n, m) = [int(i) for i in input().split()]
matrix = [[0 for j in range(n)] for i in range(m)]
for j in range(n):
	for (i, el) in enumerate(input().split()):
		matrix[i][j] = int(el)
ans = [0] * m
for i in range(m):
	matrix[i].sort()
	(pr_l, pr_r) = ([0] * n, [0] * n)
	for j in range(1, n):
		pr_l[j] = pr_l[j - 1] + j * (matrix[i][j] - matrix[i][j - 1])
		pr_r[n - 1 - j] = pr_r[n - j] + j * (matrix[i][n - j] - matrix[i][n - 1 - j])
	mn = pr_l[0] + pr_r[0]
	mnind = 0
	for j in range(1, n):
		if pr_l[j] + pr_r[j] < mn:
			(mn, mnind) = (pr_l[j] + pr_r[j], j)
	print(matrix[i][mnind], end=' ')


(n, m) = map(int, input().split())
points = []
for _ in range(n):
	point = tuple(map(int, input().split()))
	points.append(point)
index = n // 2 if n % 2 == 1 else n // 2 - 1
ans = []
for i in range(m):
	coords = [point[i] for point in points]
	coords.sort()
	ans.append(coords[index])
print(' '.join(map(str, ans)))


def median(l):
	l.sort()
	if len(l) % 2 == 0:
		return l[len(l) // 2 - 1]
	else:
		return l[len(l) // 2]
(n, m) = [int(x) for x in input().split()]
dimensions = [[] for x in range(m)]
for i in range(n):
	d = input().split()
	for j in range(m):
		dimensions[j].append(int(d[j]))
print(' '.join([str(median(dimensions[x])) for x in range(m)]))


(n, m) = map(int, input().split())
import math
ar = []
for _ in range(n):
	ar.append([int(i) for i in input().split()])
ans = []
for i in range(m):
	temp = 0
	line = []
	for j in range(n):
		line.append(ar[j][i])
		temp += ar[j][i]
	line.sort()
	if n % 2 == 0:
		p = n // 2 - 1
	else:
		p = n // 2
	ans.append(line[p])
final = ''
for x in range(len(ans)):
	final += str(ans[x]) + ' '
print(final.strip())


from operator import add
from operator import sub
(n, m) = map(int, input().split())
pts = []
for i in range(m):
	pts.append([])
for i in range(n):
	l = list(map(int, input().split()))
	for j in range(m):
		pts[j].append(l[j])
for i in range(m):
	pts[i].sort()
idx = (n - 1) // 2
for i in range(m):
	print(pts[i][idx], end=' ')


import math

def findIndex(lista):
	lista.sort()
	n = len(lista)
	return lista[(n - 1) // 2]
(n, m) = list(map(int, input().split()))
lista = [[] for i in range(0, m)]
for i in range(0, n):
	inp = list(map(int, input().split()))
	for j in range(0, m):
		lista[j].append(inp[j])
for i in range(0, m - 1):
	print(findIndex(lista[i]), end=' ')
print(findIndex(lista[m - 1]))


(n, m) = [int(s) for s in input().split()]
a = []
for i in range(n):
	a.append([int(s) for s in input().split()])
b = []
for j in range(m):
	c = []
	for i in range(n):
		c.append(a[i][j])
	c.sort()
	if n % 2 == 0:
		b.append(min(c[n // 2 - 1], c[n // 2]))
	else:
		b.append(c[n // 2])
print(' '.join([str(x) for x in b]))


(n, m) = [int(i) for i in input().split()]
coords = []
for i in range(m):
	coords.append([])
for i in range(n):
	coord = [int(i) for i in input().split()]
	for j in range(m):
		coords[j].append(coord[j])

def find_min_dist(coord):
	coord.sort()
	n = len(coord)
	d = 0
	min_d = 0
	right = n - 1
	min_x = coord[0]
	for i in range(1, len(coord)):
		d -= (coord[i] - coord[i - 1]) * (right - 1)
		if d < min_d:
			min_d = d
			min_x = coord[i]
		right -= 2
	return min_x

def get_dist(coord):
	dist = []
	for x in coord:
		total = 0
		for y in coord:
			total += abs(y - x)
		dist.append(total)
	return dist
point = []
for coord in coords:
	point.append(find_min_dist(coord))
print(' '.join([str(p) for p in point]))


(n, m) = map(int, input().split(' '))
cum = []
for j in range(0, m):
	cum.append([])
for i in range(0, n):
	x = [int(x_temp) for x_temp in input().strip().split()]
	for j in range(0, m):
		cum[j].append(x[j])
for j in range(0, m):
	cum[j].sort()
if n % 2 == 0:
	s = int(n / 2 - 1)
else:
	s = int((n - 1) / 2)
for i in range(0, m):
	print(cum[i][s], end=' ', flush=True)


import statistics
(n, m) = map(int, input().split(' '))
x = []
for i in range(n):
	x.append([int(temp) for temp in input().split(' ')])
f = []
l = [0] * n
for j in range(m):
	for k in range(n):
		l[k] = x[k][j]
	f.append(sorted(l))
ans = [0] * m
if n % 2 != 0:
	for _ in range(m):
		ans[_] = int(statistics.median(f[_]))
	print(' '.join((str(i) for i in ans)))
else:
	for _ in range(m):
		ans[_] = int(f[_][n // 2 - 1])
	print(' '.join((str(i) for i in ans)))


def solve(Xs):
	return tuple((sorted(x)[(len(x) - 1) // 2] for x in zip(*Xs)))
(n, m) = map(int, input().split())
Xs = [tuple(map(int, input().split())) for _ in range(n)]
print(*solve(Xs))


def get_optimal_meeting_spot(X):
	sorted_X = sorted(X)
	n = len(X)
	return sorted_X[(n - 1) // 2]
(n, m) = map(int, input().split())
x_s = [list() for i in range(m)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in range(m):
		x_s[j].append(x[j])
for i in range(m):
	print(get_optimal_meeting_spot(x_s[i]), end=' ')


from statistics import median
(n, m) = [int(a) for a in input().split()]
p = bool(n & 1)
locs = []
res = []
for _ in range(n):
	locs.append([int(a) for a in input().split()])
locs = list(map(list, zip(*locs)))
for dim in locs:
	if not p:
		dim.remove(max(dim))
	res.append(median(dim))
print(*res)


(num_pts, dim) = (int(x) for x in input().split())
pts = []
for i in range(num_pts):
	pt = tuple((int(x) for x in input().split()))
	pts.append(pt)
for d in range(dim):
	x = [pts[i][d] for i in range(num_pts)]
	x = sorted(x)
	print(x[(num_pts - 1) // 2], end=' ')
print()


(n, m) = map(int, input().split())
coords = [[0] * n for i in range(m)]
for i in range(n):
	loc = [int(x) for x in input().split()]
	for j in range(m):
		coords[j][i] = loc[j]
loc = [0] * m
mid = n - 1 >> 1
for j in range(m):
	row = coords[j]
	row.sort()
	loc[j] = row[mid]
print(*loc)


import sys
import math

def read_one():
	return int(input().strip())

def read_all():
	x = input().strip().split(' ')
	return [int(i) for i in x]

def meet(xs):
	x = sorted(xs)
	return x[(len(x) - 1) // 2]

def execute(n, m, points):
	meetup = [meet([p[i] for p in points]) for i in range(m)]
	return ' '.join([str(i) for i in meetup])

def dist(p, points):
	m = len(p)
	return sum([sum([abs(pp[i] - p[i]) for i in range(m)]) for pp in points])
(n, m) = read_all()
points = [read_all() for _ in range(n)]
r = execute(n, m, points)
print(r)


def median(A):
	n = len(A)
	return sorted(A)[(n - 1) // 2]
(n, m) = map(int, input().split())
X = [None] * n
for i in range(n):
	X[i] = list(map(int, input().split()))
print(*[median([x[j] for x in X]) for j in range(m)])


import sys
from math import ceil, floor

def solve(pp):
	m = len(pp[0])
	k = len(pp) // 2
	if len(pp) % 2 == 0:
		k -= 1
	rval = list()
	for i in range(m):
		cc = sorted((p[i] for p in pp))
		c = cc[k]
		rval.append(c)
	return rval
(n, m) = map(int, input().split())
pp = list()
for _ in range(n):
	t = tuple(map(int, input().split()))
	pp.append(t)
cc = solve(pp)
print(' '.join(map(str, cc)))


(n, m) = (int(a) for a in input().split())
A = []
for i in range(n):
	c = [int(a) for a in input().split()]
	A.append(c)
R = []
if n % 2 == 0:
	r = n // 2 - 1
else:
	r = n // 2
for i in range(m):
	t = []
	for j in range(n):
		t.append(A[j][i])
	t.sort()
	R.append(t[r])
print(' '.join((str(r) for r in R)))


import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()


import math
import os
import random
import re
import sys

def solve(friends, dim):
	coordinates = [[] for _ in range(dim)]
	for f in friends:
		for d in range(dim):
			coordinates[d].append(f[d])
	result = list()
	for d in coordinates:
		d.sort()
		result.append(d[(len(friends) - 1) // 2])
	return ' '.join(map(str, result))
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
friends = []
for _ in range(n):
	friends.append(list(map(int, input().rstrip().split())))
print(solve(friends, m))


import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()


import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()


import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()


import operator

def main():
	(lines, dim) = map(int, input().split())
	points = [list(map(int, input().split())) for i in range(lines)]
	coords = map(sorted, zip(*points))
	getter = operator.itemgetter((lines - 1) // 2)
	print(*map(getter, coords))
main()