Description

Xiao L and Xiao Q are playing a strategy game.

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

The game has $q$ rounds. In each round, $4$ 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 the game, Xiao L first chooses an index $x$ between $l_1 \sim r_1$, and then Xiao Q chooses an index $y$ between $l_2 \sim r_2$. The score of this round is defined as $C_{x y}$.

Xiao L’s goal is to make this score as large as possible, while Xiao Q’s goal is to make it as small as possible. Both players are sufficiently smart and always use optimal strategies.

Question: Under both players’ optimal strategies, what is the score in each round?

Input Format

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

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

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

Then follow $q$ lines. Each line contains four positive integers, representing $l_1, r_1, l_2, r_2$ for this round.

Output Format

Output $q$ lines. Each line contains one integer, representing the score in that round under the players’ optimal strategies.

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

Hint

Sample Explanation #1

In this dataset, the matrix $C$ is as follows:

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

In the first round, no matter whether Xiao L chooses $x = 2$ or $x = 3$, Xiao Q can choose some $y$ to make the final score negative. Therefore, choosing $x = 1$ is optimal for Xiao L, because then the score is guaranteed to be $0$.

In the second round, since Xiao L can choose $x = 2$, Xiao Q can only choose $y = 2$, so the score is $4$.

Sample #3

See the attachments game/game3.in and game/game3.ans.

Sample #4

See the attachments game/game4.in and game/game4.ans.

Constraints

For all testdata, $1 \le n, m, q \le {10}^5$, $-{10}^9 \le A_i, B_i \le {10}^9$. For each round, $1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le m$.

Test point ID	$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

Here, special property 1: guarantee $A_i, B_i > 0$.
Special property 2: guarantee that for each round, either $l_1 = r_1$ or $l_2 = r_2$.

Translated by ChatGPT 5