要过年了！《蓝猫淘气三千问》里的淘气决定囤积一些好吃的以完成“每逢佳节胖十斤”的计划。然而，超威蓝猫早就把他之前的大米都偷吃完了，淘气只好出门买一些。

这天，淘气带着 $m$ 块钱来到了一家有 $n$ 袋大米正在出售的商店。这 $n$ 袋大米的编号依次为 $1, \dots, n$，其中第 $i$ 袋大米的重量为 $w_i$，价格为 $p_i$。

正当淘气觉得价格太贵准备走的时候，老板突然告诉他：这家商店正在进行年底促销，有两种促销方式！

1. 买 $a$ 赠一：每买 $a$ 袋大米，即可白送一袋没有买的大米；
2. 买 $b$ 赠一：每买 $b$ 袋大米，即可白送一袋没有买的大米。

不仅如此，这两种促销方式还可以同时使用。也即，如果淘气如果买了 $k$ 袋大米，那么他就可以在剩下的没有买的大米中，挑至多 $\lfloor k/a \rfloor + \lfloor k/b \rfloor$ 袋免费拿走（其中$\lfloor x \rfloor$ 表示小于等于 $x$ 的最大的整数）。

现在淘气想知道，对于每一个 $1 \le j \le m$，在花费至多 $j$ 块钱的情况下，从商店买走或免费拿走的大米总重量最大是多少。

输入格式

第一行四个正整数 $n, m, a, b$。保证 $1 \le a \le b \le n$。

第二行包含 $n$ 个正整数，分别表示 $w_1, \dots, w_n$。

第三行包含 $n$ 个正整数，分别表示 $p_1, \dots, p_n$。保证 $1 \le p_i \le m$。

输出格式

一行，包含 $m$ 个整数。其中第 $j$ 个整数表示在花费至多 $j$ 块钱的情况下，从商店买走或免费拿走的大米的最大总重量。

样例一

input

8 4 1 2
4 5 3 2 6 7 3 1
2 2 2 2 2 2 2 2

output

0 13 13 25

explanation

• 如果淘气只花一块钱，那么什么都买不到。
• 如果淘气花两块钱，那么淘气可以买下重量为 $7$ 的大米，然后利用 “买一赠一” 拿走一袋重量为 $6$ 的大米。
• 如果淘气花四块钱，那么淘气可以买下重量为 $4$ 和 $5$ 的大米，然后利用 “买一赠一” 和 “买二赠一” 拿走三袋重量分别为 $3, 6, 7$ 的大米。

样例二

input

10 15 3 3
9 9 2 6 9 7 6 2 8 5
6 2 2 2 9 2 8 7 3 2

output

0 9 9 16 17 40 42 45 48 48 53 53 63 63 63

explanation

在这个例子里，$a = b = 3$，也就是 “买三赠二”。淘气可买下的米的重量随着花的钱数递增。当淘气可以花 $13$ 块钱的时候，淘气可以买走第 $2, 3, 4, 6, 9, 10$ 号大米，然后免费拿走剩下的大米。

样例三

见“样例数据下载”

限制与约定

对于所有数据，保证 $1 \le w_i \le 10^6$。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载