题目描述

利用空闲时间，BX 希望外出工作，工作开始之前，公司就会给 BX 一个评估值 X0​，之后每天 BX 的评估值都是根据上一天的评估值和当天公司的运行状况得出，即 Xi​=Xi−1​+Di​，但是每天的评估值有一个上限，也就是说完整的评估公式因该是 Xi​=min{Xi−1​+Di​,Li​}。现在 BX 已经知道了该公司对自己的初始评估值 X0​、公司每天的运行状况 Di​、每天的评估上限 Li​，他的空闲时间是从第 A 天到第 B 天，他希望找到一段时间 [i,j],(A≤i≤j≤B)，使得从第 i 天开始工作，到第 j 天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都小于初始评估值 X0​，BX 可以选择不工作，从而得到最大的评估值。

输入格式

输入的第一行包含两个整数 N,M，分别表示总共工作天数和询问数。
第二行 N 个数，表示 Di​。
第三行 N 个数，表示 Li​。
以下 M 行，每行 3 个数 A,B,X0​，表示一次询问。

输出格式

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≤5×104,∣Di​∣≤104,0≤Li​≤109。