Watermelon Festival#253
Every year, a village holds a fun watermelon festival. Farmers from all around bring their watermelons to the competition to determine the biggest and heaviest watermelon of the season. This year, festival organizer Oleksandr decided to make the event even more interesting — he introduced a special service for tourists: a photo with the champion watermelon of the day!
Since the watermelons at the festival continue to grow throughout the celebration, Oleksandr needs to determine each day which watermelon is the heaviest at that moment. At the beginning of the festival, he measured the initial weight of each watermelon and its growth rate. Now, for any -th day of the festival, he can calculate the weight of each watermelon using the formula W_K = W_0 + S \cdot K, where W_0 is the initial weight and is the growth rate of this watermelon.
Oleksandr is too busy organizing the festival to do these calculations by hand every day, so he asks you to help. Write a program that will determine the heaviest watermelon on the given days.
The first line of the input file contains one integer — the number of watermelons at the festival (1 \leq N \leq 10^5). Each of the next lines contains two space-separated integers W_0 and (1 \leq W_0, S \leq 10^9) — the initial weight and the growth rate for the corresponding watermelon.
The next line contains one integer — the number of days for which you need to find the heaviest watermelon (1 \leq M \leq 10^5). Each of the last lines of the input contains one positive integer, indicating the day number (1 \leq K \leq 10^9) for which you need to answer the task question.
The output file should contain lines — one line for each day in the same order as in the input. On the corresponding line, output one integer — the number of the heaviest watermelon for that day. In the case when there are several such watermelons, output the minimal number of such watermelon. Watermelons are enumerated from to in the order they appear in the input.
Example 1