ATM

Mouse Adrian currently lives in the United States. This summer, he visited New York for the first time and he was very impressed by Manhatten. Mouse Adrian particularly liked the fact that all roads are arranged in a grid, which makes orientation very easy. Surprisingly, Mouse Adrian recently got contacted by a bank to help them solve a problem. The bank wants to open a new money distribution center and is looking for the optimal location. Once a day, a transporter delivers money from the distribution center to all ATMs (cash machines). For security reasons, the transporter is allowed to carry money for only one ATM at a time. Thus, the transporter has to go back to the distribution center after each delivery in order to get more money. Determine the location for the money distribution center such that the transporter's daily travel distance is minimized.

Input

Assume that you know the number of ATMs $N$. Furthermore, you are given two arrays of positive, integer coordinates, $X = (X_0, \ldots, X_{N-1})$ and $Y = (Y_0, \ldots, Y_{N-1})$. The distance to travel from $(X_i, Y_i)$ to $(X_j, Y_j)$ is $|X_i - X_j| + |Y_i - Y_j|$.

Output

The x- and y-coordinates of the optimal location for the money distribution center.

Task

Describe an algorithm that solves the described problem. This is a theoretical task, you do not have to write working source code. You can provide pseudocode if it helps you.

Reason why your algorithm is correct and analyze its run time and storage complexity. Before you get started, read the HowTo (link).

Submission