Complejidonia 并不总是像我们今天所知道的那样和平与平等。富有的 Constantones 控制了当地的媒体，并将 Complejidonia 拖入了他们残酷经济体制的暴政之中：Nlogonialism。这一体制宣扬极端的分配不公，而令人感到奇怪的是，这种不公总是让 Constantones 受益。

当 Constantones 占有绝大部分财富时，Cuadradones 却生活在极度贫困中，而不平等却被冠以 Cuadradones 懒惰和低效的标签而被合理化。Nlogones 通常看不起 Cuadradones，尽管后者和他们一样努力工作，但 Nlogones 认为自己过得更好是因为他们将勤奋和狡黠完美结合。对于 Cubiones 和 Cuaterniones 来说，情况甚至更糟，他们来自邻国，被视为罪犯，同时还被指控窃取了 Complejidonia 的工作岗位。

在国际集体主义与大众代表大会（ICPC）成功推翻 Constantones 并建立新的经济体制后，一切都改变了。新体制致力于公平，并考虑到每个居民在生活中都可能经历经济状况好与坏的时期。

在新体制中，设立了个人可以积累的财富上限 $U$，以及代表个人维持体面生活所需最低财富的下限 $L$。在每个月末，每个居民都会评估自己的财富。那些财富超过 $U$ 的人将把超出上限的部分捐赠给 ICPC，而那些不幸财富低于 $L$ 的人将从 ICPC 获得足够的资助，以达到规定的下限。

Cuadradones 是非常优秀的农民，他们需要你帮助管理财务。长期以来的 Nlogonialism 严重破坏了环境，现在 Complejidonia 的天气非常多变。这对农业产生了巨大影响，农业在好时期和坏时期之间波动。

一位农民记录了他在连续 $N$ 个月内的净收入（收入减去支出）的历史数据 $A_1, A_2, \dots, A_N$。基于这些数据，农民希望规划如何投资自己的财富，以避免未来成为 ICPC 的负担。农民希望能够知道，如果他在第 $B$ 个月初拥有初始财富 $X$，那么在第 $E$ 个月末他将拥有多少财富（考虑到在每个月末，他们可能会捐赠或接受资助，以确保其财富在 $L$ 和 $U$ 之间，含端点）。

输入格式

第一行包含三个整数 $N$ ($1 \le N \le 10^5$)，$L$ 和 $U$ ($1 \le L \le U \le 2 \times 10^6$)，分别表示农民拥有净收入记录的月份数、财富下限和财富上限。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($-10^6 \le A_i \le 10^6$，对于 $i = 1, 2, \dots, N$)，其中 $A_i$ 是第 $i$ 个月的净收入。

第三行包含一个整数 $Q$ ($1 \le Q \le 10^5$)，表示农民感兴趣的情景数量。

接下来的 $Q$ 行中，每行描述一个情景，包含三个整数 $B, E$ ($1 \le B \le E \le N$) 和 $X$ ($L \le X \le U$)，表示农民想知道：如果他在第 $B$ 个月初拥有财富 $X$，且在接下来的每个月 $j = B, B + 1, \dots, E$ 他的净收入为 $A_j$，那么在第 $E$ 个月末他将拥有多少财富。

输出格式

输出 $Q$ 行，每行包含一个整数，表示在对应情景描述的时期结束时，农民最终拥有的财富。

样例

输入样例 1

5 1 41
-10 10 1 -1 -70
10
2 5 31
2 4 30
2 4 29
2 4 28
1 2 20
1 2 10
1 4 11
1 4 10
1 4 40
1 4 41

输出样例 1

1
40
39
38
20
11
11
11
40
40

说明

在第一个情景中，农民的净收入序列为 $[10, 1, -1, -70]$，初始财富为 $31$：

• 在第一个月结束时，他的财富为 $41$。由于 $1 \le 41 \le 41$，他既不需要捐赠，也不会收到资助。
• 在第二个月结束时，他的财富为 $42$。由于 $42 > 41$，他捐赠了 $1$，月末财富为 $41$。
• 在第三个月结束时，他的财富为 $40$。由于 $1 \le 40 \le 41$，他同样不需要捐赠，也不会收到资助。
• 最后，在第四个月结束时，他的财富为 $-30$。由于 $-30 < 1$，他从 ICPC 获得了资助，月末财富为 $1$。

因此，在此情景下，农民最终拥有的财富为 $1$。