Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 July, 2006

IARCS home > OLYMPIAD

Advanced Division

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⁸ 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⁶ 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

Sample Output

2 1
4 5