Strategy Game Score Calculation

Players L and Q play a strategy game defined on two arrays. You are given an array \(A\) of length \(n\) and an array \(B\) of length \(m\). A matrix \(C\) of size \(n \times m\) is then defined by the formula \(C_{ij} = A_{i} \times B_{j}\) for \(1 \le i \le n\) and \(1 \le j \le m\).

The game consists of \(q\) rounds. In each round, four parameters \(l_1, r_1, l_2, r_2\) are given satisfying \[ 1 \le l_1 \le r_1 \le n, \quad 1 \le l_2 \le r_2 \le m. \] In each round, player L chooses an index \(x\) from \([l_1, r_1]\). Then player Q chooses an index \(y\) from \([l_2, r_2]\). The score for that round is \(C_{xy} = A_{x} \times B_{y}\).

Player L wants to maximize the score while player Q wants to minimize it. Both players play optimally. Therefore, the final score of each round is given by:

[ \max_{x \in [l_1,r_1]} \begin{cases} A_{x} \times \min{B_{l_2}, \ldots, B_{r_2}} & \text{if } A_{x} \ge 0, \ A_{x} \times \max{B_{l_2}, \ldots, B_{r_2}} & \text{if } A_{x} < 0. \end{cases} ]

For each round, compute the score under the optimal strategies.

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(m\) (the sizes of the arrays \(A\) and \(B\)).
2. The second line contains \(n\) integers representing the array \(A\).
3. The third line contains \(m\) integers representing the array \(B\).
4. The fourth line contains an integer \(q\), the number of rounds.
5. Each of the next \(q\) lines contains four integers \(l_1, r_1, l_2, r_2\) as described above.

outputFormat

Output \(q\) lines, each containing one integer representing the score of the corresponding round according to the optimal strategies.

sample

3 3
1 2 3
-1 0 1
3
1 3 1 3
1 2 2 3
2 3 1 2

-1
0
-2