Farming Sesh

Erin loves farming PP (performance points) in osu!, and he wants to maximize his gains. He has an assortment of $N$ beatmaps which he has played before, numbered from $0$ to $N-1$, where each beatmap has an assigned PP value. He also has $M$ other beatmaps that he hasn't played yet, which are likewise numbered from $0$ to $M-1$ and each one of the $N+M$ beatmaps has an assigned PP value.

Task

In order to quench his addiction, he decides to take a look at $Q$ scenarios of the type: "What if my top plays are only made up of the already played maps from $[l_1, r_1]$, and I can take any number, $K$, of unplayed maps from $[l_2, r_2]$, and overwrite any $K$ of my top plays; what is the maximum possible PP sum that I can obtain, if I choose $K$ and the $K$ beatmaps optimally?"

For each of these scenarios, you have to find the maximum PP sum that can be obtained, choosing $K$ optimally.

Input data

The first line contains the space-separated integers $N$, $M$ and $Q$.
The second line contains $N$ space-separated integers, $A_0, A_1, \dots, A_{N-1}$.
The third line contains $M$ space-separated integers, $B_0, B_1, \dots, B_{M-1}$.
Each of the next $Q$ lines contain four space-separated integers, $l_1, r_1, l_2, r_2$.

Output data

The output file must contain $Q$ lines corresponding to the test cases, each consisting of 64-bit integer $\mathtt{ans}_{i}$.

Constraints and clarifications

• $1 \le N \le 500 \ 000$.
• $1 \le M \le 500 \ 000$.
• $1 \le Q \le 500 \ 000$.
• $1 \le A_i \le 1\ 000\ 000\ 000$ for each $i=0\ldots N-1$.
• $1 \le B_i \le 1\ 000\ 000\ 000$ for each $i=0\ldots M-1$.
• $0 \le {l_1}_i \le {r_1}_i < N$, for each $i=0\ldots Q-1$.
• $0 \le {l_2}_i \le {r_2}_i < M$, for each $i=0\ldots Q-1$.

Example

stdin

5 4 5
50 40 26 100 72
500 999 1 2
0 4 0 3
1 3 0 2
3 4 2 3
3 4 1 2
1 4 0 1

stdout

1721
1599
172
1099
1671

Explanation

In the first scenario, your played maps are $\{50, 40, 26, 100, 72\}$, and your unplayed maps are $\{500, 999, 1, 2\}$. Choosing to play the beatmaps with values $500$ and $999$, and overwriting the already played ones with values $26$ and $40$, you obtain the optimal sum of $50 + 999 + 500 + 100 + 72 = 1721$.

In the second scenario, your played maps are $\{40, 26, 100\}$, and your unplayed maps are $\{500, 999, 1\}$. Choosing to play the beatmaps with values $500$ and $999$, and overwriting the already played ones with values $26$ and $40$, you obtain the optimal sum of $999 + 500 + 100 = 1599$.

In the third scenario, your played maps are $\{100, 72\}$, and your unplayed maps are $\{1, 2\}$. Choosing to keep all of your current top plays, you obtain the optimal sum of $100 + 72 = 172$.

In the fourth scenario, your played maps are $\{100, 72\}$, and your unplayed maps are $\{999, 1\}$. Choosing to play the beatmap with value $999$ and overwriting the already played one with value $72$, you obtain the optimal sum of $999 + 100 = 1099$.

In the fifth scenario, your played maps are $\{40, 26, 100, 72\}$, and your unplayed maps are $\{500, 999\}$. Choosing to play the beatmaps with values $500$ and $999$ and overwriting the already played ones with values $26$ and $40$, you obtain the optimal sum of $999 + 500 + 100 + 72 = 1671$.