Speeding

Speeding is a dangerous violation that greatly increases the chance of fatal traffic accidents. Unfortunately, speed enforcement with radars and cameras does not solve the problem completely. Some drivers slow down in front of cameras and drive far above the limit on stretches where no enforcement takes place. To prevent this behavior, a fine is imposed for guaranteed speeding, based on the time it takes to travel the road.

Consider a road made of n segments numbered from 1 to n. The length of segment i is li meters. Segment i has a speed limit of vi meters per second.

Fines are imposed for speeding. Several fines are defined depending on the amount of excess, and the fine is computed as follows.

Let e be the maximum amount by which the car exceeded the allowed speed while on the whole road, that is, the maximum difference between the car's speed and the maximum allowed speed on the segment where the car is at that moment. If the car never sped, no fine is imposed. Otherwise the fine is computed as follows:

• if 0 < e ≤ a1, the fine is f1 monetary units;
• if a1 < e ≤ a2, the fine is f2 monetary units;
• . . .
• if am−2 < e ≤ am−1, the fine is fm−1 monetary units;
• if am−1 < e, the fine is fm monetary units.

Thus there are m speeding ranges and the fines that correspond to them.

The automatic fining system received data on q cars. For convenience, number them from 1 to q. Car i entered the road at time si, traveled all n segments, and left the road at time ti. Time is measured in seconds from the opening of the road.

For each car, the system must determine the maximum fine that can be guaranteed to be issued to that car based only on the time it entered the road and the time it left.

Write a program that, given the descriptions of the speeding range boundaries, the corresponding fines, and the entry and exit times of the cars, determines for each car the maximum fine that can be issued to it.

The first line of the input contains a single integer n, the number of segments on the road (1 ≤ n ≤ 10).

The second line contains n integers vi, the speed limits on the segments (1 ≤ vi ≤ 109).

The third line contains n integers li, the lengths of the segments (1 ≤ li ≤ 109).

The fourth line contains a single integer m, the number of speeding range boundaries (1 ≤ m ≤ 105).

The fifth line contains m − 1 integers ai, the speeding range boundaries (1 ≤ ai ≤ 109). The values ai are guaranteed to be strictly increasing. Note that if m = 1, the fifth line of the input is empty.

The sixth line contains m integers fi, the fines for the speeding ranges (1 ≤ fi ≤ 109). The values fi are guaranteed to be increasing.

The seventh line contains a single integer q, the number of cars to process (1 ≤ q ≤ 105).

Each of the following q lines contains two integers si and ti, the time car i entered the road and the time it left (1 ≤ si < ti ≤ 109).

For each of the q cars, print on a separate line the maximum fine that can be guaranteed to be issued to that car based only on the times it entered and left the road. If it is possible that the car never exceeded the allowed speed, print 0.

It is guaranteed that changing a car's entry or exit time by at most 10−5 does not change the fine that can be issued to it.