Problem Description
Rar the Cat is part-timing as an urban planner. As part of his new career, he has to model the effects of potential explosions in his city.
Rar's city can be modelled as a 2D grid, with N buildings, where the ith building is located at a coordinate (Xi, Yi).
In his simulation, an explosion occurs at the point (A, B), and the explosion produces a blastwave that spreads in a diamond shape, as shown below.
Help Rar determine the order in which the buildings will be hit by the expanding blastwave. If two buildings are hit at the same time, output the one with the lowest ID first.
Input
The first line of input will contain three integers, N, A and B.
The next N lines of input will contain two integers each, with the ith line containing integers Xi and Yi.
Output
Output a single line containing N integers, indicating the order in which the buildings will be hit. The IDs should be 1-indexed.
Limits
Subtask 1 (25%): 1 ≤ N ≤ 2 000. -1 000 ≤ Xi, Yi ≤ 1 000.
Subtask 2 (33%): 1 ≤ N ≤ 500 000. -1 000 ≤ Xi, Yi ≤ 1 000.
Subtask 3 (42%): 1 ≤ N ≤ 500 000. -109 ≤ Xi, Yi ≤ 109
Subtask 4 (0%): Sample Testcases
Sample Testcase 1
Input
4 0 0
0 0
2 0
1 1
1 0
Output
1 4 2 3
Sample Testcase 2
Input
5 2 3
5 -1
-2 -3
4 5
2 1
0 0
Output
4 3 5 1 2