Problem Description

Given sequences $a_1, a_2, ..., a_W$ of length $W$ and $b_1, b_2, ..., b_H$ of length $H$, consider a $W \times H$ grid where the cell at the $i$-th column from the left and the $j$-th row from the top contains the value $a_i + b_j$.

You are given $Q$ queries of the following form, which you need to process:

• Given $A$ and $B$, output the maximum sum of values of cells that can be chosen such that the chosen cells form a rectangle and are within the $A$-th column from the left and the $B$-th row from the top.

Note that you cannot choose zero cells.

Input Format

The input is given from the standard input in the following format:

$W$ $H$ $a_1$ $a_2$ ... $a_W$ $b_1$ $b_2$ ... $b_H$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_Q$ $B_Q$

Here, $A_i$ and $B_i$ represent $A$ and $B$ for the $i$-th query, respectively.

Output Format

Output $Q$ lines.

The $i$-th line should contain the result for the $i$-th query.

Sample Input and Output

Sample Input #1

2 2
0 10
0 -1
4
1 1
1 2
2 1
2 2

Sample Output #1

0
0
10
19

Sample Input #2

3 3
1 10 100
1000 10000 100000
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Sample Output #2

1001
11002
111003
2011
22022
222033
3111
33222
333333

Sample Input #3

10 8
2 -4 0 0 -1 4 5 0 -3 0
2 0 0 -3 -5 -5 -4 -4
10
2 6
1 4
1 2
5 7
1 5
7 6
7 4
1 5
3 5
10 7

Sample Output #3

8
8
6
8
8
34
34
8
8
36

Notes/Hints

Constraints

• $1 \leq W, H \leq 2000$
• $1 \leq Q \leq 2000$
• $1 \leq A \leq W$
• $1 \leq B \leq H$
• $-100,000 \leq a_i, b_i \leq 100,000$

见题面 Input 部分

见题面 Output 部分