E. Arithmetics Competition
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the arithmetic competition, participants need to achieve the highest possible sum from the cards they have. In the team "fst_ezik", Vadim has $$$n$$$ cards with numbers $$$a_i$$$, and Kostya has $$$m$$$ cards with numbers $$$b_i$$$. In each of the $$$q$$$ rounds, they want to win, but this time the rules of the competition are slightly different from the usual ones.

In each round, the participants are given three numbers $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$. The team "fst_ezik" must choose exactly $$$z_i$$$ cards from all the cards they have, but Vadim can choose no more than $$$x_i$$$ cards from his set, and Kostya can choose no more than $$$y_i$$$ cards from his set. Help them find the highest possible sum for each of the $$$q$$$ rounds.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The descriptions of the test cases follow.

In the first line of each test case, three integers $$$n$$$, $$$m$$$, $$$q$$$ are given $$$(1 \le n, m \le 2 \cdot 10^5, 1 \le q \le 10^5)$$$ — the number of cards Vadim has, the number of cards Kostya has, and the number of rounds in the competition.

The second line contains $$$n$$$ integers $$$a_i$$$ — the numbers on Vadim's cards $$$(1 \le a_i \le 10^9)$$$.

The third line contains $$$m$$$ integers $$$b_i$$$ — the numbers on Kostya's cards $$$(1 \le b_i \le 10^9)$$$.

The following $$$q$$$ lines describe the rounds with three integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ $$$(0 \le x_i \le n, 0 \le y_i \le m, 0 \le z_i \le x_i + y_i)$$$ — the limit on the number of cards Vadim can choose, the limit on the number of cards Kostya can choose, and the number of cards they need to select together.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$, the sum of $$$m$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$q$$$ numbers — the highest possible sum for the corresponding round.

Example
Input
4
3 4 5
10 20 30
1 2 3 4
0 0 0
3 4 7
3 4 4
1 4 4
2 2 4
5 5 2
500000000 300000000 100000000 900000000 700000000
800000000 400000000 1000000000 600000000 200000000
1 4 3
5 2 6
4 4 1
100 100 20 20
100 100 20 20
4 4 5
3 3 6
2 363 711
286 121 102
1 1 1
3 1 1
1 2 0
1 3 2
0 1 0
3 3 3
Output
0
70
64
39
57
2700000000
4200000000
420
711
711
0
997
0
1360