题目描述

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

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

$$f_i = \max_{\substack{1 \le x \le i \le y \le n \\ l \le y - x + 1 \le r}} \,\, \sum_{k=x}^{y}a_k $$

输入格式

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

输出格式

一行 (n) 个整数，第 (i) 个整数表示 (f_i)。

样例

输入

5 1 3
-1 -6 7 7 -4

输出

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 n \le 10^5)，(1 \le l \le r \le n)，(-10^9 \le a_i \le 10^9)。