Score: $600$ points

问题陈述

给定 $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$。

找到字典序最小的 好整数序列 $A$，使得 $\displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$ 最小化。

序列的字典序是什么？

如果满足以下 1. 或 2. 中的任一条件，我们说序列 $S = (S_1,S_2,\ldots,S_{|S|})$ 字典序小于序列 $T = (T_1,T_2,\ldots,T_{|T|})$。这里，$|S|, |T|$ 分别表示 $S$ 和 $T$ 的长度。

1. $|S| \lt |T|$ 并且 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$。
2. 存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ 使得以下两个条件同时成立：
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$。
   • $S_i$ 数字上小于 $T_i$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

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$.

A sequence of $N$ integers $A = (A_1, A_2, \ldots, A_N)$ is called a good integer sequence if it satisfies the following condition:

• $L_i \leq A_i \leq R_i$ for all $1 \leq i \leq N$.

Find the lexicographically smallest good integer sequence $A$ that minimizes $\displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$.

What 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.

1. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$.
2. There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold:
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$.
   • $S_i$ is smaller than $T_i$ (as a number).

Constraints

• All input values are integers.
• $2 \leq N \leq 5 \times 10^5$
• $0 \leq L_i \leq R_i \leq 10^9$

Input

The input is given from Standard Input in the following format:

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

Output

Print the answer in a single line in the following format:

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

Sample Input 1

4
1 10
8 13
3 4
5 20

Sample Output 1

8 8 4 5

$(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}|$.

Sample Input 2

3
20 24
3 24
1 75

Sample Output 2

20 20 20

Note 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.

Sample Input 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

Sample Output 3

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