Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
H. Bacteria Colony
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dr. Vijayram has an infinite grid of agar to grow bacteria. This grid can be represented by the $$$xy$$$-plane where bacteria can grow at integer coordinates. Every minute, each living bacteria on the grid can spread to any number of adjacent locations$$$^\dagger$$$ (including not spreading at all). A bacteria might also die and be decomposed after spreading.

To prepare for future experiments, Dr. Vijayram had sterilized the grid. Unfortunately, the grid was contaminated $$$t$$$ minutes ago by a bacteria at the point $$$(x_0, y_0)$$$. Dr. Vijayram doesn't know what $$$t$$$, $$$x_0$$$, and $$$y_0$$$ are, but he can tell you the locations of all bacteria that are currently alive. Help him find the lexicographically minimum valid tuple $$$(t, x_0, y_0)$$$ that is consistent with Dr. Vijayram's observations.

$$$^\dagger$$$Two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are adjacent if $$$\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$$$.

Input

The first line of the input will contain the integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) representing the number of living bacteria.

Each of the next $$$n$$$ lines will contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 10^9$$$).

Output

Print three integers $$$t$$$, $$$x_0$$$, and $$$y_0$$$, a valid time and location for the initial bacteria contamination that is the lexicographically minimum possible.

Example
Input
6
7 1
4 1
6 1
1 10
5 7
4 5
Output
8 1 3
Note

In the sample test case, it can be shown that a bacteria can start at $$$(1, 3)$$$ and spread to each of the $$$n$$$ locations in $$$8$$$ minutes and that $$$(8, 1, 3)$$$ is the lexicographically minimum achievable tuple.