CSES - Minimum Euclidean Distance
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Given a set of points in the two-dimensional plane, your task is to find the minimum Euclidean distance between two distinct points.

The Euclidean distance of points (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) is (x1x2)2+(y1y2)2\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

Input

The first input line has an integer nn: the number of points.

After this, there are nn lines that describe the points. Each line has two integers xx and yy. You may assume that each point is distinct.

Output

Print one integer: d2d^2 where dd is the minimum Euclidean distance (this ensures that the result is an integer).

Constraints

  • 2n21052 \le n \le 2 \cdot 10^5
  • 109x,y109-10^9 \le x,y \le 10^9

Example

Input:

4
2 1
4 4
1 2
6 3

Output:

2