{"raw_statement":[{"iden":"problem statement","content":"You are given $N$ pairs of integers $(L_1, R_1), (L_2, R_2), \\dots, (L_N, R_N)$. Here, $L_i \\leq R_i$ for all $1 \\leq i \\leq N$.\nA sequence of $N$ integers $A = (A_1, A_2, \\ldots, A_N)$ is called a **good integer sequence** if it satisfies the following condition:\n\n*   $L_i \\leq A_i \\leq R_i$ for all $1 \\leq i \\leq N$.\n\nFind the lexicographically smallest **good integer sequence** $A$ that minimizes $\\displaystyle \\sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$.\nWhat is lexicographical order for sequences?A sequence $S = (S_1,S_2,\\ldots,S_{|S|})$ is said to be **lexicographically smaller** than a sequence $T = (T_1,T_2,\\ldots,T_{|T|})$ if 1. or 2. below holds. Here, $|S|, |T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1,S_2,\\ldots,S_{|S|}) = (T_1,T_2,\\ldots,T_{|S|})$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ such that both of the following hold:\n    *   $(S_1,S_2,\\ldots,S_{i-1}) = (T_1,T_2,\\ldots,T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number)."},{"iden":"constraints","content":"*   All input values are integers.\n*   $2 \\leq N \\leq 5 \\times 10^5$\n*   $0 \\leq L_i \\leq R_i \\leq 10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$"},{"iden":"sample input 1","content":"4\n1 10\n8 13\n3 4\n5 20"},{"iden":"sample output 1","content":"8 8 4 5\n\n$(A_1, A_2, A_3, A_4) = (8, 8, 4, 5)$ is a good integer sequence. In this case, $\\sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| = |8 - 8| + |4 - 8| + |5 - 4| = 5$, which is the minimum value of $\\sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$."},{"iden":"sample input 2","content":"3\n20 24\n3 24\n1 75"},{"iden":"sample output 2","content":"20 20 20\n\nNote that when multiple good integer sequences $A$ minimize $\\sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$, you should print the lexicographically smallest of them."},{"iden":"sample input 3","content":"15\n335279264 849598327\n446755913 822889311\n526239859 548830120\n181424399 715477619\n342858071 625711486\n448565595 480845266\n467825612 647639160\n160714711 449656269\n336869678 545923679\n61020590 573085537\n626006012 816372580\n135599877 389312924\n511429216 547865075\n561330066 605997004\n539239436 921749002"},{"iden":"sample output 3","content":"526239859 526239859 526239859 467825612 467825612 467825612 467825612 449656269 449656269 449656269 626006012 389312924 511429216 561330066 561330066"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}