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.

Input

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

Output

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

Note

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

Samples

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