题目描述

There are $N$ police stations in Flatland and the $i^{th}$ police station is located at a coordinate $(x_i, y_i)$. The authority plans to increase the synergy between these police stations by reducing any miscommunication that often arises among them. To do this, the authority decides to build a new tower that will serve as the Communication Control Center (CCC). Note that the CCC can only be built at $(x, y)$ where $x$ and $y$ are integers. It does not matter whether there is already a police station at $(x, y)$; CCC can be built along with that police station.

CCC then will draw a communication cable to each of the police stations with some restrictions.

• Each cable only serves a police station, thus, to serve $N$ police stations, they will need $N$ cables.
• The cable can only be laid out parallel to $x$-axis and $y$-axis; no diagonal crossing is allowed.

Due to some weird physics law in Flatland, each cable can only have a length of at most $L$ in $x$-axis direction and a length of at most $W$ in $y$-axis direction; this is the reason why this type of cable is known as $(L, W)$ cable in Flatland. To have stable communication, all police stations should be connected by the same type of cable.

Recent science and technology advancements in Flatland allows the physicists to build an $(L, W)$ cable for any $L$ and $W$ they like, with a cost. As the cost becomes quite expensive for larger $L$ and $W$, the authority needs to figure out $L$ and $W$ that can satisfy their need, i.e. to connect all police stations with CCC, while minimizing the value of $L + W$.

Your task in this problem is to find $L$ and $W$ such that the value of $L + W$ is minimum and the authority can build CCC at $(x, y)$ where both $x$ and $y$ are integers while all police stations can be connected to the CCC with $(L, W)$ cables. If there are multiple solutions, minimize $L$ first, and then minimize $W$.

输入格式

Input begins with a line containing an integer: $N$ ($1 \leq N \leq 100\,000$) representing the number of police stations in Flatland. The next $N$ lines each contains two integers: $x_i\ y_i$ ($-10^6 \leq x_i, y_i \leq 10^6$) representing the location of each police station.

输出格式

Output in a line two integers (separated by a single space), $L$ and $W$, respectively, such that the value of $L + W$ is minimum and the authority can build CCC at $(x, y)$ where both $x$ and $y$ are integers while all police stations can be connected to the CCC with $(L, W)$ cables. If there are multiple solutions, minimize $L$ first, and then minimize $W$.

5
20 90
-10 40
90 20
50 -30
50 70

50 60

提示

Explanation for the sample input/output #1

The optimal decision that can be made by the authority is to build the CCC at $(40, 30)$ and prepare for $\langle 50, 60 \rangle$ cables to connect all police stations to the CCC.

Explanation for the sample input/output #2

To have a minimum $L + W$, the CCC must be built at $(121, 744)$ or $(121, 745)$. Either way, they will need $\langle 1, 5 \rangle$ cables to connect both police stations to the CCC.

Explanation for the sample input/output #3

The optimal decision that can be made by the authority is to build the CCC at $(31, 30)$ and prepare for $\langle 61, 50 \rangle$ cables to connect all police stations to the CCC.