Watermelons of the Field of Wonders

Time limit2sMemory limit256 MB

Summary

Given N lines W0 + S*K, report the line with the largest value at each of M query days, breaking ties by smallest index.

Level: Medium7 of 10
Topics: Segment tree, Sorting, Binary search
Solved: No attempts yet

Problem

The world financial crisis broke the economy of the Land of Fools, so Buratino started growing watermelons for extra income. He runs the business on the famous Field of Wonders, of course. Whether it is his diligence or the odd nature of the field, each watermelon grows at its own speed, and that speed never changes over time. The watermelons of the Field of Wonders soon became famous and tourists came for them.

When Buratino noticed that tourists like photos with watermelons, he opened one more service for VIP tourists: a photo with the heaviest watermelon.

One day he measured the weight and the growth speed of every watermelon at the same time. On the day $K$ days after that, a watermelon weighs $W_K = W_0 + S \times K$ , where $W_0$ is the weight he measured and $S$ is the growth speed of that watermelon.

Buratino does not want to redo this arithmetic by hand every day. Write a program that finds the heaviest watermelon on a given day.

Input

The first line contains the number of watermelons $N$ . ( $1 \le N \le 10^5$ ) Each of the next $N$ lines contains the initial weight $W_0$ and the growth speed $S$ of one watermelon, separated by a single space. ( $1 \le W_0, S \le 10^9$ )

The next line contains the number of days $M$ you have to answer for. ( $1 \le M \le 10^5$ ) Each of the last $M$ lines contains one day number $K$ . ( $1 \le K \le 10^9$ )

Output

Print $M$ lines, one per day, in the same order as the input. On each line print the number of the heaviest watermelon on that day. When several watermelons are the heaviest, print the smallest of their numbers. The watermelons are numbered from $1$ to $N$ in the order they appear in the input.

Examples5

Example 1
Input
```
3
1 4
4 3
8 1
3
1
3
2
```
Expected output
```
3
1
2
```
Example 2
Input
```
1
1 1
3
1
500000000
1000000000
```
Expected output
```
1
1
1
```
Example 3
Input
```
3
7 5
7 5
7 5
3
1
2
1000000000
```
Expected output
```
1
1
1
```

Example 4

Input

Expected output

Example 5

Input

3
1000000000 1000000000
1000000000 999999999
999999999 1000000000
2
1
1000000000

Expected output

1
1