Maou is the demon king of some other world consisting of a single peaceful and quiet kingdom with ~N~ villages that can be mapped as points in a 2-D plane. Bored out of his mind, Maou decided to divide the villages of the kingdom into two conflicting nations and witness the ensuing battles. To maximize chaos, he wants to divide the villages in such a way that the minimum distance between any two villages in the same nation is as large as possible. As a servant of Maou, help him compute this value.

Constraints

~3 \le N \le 5 \times 10^5~

~-10^9 \le x_i, y_i \le 10^9~

All villages are at distinct locations.

Subtask 1 [10%]

~3 \le N \le 2 \times 10^3~

Subtask 2 [70%]

~3 \le N \le 10^5~

Subtask 3 [20%]

No additional constraints.

Input Specification

The first line contains an integer ~N~.

The next ~N~ lines each contain ~2~ integers ~x_i~ and ~y_i~, the coordinates of the ~i~-th village.

Output Specification

Since Maou does not like floating point values, output the square of the maximum possible value of the minimum distance between any two villages in the same nation.

Sample Input

9
-2 -2
-1 0
2 3
1 2
0 0
0 -3
-3 1
2 -1
4 -2

Sample Output

8

Explanation

A diagram of an optimal division of the villages in this case is provided above. Red points denote villages in the first nation, whereas blue points denote those in the second nation. The minimum distance between any two villages in the same nation is ~2 \sqrt 2~ (for which the square is ~8~), and it can be shown that this is the largest possible distance.