CF2193C.Replace and Sum

Today, KQ has an exam at the Grail Academy. A strict teacher gave a task that KQ could not solve. He was given two arrays $a$ and $b$ of length $n$. KQ is allowed to perform the following operations on the arrays:

• Choose an index $i$ ($1\le i\lt n$) and replace $a_i$ with $a_{i+1}$.
• Choose an index $i$ ($1\le i\le n$) and replace $a_i$ with $b_i$.

Now he has $q$ queries. Each query is described by two numbers $l$ and $r$. His task is to find the maximum value of the sum $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ for each query, if he can perform any number of operations on any elements of the array. Since he is not skilled enough for this, he asks for your help.

今天，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)$ 的最大可能值。由于他尚不具备解决此题的能力，因此向你求助。

Each test consists of several test cases. The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $q$ $(1\le n, q\le 2 \cdot 10^5)$.

The second line of each test case contains $n$ integers $a_1, a_2,...,a_n$ $(1\le a_i\le 10^4)$.

The third line of each test case contains $n$ integers $b_1, b_2,...,b_n$ $(1\le b_i\le 10^4)$.

The following $q$ lines contain two integers $l$ and $r$ $(1\le l\le r\le n)$.

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

每个测试包含若干测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\le n, q\le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2,\dots,a_n$（$1\le a_i\le 10^4$）。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2,\dots,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$。

For each test case, output $q$ numbers separated by spaces — the maximum values of the sums $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$.

对于每个测试用例，输出 $q$ 个用空格分隔的数字——即和 $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ 的最大值。

Consider the first test case. Replace $a_3$ with $b_3$, $a = [3, 2, 3]$. Replace $a_2$ with $a_3$, $a = [3, 3, 3]$. The sum $a_1 + a_2 + a_3 = 9$.

考虑第一个测试用例。将 $a_3$ 替换为 $b_3$，得到 $a = [3, 2, 3]$。再将 $a_2$ 替换为 $a_3$，得到 $a = [3, 3, 3]$。此时和 $a_1 + a_2 + a_3 = 9$。