F. Cool Operations
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n$$$ and $$$q$$$ and two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$.

You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you're given three integers $$$k_i, l_i$$$, and $$$r_i$$$.

At first, a variable $$$x$$$ is set to $$$k_i$$$. Then, for each $$$j$$$ from $$$l_i$$$ to $$$r_i$$$, you must choose exactly one of the following two types of operations:

  1. set $$$x := x + a_j$$$;
  2. set $$$x := \max(x, b_j)$$$.

You need to find the maximum possible value of $$$x$$$ for each query.

Input

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases.

  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n,q \leq 5 \cdot 10^5$$$);
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$);
  • The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

Each of the next $$$q$$$ lines contains three integers $$$k_i, l_i$$$, and $$$r_i$$$ ($$$-10^9 \leq k_i \leq 10^9, 1 \le l_i \le r_i \le n$$$).

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

Output

For each query, output an integer in a new line  — the maximum possible value of $$$x$$$.

Examples
Input
1
4 5
10 2 3 -1
20 24 28 -10
8 1 2
17 1 2
19 2 3
25 2 3
-2 4 4
Output
24
29
28
30
-2
Input
1
5 5
756829654 557600139 843962687 -24632597 -866775049
505319834 616877613 657487273 912786344 924284486
481299777 1 3
-566119234 2 4
478992801 1 2
-694494781 3 5
-579759578 1 4
Output
2639692257
1460840300
1793422594
924284486
1906882660
Note

In the first query of the first test case, we have $$$x=8$$$ at first. We can do the following operations:

  1. for $$$j=1$$$, set $$$x := x+a_1 =8+10=18$$$;
  2. for $$$j=2$$$, set $$$x := \max(x, b_2)=\max(18,24)=24$$$.

It can be proven that $$$24$$$ is the maximum possible value of $$$x$$$.

In the second query of the first test case, we have $$$x=17$$$ at first. We can do the following operations:

  1. for $$$j=1$$$, set $$$x := x+a_1 =17+10=27$$$;
  2. for $$$j=2$$$, set $$$x := x+a_2 =27+2=29$$$.

It can be proven that $$$29$$$ is the maximum possible value of $$$x$$$.