Cow Runnings running.X
Cows have their own Olympics, called Cowlympics). This year Farmer Ran's
farm is participating in a new sport in Cowlympics called Cow Runnings.
When the whistle is blown (at T == 0), the cows start to run and when the second whistle
is blown all cows will stop. Then the first cow (the cow in front) will be the winner.
Of course the period of time between two whistles affects the match a lot.
In addition, the cows are each assigned a starting location in this race:
some start further ahead than others.
All coaches will have a meeting before the competition to select the period
of time between the start and stop whistles. Farmer Ran wants to know whether his
cows will win or not!
There are N (1 <= N <= 100,000) cows participating (numbered 1..N) and each
one has a constant integer speed V (-1,000,000,000 <= V <= 1,000,000,000)
(Some cows may even travel backwards -- there is not a strong will to win
among cows.) Each cow also has an integer representing its starting position, P
(-1,000,000,000 <= P <= 1,000,000,000).
No two cows will have the same speed and the same initial position.
The possible race-stopping times T are in the range 1 <= T <= 100,000.
Help Farmer Ran determine which cow will be the winner for each T.
PROBLEM NAME: running
INPUT FORMAT:
* Line 1: Two space-separated integers, N and T.
* Lines 2..N+1: Line i+1 contains two numbers Vi and Pi showing the
speed and initial position of i-th cow.
* Lines N+2..N+T+1: Line N+1+i contains a number Ti (0 <= Ti <=
1,000,000,000) which is a candidate stopping time.
The Ti are sorted; that is, T1 <= T2 <= ... <= TN.
SAMPLE INPUT (file running.in):
4 2
1 0
-2 1
3 0
10 -12
1
5
INPUT DETAILS:
There are four cows participating, with speeds of 1, -2, 3, and 10, and
they are initially placed at positions 0, 1, 0, and -12. Farmer Ran wants
to test two times, 1 and 5.
OUTPUT FORMAT:
* Lines 1..T: Line i should contain the number of winner for the time
period Ti. In case of a tie output the cow with the highest
speed.
SAMPLE OUTPUT (file running.out):
3
4
OUTPUT DETAILS:
At time 1 the cows will be at positions 1, -1, 3, and -2.
So cow 3 will be the winner.
At time 5 the cows will be at positions 5, -9, 15, and 38.
So cow 4 will be the winner.