eolymp
bolt
Try our new interface for solving problems
Problems

Watermelon Fields Wonderland Countries Fools

Watermelon Fields Wonderland Countries Fools

Time limit 2 seconds
Memory limit 64 MiB

The world financial crisis defeated the economics of the Fool's Land, and Buratino decided to cultivate watermelons for additional income. Of course, for the business he started to use the famous Field of Wonder. Because of the special diligence (or maybe because of the wonderful features of the Field of Wonder), the speed of growth of each watermelon was not changed in time, but could be different for different watermelons. Watermelons of the Field of Wonder become very famous and attractive for tourists.

When Buratino noticed that tourists like photos with watermelons, he also introduced the new service for VIP tourists: photo with the heaviest watermelon.

One day he simultaneously measured the weights and the speeds of growth of all watermelons. Then for any K-th day after this day he can compute the weight of any watermelon by the formula W_K = W_0 + S*K, where W_0 is the initial weight and S is the speed of growth for this watermelon.

Buratino is too lazy to carry out all these computations every day by hand and asks you to help him. Write a program that will find the heaviest watermelon at the given day.

Input data

First line of input file contains one integer N - the number of watermelons (1 <= N <= 10^5). Each of the next N lines contains two single space separated integers W_0 and S (1 <= W_0, S <= 10^9) - the initial weight and the speed of growth for the corresponding watermelon.

The next line contains one integer M - the number of days for which you have to find the heaviest watermelon (1 <= M <= 10^5). Each of the last M lines of the input contains one positive integer, indicating day number K (1 <= K <= 10^9) for which you have to answer the task question.

Output data

Output file should contain M 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 this day. In case when there are several such watermelons, output the minimal number of such watermelon. Watermelons are enumerated from 1 to N in order they appear in the input.

Examples

Input example #1
3
1 4
4 3
8 1
3
1
3
2
Output example #1
3
1
2