Maximum Area of Good Rectangles Under Cost Constraint

You are given n vertical lines with x-coordinates \(x_1, x_2, \ldots, x_n\) and weights \(a_1, a_2, \ldots, a_n\), and m horizontal lines with y-coordinates \(y_1, y_2, \ldots, y_m\) and weights \(b_1, b_2, \ldots, b_m\). A rectangle is defined as good if and only if all of its four edges lie on the given lines. The cost of a good rectangle is the sum of the costs of its four segments, where the cost of a segment is the product of its length and the weight of the line it belongs to.

More formally, if a rectangle is formed by choosing two distinct vertical lines \(i\) and \(j\) (with \(i<j\)) and two distinct horizontal lines \(p\) and \(q\) (with \(p<q\)), then let \(\Delta x = x_j - x_i\) and \(\Delta y = y_q - y_p\). The cost of the rectangle is computed as:

[ \text{Cost} = \Delta x \cdot (b_p+b_q) + \Delta y \cdot (a_i+a_j). ]

The area of the rectangle is \(\Delta x \cdot \Delta y\). Note that rectangles with zero width or height (and hence zero area) are allowed. You are given T queries. In each query you are provided with an integer \(c\) and you have to find the maximum possible area of a good rectangle whose cost is no more than \(c\>.

inputFormat

The first line contains two integers n and m --- the number of vertical and horizontal lines respectively.

The second line contains n integers \(x_1, x_2, \ldots, x_n\): the x-coordinates of the vertical lines.

The third line contains n integers \(a_1, a_2, \ldots, a_n\): the weights for the vertical lines.

The fourth line contains m integers \(y_1, y_2, \ldots, y_m\): the y-coordinates of the horizontal lines.

The fifth line contains m integers \(b_1, b_2, \ldots, b_m\): the weights for the horizontal lines.

The sixth line contains an integer T --- the number of queries.

Each of the next T lines contains a single integer \(c\), representing a cost constraint for that query.

outputFormat

For each query, output a single line containing the maximum area of a good rectangle with cost no more than \(c\). If no rectangle (with positive area) satisfies the cost constraint, output 0.

sample

2 2
1 3
2 1
2 5
3 4
3
22
23
30

0
6
6