Problem 2: Cellular Jail, *(Indraneel Mukherjee / R Shreevatsa, CMI)*

On the planet of Zorg, scientists have conquered the limitations
of space-time and designed a cellular jail in which the cells are
organized as an *n*-dimensional hypercube with upto
10^{8} prison cells along each dimension. A clever system of
connected corridors makes it possible to walk from any cell in the
jail to any other cell. Each corridor runs parallel to one of the
axes, so all paths from one cell to another are grid paths.

Two desperate criminals have just been sentenced to life imprisonment in this jail. The jail authorities have a list of the cells in the jail that are currently empty. To prevent any possibility of the new prisoners colluding to create trouble, the authorities want to place them in two empty cells that are as far apart as possible with respect to the distance to be travelled along the jail corridors.

For instance, suppose we have a simple two dimensional jail with empty cells at positions (2,1), (1,4), (4,5) and (5,3). Then, the pair of empty cells that are furthest apart are (2,1) and (4,5), which are separated by a corridor path of length 6.

Input format

The first line of input contains two integers, *N* and
*D*, where *N* is the number of empty cells in the jail
and *D* is the number of dimensions of the cellular jail. This
is followed by *N* lines of input describing the locations of
the empty cells. Each line consists of *D* integers, giving
the *D* coordinates of the cell.

Output format

Two lines, each containing *D* integers. Each line gives
the *D* coordinates of one of the two empty cells to be used
for the new prisoners. The two cells can be listed in any order. If
there is more than one valid solution, print any one.

Test Data:

You may assume that *N* ≤ 10^{6} and *D*
≤ 5. In 60% of the test cases, *D* = 2.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

4 2 2 1 1 4 4 5 5 3

Sample Output

2 1 4 5

Copyright (c) IARCS 2003-2020; Last Updated: 03 Sep 2006