今天,KQ 在圣杯学院进行考试。一位严厉的老师布置了一个KQ无法解决的任务。他得到了两个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$。 KQ 可以对数组执行以下操作:
- 选择索引 $$$i$$$ ($$$1\le i\lt n$$$) 并将 $$$a_i$$$ 替换为 $$$a_{i+1}$$$。
- 选择索引 $$$i$$$ ($$$1\le i\le n$$$) 并将 $$$a_i$$$ 替换为 $$$b_i$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ $$$(1\le n, q\le 2 \cdot 10^5)$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,...,a_n$$$ $$$(1\le a_i\le 10^4)$$$。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2,...,b_n$$$ $$$(1\le b_i\le 10^4)$$$。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ $$$(1\le l\le r\le n)$$$。
保证所有测试用例中 $$$n$$$ 的值之和以及 $$$q$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出以空格分隔的 $$$q$$$ 数字 — 总和的最大值 $$$(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$$$。
示例
输入复制
43 13 2 11 2 31 31 1121 13 26 7 59 6 81 22 34 34 3 2 15 1 3 11 22 43 4
输出复制
9217 168 7 4
注意
考虑第一个测试用例。将 $$$a_3$$$ 替换为 $$$b_3$$$,$$$a = [3, 2, 3]$$$。将 $$$a_2$$$ 替换为 $$$a_3$$$,$$$a = [3, 3, 3]$$$。总和 $$$a_1 + a_2 + a_3 = 9$$$。