题目描述

众所周知，zrq 在机房不仅可以学物理，甚至可以学竞赛！

zrq 看着自己的一堆物理书（每本物理书有权值，表示难易度，即 $a_i$），同时想出了一对 $l,r$。他先将这些书在地上排成一行，他想知道对于某本书 $i$，所有经过这本书、且长度在 $[l,r]$ 之间的连续子序列中，最大的连续子序列的权值和。即对于每一个 $i$ ，求：

$$ \Large fi = \max{1 \le x \le i \le y \le n \mathop{且}\:\; l \le y - x + 1 \le r} \,\, \sum_{k=x}^{y}a_k $$

输入格式

第一行三个整数 $n,l,r$，表示序列长度、区间范围。
第二行 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示 $f_i$

样例

input

5 1 3
-1 -6 7 7 -4

output

0 8 14 14 10

数据范围与提示

对于 $10 \%$ 的数据，保证$n \le 10$
对于另外 $10 \%$ 的数据，保证 $\forall i,j \in [1,n] \cap Z, a_i=a_j$
对于另外 $10 \%$ 的数据，保证 $r - l + 1 \le 10$
对于另外 $10 \%$ 的数据，保证 $\forall i \in [1, n] \cap Z, a_i = i$
对于另外 $10 \%$ 的数据，保证 $\forall i \in [1, n] \cap Z, a_i \ge 0$
对于另外 $10 \%$ 的数据，保证 $\forall i \in [1, n] \cap Z, 0 \le | a_i | \le 10$
对于另外 $10 \%$ 的数据，保证 $\forall i \in [1, n] \cap Z, a_i = 0$
对于 $100 \%$ 的数据，保证$1 \le l \le r \le n \le 10^5,0 \le | a_i | \le 10^5$