题目描述

利用空闲时间，BX 希望外出工作，工作开始之前，公司就会给 BX 一个评估值 $X_0$，之后每天 BX 的评估值都是根据上一天的评估值和当天公司的运行状况得出，即 $X_i = X_{i-1} + D_i$，但是每天的评估值有一个上限，也就是说完整的评估公式因该是 $X_i = min \{X_{i - 1} + D_i,L_i\}$。现在 BX 已经知道了该公司对自己的初始评估值 $X_0$、公司每天的运行状况 $D_i$、每天的评估上限 $L_i$，他的空闲时间是从第 $A$ 天到第 $B$ 天，他希望找到一段时间 $[i,j],(A\le i\le j\le B)$，使得从第 $i$ 天开始工作，到第 $j$ 天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都小于初始评估值 $X_0$，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\le 5 \times 10^4,\mid D_i \mid \le 10^4,0\le L_i\le 10^9$。