#479. 乘法与加法

给你两个长度为 $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$。

第一行，两个整数 $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)$ 的最大值。

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

输入样例1

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

输出样例1

-1
0
27
128
375

输入样例2

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

输出样例2

96
63
12
720
117
925
459
459
80
80