403023: GYM100971 D Laying Cables

One-dimensional country has n cities, the i-th of which is located at the point x_i and has population p_i, and all x_i, as well as all p_i, are distinct. When one-dimensional country got the Internet, it was decided to place the main server in the largest city, and to connect any other city j to the city k that has bigger population than j and is the closest to it (if there are many such cities, the largest one should be chosen). City k is called a parent of city j in this case.

Unfortunately, the Ministry of Communications got stuck in determining from where and to where the Internet cables should be laid, and the population of the country is suffering. So you should solve the problem. For every city, find its parent city.

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of cities.

Each of the next n lines contains two space-separated integers x_i and p_i (1 ≤ x_i,  p_i ≤ 10⁹) — the coordinate and the population of the i-th city.

Output n space-separated integers. The i-th number should be the parent of the i-th city, or  - 1, if the i-th city doesn't have a parent. The cities are numbered from 1 by their order in the input.

4
1 1000
7 10
9 1
12 100

-1 4 2 1

3
1 100
2 1
3 10

-1 1 1

3
1 10
3 100
2 1

2 -1 2