在算术比赛中,参赛者需要从他们拥有的卡片中获得尽可能高的总和。在团队中 “fst_ezik”,Vadim 有 $$$n$$$ 牌,号码为 $$$a_i$$$,Kostya 有 $$$m$$$ 牌,号码为 $$$b_i$$$。在每一轮$$$q$$$中,他们都想获胜,但这一次的比赛规则与平常略有不同。
在每一轮中,参与者都会获得三个数字 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$。团队 “fst_ezik” 必须从他们拥有的所有牌中准确选择$$$z_i$$$牌,但Vadim可以从他的牌组中选择不超过$$$x_i$$$牌,而Kostya可以从他的牌组中选择不超过$$$y_i$$$牌。帮助他们找到每一轮 $$$q$$$ 中可能的最高金额。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。测试用例的描述如下。
在每个测试用例的第一行,给出三个整数 $$$n$$$、$$$m$$$、$$$q$$$ $$$(1 \le n, m \le 2 \cdot 10^5, 1 \le q \le 10^5)$$$ - Vadim 拥有的牌数、Kostya 拥有的牌数以及比赛的轮数。
第二行包含 $$$n$$$ 整数 $$$a_i$$$ - Vadim 卡片上的数字 $$$(1 \le a_i \le 10^9)$$$。
第三行包含 $$$m$$$ 整数 $$$b_i$$$ — Kostya 卡片上的数字 $$$(1 \le b_i \le 10^9)$$$。
以下 $$$q$$$ 行用三个整数描述回合 $$$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)$$$ — 卡牌数量限制 Vadim可以选择的卡片数量、Kostya 可以选择的卡片数量的限制以及他们需要一起选择的卡片数量。
保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 数字 — 相应轮次的最高可能总和。
示例
输入复制
43 4 510 20 301 2 3 40 0 03 4 73 4 41 4 42 2 45 5 2500000000 300000000 100000000 900000000 700000000800000000 400000000 1000000000 600000000 2000000001 4 35 2 64 4 1100 100 20 20100 100 20 204 4 53 3 62 363 711286 121 1021 1 13 1 11 2 01 3 20 1 03 3 3
输出复制
0 70 64 39 57 2700000000 4200000000 420 711 711 0 997 0 1360