问题描述

水果市场刚开市时，架子上有 $n$ 颗苹果，每颗苹果有自己的标价，小明想要买 $x$ 颗苹果，但他怕太便宜的苹果品质不好，所以他决定买第 $k$ 便宜至第 $k + x - 1$ 便宜的 $x$ 颗。

例如当 $n = 5, x = 2, k = 3$ 时，$5$ 颗苹果的标价分别为：$15, 12, 13, 13, 19$，那么第一便宜至第五便宜的苹果分别是：$12, 13, 13, 15, 19$，所以小明会买的苹果总价格是 $13 + 15 = 28$。

我们要你算出小明总共会花多少钱买 $x$ 颗苹果。

但事情没有那么简单，之后工作人员又依序放上新的 $m$ 颗苹果，每颗苹果也有各自的标价。我们想要知道，每放上一颗新的苹果时，第 $k$ 便宜的苹果至第 $k + x - 1$ 便宜的苹果总价钱是多少。

输入格式

输入共有 $3$ 行。

第一行有四个正整数，依序代表 $n, m, x, k$，满足 $x + k - 1 \le n$。

第二行有 $n$ 个正整数，代表刚开市时架子上的 $n$ 个苹果的价钱。

第三行有 $m$ 个正整数，其中的第 $i$ 个数为工作人员新放上的第 $i$ 颗苹果的价钱。

输入的相邻两个数之间都恰有一个空白分隔。

任何苹果的价钱都不会超过 $10^8$。

输出格式

输出共有 $m + 1$ 行。

第 $1$ 行输出刚开市时，第 $k$ 便宜至第 $k + x - 1$ 便宜的 $x$ 颗苹果的价格总和。

对于之后的 $m$ 行，每一行都输出一个正整数，代表每放上一颗新的苹果后，第 $k$ 便宜至第 $k + x - 1$ 便宜的 $x$ 颗苹果的价格总和。

数据范围

对于 $20\%$ 的数据，$n, m \le 100$。

对于另外 $40\%$ 的数据，$n, m \le 10^5$，$x = 1$。

对于所有的数据，$n, m \le 10^5$ 。

样例输入1

5 3 2 3
15 12 13 13 19
17 14 13

样例输出1

28
28
27
26

样例输入2

3 4 1 3
100 90 12
150 190 2 1

样例输出2

100
100
100
90
12