Given the coordinates of $N$ points in a plane, find the $K$-th farthest pair of points under Euclidean distance.
The Euclidean distance between two points $P(x_1, y_1)$ and $Q(x_2, y_2)$ is defined as $d(P, Q) = \sqrt {(x_1 - x_2)^2 + (y_1 - y_2)^2}$.
Input
The first line of the input contains two space-separated integers $N$ and $K$.
The next $N$ lines each contain two integers $X$ and $Y$, representing the coordinates of a point.
Output
The first line of the output contains a single integer, representing the square of the distance of the $K$-th farthest pair of points (which is guaranteed to be an integer).
Examples
Input 1
10 5 0 0 0 1 1 0 1 1 2 0 2 1 1 2 0 2 3 0 3 1
Output 1
9
Subtasks
| Case # | $N$ |
|---|---|
| 1 | $2000$ |
| 2 | $5000$ |
| 3 | $10000$ |
| 4 | $15000$ |
| 5 | $20000$ |
| 6 | $60000$ |
| 7 | $70000$ |
| 8 | $80000$ |
| 9 | $90000$ |
| 10 | $100000$ |
For all test cases, $1 \leq K \leq 100$, $K \leq \frac {N(N-1)} {2}$, and $0 \leq X, Y < 2^{31}$.