You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

那些日子，终成为了小 C 难忘的回忆。

他依稀记得 $n$ 个与她相处的美好瞬间，但是都忘记了日期，只记得是在 $[l_i,r_i]$ 间。

为了让自己感到开心，他想让每件事情都充实在每一天。也就是说，每一天最多发生一个瞬间。

那么，你能不能帮他排出一个好的事件发生节点呢？

输入格式

第一行一个正整数 $n$，表示相处的瞬间数。

接下来 $n$ 行，每一行两个正整数 $l_i,r_i$。对于整个输入数据的第 $i+1$ 行，表示第 $i$ 个瞬间可能发生的时间区间为 $[l_i,r_i]$。

输出格式

一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个瞬间可能发生的时间。

如果存在多组解，输出任意一种。

数据保证有解。

样例

5
2 5
1 3
3 4
6 8
1 7

3 2 4 8 7

5
1 4
1 4
2 6
3 5
9 11

1 2 6 5 11

数据范围

对于 $100\%$ 的数据，$1\le n\le 200,1\le l_i, r_i\le 5\times10^6$。