CF2132E Arithmetics Competition

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.

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$$$.

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