Description

特雷森学院的Z训练员将他负责的赛马娘进行了一个排序，将其能力量化为了两项，并标注到了坐标轴上。为了年末的有马纪念大赛，Z训练员得选一个最强的赛马娘。赛马娘的强度跟她超过的赛马娘数量有关。即A的坐标为（Xa，Ya），而B的坐标（Xb<Xa，Yb<Ya），那么A就超过B。现在请依次输出每个赛马娘的强度，最后输出强度最大的赛马娘编号（如果若干位赛马娘强度并列最高，输出其中最大的编号）。

Format

Input

一个整数n，对应下面的n组坐标，表示赛马娘能力量化后的点。N<=100 n个点的坐标。

Output

每赛马娘的强度，还有最强赛马娘的编号。

每个数据均各成一行。

Samples

4
1 1
2 3
3 2
5 5

0
1
1
3
4

Limitation

1s, 1024KiB for each test case.