Description

希蒙收集了 $n$ 个正多边形积木，编号依次是 $1$ 到 $n$，为了更好收拾这些积木，现在他想要把这些正多边形按照一个规则排序一下，排序的规则是：

• 周长长的在前面
• 如果有两个多边形的周长相同，那么边数多的排在前面
• 如果周长和边数都相同，那么编号小的在前面

Format

Input

输入一个整数 $n(1 \le n \le 50000)$，表示正多边形的数量 。

接下来 $n$ 行数据，每行输入两个整型 $k(2 \le k \le 10000)$ 和 $s(1 \le s \le 10000)$，分别表示正多边形的边数和边长。

Output

输出排序后每个正多边形的编号。

Samples

5                                  
1 2                             
5 9
7 4
3 3
7 7

5 2 3 4 1

提示

正多边形的周长 = 边数 * 边长