题目描述

利用空闲时间，$\text{BX}$希望外出工作，工作开始之前，公司就会给$\text{BX}$一个评估值$X_0$，之后每天$\text{BX}$的评估值都是根据上一天的评估值和当天公司的运行状况得出，即$X_i=X_{i-1}+D_i$,但是每天的评估值有一个上限，也就是说完整的评估公式因该是:

现在$\text{BX}$已经知道了该公司对自己的初始评估值$X_0$、公司每天的运行状况$D_i$、每天的评估上限$L_i$，他的空闲时间是从第$A$天到第$B$天，他希望找到一段时间$i,j (A≤i≤j≤B)$，使得从第$i$天开始工作，到第j天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都小于初始评估值$X_0$，$\text{BX}$可以选择不工作，从而得到最大的评估值。

输入格式

输入的第一行包含两个整数$N,M$，分别表示总共工作天数和询问数。

第二行$N$个数，表示$D_i$。第三行$N$个数，表示$L_i$。

以下$M$行，每行$3$个数$A,B,X_0$，表示一次询问。

输出格式

$M$行，每行输出一个整数，表示评估的最大值

样例

6 3
-6 5 3 2 -3 4
8 10 8 1 9 9
1 3 9
2 6 3
3 4 0

10
8
3

数据规模与约定

对于$100\%$数据,满足$N,M<50001,|Di|<10001,0\le Li<1000000001$.