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 x_i on this line and wait at that point in their vehicle with speed v_i. 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!

Input

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 ≤ x_i < 10⁹  and 0 < v_i ≤ 10⁹ - the point on the line where the i-th person is waiting and the speed of his vehicle. Additionally, x_i = x_j → v_i ≠ v_j.

The last line contains q distinct integers 0 ≤ q_i < 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.

Output

For each query q_i output the number of people who will arrive at the spaceship first if it lands at that point. A person at x_j with speed v_j will arrive at q_i in time |x_j - q_i| / v_j. 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.

Example

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

Output:
1 1
1 2
1 3
1 1
2 1 4
2 1 3
1 1