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 ≤ 300000 - 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 ith person is waiting and the speed of his vehicle. Additionally, xi = xj → vi ≠ vj.
The last line contains Q distinct integers 0 ≤ qi < 109 - 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 qi output 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
Time and memory limit:
- 3 seconds
Problem source: SPOJ