题目描述

人们认为转经就相当于念经，是忏悔往事、消灾避难、修积功德的最好方式。

阿兔也有一只转经筒，转经筒上有 $n$ 个数字： $a_{1},a_{2}...a_{n}$，接下来，阿兔将持续转经 $k$ 天，并在每次转经时积功德。

积功德的规则如下：

• 每次转经时，阿兔会依次遍历转经筒上的 $n$ 个数字。对于每个数字，阿兔可以选择接受该数字所对应的功德值，并获得其数值，随后该数字的功德值会减少 $1$。
• 阿兔会重复这一过程，直到完成 $r$ 次转经。

请问，阿兔每天能获得的最大功德是多少？由于结果可能非常大，请对 $10^{9}+7$ 取模。

注意，每天转经筒上的数字会重置。

输入格式

第一行包含两个正整数 $n,k \ (1\leq n,k \leq 2*10^{5})$，分别表示转经筒的长度和转经的天数。

第二行包含 $n$ 个正整数 $a_{i} \ (1\leq a_{i} \leq 10^{9})$，表示转经筒上的数字。

第三行包含 $k$ 个正整数 $r \ (0\leq r \leq10^{9})$，表示阿兔每天进行转经的次数。

输出格式

输出 $k$ 行，每行包含一个整数，表示阿兔当天能够获得的最大功德值，结果需要对 $10^{9}+7$ 取模。

4 5
1 2 4 3
0 1 2 3 100000

0
10
16
19
20

解释 #1

对于第三天，阿兔可以获得的功德为 $(1+2+4+3)+(0+1+3+2)=16$ 分。

对于第四天，阿兔可以获得 $(1+2+4+3)+(0+1+3+2)+(0+2+1)=19$​ 分，其中阿兔在第三次转经时选择不接受 $a_{1}$ 的功德。