{"raw_statement":[{"iden":"problem statement","content":"There are $N$ houses numbered $1$ through $N$ on a two-dimensional plane. House $i$ is at $(x_i, y_i)$.\nWe use Chebyshev distance to calculate the distance between two houses. That is, the distance between Houses $i$ and $j$ is $\\max(|x_i - x_j|, |y_i-y_j|)$.\nThere are $\\frac{N(N-1)}{2}$ pairs formed by two different houses. For each of these pairs, we will calculate the distance between the houses, and then we will sort these distances in **descending order** to get a sequence of length $\\frac{N(N-1)}{2}$. Find the second value from the beginning of this sequence."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $3 \\leq N \\leq 2 \\times 10^{5}$\n*   $-10^{9} \\leq x_i, y_i \\leq 10^{9}$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$x_{1}$ $y_{1}$\n$\\vdots$\n$x_{N}$ $y_{N}$"},{"iden":"sample input 1","content":"3\n0 0\n1 2\n4 0"},{"iden":"sample output 1","content":"3\n\n*   The distance between Houses $1$ and $2$ is $2$;\n*   The distance between Houses $1$ and $3$ is $4$;\n*   The distance between Houses $2$ and $3$ is $3$.\n*   By sorting these in descending order, we get $(4,3,2)$, where the second value from the beginning is $3$."},{"iden":"sample input 2","content":"4\n0 0\n0 0\n1 0\n0 1"},{"iden":"sample output 2","content":"1\n\n*   There may be multiple houses at the same coordinates."},{"iden":"sample input 3","content":"20\n407 361\n167 433\n756 388\n-551 -47\n306 -471\n36 928\n338 -355\n911 852\n288 70\n-961 -769\n-668 -386\n-690 -378\n182 -609\n-677 401\n-458 -112\n184 -131\n-243 888\n-163 471\n-11 997\n119 544"},{"iden":"sample output 3","content":"1766"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}