There are children, numbered , sitting around a circle in a clockwise manner. The th child has a piece of paper with the number written on it. They play the following game:
- In the st round, the child numbered increases his number by the sum of the numbers of his neighbors.
- In the nd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
- In the rd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
- And so on.
The game ends after rounds have been played.
For every , find the numbers that the children end up with if the game starts with child playing the first round. Since the numbers can be large, output them modulo .
Input Format
The first line contains , the number of test cases. cases follow.
The first line of each test case contains two space-separated integers and . The next line contains integers, the th of which is .
Constraints
Output Format
For each test case, print lines, each having integers. The th integer on the th line contains the number that the th child ends up with if the game starts with child playing the first round.
Print a blank line after each test case except the last one.
Since the numbers can be large, output them modulo .
Sample Input 0
2
5 1
10 20 30 40 50
3 4
1 2 1
Sample Output 0
80 20 30 40 50
10 60 30 40 50
10 20 90 40 50
10 20 30 120 50
10 20 30 40 100
23 7 12
11 21 6
7 13 24