{"raw_statement":[{"iden":"problem statement","content":"Snuke loves flags.\nSnuke is placing $N$ flags on a line.\nThe $i$\\-th flag can be placed at either coordinate $x_i$ or coordinate $y_i$.\nSnuke thinks that the flags look nicer when the smallest distance between two of them, $d$, is larger. Find the maximum possible value of $d$."},{"iden":"constraints","content":"*   $2 ≤ N ≤ 10^{4}$\n*   $1 ≤ x_i, y_i ≤ 10^{9}$\n*   $x_i$ and $y_i$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$"},{"iden":"sample input 1","content":"3\n1 3\n2 5\n1 9"},{"iden":"sample output 1","content":"4\n\nThe optimal solution is to place the first flag at coordinate $1$, the second flag at coordinate $5$ and the third flag at coordinate $9$. The smallest distance between two of the flags is $4$ in this case."},{"iden":"sample input 2","content":"5\n2 2\n2 2\n2 2\n2 2\n2 2"},{"iden":"sample output 2","content":"0\n\nThere can be more than one flag at the same position."},{"iden":"sample input 3","content":"22\n93 6440\n78 6647\n862 11\n8306 9689\n798 99\n801 521\n188 206\n6079 971\n4559 209\n50 94\n92 6270\n5403 560\n803 83\n1855 99\n42 504\n75 484\n629 11\n92 122\n3359 37\n28 16\n648 14\n11 269"},{"iden":"sample output 3","content":"17"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}