题目描述

今天，KQ 在圣杯学院有一场考试。一位严格的老师布置了一道 KQ 无法解决的题目。他得到了两个长度为 $n$ 的数组 $a$ 和 $b$。KQ 被允许对数组执行以下操作：

• 选择一个索引 $i$（$1 \le i < n$）并将 $a_i$ 替换为 $a_{i+1}$。
• 选择一个索引 $i$（$1 \le i \le n$）并将 $a_i$ 替换为 $b_i$。

现在他有 $q$ 个查询。每个查询由两个数字 $l$ 和 $r$ 描述。他的任务是对于每个查询，如果可以对数组的任意元素执行任意次数的操作，找出和 $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ 的最大值。由于他不够熟练，他请求你的帮助。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $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)$ 的最大值。

样例

4
3 1
3 2 1
1 2 3
1 3
1 1
1
2
1 1
3 2
6 7 5
9 6 8
1 2
2 3
4 3
4 3 2 1
5 1 3 1
1 2
2 4
3 4

9
2
17 16
8 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$。

翻译由 DeepSeek 生成。

来源

Codeforces 2193C，英文题名 Replace and Sum。