MEETSHIP - First to meet the spaceship

no tags 

A spaceship has been sighted heading towards Earth. For the entire time that humanity has been monitoring it, it has not altered its course, it only changed speed for unknown reasons. As such, all the possible places on Earth where the spaceship might end up landing form a straight line; depending on how much it changes speed, it will land at different times, meaning a different point on this line due to Earth's rotation.

n people want to be the first to meet the aliens - they picked a point xi on this line and wait at that point in their vehicle with speed vi. Now they are all anxiously waiting for the spaceship's arrival. NASA has given a list of q most likely locations where the spaceship might end up landing - and everyone wants to know who would get to be the first to meet the aliens if the spaceship landed at each of the given points. They turned to you for help!


The first line contains two integers 1 ≤ n , q ≤ 300,000 - the number of people wishing to meet the aliens and the number of possible points where the spaceship might land.

The following n lines contain two integers 0 ≤ xi < 109  and 0 < vi ≤ 109 - the point on the line where the i-th person is waiting and the speed of his vehicle. Additionally, xi = xj → vi ≠ vj.

The last line contains q distinct integers 0 ≤ qi < 10- the points on the line where the spaceship might end up landing. You may assume the spaceship will not land at any point containing a person waiting in a vehicle.


For each query qoutput the number of people who will arrive at the spaceship first if it lands at that point. A person at xj with speed vj will arrive at qi in time |xj - qi| / vj. The people who will arrive at the spaceship first are those j for whom the fraction is minimal out of all people. Then, in the same line, output the 1-based indices of these people as they were given in the input, sorted in ascending order.


4 7
10 5
30 1
20 4
100 1
5 31 22 15 85 60 61

1 1
1 2
1 3
1 1
2 1 4
2 1 3
1 1

Note: I don't have another tester for this problem; FYI, the inputs were validated using and my solutions outputs are identical with this bruteforce This note will be removed once someone gets AC :)

Added by:Hodobox
Time limit:3.141s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem