阿兔与转经筒
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

人们认为转经就相当于念经，是忏悔往事、消灾避难、修积功德的最好方式。
阿兔也有一只转经筒，转经筒上有 n 个数字： a_{1},a_{2}...a_{n}，接下来，阿兔将持续转经 k 天，并在每次转经时积功德。
积功德的规则如下：
  • 每次转经时，阿兔会依次遍历转经筒上的 n 个数字。对于每个数字，阿兔可以选择接受该数字所对应的功德值，并获得其数值，随后该数字的功德值会减少 1 。
  • 阿兔会重复这一过程，直到完成 r 次转经。
请问，阿兔每天能获得的最大功德是多少？由于结果可能非常大，请对 10^{9}+7109+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 取模。
示例1

输入

复制 
4 5
1 2 4 3
0 1 2 3 100000

输出

复制 
0
10
16
19
20

说明

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