Problem Description

Score: $ 400 $ points

ZRK received a chessboard from Mr.RKZ for his birthday. The chessboard is $ H $ squares tall and $ W $ squares wide, with all edges parallel or perpendicular to the outer frame. The square at the $ i $-th row from the top and the $ j $-th column from the left is referred to as square $ (i, j) $. Additionally, the square $ (1, 1) $ is black, and adjacent squares are painted in different colors, as shown in the figure below.

However, the chessboard has irregular square sizes. The squares in the $ i $-th row all have a height of $ a_i $, and the squares in the $ j $-th column all have a width of $ b_j $. (Refer to the figure below for more details.)

ZRK, receiving a defective product, decided to calm his mind by playing a game where he calculates "the total area of black rectangles - the total area of white rectangles" for a rectangle with the top-left square at $ (px, py) $ and the bottom-right square at $ (qx, qy) $ for $ Q $ times. For the angry ZRK, find the answers.

The following is an example of a chessboard with $ a_1=7, a_2=35, a_3=5, b_1=14, b_2=9, b_3=50 $.

Input Format

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

$ H $ $ W $ $ Q $ $ a_1 $ $ a_2 $ $ a_3 $ ... $ a_H $ $ b_1 $ $ b_2 $ $ b_3 $ ... $ b_W $ $ px_1 $ $ py_1 $ $ qx_1 $ $ qy_1 $ $ px_2 $ $ py_2 $ $ qx_2 $ $ qy_2 $ $ px_3 $ $ py_3 $ $ qx_3 $ $ qy_3 $ ... $ px_Q $ $ py_Q $ $ qx_Q $ $ qy_Q $

Output Format

Output $ Q $ lines.

The $ i $-th line should contain the "total area of black rectangles - total area of white rectangles" for the rectangle with the top-left square at $ (px_i, py_i) $ and the bottom-right square at $ (qx_i, qy_i) $.

Sample Input and Output

Sample Input #1

3 3 2
7 35 5
14 9 50
1 1 2 2
1 1 3 2

Sample Output #1

-140
-115

Sample Input #2

5 5 5
1 6 15 15 7
14 11 11 5 14
3 5 5 5
2 3 3 4
1 5 3 5
4 3 4 4
2 2 4 3

Sample Output #2

98
54
140
-90
0

Notes/Hints

Constraints

• $ H, W, Q $ are integers between $ 1 $ and $ 100,000 $ inclusive.
• $ a_i, b_i $ are integers between $ 1 $ and $ 10,000 $ inclusive.
• $ px_i, qx_i $ are integers between $ 1 $ and $ H $ inclusive.
• $ py_i, qy_i $ are integers between $ 1 $ and $ W $ inclusive.
• $px_i \leq qx_i$, $py_i \leq qy_i$.

Subtasks

Subtask 1 \[ $ 30 $ points \]

• Satisfies $H, W \leq 1,000$.
• Satisfies $Q \leq 5$.

Subtask 2 \[ $ 120 $ points \]

• Satisfies $H, W \leq 1,000$.

Subtask 3 \[ $ 250 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分