Background

Special for beginners, ^_^

Description

tabris实在是太菜了,没打败恶龙,在绿岛也只捡到一块生铁回去了,为了不在继续拉低acimo星球的平均水平逃离地球,来到了Sabi星球.

在这里tabris发现了一种神奇的生物,这种生物不需要与外界交流,种群间不同个体能互相维持生命存在及提供生长所需的能量.

每个种群有\(N\)个不同个体,围成一个圈,每隔一个单位时间都会生长.

在一个单位时间里,每个个体会向两边辐射能量,辐射范围与强度均为\(K\),随着距离的增加辐射强度会减小,距离每增加\(1\)辐射强度减小\(1\) ,在这单位时间通过辐射接受的能量会保留,最开始的能量会消耗掉。

对于两个个体a、b,其中a对b的辐射会使b增加[辐射强度\(\times \)a最开始的能量值].

总体的改变可以表示成
\(a[i]' = \sum_{j=1}^{N} a[j]\times (K-dis(i,j)) \times [i!=j]\)
注：\([*]\) * 为真是为1 *为假时为0

现在tabris想知道经过\(M\)单位时间后,每个个体的能量值是多少.

Format

Input

输入一个T,表示测试数据的组数
每个测试数据第一行包含三个正整数N,M,K.
接下来一行包含N个正整数a[i];

\(T\in[1,200]\)
\(N \in [1,200]\)
\(K \in [1,\lfloor \frac{n}{2} \rfloor]\)
\(M \in [1,10^{18}]\)
\(a[i] \in [1,10^6]\)

Output

对每组测试样例输出经过M单位时候后每个个体的能量,为了方便起见对1e9+7取模.

Sample 1

Input

1
5 1 3
1 1 1 1 1

Output

6 6 6 6 6

Limitation

1s, 1024KiB for each test case.

Hint

code

Source

tabris