众所周知，zrq 在机房不仅可以学物理，甚至可以学竞赛！
zrq 看着自己的一堆物理书（每本物理书有权值，表示难易度，即 ），同时想出了一对 。他先将这些书在地上排成一行，他想知道对于某本书 ，所有经过这本书、且长度在 之间的连续子序列中，最大的连续子序列的权值和。即对于每一个 求：
第一行三个整数 ，表示序列长度、区间范围。 第二行 个整数，其中第 个整数表示 。
一行 个整数，第 个整数表示 。
输入
5 1 3 -1 -6 7 7 -4
输出
0 8 14 14 10
对于 的数据，保证
