F. 乘法与加法
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给你两个长度为 $$$n$$$ 的数组 $$$a,b$$$。

令 $$$f(x,y,k)$$$ 表示在最多进行 $$$k$$$ 次赋值操作 $$$a_i:=b_i(1\le i\le n)$$$ 的情况下 $$$\sum_{i=x}^y\sum_{j=x}^y a_i\times a_j-\sum_{i=x}^y\sum_{j=x}^y (a_i+a_j)$$$ 的最大值。

你需要对于 $$$q$$$ 个独立的提问的 $$$x,y,k$$$ 分别求出 $$$f(x,y,k)$$$ 的最大值。

独立的提问的含义为，数组 $$$a,b$$$ 是不变的，这就意味着对于每个提问你只是假定操作去回答，而不会实际改变数组 $$$a,b$$$。

Input

第一行，两个整数 $$$n,q(1\le n,q \le 2·10^5)$$$，代表数组长度和询问次数。

第二行，$$$n$$$ 个整数 $$$a_i(-10^9\le a_i \le 10^9)$$$，代表数组 $$$a$$$。

第三行，$$$n$$$ 个整数 $$$b_i(-10^9\le b_i \le 10^9)$$$，代表数组 $$$b$$$。

接下来连续的 $$$q$$$ 行，每行三个整数 $$$x,y,k(1\le x \le y\le n,0\le k \le 10^9)$$$，代表你需要求的 $$$f(x,y,k)$$$ 的最大值。

Output

对于每次提问，输出一行整数代表当前询问下的 $$$f(x,y,k)$$$ 的最大值。

Examples
Input
5 5
1 2 3 4 5
1 3 5 7 9
1 1 3
1 2 1
1 3 7
1 4 3
1 5 5
Output
-1
0
27
128
375
Input
5 6
-3 2 8 -4 0
1 2 1 2 1
1 5 0
2 5 1
3 5 2
4 5 3
5 5 4
1 5 5
Output
-21
48
55
32
0
56
Input
10 10
10 7 5 -7 10 -1 2 7 9 -3
-2 0 -4 7 1 -8 -1 -9 6 -5
2 3 9
4 4 8
9 10 5
3 10 4
6 7 6
3 8 4
6 10 8
5 9 9
1 1 8
6 6 4
Output
96
63
12
720
117
925
459
459
80
80