Cosmic Assembly

A space company is organizing a meeting of the executive directors of its $N$ divisions. Each director has a personal single-seat spaceship, and the coordinates $(x_i, y_i, z_i)$ of every director are known.

Spaceship fuel is very expensive, so the company wants to pick a meeting location $(x, y, z)$ that minimizes the sum of all travel distances. Space traffic rules require moving in only one of the $x$, $y$, or $z$ directions at any moment, so the distance of a single trip is computed as $|x_i - x| + |y_i - y| + |z_i - z|$.

Given the directors' coordinates, find the most suitable meeting location. The meeting location must be easy to mark on a map, so its coordinates must be integers.

The first line contains the number of directors $N$. Each of the next $N$ lines contains three space-separated integers $x_i$, $y_i$, $z_i$, giving the coordinates of the $i$-th director.

Several directors may initially be at the same location.

Output the coordinates of a meeting location that minimizes the total travel distance, as three space-separated integers $x$, $y$, $z$. If several meeting locations are optimal, output the lexicographically smallest one: the smallest $x$, breaking ties by the smallest $y$, then by the smallest $z$.

• $1 \le N \le 100,000$
• $-10^8 \le x_i, y_i, z_i \le 10^8$