题目描述

黑胡椒有一个序列，一天他对这个序列产生了一个问题，他想知道对于序列中第 $i$ 个元素 $a_i$，所有长度在 $[l,r]$ 之间的包含这个元素的区间中，区间和最大的区间是多少。

即令

$$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$$

对每个元素 $a_i$ ,求出 $f_i$ 。

输入格式

第一行三个整数 $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\mathbb Z$，$a_i=a_j$。

对于另外 $10\%$ 的数据，保证 $r-l+1\le 10$。

对于另外 $10\%$ 的数据，保证 $\forall i\in[1,n]\cap\mathbb Z$，$a_i=i$。

对于另外 $10\%$ 的数据，保证 $\forall i\in[1,n]\cap\mathbb Z$，$a_i\ge 0$。

对于另外 $10\%$ 的数据，保证 $\forall i\in[1,n]\cap\mathbb Z$，$0\le |a_i|\le 10$。

对于另外 $10\%$ 的数据，保证 $\forall i\in[1,n]\cap\mathbb Z$，$a_i=0$。

对于 $100\%$ 的数据，保证 $1\le l\le r\le n\le 10^5$，$0\le |a_i|\le 10^5$。