Person in Charge

• SleepingCup

Problem Description

Little L and Little Q are playing a strategy game.

Given an array $A$ of length $n$ and an array $B$ of length $m$, we define an $n \times m$ matrix $C$ such that $C_{ij} = A_i \times B_j$. All indices start from $1$.

The game consists of $q$ rounds. For each round, four parameters $l_1, r_1, l_2, r_2$ are given in advance, satisfying $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le m$.

In each round, Little L first selects an index $x$ in the range $[l_1, r_1]$, then Little Q selects an index $y$ in the range $[l_2, r_2]$. The score of both players for this round is defined as $C_{xy}$.

Little L aims to maximize this score, while Little Q aims to minimize it. Both players are sufficiently smart and will always adopt the optimal strategy in each move.

Please find the score obtained in each round under their optimal strategies.

Input Format

The first line contains three positive integers $n, m, q$, representing the length of array $A$, the length of array $B$, and the number of game rounds respectively.

The second line contains $n$ integers, denoting the elements $A_i$ of array $A$.

The third line contains $m$ integers, denoting the elements $B_i$ of array $B$.

The next $q$ lines each contain four positive integers, representing $l_1, r_1, l_2, r_2$ for the corresponding round of the game.

Output Format

Output $q$ lines, each with an integer representing the score of the corresponding round under the optimal strategies of Little L and Little Q.

Samples

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

0
4

6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3

0
-2
3
2
-1

Sample (1) Explanation

Matrix $C$ for this test case is as follows:

$$\begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix}$$

In the first round, no matter whether Little L chooses $x=2$ or $x=3$, Little Q can always select a corresponding $y$ to make the final score negative. Thus, the optimal choice for Little L is to select $x=1$, which guarantees a score of $0$.

In the second round, Little L can choose $x=2$, and Little Q has no choice but to select $y=2$, resulting in a score of $4$.

Sample (3)

See game/game3.in and game/game3.ans in the contestant's directory.

Sample (4)

See game/game4.in and game/game4.ans in the contestant's directory.

Data Range

For all test data, $1 \le n, m, q \le 10^5$ and $-10^9 \le A_i, B_i \le 10^9$. For each round of the game, $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le m$.

Test Case No.	$n, m, q \le$	Special Condition
$1$	$200$	1, 2
$2$		1
$3$		2
$4 \sim 5$		None
$6$	$1000$	1, 2
$7 \sim 8$		1
$9 \sim 10$		2
$11 \sim 12$		None
$13$	$10^5$	1, 2
$14 \sim 15$		1
$16 \sim 17$		2
$18 \sim 20$		None

Where:

• Special Property 1: It is guaranteed that $A_i, B_i > 0$.
• Special Property 2: For each round of the game, either $l_1 = r_1$ or $l_2 = r_2$.