← 返回题目列表

Codeforces · 45/D

D. 活动日期

中文机器翻译题面 查看原题

在历史课上,老师要求 Vasya 说出 n 个著名事件发生的日期。他不记得确切的日期,但他记得该事件可能发生的一段日子[li,ri](含)。不过瓦夏也记得一天最多发生一件事情。帮助他选择满足这两个条件的 n 个著名事件的日期。保证是可能的。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 已知事件的数量。然后接下来的 n 行分别包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 107) — 第 i 个事件的最早可接受日期和最晚可接受日期。

输出

打印 n 个数字 — 事件发生的日期。如果有多个解决方案,请打印其中任何一个。保证存在解。

示例

输入 #1

3
1 2
2 3
3 4

输出 #1

1 2 3

输入 #2

2
1 3
1 3

输出 #2

1 2