Problem H
Top Secret

Ralph was hired as a knight by a rich German earl some years ago. One day, he captured a spy that presumably intended to deliver a message to his earl's arch-enemy. At those ancient times, it was very popular to engrave a message into the inside of a ring in order to hide it. Knowing about this technique, Ralph quickly examined the spy's rings and found the message. But, unfortunately, it was encrypted.

Thus, Ralph tortured the spy until he disclosed how to decode the engraved message: The encrypted message is a single line of $N$ numbers. One has to apply the following decoding procedure for $S$ times: add to each number $L$ times the number to its left and $R$ times the number to its right. Note, that due to the cyclic engraving each number has exactly two neighbours. As numbers can be quite large, one only has to take care of the $X$ lower digits.

Unfortunately, Ralph has never learnt how to add and multiply numbers. Please help him!

Input
The first line indicates the number $T$ of test cases that follow. Test cases are separated by a blank line. Each test case starts with a line holding $N$ , $S$ , $L$ , $R$ , and $X$ separated by single spaces ( $2 < N \le 1000$ , $0 \le S \le 2^{30}$ , $0 < L,R,X < 10$ ). The next line contains $N$ numbers (separated by single spaces). These numbers are the encrypted message from left to right. Each of these numbers is a non-negative integer less than $1000$ .

Output
For each test case, output one line containing the $N$ decrypted numbers, separated by single spaces.

Sample Input

5
3 1 1 1 3
1 1 1

3 0 1 1 3
23 42 0

3 1 1 1 3
23 42 0

4 10 2 1 9
1 2 3 4

5 999999999 3 8 7
8 7 8 7 12

 

Sample Output

3 3 3
23 42 0
65 65 65
2620960 2621920 2620896 2621984
2425139 2372828 6040064 4331745 9713040