After Ralph escaped from his game, they began to search for him - n specially trained drones were sent after him. However, Ralph is not so simple and took up a defensive position with a turret in his hands.

After carefully assessing the situation, Ralph realized that if we consider the plane where he is located at the origin - the point (0, 0), then it turns out that i-th of the drones is located at the point with coordinates (xi, yi). However, while Ralph was scouting the situation, the drones noticed him, which means it's time to act. In one second, Ralph can hit any drone from the turret, and after that all surviving drones can move to any of 8 adjacent points horizontally, vertically or diagonally (some drones may end up in points with the same coordinates) .

The task of the drones is to get to Ralph, that is, to the point (0, 0), and the task of Ralph is to hit all the drones before they get to him. For his part, Ralph guarantees you that he will never miss and hit exactly one drone with each shot. He asks you to tell him in what order to hit them. Help him - tell him in what order to hit the drones so that they do not get to the point (0, 0), or tell him that this will not work, and Ralph better flee.

Input

The first line contains the number of drones n (1 ≤ n ≤ 105). The i-th of the following n lines contains two integers xi and yi - the coordinates of the i-th drone (|xi |, |yi| ≤ 105). It is guaranteed that there are no drones at the point (0, 0).

Output

On one line print n numbers from 1 to n - the numbers of the drones in the order in which Ralph needs to shoot them. If some drone reaches the point (0, 0) anyway, print -1. If there are multiple solutions, print any of them.