题目描述

给定 $N$ 个整数对 $(L_1, R_1), (L_2, R_2), \dots, (L_N, R_N)$。其中，对于所有 $1 \leq i \leq N$，都有 $L_i \leq R_i$。

我们称满足以下条件的 $N$ 元整数列 $A = (A_1, A_2, \ldots, A_N)$ 为良好整数列：

• 对于所有 $1 \leq i \leq N$，都有 $L_i \leq A_i \leq R_i$。

请在所有使得 $\displaystyle \sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的良好整数列 $A$ 中，输出字典序最小的一个。

数列的字典序定义如下：设数列 $S = (S_1, S_2, \ldots, S_{|S|})$，$T = (T_1, T_2, \ldots, T_{|T|})$。$S$ 的字典序小于 $T$，当且仅当下列两条之一成立：

1. $|S| < |T|$ 且 $(S\_1, S\_2, \ldots, S\_{|S|}) = (T\_1, T\_2, \ldots, T\_{|S|})$。
2. 存在整数 $1 \leq i \leq \min\{|S|, |T|\}$，使得
   • $(S\_1, S\_2, \ldots, S\_{i-1}) = (T\_1, T\_2, \ldots, T\_{i-1})$，
   • 且 $S_i < T_i$。

输入格式

输入按以下格式从标准输入读入：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

请将答案以 $1$ 行输出：

$A_1$ $A_2$ $\ldots$ $A_N$

样例 1

输入

4
1 10
8 13
3 4
5 20

输出

8 8 4 5

样例 2

输入

3
20 24
3 24
1 75

输出

20 20 20

样例 3

输入

15
335279264 849598327
446755913 822889311
526239859 548830120
181424399 715477619
342858071 625711486
448565595 480845266
467825612 647639160
160714711 449656269
336869678 545923679
61020590 573085537
626006012 816372580
135599877 389312924
511429216 547865075
561330066 605997004
539239436 921749002

输出

526239859 526239859 526239859 467825612 467825612 467825612 467825612 449656269 449656269 449656269 626006012 389312924 511429216 561330066 561330066

说明/提示

数据范围

• 输入的所有数均为整数。
• $2 \leq N \leq 5 \times 10^5$
• $0 \leq L_i \leq R_i \leq 10^9$

样例解释 1

$(A_1, A_2, A_3, A_4) = (8, 8, 4, 5)$ 是一个良好整数列。此时 $\sum\_{i=1}^{N-1} |A\_{i+1} - A\_i| = |8 - 8| + |4 - 8| + |5 - 4| = 5$，这是 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 的最小值。

样例解释 2

当使 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的良好整数列 $A$ 有多个时，请输出其中字典序最小的一个。

由 ChatGPT 4.1 翻译