在历史课上,老师要求 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