seuOJ479 - 乘法与加法

题目描述

给你两个长度为 nn 的数组 a,ba,b。

令 f(x,y,k)f(x,y,k) 表示在最多进行 kk 次赋值操作 ai:=bi(1≤i≤n)a_i:=b_i(1\le i\le n) 的情况下 ∑i=xy∑j=xyai×aj−∑i=xy∑j=xy(ai+aj)\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) 的最大值。

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

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

输入格式

第一行，两个整数 n,q(1≤n,q≤2⋅105)n,q(1\le n,q \le 2·10^5)，代表数组长度和询问次数。
第二行，nn 个整数 ai(−109≤ai≤109)a_i(-10^9\le a_i \le 10^9)，代表数组 aa。
第三行，nn 个整数 bi(−109≤bi≤109)b_i(-10^9\le b_i \le 10^9)，代表数组 bb。
接下来连续的 qq 行，每行三个整数 x,y,k(1≤x≤y≤n,0≤k≤109)x,y,k(1\le x \le y\le n,0\le k \le 10^9)，代表你需要求的 f(x,y,k)f(x,y,k) 的最大值。

输出格式

对于每次提问，输出一行整数代表当前询问下的 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