Maggu is a weird guy. Whenever he gets bored, he starts playing weird games. As he is an odd boy, he likes to play only with arrays of even length n. Maggu cannot play with large numbers, so he will do all the operations modulo 10^9 + 7.

He likes performing "weird operations" on the array very much. A Weird Operation#1 on an array seq[] is defined as follows:

tempSeq[n] ; //is a temporary array
for (i = 0; i < n; i++)  {
    int cnt = 0;
    for (cnt = 0; cnt < k; cnt++) {
        int j = (i + cnt) % n;
        if (cnt % 2 == 0) tempSeq[i] += seq[j];
        else tempSeq[i] -= seq[j];
    }
}
for (int i = 0; i < n; i++) seq[i] = tempSeq[i];

Weird operation#2 is even more cooler than this. In this operation, he swaps the adjacent entries of the array.

Pseudo code is as follows:

for (int i = 0; i < n; i += 2) swap (seq[i], seq[i + 1]);

A "Super Weird operation" is applying weird operation #1 followed by weird operation #2 on the array seq[]. He wants to apply this operation m times and desires to know the final contents of the seq.

He is bored of playing this game, So he asks you to find out the final content of the seq.

Input

First line contains number of test cases: T (1 <= T <= 100).

For each test case, first line contains three space separated n, k, m (1 <= n <= 50, 1 <= k <= n, 1 <= m <= 10^9). n is always even.

The next line contains n space separated integers seq[i](starting from 0), -10^9 <= seq[i] <= 10^9.

Output

For each test case, output n space separated integers where ith element represents seq[i] after m "Super Weird Operations".

Example

Input:
1
4 3 1
2 4 -3 5

Output:
12 1000000002 7 1000000001