{"raw_statement":[{"iden":"problem statement","content":"You are given positions $(X_i, Y_i)$ of $N$ enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).\nYou're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.\nYou can't enter a cell that is being attacked by a rook. Additionally, you **can't move diagonally to an empty cell** (but you can beat a rook diagonally).\n(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)\nFor each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 200\\,000$\n*   $1 \\leq X_i, Y_i \\leq 10^6$\n*   $X_i \\neq X_j$\n*   $Y_i \\neq Y_j$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format.\n\n$N$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_N$ $Y_N$"},{"iden":"sample input 1","content":"6\n1 8\n6 10\n2 7\n4 4\n9 3\n5 1"},{"iden":"sample output 1","content":"5\n0\n7\n5\n0\n0\n\nSee the drawing below. If we replace rook 3 with a king, we can beat at most two other rooks. The red path is one of optimal sequences of moves: beat rook 1, then keep going down and right until you can beat rook 4. There are 7 steps and that's the third number in the output.\n![image](https://img.atcoder.jp/agc047/rooks_path_small3.png)\n_x-coordinate increases from left to right, while y increases bottom to top._\nStarting from rook 2, 5 or 6, we can't beat any other rook. The optimal number of moves is 0."},{"iden":"sample input 2","content":"5\n5 5\n100 100\n70 20\n81 70\n800 1"},{"iden":"sample output 2","content":"985\n985\n1065\n1034\n0"},{"iden":"sample input 3","content":"10\n2 5\n4 4\n13 12\n12 13\n14 17\n17 19\n22 22\n16 18\n19 27\n25 26"},{"iden":"sample output 3","content":"2\n2\n9\n9\n3\n3\n24\n5\n0\n25"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}