[ARC175] C - Jumping Through Intervals

C - Jumping Through Intervals

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 分

题面

给定 对整数 。这里，对于所有 ，有 。

一个长度为 的整数序列 被称为好的整数序列，如果它满足以下条件：

• 对于所有 ，有 。

找到字典序最小的好的整数序列 ，使得 最小化。

什么是字典序？

一个序列 被称为字典序较小于另一个序列 ，如果满足以下条件之一或两者同时满足。这里， 分别表示 和 的长度。

1. 并且 。
2. 存在整数 ，使得以下两个条件同时成立：
   • 。
   • 作为数字比 小。

限制条件

• 所有输入值均为整数。

---

输入

输入从标准输入中获取，格式如下：

输出

以以下格式在一行中输出答案：

---

输入样例 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