区间跳跃

时间限制：2s
空间限制：1024MB

题目描述

给定 $N$ 个整数区间 $[L_1,R_1],[L_2,R_2],\ldots,[L_N,R_N]$。选择一个整数序列 $A=(A_1,A_2,\ldots,A_N)$，要求对每个 $i$ 都有 $L_i\le A_i\le R_i$。

在所有使

最小的合法序列中，输出字典序最小的一个。

输入格式

第一行输入整数 $N$，接下来 $N$ 行每行输入两个整数 $L_i,R_i$。

输出格式

输出一行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

样例输入 1

4
1 10
8 13
3 4
5 20

样例输出 1

8 8 4 5

样例输入 2

3
20 24
3 24
1 75

样例输出 2

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

样例输出 3

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

数据范围

对于所有数据，$2\le N\le5\times10^5$，$0\le L_i\le R_i\le10^9$。