Little L and Little Q are playing a strategy game.

There is an array $A$ of length $n$ and an array $B$ of length $m$. Based on these, a matrix $C$ of size $n \times m$ is defined, satisfying $C_{ij} = A_i \times B_j$. All indices are 1-based.

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$ and $1 \le l_2 \le r_2 \le m$.

In the game, Little L first chooses an index $x$ such that $l_1 \le x \le r_1$, and then Little Q chooses an index $y$ such that $l_2 \le y \le r_2$. The score for this round is defined as $C_{xy}$.

Little L's goal is to make this score as large as possible, while Little Q's goal is to make this score as small as possible. Both are sufficiently intelligent players and will always adopt their optimal strategies.

What is the score of each round under the players' optimal strategies?

Input

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

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

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

The next $q$ lines each contain four positive integers, representing $l_1, r_1, l_2, r_2$ for that round.

Output

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

Examples

Input 1

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

Output 1

0
4

Note

In this dataset, matrix $C$ is as follows: 0 0 -3 4 6 -8

In the first round, regardless of whether Little L chooses $x = 2$ or $x = 3$, Little Q has a way to choose a $y$ such that the final score is negative. Therefore, it is optimal for Little L to choose $x = 1$, as the score will then be $0$.

In the second round, since Little L can choose $x = 2$, Little Q can only choose $y = 2$, resulting in a score of $4$.

Input 2

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

Output 2

0
-2
3
2
-1

Input 3

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

Input 4

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

Constraints

For all data, $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$.

Special condition 1: Guaranteed $A_i, B_i > 0$.

Special condition 2: Guaranteed that for each round, either $l_1 = r_1$ or $l_2 = r_2$.